南华大学操作系统期末复习13级

1、司机和售票员之间的同步关系司机和售票员之间的同步关系 司机只有在售票员关车门后，才能启动汽车。 售票员只有在司机到站停车后，才能开车门。解： Semaphore close=0，stop=0； driver( ) /*司机*/while(True) P(close);启动车辆;正常行车;到站停车;V(stop); Conductor( )/*售票员*/while(True)关车门;V(close);售票;P(stop);开车门;上下乘客;Main( ) parbegin(driver,conductor);()在每个程序中用于实现互斥的wait(mutex)和signal(mutex)必须成对

2、地出现。()对资源信号量empty和full的wait和signal操作，同样需要成对地出现，但它们分别处于不同的进程中，这样保证生产者进程和消费者进程的同步及交替执行。()在每个进程中，多个wait操作顺序不能颠倒，而signal操作的次序是无关紧要的 。例例一台计算机有10台磁带机被n个进程竞争，每个进程最多需要3台磁带机，那么n最多为_时，系统没有死锁的危险？解：n最大为4。用整型信号量描述在哲学家进餐问题中，至多允许用整型信号量描述在哲学家进餐问题中，至多允许4个哲学个哲学家同时进餐的算法。家同时进餐的算法。解：解：public class diningphilosophers sem

3、aphore fork 5 = (1,1,1,1,1); semaphore room = 4; int i; void philosopher (int i) /第i个哲学家进餐进程 while (true) think(); wait (room); wait (forki); wait (fork (i+1) % 5); eat(); signal (fork (i+1) % 5); signal (forki); signal (room); 例例在银行家算法中，若出现下述的资源分配情况：ProcessMax AllocationAvailableP00 0 4 40 0 3 21 6

4、 2 2P12 7 5 01 0 0 0P23 6 10 101 3 5 4P30 9 8 40 3 3 2P40 6 6 100 0 1 4试问：1）该状态是否安全？ 2）若进程P2提出请求Request（1，2，2，2）后，系统能否将资源分配给它？3）如果系统立即满足P2的上述请求，系统是否立即进入死锁状态？解：1）利用安全性算法对上面的状态进行分析（如下表所示），找到了一个安全序列P0，P3，P4，P1，P2或P0，P3，P1，P4， P2，故系统是安全的。 资源情况资源情况进程进程WorkNeedAllocationWork+AllocationFinishA B C DA B C D

5、 A B C D A B C DP01 6 2 20 0 1 20 0 3 2 1 6 5 4TrueP31 6 5 40 6 5 20 3 3 2 1 9 8 6TrueP41 9 8 60 6 5 60 0 1 4 1 9 9 10TrueP11 9 9 101 7 5 01 0 0 02 9 9 10TrueP22 9 9 102 3 5 61 3 5 4 3 12 14 14True2) P22) P2发出请求向量发出请求向量RequestRequest（1 1，2 2，2 2，2 2）后，系统按照银行）后，系统按照银行家算法进行检查：家算法进行检查：Request2Request2（

6、1 1，2 2，2 2，2 2）Need2Need2（2 2，3 3，5 5，6 6）；）；Request2Request2（1 1，2 2，2 2，2 2）AvailableAvailable（1 1，6 6，2 2，2 2）；）；系统先假定可为系统先假定可为P2P2分配资源，并修改分配资源，并修改AvailableAvailable，Allocation2Allocation2和和Need2Need2向量：向量：Availabe=Availabe=（0 0，4 4，0 0，0 0）Allocation2=Allocation2=（2 2，5 5，7 7，6 6）Need2=(1,1,3,4

7、) Need2=(1,1,3,4) 进行安全性检查：此时对所有进程，条件进行安全性检查：此时对所有进程，条件NeediNeedi Available Available（0 0，4 4，0 0，0 0）都不成立，即）都不成立，即AvailableAvailable不能满足任何进程的不能满足任何进程的请求，故系统进入不安全状态。因此，当进程请求，故系统进入不安全状态。因此，当进程P2P2提出请求提出请求RequestRequest（1 1，2 2，2 2，2 2）后，系统不能将资源分配给它。）后，系统不能将资源分配给它。3）系统立即满足进程系统立即满足进程P2P2的请求（的请求（1 1，2 2，

8、2 2，2 2）后，并没有马上）后，并没有马上进入死锁状态。因为，此时上述进程并没有申请新的资源，进入死锁状态。因为，此时上述进程并没有申请新的资源，并未因得不到资源而进入阻塞状态。只有当上述进程提出新并未因得不到资源而进入阻塞状态。只有当上述进程提出新的请求，并导致所有没执行完的多个进程因得不到资源而阻的请求，并导致所有没执行完的多个进程因得不到资源而阻塞时，系统才进入死锁状态。塞时，系统才进入死锁状态。先进先出（先进先出（FIFOFIFO）页面置换算法）页面置换算法引用率70770170122010323104430230321013201770201页框23042042302301271

9、2701最近最久未使用最近最久未使用(LRU)(LRU)置换算法置换算法引用率70770170122010320304403230321132201770101页框402432032102地址结构分页地址中的地址结构如下：它含有两部分：前一部分为页号P，后一部分为位移量W(或称为页内地址)。图中的地址长度为32位，其中011位为页内地址，即每页的大小为4 KB；1231位为页号，地址空间最多允许有1 M页。 例：在分页存储管理中，假设程序地址字为32位，页长为4KB，则页号占用_位，空间最多有_页。某分页存储器每页大小为1KB，某进程的页表如下所示：页号块号05110 24 37 问：逻辑地址

