操作系统期末复习知识点二计算与应用

1.理解银行家算法判断死锁的定理并能计算相关的参数。
2.能利用LRU、FIFO算法求缺页率。
3.纯页式管理中，求逻辑地址对应的物理地址，页号、页内地址长度，画出逻辑地址的格式，在引入块表时，求出有效访问时间。
4.可变分区方式下，FF、BF、WF算法下如何分配作业，画出分配图。
5.资源分配中，利用银行家算法如何判断系统是否为安全状态。
6.能利用P-V原语实现进程的并发执行(同步互斥）。
7.能明确FCFS和静态优先级调度算法下进程的调度顺序和平均等待时间。
8.能利用FCFS、SSTF、SCAN算法求出平均寻道长度。参考课堂例题(笔记）和课后作业。

1. 银行家算法是一种避免死锁的著名算法，由艾兹赫尔·戴克斯特拉在1960年代提出。该算法以银行借贷系统的风 判断为背景，通过判断系统的安全状态来避免进入不安全状态，从而避免死锁的发生。Need=Max-Used Available=Available-Request Used[i]=Used[i]+Request Nedd[i]=Need[i]-Request。

2. 资源分配中，利用银行家算法如何判断系统是否为安全状态。
   在银行家算法中，系统被抽象为多个进程和多个资源。每个进程在运行过程中需要申请一定数量的资源，并在申请成功后使用这些资源。当进程使用完资源后，再释放这些资源。如果在进程运行过程中，所需要的资源得不到满足（即资源数小于其所申请的数量），则该进程会被阻塞，等待资源的释放。
   银行家算法通过判断系统的安全状态来避免死锁的发生。安全状态是指系统中的所有进程都能在有限的时间内完成其运行，并释放其占用的所有资源。在银行家算法中，通过不断地检查系统的安全状态，如果发现系统可能进入不安全状态，则拒绝资源的申请，以避免死锁的发生。
   银行家算法的具体参数包括：
   最大需求矩阵：表示每个进程对资源的最大需求。
   分配矩阵：表示每个进程已经分配到的资源数量。
   可用资源向量：表示当前可用的资源数量。
   需求矩阵：表示每个进程还需要多少资源才能完成其任务。
   安全序列：表示一组进程，按照这组进程的顺序来请求资源，可以使得系统始终处于安全状态。
   通过这些参数，银行家算法可以判断系统是否处于安全状态，以及如何避免死锁的发生。
   在银行家算法中，安全状态是指系统中的所有进程都能在有限的时间内完成其运行，并释放其占用的所有资源。具体来说，如果存在一个由系统中所有进程构成的安全序列，则系统处于安全状态。安全序列是指一个进程序列<P1,P2,…,Pn>，系统按该序列为每个进程分配其所需要的资源，直至最大需求，最终能使每个进程都可顺利完成。安全状态一定是没有死锁发生。如果不存在这样的安全序列，则称系统处于不安全状态。
   安全状态：Pi还需要的资源量≤系统当前剩余的资源量+Pi…+Pi-n已占有的资源量之和。
   定理：某系统有同类互斥资源m个，供n个进程共享使用。如果每一个进程最多申请x个资源（1≤x≤m），当n（x-1）+1≤m时，系统不会发生死锁。
   
   
   
   原则：某进程还需要的资源量need≤当前可利用的资源量available就可以为该进程分配资源，所有进程按照某种顺序资源分配完毕，即为安全状态。
   公式：当前可利用资源量=当前进程已占有的资源量used+之前可利用的资源量。最开始仅有系统剩余的资源量作为当前利用资源。
   
   
   

3. 能利用LRU（最近最久未使用算法least recently used）、FIFO（先进先出）算法求缺页率。
   缺页率计算公式：==缺页率=页面失效次数/总页面访问次数。页面失效次数指的是当内存中不存在请求的页时需要将该页调入内存中的次数，总页面访问次数是指请求访问页面的总次数，无论该页是否在内存中。
   例子：
   考虑一个访问序列：7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2。
   假设物理内存可以容纳3个页面。
   解答：

LRU算法：最近最久未使用算法，发生缺页中断时，选择以后永不使用或者在最长时间内不再被访问的页面进行淘汰。
初始状态：内存为空。

FIFO算法：先进先出置换算法，在发生缺页时，选择最先进入内存的页面进行置换。
初始状态：内存为空。
访问7：加载7到内存。
访问0：加载0到内存（此时内存中有7、0）。
访问1：加载1到内存（此时内存中有7、0、1）。
访问2：因为内存已满，需要替换一个页面。最早进入的页面是7，所以替换7并加载2（此时内存中有0、1、2）。
访问0：0已经在内存中，不需要替换。
访问3：因为内存已满，需要替换一个页面。最早进入的页面是1，所以替换1并加载3（此时内存中有0、2、3）。
访问0：0已经在内存中，不需要替换。
访问4：因为内存已满，需要替换一个页面。最早进入的页面是2，所以替换2并加载4（此时内存中有0、3、4）。
访问2：2不在内存中，需要替换一个页面。最早进入的页面是4，所以替换4并加载2（此时内存中有0、3、2）。
访问3：3已经在内存中，不需要替换。
访问0：0已经在内存中，不需要替换。

3. 纯页式管理中，求逻辑地址对应的物理地址，页号、页内地址长度，画出逻辑地址的格式，在引入块表时，求出有效访问时间。

   物理地址（内存地址）：块号+块内地址。因块的大小与页的大小相同，故块内地址长度=页内地址长度。块号的长度由内存分配的块数决定。
   确定逻辑地址中的页号和页内地址：
   页号=逻辑地址（十进制数）DIV页面大小（字节）
   页内地址=逻辑地址（十进制数）MOD页面大小（字节）
   根据求得页号在页表中找到相应块号
   根据块号和块内地址确定物理地址。物理地址=块号*页面大小（字节）+块内地址
   在一个16位的系统中，某作业在逻辑地址1000号单元处有指令MOV R1，[2500]，2500号单元有数据5678，采用纯分页存储管理，页面大小为1K，该作业进入内存后，其页面0，1，2被分配到内存的6，7，10块中，完成下列要求：
   （1）画出该作业的页表。
   

（2）当执行MOV R1，[2500]时，如何实现将逻辑地址2500号单元处数据5678送入R1寄存器的地址重定位 。
1. 确定页内地址、页号
页号=逻辑地址 DIV 页面大小（整除）
2500 DIV 1024 =2
页内地址=逻辑地址 MOD 页面大小 （取余）
页内地址： 2500 MOD 1024 =452
2.通过页号去页表中查找块号：
在页表中2页对应的块号为10
3.确定物理地址
物理地址=块号×页面大小+页内地址
10×1024+452=10692
将逻辑地址2500号单元处数据5678送入R1寄存器的地址重定位 后的物理地址是10692
（3）在逻辑地址中页内地址和页号各占多少位？画出其格式。
因页面大小 1KB=2^10B，故页内地址为10位，页号为16-10=6位。

（4）如果系统访问内存需要0.2秒，有效访问时间是多少？
访问内存的有效访问时间包括两次访问内存的时间，第一次访问页表，第二次存取页面数据，且两次时间相等。 0.2×2=0.4秒
逻辑地址（虚拟地址）：页号+页内地址，每个逻辑地址有一定长度。
如何确定页号位数和业内地址位数：
若机器地址长n位，页面大小为：mKB, 1kb=2^10b
由于mKB=2^b B，则页内地址长度=b位,页号位数为n-b=t位
如果逻辑空间有2^t页，则t为页号位数
若机器地址长32位，页面大小为：4KB,则页内地址和页号各占多少位？
n=32,4kb=2^12b t=32-12=20位
页内地址：12位 页号：20位
某作业有16页的逻辑空间，页面大小为2KB，则 页号和页内地址各占多少位？
页号：2^t=16, t=4，页内地址：2kb=2^11b，b=11位。
在分区存储管理中，不论采用什么办法都会出现碎片问题，从而降低了内存的利用率。虽然采用移动存储区可以解决碎片问题，但系统开销太大，而无实用价值。所以产生了分页技术。基本思想：将整个系统的内存空间划分成若干个块，每一块的大小相等，每个块称为一个物理块、物理页或实页，可简称为块，所有的块按物理地址递增顺序连续编号为0、1、2、…。每个作业的地址空间划分成若干个页面，每一个页面的大小相等。所有的页按照逻辑地址递增顺序编号为0、1、2…。作业中的每一个页与内存中的每一个块的大小相等。在作业运行时，一次性把作业的全部页面装入内存，作业中的每一页放入到内存的其中一个块中，作业所有的页所占的块可以不连续。操作系统为作业建立一个页号与块号的对照表（页表，位于内存。），反映出作业中的哪一页对应到内存的哪一个块中。只要该作业的总页数不大于内存中的可用块数，系统就可以对它实施分配。
页表包含以下几个表项：页号（登记程序地址空间的页号），块号（登记相应的页所对应的内存块号），其他（登记与存储信息保护有关的信息。）
纯页式管理是一种内存管理方式，它将程序划分为固定大小的页，并使用一个页表来映射逻辑地址到物理地址。

4. 可变分区方式下，FF（最先适应法First Fit：从用户的地地址开始查找，找到能满足程序需求的第一个空闲区用于分配。把空闲分区按其所在存储空间按地址递增的顺序连接在一起。。小程序集中运行在低地址部分的存储空间上，大程序装入较高地址部分的存储空间上。 ）、BF（先找最小最佳适应法Best Fit：分区大小由小到大进行排列，当有作业申请内存时，总是首先找到满足要求最接近作业大小的空闲分区。查找一个能满足程序需求的、长度最小的空闲区用于分配。尽量把较大的空闲区保留下来，以便满足后续大程序的需求，但它将小的空闲区分割成两个分区，使得分配后剩余的空闲区更小，这些小的空闲区不利于将来的程序装入操作，容易造成外碎片。）、WF（先找最大最坏适应法Worst Fit：空闲区按大小递减排列。查找一个能满足程序需求的、长度最大的空闲区用于分配。查找大的空闲区用于分配，使得分配后剩余的空闲区尽可能大，有利于其他程序的装入。）（每分配一个作业，都需要按空闲区顺序从头开始查找适用于分配的空闲区。）算法下如何分配作业，画出分配图。
   例题：用可变分区方式管理主存时，假定主存中按地址顺序依次有四个空闲区，空闲区大小依次是：16K，14K，5K，30K，现有三个作业A、B、C，它们各需主存依次为15K，16K，15K。
   1.分别利用FF算法、BF算法、WF算法分别将该三个作业依次装入主存，哪些算法是合适的？
   

   2.若采用BF算法，怎样的次序装入这三个作业，可使主存利用率最高
   

5. 能利用P-V原语实现进程的并发执行(同步互斥）。
   原语：是由若干指令构成的，用于完成特定功能的一个过程，该过程在操作时是不可分割的。原语的主要作用是保证系统费运行的一致性。
   原子操作：一个操作中的所有动作，与一般过程的区别，要么全做，要么全不做。
   当S≥0时，表示某类可用资源的数目，或者说表示可以申请资源而不会被阻塞的进程的数目；
   当S＜0时，其绝对值表示信号量S的阻塞队列Q中的进程数，即想要获得资源但当前暂时不能获得资源而阻塞的进程数，这些进程需要别的进程发出相应的信号灯来唤醒。
   S的值只能由P、V操作来改变。
   P操作：P代表荷兰语的Passeren/proberen，同步过程中表示等信号，在互斥关系中表示请求一个资源。
   V操作：V代表荷兰语的Vrijgeren/verhogen，同步关系中表示发信号，在互斥关系中表示释放一个资源。
   ==定义在信号量S上的P（S）原语操作的算法描述为：
   （1）S-1；
   （2）若S-1≥0，表示为进程分配资源；
   （3）若S-1<0，表示无资源可分配， 此时S每减一次1表示有一个进程在等待获得资源而把自己插入到阻塞队列Q中。
   ==
   定义在信号量S上的V（S）原语操作的算法描述为：
   （1）S+1；
   （2）若S+1≤0 ，表示把阻塞队列Q中的进程逐次唤醒，等待获得资源。
   （3）若S+1>0 ，表示某进程释放一个资源
   如何解答进程同步问题
   解答进程同步问题的主要三大步：（方法1）
   (1)分析清楚题目涉及的进程间的制约关系
   (2)设置信号量（包括信号量的个数和初值及其物理含义），合作进程间需要收发几条消息相应就设置几个信号量。
   (3)给出进程相应程序的算法描述或流程控制，并把P、V操作加到程序的适当处。
   解答进程同步问题的主要三大步：（方法2）
   (1)分析题目中进程间的制约关系
   (2)设置信号量：
   A.有几个进程设置几个同步（资源）信号量.
   B.有几个临界区设置几个互斥信号量。
   C.给出信号量的含义及初值。
   (3)给出进程P、V操作的算法描述：
   A.有几个进程就有几个算法描述.
   B.针对每个进程的算法描述利用PV原语实现对应的同步和互斥操作。
   用信号量机制解这类题的三个步骤：
   （1）分析进程间的制约关系
   （2）设置信号量
   （3）实施P、V操作。
   第一步是基础、关键，第三步是核心。
   掌握实现进程互斥与进程同步的第三步在形式上差异：即P、V操作总是配对出现的。
   但P,V在互斥问题中总是出现在同一个进程的代码中，且紧紧夹着临界区；而在同步问题中，却是分别出现在两个合作进程的代码中，需要等消息的一方用P操作，相应的对同一信号量的V操作则在发出此消息的另一方中。
   例：
   某小型超级市场，可容纳50人同时购物。入口处有篮子，每个购物者可拿一只篮子入内购物。出口处结帐，并归还篮子（出、入口禁止多人同时通过）。试用信号量和P、V操作写出购物者的同步算法。
   这是个典型的进程互斥问题
   ①所用信号量设置如下：
   Ⅰ）资源信号量S，初值为50，用以保证最多可以有50个购物者进入超市。
   Ⅱ）互斥信号量mutex1，mutex2初值为1，（用于描述临界区的占有、释放情况）用以保证同时只能有一个购物者进程进入入口或者结帐后通过出口。
   ②用信号量机制给出的每个购物者购物过程的算法描述如下：
   练习题：
   1.有两个用户进程A和B，在运行过程中都要使用系统中的一台打印机输出计算结果。
   试说明A、B两进程之间存在什么样的制约关系？
   为保证这两个进程能正确地打印出各自的结果，请用信号量和P、V操作写出各自的有关申请、使用打印机的代码。要求给出信号量的含义和初值。
   解：(1) A、B两进程之间存在互斥的制约关系。因为打印机属于临界资源，必须一个进程使用完之后另一个进程才能使用。
   （2）mutex：用于互斥的信号量，初值为1。
   进程A 进程B
   … …
   … …
   P(mutex) P(mutex)
   申请打印机 申请打印机
   使用打印机 使用打印机
   V(mutex) V(mutex)
   … …
   2.有一个阅览室，共有100个座位，读者进入时必须先在一张登记表上登记，该表为每一座位列一表目，包括座号和读者姓名等，读者离开时要消掉登记的信息，试问：（1） 为描述读者的动作，应编写几个程序，设置几个进程？（2） 试用PV操作描述读者进程之间的同步关系。
   读者的动作有两个，一是填表进入阅览室，这时要考虑阅览室里是否有座位；一是读者阅读完毕，离开阅览室，这时的操作要考虑阅览室里是否有读者。读者在阅览室读书时，由于没有引起资源的变动，不算动作变化。
   算法的信号量有三个：
   seats——表示阅览室是否有座位（初值为100，代表阅览室的空座位数）；
   readers——表示阅览室里的读者数，初值为0；
   用于互斥的mutex，初值为1。
   读者进入阅览室的动作描述getin：
   
   读者离开阅览室的动作描述getout：
   

1.如果信号量S的初值是1，当前值为-4，则表示有多少个进程等待？
信号量S的当前值为-4，这表示当前有4个进程在等待。因为当一个进程试图获取一个资源但信号量为0时，该进程会被阻塞并放到等待队列中，此时信号量减1。所以，当前值为-4表示有4个进程在等待。
2.在操作系统中，对信号量S的P源语操作定义中，使进程进入相应等待队列等待的条件是：C
A.S>0 B.S<0 C.S=0 D.S≠0
如果S大于0，表示资源可用，进程可以继续执行并消耗一个单位的资源，此时S减1。如果S等于0，表示资源不可用，进程需要等待，会被放入等待队列中，直到资源变得可用。因此，使进程进入相应等待队列等待的条件是
S=0

7. 能明确FCFS（先来先服务算法，按照进入就绪队列的先后顺序，调度时选择最先进入就绪队列的进程。）和静态优先级调度算法（对每个进程给一个优先数，调度时选择优先级最高的进程。）下进程的调度顺序和平均等待时间。
   例题：
   有5个进程P1-P5，同时依次进入就绪队列，他们的优先数和需要的处理机时间：
   

（1）
采用FCFS：P1–>P2–>P3–>P4–P5
采用静态优先级：P4–>P1–>P3–>P5–>P2
（2）某个进程等待时间=前一个处理时间+前一个等待时间

8. 能利用FCFS（先来先服务算法，按照时间先后顺序，调度时选择最先提出的操作请求。容易实现具有公平性，平均寻道时间长）、SSTF（最短寻道时间优先，按照各请求所在的柱面，调度时选择距离当前磁头最近柱面的操作请求。）、SCAN算法（扫描算法，可以减少磁头改变方向。磁头从着陆区启动后，从内向外方向扫描移动，在到达最外层柱面后，改变方向从外向内扫描移动，在移动过程中总是选择当前磁头方向上距离最近柱面的操作。）求出平均寻道长度。参考课堂例题(笔记）和课后作业。
   求寻道总长度及平均寻道长度的规则：
   1.寻道总长度等于所有访问的相邻磁道两两相减，再将减得的所有结果相加。
   2.平均寻道长度=寻道总长度/相邻磁道数两两相减得出的数据个数
   例题：
   FCFS：
   如果现在读写磁头正在53号柱面上执行输入输出操作，而等待访问者依次要访问的柱面为98，183，37，122，14，124，65，67。那么，当53号柱面上的操作结束后，移动臂将按请求的先后次序先移到98号柱面，最后到达67号柱面，如下图所示。
   
   其相应的寻道总长度为：
   （98-53）+（183-98）+（183-37）+（122-37）+（122-14）+（124-14）+（124-65）+（67-65）=45 + 85+146+85+108+110+59+2 = 496+144=640
   平均寻道长度=640/8=80
   SSTF：
   如果现在读写磁头正在53号柱面上执行输入输出操作，而等待访问者依次要访问的柱面为98，183，37，122，14，124，65，67。
   现按最短路径优先的服务算法规则对需要访问的磁道进行排序：65，67，37，14，98，122，124，183
   
   其相应的寻道总长度为：（65-53）+（67-65）+（67-37）+（37-14）+（98-14）+（122-98）+（124-122）+（183-124）=185
   平均寻道长度：185/8=23.125
   SCAN（扫描算法/电梯调度算法）：总是从移动臂当前位置开始沿着臂的移动方向去选择离当前移动臂最近的那个柱面的访问者，如果沿臂的移动方向无请求访问时，就改变臂的移动方向再选择
   该算法既考虑磁臂移动的方向又考虑访问磁道与磁头当前的距离,能避免进程饥饿。（进程要访问的下一个磁道一定是沿着移动臂移动的方向并距当前正访问磁道最近的磁道）
   例题：
   如果现在读写磁头正在53号柱面上执行输入输出操作，而等待访问者依次要访问的柱面为98，183，37，
   122，14，124，65，67。
   磁头向外移动访问的柱面为：37，14，65，67，98，122，124，183，磁头向内移动访问的柱面为：65，67，98，122，124，183，37，14
   
   （a）总长度：（53-37）+（37-14）+（65-14）+（67-65）+（98-67）+（122-98）+（124-122）+（183-124）= 208
   平均长度：208/8=26
   （b）总长度：（65-53）+（67-65）+（98-67）+（122-98）+（124-122）+（183-124）+（183-37）+（37-14）=299
   平均长度：299/8=37.375