操作系统第三版习题答案

操作系统教程第三版作者孙钟秀部分课后习题答案第一章操作系统概论二、应用题1、有一台计算机，具有1MB内存，操作系统占用200KB，每个用户占用200KB。如果用户进程等待I/O的时间为80，若增加1MB内存，则CPU的利用率提高多少解每个进程等待的百分比率为P，则N个进程同时等待的概率为PN，当N个进程同时等待I/O期间CPU是空闲的，故CPU的利用率是1PN除去操作系统占用的内存，剩余内存能容纳4个用户进程，由于每个用户进程等待I/O的时间为80，故CPU的利用率为180459若再增加1M内存，内存就能容纳9个用户进程了，CPU的利用率为180987利用率提高为87/5914714710047增加1M内存CPU利用率47。2、设一计算机系统有输入机一台、打印机两台，现有二道程序同时投入运行，且程序A先开始运行，程序B后运行。程序A的运行轨迹为计算50MS，打印信息100MS，再计算50MS,打印信息100MS,结束。程序B运行的轨迹为计算50MS，输入数据80MS，再计算100MS，结束。要求1用图画出这二道程序并发执行时的工作情况。2说明在二道程序运行时，CPU有无空闲等待若有，在哪段时间内等待为什么会空闲等待3程序A、B运行时有无等待现象在什么时候会发生等待现象答1工作情况如图。2CPU有空闲等待，它发生在100MS150MS时间段内，此时间段内程序A与程序B都在进行I/O操作。3程序A无等待现象，程序B在0MS50MS时间段与180MS200MS时间段内有等待现象。100MS50MS计算100MS打印50MS计算打印50MS80MS计算输入100MS计算50MS等待20MS等待050100150180200300MS程序A程序B时间如果将上题的轨迹更改为如下，情况又如何呢即一个计算机系统，有一台输入机和一台打印机，现有两道程序投入运行，且程序A先开始运行，程序B后开始运行。程序A的轨迹为计算50MS、输入80MS、再计算100MS，结束；程序B的运行轨迹为计算50MS、打印100MS、再计算50MS、打印100MS，结束。问题1画出两道程序运行的时间关系图；2两道程序运行时，CPU有无空闲等待若有，在哪段时间等待3程序A、B有无等待CPU的情况若有，在哪段时间等待解答1两道程序运行的时间关系图2CPU有空闲等待，它发生在100MS130MS时间段内，此时间段内程序A与程序B工作情况的另一种描述形式如下程序A程序B输入程序A打印计算程序A程序B打印机输入设备50100150180200300MS时间计算计算打印输入计算程序A程序B程序BCPU25050计算程序A程序B打印机输入设备100130200230380MS时间计算计算输入打印计算程序A程序B程序BCPU280输入程序A打印程序B打印打印都在进行I/O操作。3程序A无等待现象，程序B在0MS50MS时间段与200MS230MS时间段内有等待现象。3、设三道程序，按照A、B、C优先次序运行，其内部计算和I/O操作时间由图给出。ABCC1130MSC2160MSC3120MS|I1240MSI2230MSI3240MS|C1310MSC2310MSC3320MS试画出按多道运行的时间关系图忽略调度执行时间。完成三道程序共花多少时间比单道程序节省了多少时间若处理器调度程序每次运行程序的转换时间花1MS，试画出各程序状态转换的时间关系图。解答完成三道程序抢占式花费时间是190MS，非抢占花费时间是180MS，单道花费时间是260MS，抢占式比单道节省时间为70MS。单道程序运行时间260MSA30401080MSB603010100MSC20402080MS4、在单CPU和两台I/OI1和I2设备的多道程序设计环境下，同时投入三个作业运行。它们的执行轨迹如下JOB1I230MS、CPU10MS、I130MS、CPU10MS、I220MSJOB2I120MS、CPU20MS、I240MSJOB3CPU30MS、I120MS、CPU10MS、I110MS如果CPU、I1和I2都能并行工作，优先级从高到低为JOB1、JOB2和JOB3，优先级高的作业可以抢占优先级低的作业的CPU，但是不抢占I1和I2。试求1每个作业从投入到完成分别需要多少时间。2从投入到完成CPU的利用率。3I/O设备的利用率。答1JOB1,JOB2,JOB3从投入到完成分别所需时间为110，90，110。2每个作业从投入到完成CPU的利用率是727。3I1的利用率是727，I2的利用率是818。5、在单CPU和两台I/OI1和I2设备的多道程序设计环境下，同时投入三个作业运行。它们的执行轨迹如下JOB1I230MS、CPU10MS、I130MS、CPU10MSJOB2I120MS、CPU20MS、I240MSJOB3CPU30MS、I120MS如果CPU、I1和I2都能并行工作，优先级从高到低为JOB1、JOB2和JOB3，优先级高的作业可以抢占优先级低的作业的CPU，但是不抢占I1和I2。试求1每个作业从投入到完成分别需要多少时间。2从投入到完成CPU的利用率。3I/O设备的利用率。答1JOB1,JOB2,JOB3从投入到完成分别所需时间为80，90，90MS。2每个作业从投入到完成CPU的利用率是778。3I1的利用率是778，I2的利用率是778。6、若内存中存在3道程序A、B、C，它们按照A、B、C的优先次序运行。各程序的计算轨迹为A计算20MS、I/O30MS、计算10MSB计算40MS、I/O20MS、计算10MSC计算10MS、I/O30MS、计算20MS如果三道程序都使用相同的设备进行I/O即程序用串行方式使用设备，调度开销忽略不计。试分别画出单道和多道运行的时间关系图。两种情况下，CPU的平均利用率各为多少答单道总运行时间是190MS，CPU的利用率是110/190613。多道多道的总运行时间140MS，CPU的利用率是110/140786。7、若内存中存在3道程序A、B、C，它们按照A、B、C的优先次序运行。它们单独运行时的CPU和I/O占用时间为程序A60203010402020MSI/O2CPUI/O1CPUI/O1CPUI/O1程序B3040703030MSI/O1CPUI/O2CPUI/O2程序C40603070MSCPUI/O1CPUI/O2如果三道程序同时并发执行，调度开销忽略不计，但是优先级高的程序可以中断优先级低的程序，优先级与I/O设备无关。试画出多道运行的时间关系图，并问最早与最迟结束的程序是哪个每道程序执行到结束分别使用了多少时间计算三个程序全部运算结束时的CPU平均率答最早结束的是B，最晚的是C，A的运行时间是250MS，B的运行时间是220MS，C的运行时间是310MS，CPU的利用率是190/310613。8、若两个程序，A程序按顺序使用CPU10S，设备甲5S，CPU10S，设备乙10S，CPU10S。B程序按顺序使用设备甲10S，CPU10S，设备乙5S，CPU5S，设备乙10S。在顺序环境下先执行A，在执行B，求出总的CPU利用率为多少答程序A的执行了40秒，其中CPU使用了25秒，B程序执行40秒，其中CPU使用了15秒，而程序共使用了80秒，CPU花40秒，CPU的利用率是40/8050。9、在某计算机系统中，时钟中断处理程序每次执行时间为2MS包括进程切换开销。若中断频率为60HZ，试问CPU用于时钟中断处理的时间比率为多少答因为时钟中断频率是60HZ，时钟周期是1000MS/6050/3MS在每一个时钟周期里，CPU花2MS处理执行任务，所以CPU用于时钟中断的时间比例是2/50/36/5012。第二章处理机管理二、应用题1、下列指令中，哪些只能在核心态运行1读时钟日期；2访管指令；3设时钟日期；4加载PSW；5置特殊寄存器；6改变存储器映象图；7启动I/O指令。答可以在核心态下运行的是3设时钟日期；4加载PSW；5置特殊寄存器；6改变存储器映象图；7启动I/O指令。2、假设有一种低级调度算法是让“最近使用处理器较少的进程”运行，试解释这种算法对“I/O繁重”型作业有利，但并不是永远不受理“处理器繁重”型作业。答因为I/O繁忙作业忙于I/O，所以使用CPU较少，按照调度策略算法优先执行。一个进程等待CPU时间够长，是最近最少使用CPU进程，被优先调度。3、并发进程之间有什么样的相互制约关系下列日常生活中的活动属于哪种制约关系1踢足球；2吃自助餐；3图书馆借书；4电视机生产流水线工序答并发进程之间的相互制约关系有互斥和同步。属于互斥关系的有1踢足球；3图书馆借书；属于同步关系的有2吃自助餐；4电视机生产流水线工序5、若后备作业队列中等待运行的同时有三个作业J1、J2和J3，已知它们各自的运行为A、B、C，且满足A0可见，采用短作业优先算法调度能获得最小平均周转时间时间。7、假定执行表中作业队列，作业号为到达顺序，依次在时刻0按次序1、2、3、4、5进入单处理器系统。1分别用先来先服务调度算法、时间片轮转调度算法、短作业优先调度算法以及非抢占优先权调度算法算出各作业的执行先后次序注意优先权高的数值小；2计算各种情况下作业的平均作业周转时间和平均作业带权周转时间。作业号执行时间优先权1103211323414552解答FCFS作业执行时间等待时间开始时间完成时间周转时间带权周转时间1100010101211010111111321111131365411313141414551414191938T134W726时间片轮转，时长为Q1作业执行时间提交时间完成时间周转时间带权周转时间11001919192102223207735410444550141428T92W284SJF次序执行时间等待时间开始时间完成时间周转时间带权周转时间2100111411122232224425544991811099191919T7W174非强占优先权调度次序执行时间等待时间开始时间完成时间周转时间带权周转时间210011155116612326688411088181818411818191919T104W5410、有5个批处理作业A到E均已到达计算中心，其运行时间分别为2、4、6、8和10分钟；各自的优先级分别被规定为1、2、3、4和5，这里5为最高级。对于1时间片轮转算法、2优先数算法、3短作业优先算法、4先来先服务调度算法按到达次序C、D、B、E、A，在忽略进程切换时间的前提下，计算出平均作业周转时间。对1每个作业获得相同的2分钟的时间片；对2到4采用单道运行，直到结束。解答FCFS作业执行时间等待时间周转时间带权周转时间C6061D8614175B4141845E10182828A2283015T192W501时间片轮转，时长为Q2作业执行时间等待时间周转时间带权周转时间A2021B48123C61420333D81826325E1020303T14W2SJF次序执行时间等待时间周转时间带权周转时间A2021B42615C66122D8122025E1020303T14W2优先权调度次序执行时间等待时间周转时间带权周转时间E100101D81018225C618244B424287A2283015T22W58511、有5个批处理作业A到E均已到达计算中心，其运行时间分别为10、6、2、4、和8分钟；各自的优先级分别被规定为3、5、2、1和4，这里5为最高级。若不考虑系统切换开销，计算出平均作业周转时间。1FCFS按A、B、C、D、E；2优先级调度算法；3时间片轮转算法。解答FCFS作业执行时间等待时间周转时间带权周转时间A100101B61016266C216189D4182255E82230375T192W438时间片轮转，时长为Q2作业执行时间等待时间周转时间带权周转时间A1020303B61622366C2463D412164E8202835T204W343优先权调度次序执行时间等待时间周转时间带权周转时间B6061E8614175A10142424C2242613D4263075T20W51315、单道批处理系统中，下列三个作业采用先来先服务调度算法和最高响应比算法进行调度，哪一种算法性能较好请完成下表作业提交时间运行时间开始时间完成时间周转时间带权周转时间110002002101010031025025平均作业周转时间T平均作业带权周转时间W解答比较可得HRRF优于FCFS算法。FCFS作业提交时间运行时间开始时间完成时间周转时间带权周转时间11000200100012002120/1202101010012001300250170/6031025025130013253180/25T261W368HRRF作业提交时间运行时间开始时间完成时间周转时间带权周转时间11000200100012002120/1202101010012251325315195/6031025025120012252120/25T241W30216、若有如表所示四个作业进入系统，分别计算在FCFS、SJF和HRRF算法下的平均周转时间与带权平均周转时间。时间以十进制表示作业提交时间估计运行时间小时1800200285005039000104950020解答FCFS作业提交时间运行时间开始时间完成时间周转时间带权周转时间18002008001000200128500501000105020043900010105010601601649500201060108013065T1725W6875SJF作业提交时间运行时间开始时间完成时间周转时间带权周转时间180020080010002128500501030108023046390001010001010110114950020101010300804T155W515HRRF作业提交时间运行时间开始时间完成时间周转时间带权周转时间1800200800100021285005010101060210423900010100010101101149500201060108013065T1625W567518、若有一个四道作业系统，如果在一段时间内先后有6个作业，它们提交和运行时间由下表给出时间单位为分钟。系统采用短作业优先SJF调度算法，作业被调度进入系统后中途不会退出，但是作业会被更短的作业抢占。问题1画图给出6个作业的执行时间序列；2完成各个作业的开始时间、完成时间、周转时间和带权周转时间。3计算平均作业周转时间和平均作业带权周转时间。作业序号提交时间运行时间开始时间完成时间周转时间带权周转时间18006028203538252048302558355684010解答由下表可知作业序号提交时间运行时间开始时间完成时间周转时间带权周转时间1800608001035155155/602582820358209559595/25383825208258452020/2014830259009255555/2522583558458501515/536840108509002020/1021作业开始于800，结束于1035，周转155分钟。2作业开始于820，结束于955，周转95分钟。3作业开始于825，结束于845，周转20分钟。4作业开始于900，结束于925，周转55分钟。5作业开始于845，结束于855，周转15分钟。6作业开始于850，结束于900，周转20分钟。所以平均作业周转时间是1552095551520/660平均作业带权周转时间是2583812232/624319、有一个具有两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用以优先数为基础的抢占式调度算法，在下表所示的作业序列，作业优先数即为进程优先数，优先数越小优先级越高。作业名提交时间估计运行时间优先数A100040分5B102030分3C103050分4D105020分61列出所有作业进入内村时间及结束时间。2计算平均周转时间。解答每个作业运行将经过两个阶段作业调度短作业优先SJF和进程调度优先数抢占式。另外，批处理系统最多容纳2道作业，更多的作业将在后备对列等待。11000作业A到达并投入运行；21020作业B到达，且优先数高于作业A，故作业B投入运行，而作业A在就绪队列等待；31030作业C到达，但是内存中已有两道作业，故作业C进入作业后备队列等待；41050作业B运行结束，作业D到达，按照短作业优先算法，作业D被装入内存，进入就绪队列，而由于作业A的优先级高于作业D，作业A投入运行；51110作业A运行结束，作业C被调入内存，且作业C的优先级高于作业D，作业C投入运行；61200作业C运行结束，作业D投入运行；71220作业D运行结束；如图所示2从图中可以看出作业名提交时间估计运行时间进入内存时间运行结束时间A100040分10001110B102030分10201050C103050分11101200D105020分10501220作业A的周转时间是70，作业B的周转时间是30，作业C的周转时间是90，作业D的周转时间是207090，所以平均周转时间是70309090/470。作业B运行结束，作业D到达，按照短作业优先算法，作业D被装入内存，进入就绪队列，而由于作业A的优先级高于作业D，作业A投入运行作业A运行结束，作业C被调入内存，且作业C的优先级高于作业D，作业C投入运行24、一个实时系统有4个周期性事件，周期分别为50、100、300和250MS，若假设其处理分别需要35、20、10和MS，则该系统可调度允许的最大值为多少MS。答X应该满足条件35/5020/10010/300X/2501,则X50/31675MS，X的最大值是1675MS类比1一个实时系统有4个周期性事件，周期分别为50、100、250和200MS，若假设其处理分别需要30、20、25和MS，则该系统可调度允许的最大值为多少MS。答X应该满足条件30/5020/10025/250X/2001,则X20MS，X的最大值是20MS2设有周期性实时任务集如下表所示，是否可以调度任务发生周期TI处理时间CIA3010B4015C505答由于，因而可以调度。第三章并发进程二、应用题4、有一阅览室，共有100个座位。读者进入时必须先在一张登记表上登记，该表为每一座位列一表目，包括座号和读者姓名。读者离开时要消掉登记内容。试用P、V操作描述读者进程的同步结构。第一步确定进程可以进入阅览室的读者可以有很多，这里设为N，即N个READER（读者）进程READER进程登记进入阅览室读书离开阅览室注销第二步确定进程的同步、互斥关系同步当教室内有空座位时，读者才可以登记，并进入阅览室互斥同时只能有一个读者在入口处进行登记互斥同时只能有一个读者在出口处进行注销第三步设置信号量教室内空座位数量，SEAT，初值100为入口处进行登记设置互斥信号量SIN，初值1，表示当前可用为出口处进行注销设置互斥信号量SOUT，初值1，表示当前可用第四步用伪代码描述BEGINSIN,SOUT,SEATSEMAPHORESEAT100SIN1SOUT1COBEGINPROCESSREADERII1,2,NBEGINPSEATPSIN登记VSIN进入阅览室读书离开阅览室PSOUT注销VSOUTV（SEAT）ENDCOENDEND7、设公共汽车上，司机的活动顺序是启动车辆、正常行车、到站停车；售票员的活动顺序是关车门、售票、开车门。现假设初始状态为司机和售票员都已经在车上，汽车处于停止状态，车门处于开的状态。在汽车不断地到站、停车、行驶过程中，请用信号量的PV操作实现司机与售票员之间的同步关系。参考答案第一步确定进程2个进程DRIVER（司机）、BUSMAN（售票员）DRIVER进程启动车辆正常行车到站停车BUSMAN进程关车门售票开车门第二步确定进程的同步、互斥关系同步当售票员将车门关上后，司机才可以启动车辆同步当司机到站停车后，售票员打开车门第三步设置信号量车门关上，CLOSE，初值0到站停车，STOP，初值0第四步用伪代码描述BEGINCLOSE,STOPSEMAPHORECLOSE0STOP0COBEGINDRIVERBUSMANCOENDENDPROCESSDRIVERBEGINL1P（CLOSE）；启动车辆；正常行始；到站停车；V（STOP）；GOTOL1ENDPROCESSBUSMANBEGINL2关车门；V（CLOSE）售票；P（STOP）开车门；GOTOL2END19、设有三个进程A、B、C，其中A与B构成一对生产者与消费者（A为生产者，B为消费者），共享一个由N个缓冲块组成的缓冲池；B与C也构成一对生产者与消费者（此时B为生产者，C为消费者），共享另一个由M个缓冲块组成的缓冲池。用P、V操作描述它们之间的同步关系。答VARMUTEXA,EMPTYA,FULLA,MUTEXC,EMPTYC,FULLCSEMAPHEREI,J,A,BINTEGERBUFFERAARRAY0N1OFITEMBUFFERCARRAY0M1OFITEMPROCEDUREPRODUCEA生产者进程ABEGINWHILETUREDOBEGINPRODUCENEXTPRODUCTPEMPTYAPMUTEXABUFFERAIPRODUCTSII1MODNVMUTEXAVFULLAENDENDPROCEDURECONSUMER_PROCEDURERB消费者和生产者进程BBEGINWHILETUREDOBEGINPFULLAPMUTEXAGOODSBUFFERJJJ1MODNVMUTEXAVEMPTYACONSUMEGOODSANDPRODUCENEXTPRODUCTCPEMPTYCPMUTEXCBUFFERCAPRODUCTCAA1MODMVMUTEXCVFULLCENDENDPROCEDURECONSUMERC消费者C进程BEGINWHILETUREDOBEGINPFULLCPMUTEXCGOODSBUFFERCBBB1MODMVMUTEXCVEMPTYCCONSUMEPRODUCTENDENDBEGINSEMINITSALMUTEXAV,1MUTEXCV,1EMPTYAV,NEMPTYCV,MFULLAV,0FULLCV,0I0J0A0B0COBEGINPRODUCEACONSUMER_PROCEDURERBCONSUMERCCOENDEND26、设当前的系统状态如下表所示，系统此时AVAILABLE1,1,2。CLAIMALLOCATION进程R1R2R3R1R2R3P1322100P2613511P3314211P4422002问题1计算各个进程还需要的资源数CKIAKI；2此时系统是否处于安全状态，为什么如果安全，则请给出一个安全序列；3当P2发出资源请求向量REQUEST21,0,1，此时系统能否把资源分配给它为什么如果能分配给它，则请给出一个安全序列；4若在P2发出资源请求向量REQUEST21,0,1后，若P1发出资源请求向量REQUEST11,0,1，此时系统能否把资源分配给它为什么5若在P1发出资源请求向量REQUEST11,0,1后，若P3发出资源请求向量REQUEST30,0,1，此时系统能否把资源分配给它为什么解答1各个进程还需要的资源数CKIAKICKIAKI进程R1R2R3P1222P2122P3103P44202此时系统是否处于安全状态，安全序列为P2，P1，P3，P4。3当P2发出资源请求向量REQUEST21,0,1，此时系统可以把资源分配给它，因为系统是安全的，相应的安全序列为P2，P1，P3，P4。4若在P2发出资源请求向量REQUEST21,0,1后，若P1发出资源请求向量REQUEST11,0,1，此时系统不能把资源分配给它，因为此时系统资源不足。5若在P1发出资源请求向量REQUEST11,0,1后，若P3发出资源请求向量REQUEST30,0,1，此时系统不能把资源分配给它，因为如果分配，系统不安全，会导致死锁。27、设系统中A、B、C、D共4种资源，在某时刻进程P0、P1、P2、P3、P4对资源的占有和需求情况如下表所示。问题1计算各个进程还需要的资源数CKIAKI；2此时系统是否处于安全状态，为什么如果安全，则请给出一个安全序列；3若在P0发出资源请求向量REQUEST00,0,1,1后，此时系统把资源分配给它是否安全如果安全，则请给出一个安全序列；4当P2发出资源请求向量REQUEST21,2,2,2，此时系统能否把资源分配给它为什么5若在P0发出资源请求向量REQUEST00,0,1,1后，P4若发出资源请求向量REQUEST40,6,2,2，此时系统能否把资源分配给它为什么ALLOCATIONCLAIMAVAILABLE进程ABCDABCDABCDP000320044P110002750P21354361010P303320984P40014066101622解答1各个进程还需要的资源数CKIAKICKIAKI进程ABCDP10012P21750P32356P40652P506562此时系统是否处于安全状态，安全序列为P0，P3，P4，P1，P2。3若在P0发出资源请求向量REQUEST00,0,1,1后，此时系统把资源分配给它是安全的，安全序列为P0，P3，P4，P1，P2。4当P2发出资源请求向量REQUEST21,2,2,2，此时系统不能把资源分配给它，因为系统将处于不安全状态，会导致死锁。5若在P0发出资源请求向量REQUEST00,0,1,1后，P4若发出资源请求向量REQUEST40,6,2,2，此时系统不能把资源分配给它，因为此时系统资源不足。28、把死锁检测算法用于下面的数据，并请问AVAILABLE1,0,2,001120100001321100011NEED00001011011100101103ALLOCATION1此时系统处于安全状态吗2若第二个进程提出资源请求REQUEST20,0,1,0，系统能分配资源给它吗3执行2之后，若第五个进程提出资源请求REQUEST50,0,1,0，系统能分配资源给它吗解1可以找到安全序列，P4,P1,P5,P2,P3。2可以，安全序列是P1,P4,P5,P2,P3。3不可以，处于不安全状态。38、桌上有一个空盘子，最多容纳两个水果，每次仅能放入或取出一个水果。爸爸向盘中放苹果，妈妈向盘中放桔子，规定两个儿子专等吃盘中的桔子，两个女儿专等吃盘中的苹果。请用信号量实现爸爸、妈妈、儿子、女儿之间的同步。第一步确定进程4个进程FATHER（爸爸）、MOTHER（妈妈）、SON（儿子）、DAUGHTER（女儿）FATHER进程将苹果放入盘中MOTHER进程将桔子放入盘中SON进程从盘中取出桔子吃桔子DAUGHTER进程从盘中取出苹果吃苹果第二步确定进程的同步、互斥关系同步FATHER当盘中无水果时，才可以将苹果放入盘中同步MOTHER当盘中无水果时，才可以将桔子放入盘中同步SON当盘中有桔子时，才可以从盘中取出桔子同步DAUGHTER当盘中有苹果时，才可以从盘中取出苹果第三步设置信号量盘中无水果，SP，初值2；盘中有桔子，SO，初值0；盘中有苹果，SA，初值0；FLAG0FLAG1FALSE；MUTEX1；PLATEARRAY0，1OF（APPLE，ORANGE）第四步用伪代码描述BEGINSP,SO,SASEMAPHORESP1SO0SA0COBEGINFATHERMOTHERSONDAUGHTERCOENDENDPROCESSFATHERBEGINL1P（SP）P（MUTEX）IF（FLAG0FALSE）THENPLATE0苹果；FLAG0TRUE；ELSEPLATE1苹果；FLAG1TRUE；V（MUTEX）V（SA）GOTOL1ENDPROCESSMOTHERBEGINL2P（SP）P（MUTEX）IF（FLAG0FALSE）THENPLATE0桔子；FLAG0TRUE；ELSEPLATE1桔子；FLAG1TRUE；V（MUTEX）V（SO）GOTOL2ENDPROCESSSONBEGINL3P（SO）P（MUTEX）IF（FLAG0V（SP）吃桔子；GOTOL3；ENDPROCESSDAUGHTERBEGINL4P（SA）P（MUTEX）IF（FLAG0V（SP）吃苹果；GOTOL4；END桌上有一个空盘子，只允许放一只水果。爸爸或向盘中放苹果，或放桔子，规定儿子只能吃桔子，女儿只能吃苹果。请用信号量实现爸爸、儿子、女儿之间的同步。解这是一个典型的同步问题。首先确定进程个数三个进程爸爸、儿子和女儿。然后确定同步信号量的个数及含义设置三个同步信号量，SP指示盘子是否为空，其初值为“1”表示开始盘子为空；SO指示盘中是否有桔子，其初值为“0”表示开始盘中无桔子；SA指示盘中是否有苹果，其初值为“0”表示开始盘中无苹果。算法描述如下BEGINSP,SO,SASEMAPHORESP1SO0SA0COBEGINFATHERSONDAUGHTERCOENDENDPROCESSFATHERBEGINL1P（SP）将水果放入盘中；IF（放入的是桔子）THENV（SO）ELSEV（SA）GOTOL1ENDPROCESSSONBEGINL2P（SO）从盘中取出桔子；V（SP）吃桔子；GOTOL2；ENDPROCESSDAUGHTERBEGINL3P（SA）从盘中取出苹果；V（SP）吃苹果；GOTO3；END桌上有一个空盘子，只允许放一只水果。爸爸向盘中放苹果，妈妈向盘中放桔子，规定儿子只能吃桔子，女儿只能吃苹果。请用PV操作实现他们之间的同步关系参考答案（1）桌上一个盘子，只能放一只水果。爸爸放苹果，妈妈放桔子，儿子只吃桔子，女儿只吃苹果。第一步确定进程4个进程FATHER（爸爸）、MOTHER（妈妈）、SON（儿子）、DAUGHTER（女儿）FATHER进程将苹果放入盘中MOTHER进程将桔子放入盘中SON进程从盘中取出桔子吃桔子DAUGHTER进程从盘中取出苹果吃苹果第二步确定进程的同步、互斥关系同步FATHER当盘中无水果时，才可以将苹果放入盘中同步MOTHER当盘中无水果时，才可以将桔子放入盘中同步SON当盘中有桔子时，才可以从盘中取出桔子同步DAUGHTER当盘中有苹果时，才可以从盘中取出苹果第三步设置信号量盘中无水果，SP，初值1盘中有桔子，SO，初值0盘中有苹果，SA，初值0第四步用伪代码描述BEGINSP,SO,SASEMAPHORESP1SO0SA0COBEGINFATHERMOTHERSONDAUGHTERCOENDENDPROCESSFATHERBEGINL1P（SP）将苹果放入盘中；V（SA）GOTOL1ENDPROCESSMOTHERBEGINL2P（SP）将桔子放入盘中；V（SO）GOTOL2ENDPROCESSSONBEGINL3P（SO）从盘中取出桔子；V（SP）吃桔子；GOTOL3；ENDPROCESSDAUGHTERBEGINL4P（SA）从盘中取出苹果；V（SP）吃苹果；GOTOL4；END桌上有一个空盘子，只允许放一只水果。爸爸放苹果，妈妈放桔子，儿子吃桔子、苹果。请用PV操作实现他们之间的同步关系第一步确定进程3个进程FATHER（爸爸）、MOTHER（妈妈）、SON（儿子）FATHER进程将苹果放入盘中MOTHER进程将桔子放入盘中SON进程从盘中取出水果（桔子或苹果）吃水果（桔子或苹果）第二步确定进程的同步、互斥关系同步FATHER当盘中无水果时，才可以将苹果放入盘中同步MOTHER当盘中无水果时，才可以将桔子放入盘中同步SON当盘中有水果（桔子或苹果）时，才可以从盘中取出水果第三步设置信号量盘中无水果，EMPTY，初值1盘中有水果（桔子或苹果），FULL，初值0第四步用伪代码描述BEGINEMPTY,FULLSEMAPHOREEMPTY1FULL0COBEGINFATHERMOTHERSONCOENDENDPROCESSFATHERBEGINL1P（EMPTY）将苹果放入盘中；V（FULL）GOTOL1ENDPROCESSMOTHERBEGINL2P（EMPTY）将桔子放入盘中；V（FULL）GOTOL2ENDPROCESSSONBEGINL3P（FULL）从盘中取出水果V（EMPTY）吃水果GOTOL3；END40、假设有三个并发进程P，Q，R，其中P负责从输入设备上读入信息并传送给Q，Q将信息加工后传送给R，R则负责将信息打印输出。写出下列条件的并发程序（1）进程P、Q共享一个缓冲区，进程Q、R共享另一个缓冲区。（2）进程P、Q共享一个由M个缓冲区组成的缓冲池，进程Q、R共享另一个由N个缓冲区组成的缓冲池。参考答案（1）进程P、Q共享一个缓冲区，进程Q、R共享另一个缓冲区。第一步确定进程3个进程P、Q、RP进程从输入设备上读入信息将信息放入缓冲区1Q进程从缓冲区1取出信息将信息放入缓冲区2中R进程从缓冲区2取出信息将信息打印输出第二步确定进程的同步、互斥关系同步P当缓存区1无数据时，才可以向缓冲区1写入信息同步Q当缓存区1有数据时，才可以从缓冲区1读取信息同步Q当缓存区2无数据时，才可以向缓冲区2写入信息同步R当缓存区2有数据时，才可以从缓冲区2读取信息第三步设置信号量缓存区1无数据，EMPTY1，初值1缓存区1有数据，FULL1，初值0缓存区2无数据，EMPTY2，初值1缓存区2有数据，FULL2，初值0第四步用伪代码描述BEGINEMPTY1,EMPTY2,FULL1,FULL2SEMAPHOREEMPTY11EMPTY21FULL10FULL20COBEGINPQRCOENDENDPROCESSPBEGINL1从输入设备上读入信息P（EMPTY1）将信息放入缓冲区1；V（FULL1）GOTOL1ENDPROCESSQBEGINL2P（FULL1）从缓冲区1取出信息V（EMPTY1）P（EMPTY2）将信息放入缓冲区2；V（FULL2）GOTOL2ENDPROCESSRBEGINL3P（FULL2）从缓冲区2取出信息V（EMPTY2）将信息打印输出GOTOL3END（2）进程P、Q共享一个由M个缓冲区组成的缓冲池，进程Q、R共享另一个由N个缓冲区组成的缓冲池。第一步确定进程3个进程P、Q、RP进程从输入设备上读入信息将信息放入缓冲池1中的一个空缓冲区中Q进程从缓冲池1中的一个非空缓冲区中取出信息将信息放入缓冲池2中的一个空缓冲区中R进程从缓冲池2中的一个非空缓冲区中取出信息将信息打印输出第二步确定进程的同步、互斥关系同步P当缓冲池1中有空的缓冲区时，才可以向缓冲池1写入信息同步Q当缓冲池1中有非空的缓冲区时，才可以从缓冲池1读取信息同步Q当缓冲池2中有空的缓冲区时，才可以向缓冲池2写入信息同步R当缓冲池2中有非空的缓冲区时，才可以从缓冲池2读取信息第三步设置信号量缓冲池1中的空缓冲区的数量，EMPTY1，初值M缓冲池1中的非空缓冲区的数量，FULL1，初值0缓冲池2中的空缓冲区的数量，EMPTY2，初值N缓冲池2中的非空缓冲区的数量，FULL2，初值0第四步用伪代码描述BEGINEMPTY1,EMPTY2,FULL1,FULL2SEMAPHOREEMPTY1MEMPTY2NFULL10FULL20COBEGINPQRCOENDENDPROCESSPBEGINL1从输入设备上读入信息P（EMPTY1）将信息放入缓冲池1中的一个空缓冲区中；V（FULL1）GOTOL1ENDPROCESSQBEGINL2P（FULL1）从缓冲池1中的一个非空缓冲区中取出信息V（EMPTY1）P（EMPTY2）将信息放入缓冲池2中的一个空缓冲区中；V（FULL2）GOTOL2ENDPROCESSRBEGINL3P（FULL2）从缓冲池2中的一个非空缓冲区中取出信息V（EMPTY2）将信息打印输出GOTOL3END某工厂有一个可以存放设备的仓库，总共可以存放10台设备。生产的每一台设备都必须入库，销售部门可从仓库提出设备供应客户。设备的入库和出库都必须借助运输工具。现只有一台运输工具，每次只能运输一台设备。请设计一个能协调工作的自动调度管理系统。参考答案第一步确定进程可以为入库（PIN）和出库（POUT）各设置一个进程PIN进程生产了一台设备使用运输工具入库POUT进程使用运输工具出库提出设备供应客户第二步确定进程的同步、互斥关系同步当仓库中有空余位置存放设备时，设备才可以入库同步当仓库中有存放的设备时，设备才可以出库互斥运输工具是临界资源，要互斥访问第三步设置信号量仓库中有空余位置数量，EMPTY，初值10仓库中有存放的设备数量，FULL，初值0为运输工具设置互斥信号量S，初值1，表示当前可用第四步用伪代码描述BEGINEMPTY,FULL,SSEMAPHOREEMPTY10FULL0S1COBEGINPINPOUTCOENDENDPROCESSPINBEGINL1生产了一台设备P（EMPTY）PS使用运输工具入库V（S）V（FULL）GOTOL1ENDPROCESSPOUTBEGINL2P（FULL）PS使用运输工具出库V（S）V（EMPTY）提出设备供应客户GOTOL2END有四个并发进程R1，R2，W1和W2，它们共享可以存放一个数的缓冲区。进程R1每次从磁盘读入一个数存放到缓冲区中，供进程W1打印输出；进程R2每次从键盘读一个数存放到缓冲区中，供进程W2打印输出。当缓冲区满时，不允许再向缓冲区中存放数据；当缓冲区空时，不允许再从缓冲区中取出数据打印输出。试用PV操作实现四个进程的协调运行。参考答案第一步确定进程4个进程R1、R2、W1、W2R1进程从磁盘上读入一个数将数存放到缓冲区中W1进程将R1进程放进缓冲区中的数取出打印输出R2进程从键盘读入一个数将数存放到缓冲区中W2进程将R2进程放进缓冲区中的数取出打印输出第二步确定进程的同步、互斥关系同步R1当缓存区无数据时，才可以向缓冲区写入数据同步R2当缓存区无数据时，才可以向缓冲区写入数据同步W1当缓存区中是R1写的数据时，才可以将数据从缓冲区中读出同步W2当缓存区中是R2写的数据时，才可以将数据从缓冲区中读出第三步设置信号量缓存区无数据，EMPTY，初值1缓存区中是R1写的数据，FULL1，初值0缓存区中是R2写的数据，FULL2，初值0第四步用伪代码描述BEGINEMPTY,FULL1,FULL2SEMAPHOREEMPTY1FULL10FULL20COBEGINR1R2W1W2COENDENDPROCESSR1BEGINL1从磁盘上读入一个数；P（EMPTY）将数存放到缓冲区中；V（FULL1）GOTOL1ENDPROCESSR2BEGINL2从键盘上读入一个数；P（EMPTY）将数存放到缓冲区中；V（FULL2）GOTOL2ENDPROCESSW1BEGINL3P（FULL1）将缓冲区中的数取出；V（EMPTY）打印输出GOTOL3ENDPROCESSW2BEGINL4P（FULL2）将缓冲区中的数取出；V（EMPTY）打印输出GOTOL4END系统中只有一台打印机，有三个进程在运行中都需要使用打印机进行打印输出，问这三个进程间有什么样的制约关系试用信号量的PV操作描述这种关系。参考答案由于打印机是临界资源，三个进程共享临界资源，是互斥关系。为临界资源设置互斥信号量S，初始值为1BEGINSSEMAPHORES1COBEGINPROCESSPII0,1,2BEGIN其他工作；PS打印；VSENDCOENDEND哲学家进餐问题五位哲学家吃面条，只有五根筷子，每个人必须用一双筷子才能吃面条。请用信号量的PV操作描述哲学家之间的关系。请问如下解答是否正确如果不正确，错在何处第一步确定进程5个进程PI（I04）PI进程思考拿起左边筷子拿起右边筷子吃面条放下右边筷子放下左边筷子第二步确定进程的同步、互斥关系互斥筷子是互斥资源，每个人都只能使用他左右的两根筷子第三步设置信号量CHOPSTICK5表示5根筷子，初值1第四步用伪代码描述BEGINCHOPSTICK04SEMAPHORECHOPSTICK041COBEGINPROCESSPII0,2,4BEGIN思考；P（CHOPSTICKI）P（CHOPSTICKI15）吃面条；V（CHOPSTICKI15）V（CHOPSTICKI）ENDCOENDEND错误原因假如所有的哲学家都同时拿起左侧筷子，看到右侧筷子不可用，都在等待右侧筷子，无限期地运行，但是都无法取得任何进展，即出现饥饿，所有哲学家都吃不上饭。解决方案至多只允许四个哲学家同时进餐,以保证至少有一个哲学家能够进餐,最终总会释放出他所使用过的两支筷子,从而可使更多的哲学家进餐。规定奇数号的哲学家先拿起他左边的筷子,然后再去拿他右边的筷子而偶数号的哲学家则相反按此规定,将是1,2号哲学家竞争1号筷子,3,4号哲学家竞争3号筷子即五个哲学家都竞争奇数号筷子,获得后,再去竞争偶数号筷子,最后总会有一个哲学家能获得两支筷子而进餐。而申请不到的哲学家进入阻塞等待队列，则先申请的哲学家会较先可以吃饭，因此不会出现饿死的哲学家。将拿筷子的操作做成原子操作，即当一个哲学家正在拿筷子的时候，其它的哲学家不能动筷子，当他那好筷子开始吃饭的时候，其它哲学家才可以拿筷子。第一步确定进程5个进程PI（I04）PI进程思考拿起左边筷子拿起右边筷子吃面条放下右边筷子放下左边筷子第二步确定进程的同步、互斥关系互斥筷子是互斥资源，每个人都只能使用他左右的两根筷子同步只能有四个人同时吃饭第三步设置信号量CHOPSTICK5表示5根筷子，初值1NUM表示允许吃面的人的个数，初值4第四步用伪代码描述BEGINCHOPSTICK04SEMAPHORENUMSEMAPHORECHOPSTICK041NUM4COBEGINPROCESSPII0,2,4BEGIN思考；PNUMP（CHOPSTICKI）P（CHOPSTICKI15）吃面条；V（CHOPSTICKI15）V（CHOPSTICKI）VNUMENDCOENDEND第四章存储器管理二、应用题1、在一个请求式分页虚拟存储管理系统中，一个程序运行的页面走向是1、2、3、4、2、1、5、6、2、1、2、3、7、6、3、2、1、2、3、6。分别使用FIFO、LRU和OPT算法，对分配给程序3个页框、4个页框、5个页框和6个页框的情况下，分别求出缺页中断次数和缺页中断率。注意给定的页块初始均为空，因此首次访问一页时就会发生缺页中断。解页框FIFOLRUOPT3161511414108512876977缺页中断率缺页中断次数/20具体计算如下3个页框情况1FIFO算法12342156212376321236111444466663333222262222111222277771111333355511116666633是否缺页是是是是是是是是是是是是是是是是缺页中断次数为162LRU算法12342156212376321236111441112222266611162222226666333333333333355511177722222