10、0A5C（H）对应的物理地址是什么？0A5C(H)=0000 1010 1001 1100(B) 后10位为页内地址，前6位为页号，因此页号为2，对应的块号为4，即000100，加上页内地址，得到物理地址为0001 0010 1001 1100(B)=125C(H)一个磁盘系统，平均寻道时间为一个磁盘系统，平均寻道时间为12ms，转速为，转速为10000转转/分，每个磁道有分，每个磁道有18个扇区，每个扇区个扇区，每个扇区512个字节。个字节。请问要读取一个扇区所花的时间是多少？请问要读取一个扇区所花的时间是多少？ 解：解： TS = 12msTR = 1/2r = 60000100000.5

11、 = 3ms TA=b/rN = (51260000)(1851210000)= 0.33ms TT = TS + TR + TA =12 + 3 + 0.33 = 15.33ms答：读取一个扇区所花的时间是答：读取一个扇区所花的时间是15.33ms。 例例5.6.2 5.6.2 磁盘调度磁盘调度 目标：减少寻道时间目标：减少寻道时间1 1、FCFSFCFS（Fisrt Come First ServedFisrt Come First Served）先来先服务）先来先服务 特点：公平、简单，寻道时间长，相当于随机特点：公平、简单，寻道时间长，相当于随机访问模式。访问模式。 仅适用于请求磁盘仅

12、适用于请求磁盘I/OI/O的进程数目较少的场合。的进程数目较少的场合。2 2、SSTFSSTF（最短寻道优先）最短寻道时间优先（最短寻道优先）最短寻道时间优先 SSTFSSTF比比FCFSFCFS有更好的寻道性能有更好的寻道性能 贪心的算法贪心的算法 饥饿现象饥饿现象 不能保证平均寻道时间最短不能保证平均寻道时间最短 ？例如，当前磁头在第例如，当前磁头在第1111磁道，申请访问磁道序列：磁道，申请访问磁道序列：1 1，9, 129, 12，1616，3232图 5-25 FCFS调度算法图 5-26 SSTF调度算法 3 3、SCAN SCAN 扫描算法（也称为电梯算法）。扫描算法（也称为电梯

13、算法）。 进程进程“饥饿现象饥饿现象”SSTFSSTF存在。存在。 SCANSCAN算法：算法： 在移动方向固定的情况下采用了在移动方向固定的情况下采用了SSTFSSTF，以避免饥饿，以避免饥饿现象现象 存在请求进程等待延迟现象存在请求进程等待延迟现象4 4、循环扫描、循环扫描CSCANCSCAN 磁头单向移动磁头单向移动 一个方向读完，不是象一个方向读完，不是象SCANSCAN那样回头，而是循环扫描。那样回头，而是循环扫描。 请求延迟时间：请求延迟时间：2T2TT+SmaxT+Smax图图 5-27 SCAN调度算法示例调度算法示例 图图 5-28 CSCAN调度算法示例调度算法示例若干个等

14、待访问磁盘者依次要访问的磁道为若干个等待访问磁盘者依次要访问的磁道为20，44，40，4，80，12，76，假设每移动一个磁道需，假设每移动一个磁道需要要3毫秒时间，移动臂当前位于毫秒时间，移动臂当前位于40号柱面，请按下列号柱面，请按下列算法分别写出访问序列并计算为完成上述各次访问总算法分别写出访问序列并计算为完成上述各次访问总共花费的寻道时间。共花费的寻道时间。 （1）先来先服务算法；）先来先服务算法； （2）最短寻道时间优先算法。）最短寻道时间优先算法。（3）扫描算法（当前磁头移动的方向为磁道递增）扫描算法（当前磁头移动的方向为磁道递增）解：解：（1）磁道访问顺序为：）磁道访问顺序为：2

15、0，44，40，4，80，12，76寻道时间寻道时间=（20+24+4+36+76+68+64）*3=292*3=876（2）磁道访问顺序为：）磁道访问顺序为：40，44，20，12，4，76，80寻道时间寻道时间=（0+4+24+8+8+72+4）*3=120*3=360（3）磁道访问顺序为：）磁道访问顺序为：40，44，76，80，20，12，4寻道时间寻道时间=（0+4+32+4+60+8+8）*3=116*3=348一个进程的大小为5个页面，为它分配了四个物理块。当前每个块的情况如下表所示（都为十进制数，且从0开始计数。）。当虚页4发生缺页时，使用下列的页面置换算法，哪一个物理块将被换出？并解释原因页号块号加载时间访问时间访问位R修改位M2 060161001 1130160010 226162103 32016311 FIFO算法（先进先出置换算法）LRU算法（最近最久未使用置换算法）CLOCK算法（最近未用置换算法，又称NRU算法）当页面的访问串为：“4，0，0，0，2，4，2，1，0，3，2”的OPT算法（最佳置换算法）解：1换出第3号虚页，因为它加载的时间最早；2换出第1号虚页，因为它最近最久没被访问；3换出第2号虚页，因为它最近既没被访问，又没被修改；4换出第3号虚页，因为它离访问点最远