操作系统复习(重点内容复习).doc

二、进程同步问题1、一个快餐厅有4类职员：(1)领班：接受顾客点菜；（2）厨师：准备顾客的饭菜；（3）打包工：将饭菜打包；（4）出纳员：收款并提交食物。每位职员可被看做一个进程，试用一种同步机制写出能让4类职员正确并发工作的程序。解：可设4个信号量S1,S2,S3,S4来协调进程工作。Semaphore S2,S3,S4,W1,W2,W3,W4;S2=S3=S4=0; W1=W2=W3=W4=1;/S为同步信号量，表示4类职员的工作顺序，W为互斥信号量，表示每一类员工一次只能为一个客户服务cobegin process P1()while(true)有顾客到来；P（W1）；/W1=W1-1, if W10 block;接受顾客点菜；V（W1）;/W1=W1+1V（S2）；/S2=S2+1;process P2()while(true) P（S2）；/S2=S2-1, if S20 block;P（W2）; /W2=W2-1, if W20 block;准备顾客的饭菜；V（W2）;/W2=W2+1V（S3）；/S3=S3+1process P3()while(true)P（S3）；P（W3）; /W3=W3-1, if W30 block;将饭菜打包；V（W3）;/W3=W3+1V（S4）；/S4=S4+1process P4()while(true)P（S4）；P（W4）; /W4=W4-1, if W40 block;收款并提交食品；V（W4）;/W4=W4+1coend2、假定一个阅览室最多可容纳100人，读者进入和离开阅览室时都必须在阅览室门口的一个登记表上进行登记，而且每次只允许一人进行登记操作，请用记录型信号量机制实现上述问题的同步。定义信号量sum,mutex，初值分别为100，1。则第i个读者的活动描述为：PiSemaphore sum,mutex;Sum=100;mutex=0;cobegeinprocedure Pi()(i=1,2,3) wait(sum);/sum=sum-1, if sum0 blockwait(mutex);/mutex=mutex-1, if mutex0 block登记；signal(mutex);/mutex=mutex+1进入阅览室； 阅读; wait(mutex);/mutex=mutex-1, if mutex0 block登记；signal(mutex); /mutex=mutex+1离开阅览室；signal(sum); /sum=sum+1 coend3、图给出了四个进程合作完成某一任务的前趋图，试说明这四个进程间的同步关系，并用P、V操作描述它。S1S3S2S4Semaphore p1,p2,p3,p4;p1=p2=p3=p4=0;cobegeinprocess s1() Signal(p1);Signal(p2) process s2() wait(p1)Signal(p3); process s3() wait(p2)Signal(p4); process s4() wait(p3); wait(P4); coend4、请用信号量解决以下的“过独木桥”问题：同一方向的行人可连续过桥，当某一方向有人过桥时，另一方向的行人必须等待；当某一方向无人过桥时，另一方向的行人可以过桥。将独木桥的两个方向分别标记为A和B；并用整形变量countA和countB分别表示A、B方向上已在独木桥上的行人数，初值为0；再设置三个初值都1的互斥信号量：SA用来实现对countA的互斥访问，SB用来实现对countB的互斥访问，mutex用来实现两个方向的行人对独木桥的互斥使用。则具体描述如下：Semaphore SA,SB,mutex,countA,countB;SA=SB=mutex=1,1,1;countA=countB=0,0; cobegin process A() wait(SA);/互斥操作countS变量if(countA=0) then wait(mutex);/A方向第一个上桥的人执行mutex=mutex-1, if mutex0 block, 否则可以上桥countA:=countA+1;signal(SA);/释放SA变量过独木桥；wait(SA); /互斥操作countS变量 countA:=countA-1; if (countA=0) then signal(mutex);/A方向第最后一个下桥的人执行mutex=mutex+1 if mutex=0 wakeup, 唤醒B进程signa(SA); process B（）/过程同Await(SB);if(countB=0) then wait(mutex);countB:=countB+1;signal(SB);过独木桥；wait(SB); countB:=countB-1; if (countB=0) then signal(mutex);signa(SB); coend5、设公共汽车上，司机和售票员的活动分别是：司机的活动：启动车辆；正常行车；到站停车；售票员的活动：关车门；售票；开车门；请用记录型信号量机制实现上述问题的同步。Semaphore s1,s2;s1=s2=0,0; /*s1表示是否允许司机启动汽车，s2表示是否允许售票员开门*/ cobegin process driver()repeatwait(s1);/s1=s1-1, if s10 block，售票员关门后司机才能开车启动车辆；正常行车；到站停车；signal(s2); /s2=s2+1，ifs2=0 wakeup busman司机停车后，售票员才可以开门 until false; process busman repeat关车门；signal(s1); /s1=s1+1，ifs1=0 wakeup driver售票员关门后，司机才可以开车售票；wait(s2); /s2=s2-1, if s2=0，则进程继续运行。若S0，则进程继续运行。若S=0，则从信号量的等待队列中移出队首进程。使其变为就绪状态。（2）描述如下：semaphore empty1,empty2,full1,full2,mutex1,mutex2；empty1=empty2=1；full1=full2=0,0;mutex1;mutex2=1; /empty1,empty2,full1,full2分别表示缓冲区1、2空和满的同步信号量，mutex1,mutex2分别表示互斥使用缓冲区1、2的互斥信号量 cobegin process PA() repeat 从磁盘读一个记录； P(empty1);/empty1=empty1-1, if empty10 block，缓冲区1不为空则阻塞 P（mutex1）；/mutex1=mutex1-1, if mutex0 block，缓冲区1正在被操作则阻塞 将记录存入缓冲区1； V（mutex1）;/mutex1=mutex1+1, if mutex1=0 wakeup, 如果有等待操作缓冲区1的进程将被唤醒 V(full1);/full1=full1+1, if full1=0 wakeup, 缓冲区1放入一个数据，如果PB进程等待取数据则被唤醒 until false; process PB repeat P(full1); P(mutex1); 从缓冲区1取出纪录； V(mutex1) V(empty1); P(empty2); P(mutex2); 将记录存入缓冲区2； V(mutex2); V(full2); until false; process PC repeat P(full2); P(mutex2); 从缓冲区2取出纪录； V(mutex2); V(empty2); 打印记录； until false; coend 三、银行家算法1、系统有A,B,C,D共4种资源，在某时刻进程P0,P1,P2,P3,P4对资源的占有和需求情况如下表所示。进程AllocationMaxAvailableA B C DA B C DA B C DP00 0 3 20 0 4 41 6 2 2P11 0 0 0 2 7 5 0P21 3 5 43 6 10 10P30 3 3 20 9 8 4P40 0 1 40 6 6 10(1) 系统此时处于安全状态吗？(2) 若此时进程P1发出request1(1,2,2,2)，系统能分配资源给它吗？为什么？解：（1）利用安全性算法分析可知，此时存在一个安全序列P0,P3,P4,P1,P2，故系统是安全的。进程WorkNeedAllocationMaxFinishNeedneed1(1,7,5,0)，其请求的资源数已超过其还需资源数，所以不能分配。2、系统中有五个进程P1、P2、P3、P4、P5，有三种类型的资源：R1、R2、和R3。在T0时刻系统状态如表所示。若采用银行家算法实施死锁避免策略，回答下列问题：1 T0时刻是否为安全状态？为什么？2 若这时P4请求资源（1，2，0），是否能实施资源分配？为什么？3 在上面的基础上，若进程P3请求资源（0，1，0），是否能实施资源分配？为什么？ T0时刻系统状态已分配资源数量最大资源需求量R1R2R3R1R2R3P1001001P2200275P3003665P4115435P5033065 R1R2R3剩余资源数330（1）进程WorkNeedAllocationMaxFinishR1 R2 R3Need=申请数(1 2 0)的，然后进行预分配后进行安全性判断。根据银行家算法，预分配后系统是安全的，安全序列为：P1，P4，P5，P2，P3（3）P3请求资源（1，1，0）20），段也已经在内存(存在位为1)，但存取控制字段不符（待段为只读R，无法将寄存器R1的内容存入地址1,20中），故产生保护性中断信号。 (3)逻辑地址合法，存取方式合法，形成物理地址8050后（始址+段内偏移=8000+50），执行指定操作。 (4)逻辑地址中段内地址超长（10080），产生越界中断信号。(5)逻辑地址及访问方式合法，形成物理地址3150(3000+150)，指令执行后，将条转到内存单元3150处继续执行。3、一个进程的大小占5个页面，每页的大小为1K，系统为它分配了3个物理块。当前进程的页表如图所示：块号存在位P访问位R修改位M0x1C1100x3F111-0000x5D100-000（1）有那些页面不在内存？（2）请分别计算进程中虚地址为0x3B7、0x12A5、0x1432单元的物理地址（用十六进制表示），并说明理由。解：（1）不在内存的是第2和4页（按页号，即从0排序），或第3和5页（按序号，即从1排序）。 （2）每页1K，故页内偏移地址10位，5个页面，故页号3位，块号中最大的为0x5D=1001111故最少7位0x3B7的逻辑地址000|1011110111，在第0页物理地址为=0001111|1011110111=0x3ef70x12A5的虚地址=100|0111110101，在第4页物理地址为=1001111|0111110101=0x13df50x1432的虚地址为=101|0000110010，该页不在内存中，产生缺页中断。注意：若页号页表长度（从0开始计）会发出越界中断4、设有一页式存储管理系统，向用户提供的逻辑地址空间最大为16页，每页2048B，内存总共有8个存储块，试问逻辑地址至少应为多少位？内存空间有多大？解：逻辑地址最多16页，故页号4位每页2048B，故页内偏移地址11位逻辑地址空间为2（4+11）位，故大小为32K内存8个块，故块号占3位，块内偏移和页内偏移一样占11位内存地址空间为2（3+11）位，故大小为16K5、在一个段式存储管理系统中，其段表为： 段号 内存起始地址 段长 0 210 500 1 2350 20 2 100 90 3 1350 590 4 1938 95试求下述逻辑地址对应的物理地址是什么？段号 段内位移0 4301 102 5003 4004 1125 32解：试求下述逻辑地址对应的物理地址是什么？段号 段内位移0 430210+430=1 10 2350+10=2 50050090 越界中断3 4001350+4004 11211295 越界中断5 32无该段 越界中断或段置换（虚拟分段存储机制中）五、页面置换1、在一个请求分页虚拟存储管理系统中，一个程序运行的页面走向是：1，2，3，1，4，5，1，2，1，4，5，3，4，5，对于分配给程序4个页框的情况，分别用FIFO，OPT和LRU算法，求出缺页中断次数，并给出缺页时加进主存的页号。解： （1）FIFO缺页10次，缺页时加进主存的页号见表中带星的页号。（先进先出置换）页框123145121453450 1*11115*5555554*412*22221*1111115*23*33332*22222234*4444443*33（2）OPT缺页6次，缺页时加进主存的页号见表中带星的页号。（最佳置换：置换以后永久不使用的或在最长时间内不再被访问的页）页框123145121453450 1*11111111113*3312*22222222222223*335*5555555534*444444444（3）LRU缺页7次，缺页时加进主存的页号见表中带星的页号。（最近最久未使用置换：选择最近最久未使用的页面进行置换）页框123145121453450 1*111111111111112*2225*5555555523*33332*2223*3334*4444444442、现有一请求分页的虚拟存储器 , 内存最多容纳 4 个页面 , 对于下面的引用串： 1,2,3,4,5,3,4,1,6,7,8,7,8,9,7,8,9,5,4,5,4,2 分别采用 FIFO, LRU, OPT页面替换算法 , 各将产生多少次缺页中断 ? FIFO:12345341678789789545421111555555888888888882222222111111999999999333333666666666555554444447777777774444LRU12345341678789789545421111222534111666678889222345341666789789995334534167878978954544534167878978954542OPT12345341678789789545421111111166888888888882222555555555555555555333333377777777744444444444444999999999FIFO共13次缺页中断，LRU也要13次缺页中断，OPT要11次缺页中断。六、磁盘调度1、若干个等待访问磁盘者依次要访问的磁道为20，44，40，4，80，12，76，假设每移动一个磁道需要3毫秒时间，移动臂当前位于40号柱面，请按下列算法分别写出访问序列并计算为完成上述各次访问总共花费的寻道时间。 （1）先来先服务算法FCFS； （2）最短寻道时间优先算法SSTF。（3）扫描算法SCAN（当前磁头移动的方向为磁道递增）（4）循环扫描算法CSCAN（当前磁头移动的方向为磁道递增）解：（1）FCFS磁道访问顺序为：20，44，40，4，80，12，76寻道时间=（20+24+4+36+76+68+64）*3=292*3=876 ms（2）SSTF磁道访问顺序为：40，44，20，12，4，76，80寻道时间=（0+4+24+8+8+72+4）*3=120*3=360 ms（3）SCAN磁道访问顺序为：40，44，76，80，（此时磁头直接向反方向移动，不用递增移到最高磁道）20，12，4寻道时间=（0+4+32+4+60+8+8）*3=116*3=348 ms（4）CSCAN磁道访问顺序为：