操作系统练习题答案.doc 37页

'《操作系统教程》（第三版）CH1应用题参考答案CH1应用题参考答案1有一台计算机，具有1MB内存，操作系统占用200KB，每个用户进程各占200KB。如果用户进程等待I/O的时间为80%，若增加1MB内存，则CPU的利用率提高多少？答：设每个进程等待I/O的百分比为P，则n个进程同时等待I/O的概率是Pn，当n个进程同时等待I/O期间CPU是空闲的，故CPU的利用率为1-Pn。由题意可知，除去操作系统，内存还能容纳4个用户进程，由于每个用户进程等待I/O的时间为80%，故：CPU利用率=1-(80%)4=0.59若再增加1MB内存，系统中可同时运行9个用户进程，此时：CPU利用率=1-(80%)9=0.87故增加1MB内存使CPU的利用率提高了47%：87%÷59%=147%147%-100%=47%2一个计算机系统，有一台输入机和一台打印机，现有两道程序投入运行，且程序A先开始做，程序B后开始运行。程序A的运行轨迹为：计算50ms、打印100ms、再计算50ms、打印100ms，结束。程序B的运行轨迹为：计算50ms、输入80ms、再计算100ms，结束。试说明(1)两道程序运行时，CPU有无空闲等待？若有，在哪段时间内等待？为什么会等待？(2)程序A、B有无等待CPU的情况？若有，指出发生等待的时刻。答：画出两道程序并发执行图如下：处理器输入机打印机程序A程序BA计算B计算计算计算时间(ms)050100150180200250300打印计算打印输入计算A打印A打印B输入A计算B计算一(1)两道程序运行期间，CPU存在空闲等待，时间为100至150ms之间(见图中有色部分)。(2)程序A无等待现象，但程序B有等待。程序B有等待时间段为180ms至200ms间(见图中有色部分)。3设有三道程序，按A、B、C优先次序运行，其内部计算和I/O操作时间由图给出。ABCC11＝30msC21=60msC31=20ms∣∣∣I12＝40msI22=30msI32=40ms∣∣∣C13＝10msC23=10msC33=20ms37 《操作系统教程》（第三版）CH1应用题参考答案试画出按多道运行的时间关系图（忽略调度执行时间）。完成三道程序共花多少时间？比单道运行节省了多少时间？若处理器调度程序每次进行程序转换化时1ms，试画出各程序状态转换的时间关系图。答：1）忽略调度执行时间，多道运行方式（抢占式）：时间0378101213141719单位10msI/OI12I22I32CPUC11C21C13C21C31C23C33抢占式共用去190ms，单道完成需要260ms，节省70ms。忽略调度执行时间，多道运行方式（非抢占式）：时间0379101213141618单位10msI/OI12I22I32CPUC11C21C13C31C23C33非抢占式共用去180ms，单道完成需要260ms，节省80ms。2）调度执行时间1ms，多道运行方式（抢占式）：时间0303132717273748485105107127136137147177178198单位1msI/OI12I22I32CPUC11C21C13C21C31C23C33OS调度执行时间1ms，多道运行方式（非抢占式）：时间03031327172939495105106124125127129139168169189单位1msI/OI12I22I32CPUC11C21C21C13C31C31C23C33OS1在单CPU和两台I/O(I1,I2)设备的多道程序设计环境下，同时投入三个作业运行。它们的执行轨迹如下：Job1：I2(30ms)、CPU(10ms)、I1(30ms)、CPU(10ms)、I2(20ms)Job2：I1(20ms)、CPU(20ms)、I2(40ms)Job3：CPU(30ms)、I1(20ms)、CPU(10ms)、I1(10ms)如果CPU、I1和I2都能并行工作，优先级从高到低为Job1、Job2和Job3，优先级高的作业可以抢占优先级低的作业的CPU，但不抢占I1和I2。试求：(1)每个作业从投入到完成分别所需的时间。(2)从投入到完成CPU的利用率。(3)I/O设备利用率。答：画出三个作业并行工作图如下(图中着色部分为作业等待时间)：37 《操作系统教程》（第三版）CH1应用题参考答案CPUI1I2Job1Job2Job3时间(ms)CPUCPU0102030405060708090100110CPUI1I1I1CPUCPUI2I2CPUI1CPUI2Job1Job2Job3Job2Job1Job2Job3Job1Job3Job2Job1Job1Job3Job3(1)Job1从投入到运行完成需110ms，Job2从投入到运行完成需90ms，Job3从投入到运行完成需110ms。(2)CPU空闲时间段为：60ms至70ms，80ms至90ms，100ms至110ms。所以CPU利用率为(110-30)/110=72.7%。(3)设备I1空闲时间段为：20ms至40ms，90ms至100ms，故I1的利用率为(110-30)/110=72.7%。设备I2空闲时间段为：30ms至50ms，故I2的利用率为(110-20)/110=81.8%。1在单CPU和两台I/O(I1,I2)设备的多道程序设计环境下，同时投入三个作业运行。它们的执行轨迹如下：Job1：I2(30ms)、CPU(10ms)、I1(30ms)、CPU(10ms)Job2：I1(20ms)、CPU(20ms)、I2(40ms)Job3：CPU(30ms)、I1(20ms)如果CPU、I1和I2都能并行工作，优先级从高到低为Job1、Job2和Job3，优先级高的作业可以抢占优先级低的作业的CPU。试求：(1)每个作业从投入到完成分别所需的时间。(2)每个作业投入到完成CPU的利用率。(3)I/O设备利用率。答：画出三个作业并行工作图如下(图中着色部分为作业等待时间)：CPUI1I2Job1Job2Job3时间(ms)CPUCPU0102030405060708090I1I1CPUCPUI2I2CPUI1CPUJob1Job2Job3Job2Job1Job2Job3Job1Job2Job1Job3Job1从投入到运行完成需80ms，Job2从投入到运行完成需90ms，Job3从投入到运行完成需90ms。(1)CPU空闲时间段为：60ms至70ms，80ms至90ms。所以CPU利用率为(90-20)/90=77.78%。(2)设备I1空闲时间段为：20ms至40ms，故I1的利用率为(90-20)/90=77.78%。设备I2空闲时间段为：30ms至50ms，故I2的利用率为(90-20)/90=77.78%。2若内存中有3道程序A、B、C，它们按A、B、C优先次序运行。各程序的计算轨迹为：A：计算(20)、I/O(30)、计算(10)37 《操作系统教程》（第三版）CH1应用题参考答案B：计算(40)、I/O(20)、计算(10)C：计算(10)、I/O(30)、计算(20)如果三道程序都使用相同设备进行I/O(即程序用串行方式使用设备，调度开销忽略不计)。试分别画出单道和多道运行的时间关系图。两种情况下，CPU的平均利用率各为多少?答：分别画出单道和多道运行的时间图02040506080100120140160180190I/OCPU时间(ms)AAABBBCCC(1)单道运行时间关系图单道总运行时间为190ms。CPU利用率为(190-80)/190=57.9%(1)单道运行时间关系图I/OCPU时间(ms)AAABC02040506080100120140BBCCB多道总运行时间为140ms。CPU利用率为(140-30)/140=78.6%1若内存中有3道程序A、B、C，优先级从高到低为A、B和C，它们单独运行时的CPU和I/O占用时间为：程序A：60203010402020(ms)I/O2CPUI/O1CPUI/O1CPUI/O1程序B：3040703030(ms)I/O1CPUI/O2CPUI/O2程序C：40603070(ms)CPUI/O1CPUI/O2如果三道程序同时并发执行，调度开销忽略不计，但优先级高的程序可中断优先级低的程序，优先级与I/O设备无关。试画出多道运行的时间关系图，并问最早与最迟结束的程序是哪个？每道程序执行到结束分别用了多少时间？计算三个程序全部运算结束时的CPU利用率?答：画出三个作业并发执行的时间图：CPUI01I02ABC时间(ms)cpu0306090120150180210240270300330I01cpucpuI02I02cpucpuI01cpuABBABCBCACI01cpuI01ACAAcpucpuI01cpucpuI02I02BCBCA37 《操作系统教程》（第三版）CH1应用题参考答案(1)最早结束的程序为B，最后结束的程序为C。(2)程序A为250ms。程序B为220ms。程序C为310ms。(3)CPU利用率为(310-120)/310=61.3%1有两个程序，A程序按顺序使用：(CPU)10秒、(设备甲)5秒、(CPU)5秒、(设备乙)10秒、(CPU)10秒。B程序按顺序使用：(设备甲)10秒、(CPU)10秒、(设备乙)5秒、(CPU)5秒、(设备乙)10秒。在顺序环境下先执行A，再执行B，求出总的CPU利用率为多少?答：程序A执行了40秒，其中CPU用了25秒。程序B执行了40秒，其中CPU用了15秒。两个程序共用了80秒，CPU化了40秒。故CPU利用率为40/80=50%。2在某计算机系统中，时钟中断处理程序每次执行的时间为2ms（包括进程切换开销）。若时钟中断频率为60HZ，试问CPU用于时钟中断处理的时间比率为多少?答：因时钟中断频率为60HZ，所以，时钟周期为：1/60s=50/3ms。在每个时钟周期中，CPU花2ms执行中断任务。所以，CPU用于时钟中断处理的时间比率为：2(50/3)=6/50=12%。CH2应用题参考答案1下列指令中哪些只能在核心态运行?(1)读时钟日期；（2）访管指令；（3）设时钟日期；（4）加载PSW；（5）置特殊寄存器；(6)改变存储器映象图；(7)启动I/O指令。答：(3)，(4)，(5)，(6)，(7)。2假设有一种低级调度算法是让“最近使用处理器较少的进程”运行，试解释这种算法对“I/O繁重”型作业有利，但并不是永远不受理“处理器繁重”型作业。答：因为I/O繁忙型作业忙于I/O，所以它CPU用得少，按调度策略能优先执行。同样原因一个进程等待CPU足够久时，由于它是“最近使用处理器较少的进程”，就能被优先调度，故不会饥饿。3并发进程之间有什么样的相互制约关系?下列日常生活中的活动是属哪种制约关系：(1)踢足球，(2)吃自助餐，(3)图书馆借书，(4)电视机生产流水线工序。答：并发进程之间的基本相互制约关系有互斥和同步两种。其中(1)、(3)为互斥问题。(2)、(4)为同步问题。4在按动态优先数调度进程的系统中，每个进程的优先数需定时重新计算。在处理器不断地在进程之间交替的情况下，重新计算进程优先数的时间从何而来?37 《操作系统教程》（第三版）CH1应用题参考答案答：许多操作系统重新计算进程的优先数在时钟中断处理例程中进行，由于中断是随机的，碰到哪个进程，就插入哪个进程中运行处理程序，并把处理时间记在这个进程的账上。1若后备作业队列中等待运行的同时有三个作业J1、J2、J3，已知它们各自的运行时间为a、b、c，且满足a0可见，采用短作业优先算法调度才能获得最小平均作业周转时间。2若有一组作业J1，…，Jn，其执行时间依次为S1，…，Sn。如果这些作业同时到达系统，并在一台单CPU处理器上按单道方式执行。试找出一种作业调度算法，使得平均作业周转时间最短。答：首先，对n个作业按执行时间从小到大重新进行排序，则对n个作业：J1’，…，Jn’，它们的运行时间满足：S1’≤S2’≤…≤S(n-1)’≤Sn’。那么有：T=[S1’+(S1’+S2’)+(S1’+S2’+S3’)+…+(S1’+S2’+S3’+…+Sn’)]/n=[n×S1’+(n-1)×S2’+(n-3)×S3’]+…+Sn’]]/n=(S1’+S2’+S3’+…+Sn’)-[0×S1’+1×S2’+2×S3’+…+(n-1)Sn’]/n由于任何调度方式下，S1’+S2’+S3’+…+Sn’为一个确定的数，而当S1’≤S2’≤…≤S(n-1)’≤Sn’时才有：0×S1’+1×S2’+2×S3’+…+(n-1)Sn’的值最大，也就是说，此时T值最小。所以，按短作业优先调度算法调度时，使得平均作业周转时间最短。3假定执行表中所列作业，作业号即为到达顺序，依次在时刻0按次序1、2、3、4、5进入单处理器系统。1）分别用先来先服务调度算法、时间片轮转算法、短作业优先算法及非强占优先权调度算法算出各作业的执行先后次序(注意优先权高的数值小)；2）计算每种情况下作业的平均周转时间和平均带权周转时间。作业号执行时间优先权1234510121531342答：采用FCFS算法调度作业，运作情况：37 《操作系统教程》（第三版）CH1应用题参考答案执行次序执行时间等待时间开始时间完成时间周转时间带权周转时间110001010121101011111132111113136.541131314141455141419193.8作业平均周转时间T=(10+11+13+14+19)/5=13.4作业平均带权周转时间W=(1+11+6.5+14+3.8)/5=7.26(1)采用RR算法调度作业，若令时间片长=1，各作业执行情况为：1、2、3、4、5、1、3、5、1、5、1、5、1、5、1、1、1、1、1。作业执行时间提交时间完成时间周转时间带权周转时间110019191.9210222320773.541044455014142.8作业平均周转时间T=(19+2+7+4+14)/5=9.2作业平均带权周转时间W=(1.9+2+3.5+4+2.8)/5=2.84采用SJF算法调度作业，运作情况：执行次序执行时间等待时间开始时间完成时间周转时间带权周转时间2100111411122232224425544991.81109919191.9作业平均周转时间T=(1+2+4+9+19)/5=7作业平均带权周转时间W=(1+2+2+1.8+1.9)/5=1.74(2)采用非剥夺优先权算法调度作业，运作情况：执行次序优先数执行时间等待时间周转时间带权周转时间211011525161.213106161.633216189441181919作业平均周转时间T=(1+6+16+18+19)/5=12作业平均带权周转时间W=(1+1.2+1.6+9+19)/5=6.36237 《操作系统教程》（第三版）CH1应用题参考答案对某系统进行监测后表明平均每个进程在I/O阻塞之前的运行时间为T。一次进程切换的系统开销时间为S。若采用时间片长度为Q的时向片轮转法，对下列各种情况算出CPU利用率。1）Q＝∞2）Q＞T3）S＜Q＜T4＝Q＝S5＝Q接近于0答：1）Q=∞CPU利用率=T/（T+S）2）Q>TCPU利用率=T/（T+S）3）T>Q>SCPU利用率=Q/（Q+S）4)Q=SCPU利用率=50%5)Q→0CPU利用率→01有5个待运行的作业，各自预计运行时间分别是：9、6、3、5和x，采用哪种运行次序使得平均响应时间最短？答：按照最短作业优先的算法可以使平均响应时间最短。X取值不定，按照以下情况讨论：1）x≤3次序为：x，3，5，6，92）3β>0是什么算法？(2)若α<β<0是什么算法答37 《操作系统教程》（第三版）CH1应用题参考答案(1)是先进先出算法。因为在就绪队列中的进程比在CPU上运行的进程的优先数提高得快，故进程切换时，先进入就绪队列的进程优先权就越高。(2)是后进先出算法。因为在就绪队列中的进程比在CPU上运行的进程的优先权下降得快，故后进入就绪队列的进程此先进入的进程的优先权高。217有一个四道作业的操作系统，若在一段时间内先后到达6个作业，它们的提交和估计运行时间由下表给出：作业提交时间估计运行时间(分钟)18：006028：203538：252048：302558：35568：4010系统采用SJF调度算法，作业被调度进入系统后中途不会退出，但作业运行时可被更短作业抢占。(1)分别给出6个作业的执行时间序列、即开始执行时间、作业完成时间、作业周转时间。(2)计算平均作业周转时间。答：执行次序提交时间执行时间开始时间完成时间周转时间J18:00608:009:0060J58:3559:009:0530J68:40109:059:1535J38:25209:159:3570J48:30259:3510:0090J28:203510:0010:35135作业平均周转时间T=(60+30+35+70+90+135)/6=70注意，J1被调度运行后，直到它执行结束，才会引出作业调度程序工作。所以，J2至J6虽在J1执行期间进入，但未被调度，均在等待。当J1撤离后，作业调度程序工作，按SJF算法，显然有执行次序：J5、J6、J3、J4、和J2。3有一个具有两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用以优先数为基础的抢占式调度算法，在下表所示的作业序列，作业优先数即为进程优先数，优先数越小优先级越高。作业名到达时间估计运行时间优先数A10：0040分5B10：2030分3C10：3050分4D10：5020分6(1)列出所有作业进入内存时间及结束时间。(2)计算平均周转时间。答：每个作业运行将经过两个阶段：作业调度(SJF算法)和进程调度(优先数抢占式)。另外，批处理最多容纳2道作业，更多的作业将在后备队列等待。进程就绪队列作业后备队列时间(分钟)10:0010:2010:3010:5011:1012:0012:20ABACDADDC37 《操作系统教程》（第三版）CH1应用题参考答案CPU(1)10:00，作业A到达并投入运行。(2)10:20，作业B到达且优先权高于作业A，故作业B投入运行而作业A在就绪队列等待。(3)10:30，作业C到达，因内存中已有两道作业，故作业C进入作业后备队列等待。(4)10:50，作业B运行结束，作业D到达，按SJF短作业优先算法，作业D被装入内存进入就绪队列。而由于作业A的优先级高于作业D，故作业A投入运行。(5)11:10，作业A运行结束，作业C被调入内存，且作业C的优先级高于作业D，故作业C投入运行。(6)12:00，作业C运行结束，作业D投入运行。(7)12:20，作业D运行结束。作业进入内存时间运行结束时间A10:0011:10B10:2010;50C11:1012:00D10:5012:20各作业周转时间为：作业A70，作业B30，作业C90，作业D90。平均作业周转时间为70分钟。1某多道程序设计系统供用户使用的主存为100K，磁带机2台，打印机1台。采用可变分区内存管理，采用静态方式分配外围设备，忽略用户作业I/O时间。现有作业序列如下：作业号进入输入井时间运行时间主存需求量磁带需求打印机需求18:0025分钟15K1128:2010分钟30K0138:2020分钟60K1048:3020分钟20K1058:3515分钟10K11作业调度采用FCFS策略，优先分配主存低地址区且不准移动已在主存的作业，在主存中的各作业平分CPU时间。现求：(1)作业被调度的先后次序?(2)全部作业运行结束的时间?(3)作业平均周转时间为多少?(4)最大作业周转时间为多少?答：(1)作业调度选择的作业次序为：作业1、作业3、作业4、作业2和作业5。(2)全部作业运行结束的时间9:30。(3)周转时间：作业1为30分钟、作业2为55分钟、作业3为40分钟、作业4为40分钟和作业5为55分钟。(4)平均作业周转时间=44分钟。(5))最大作业周转时间为55分钟。2某多道程序设计系统采用可变分区内存管理，供用户使用的主存为200K，磁带机5台。采用静态方式分配外围设备，且不能移动在主存中的作业，忽略用户作业I/O时间。现有作业序列如下：作业号进入输入井时间运行时间主存需求量磁带需求A8:3040分钟30K3B8:5025分钟120K1C9:0035分钟100K2D9:0520分钟20K3E9:1010分钟60K137 《操作系统教程》（第三版）CH1应用题参考答案现求：(1)FIFO算法选中作业执行的次序及作业平均周转时间?(2)SJF算法选中作业执行的次序及作业平均周转时间?答：(1)FIFO算法选中作业执行的次序为：A、B、D、C和E。作业平均周转时间为63分钟。(2)SJF算法选中作业执行的次序为：A、B、D、E和C。作业平均周转时间为58分钟。CH3应用题参考答案1有三个并发进程：R负责从输入设备读入信息块，M负责对信息块加工处理；P负责打印输出信息块。今提供；1）一个缓冲区，可放置K个信息块；2）二个缓冲区，每个可放置K个信息块；试用信号量和P、V操作写出三个进程正确工作的流程。答：1）varB:array[0,k-1]ofitem;sread:semaphore:=k;smanage:semaphore:=0;swrite:semaphore:=0;rptr:integer:=0;mptr:integer:=0;wptr:integer:=0;x:itemcobeginprocessreader;beginL1:readamessageintox;P(sread);B[rptr]:=x;rptr:=(rptr+1)modk;V(smanage);gotoL1;end;processmanager;beginL2:P(smanage);x:=B[mptr];mptr:=(mptr+1)modk;managethemessageinx;B[mptr]:=x;V(swrite);gotoL2;end;processwriter;beginL3:P(swrite);x:=B[wptr];wptr:=(wptr+1)modk;V(sread);Printthemessageinx;gotoL3;end;coend2）varA,B:array[0,k-1]ofitem;sput1:semaphore:=k;sput2:semaphore:=k;sget1:semaphore:=0;sget2:semaphore:=0;put1:integer:=0;put2:integer:=0;get1:integer:=0;get2:integer:=0;37 《操作系统教程》（第三版）CH1应用题参考答案cobeginprocessreader;beginL1:readamessageintox;P(sput1);A[put1]:=x;put1:=(put1+1)modk;V(sget1);GotoL1;end;processmanager;beginL2:P(sget1);x:=A[get1];get1:=(get1+1)modk;V(sput1);Managethemessageintox;P(sput2);B[put2]:=x;put2:=(put2+1)modk;V(sget2);GotoL2;end;processwriter;beginL3:P(sget2);x:=B[get2];get2:=(get2+1)modk;V(sput2);Printthemessageinx;GotoL3;end;coend2设有n个进程共享一个互斥段，如果：(1)每次只允许一个进程进入互斥段；(2)每次最多允许m个进程（m≤n）同时进入互斥段。试问：所采用的信号量初值是否相同？信号量值的变化范围如何？答：所采用的互斥信号量初值不同。1）互斥信号量初值为1，变化范围为[-n+1，1]。当没有进程进入互斥段时，信号量值为1；当有1个进程进入互斥段但没有进程等待进入互斥段时，信号量值为0；当有1个进程进入互斥段且有一个进程等待进入互斥段时，信号量值为-1；最多可能有n-1个进程等待进入互斥段，故此时信号量的值应为-(n-1)也就是-n+1。2）互斥信号量初值为m，变化范围为[-n+m，m]。当没有进程进入互斥段时，信号量值为m；当有1个进程进入互斥段但没有进程等待进入互斥段时，信号量值为m-1；当有m个进程进入互斥段且没有一个进程等待进入互斥段时，信号量值为0；当有m个进程进入互斥段且有一个进程等待进入互斥段时，信号量值为-1；最多可能有n-m个进程等待进入互斥段，故此时信号量的值应为-(n-m)也就是-n+m。3有两个优先级相同的进程P1和P2，各自执行的操作如下，信号量S1和S2初值均为0。试问P1、P2并发执行后，x、y、z的值各为多少？P1：P2：beginbeginy:=1;x:=1;y:=y+3;x:=x+5;V(S1);P(S1);z:=y+1;x:=x+y;P(S2);V(S2);y:=z+yz:=z+x;end.end.答：现对进程语句进行编号，以方便描述。P1：P2：beginbeginy:=1;①x:=1;⑤y:=y+3;②x:=x+5;⑥37 《操作系统教程》（第三版）CH1应用题参考答案V(S1);P(S1);z:=y+1;③x:=x+y;⑦P(S2);V(S2);y:=z+y④z:=z+x;⑧end.end.①、②、⑤和⑥是不相交语句，可以任何次序交错执行，而结果是唯一的。接着无论系统如何调度进程并发执行，当执行到语句⑦时，可以得到x=10，y=4。按Bernstein条件，语句③的执行结果不受语句⑦的影响，故语句③执行后得到z=5。最后，语句④和⑧并发执行，最后结果为：语句④先执行：x=10，y=9，z=15。语句⑧先执行：x=10，y=19，z=15。2有一阅览室，读者进入时必须先在一张登记表上登记，该表为每一座位列出一个表目，包括座号、姓名，读者离开时要注销登记信息；假如阅览室共有100个座位。试用：1）信号量和P、V操作；2）管程，来实现用户进程的同步算法。答：1)使用信号量和P、V操作：varname:array[1..100]ofA;A=recordnumber:integer;name:string;endfori:=1to100do{A[i].number:=i;A[i].name:=null;}mutex,seatcount:semaphore;i:integer;mutex:=1;seatcount:=100;cobegin{processreaderi(varreadername:string)(i=1,2,…){P(seatcount);P(mutex);fori:=1to100doi++ifA[i].name=nullthenA[i].name:=readername;readergettheseatnumber=i;/*A[i].numberV(mutex)进入阅览室，座位号i，座下读书;P(mutex);A[i]name:=null;V(mutex);V(seatcount);离开阅览室;}}coend.3在一个盒子里，混装了数量相等的黑白围棋子。现在用自动分拣系统把黑子、白子分开，设分拣系统有二个进程P1和P2，其中P1拣白子；P2拣黑子。规定每个进程每次拣一子；当一个进程在拣时，不允许另一个进程去拣；当一个进程拣了一子时，必须让另一个进程去拣。试写出两进程P1和P2能并发正确执行的程序。37 《操作系统教程》（第三版）CH1应用题参考答案答：实质上是两个进程的同步问题，设信号量S1和S2分别表示可拣白子和黑子，不失一般性，若令先拣白子。varS1,S2:semaphore;S1:=1;S2:=0;cobegin{processP1beginrepeatP(S1);拣白子V(S2);untilfalse;endprocessP2beginrepeatP(S2);拣黑子V(S1);untilfalse;end}coend.2设公共汽车上，司机和售票员的活动分别如下：司机的活动：启动车辆：正常行车；到站停车。售票员的活动：关车门；售票；开车门。在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系？用信号量和P、V操作实现它们的同步。答：在汽车行驶过程中，司机活动与售票员活动之间的同步关系为：售票员关车门后，向司机发开车信号，司机接到开车信号后启动车辆，在汽车正常行驶过程中售票员售票，到站时司机停车，售票员在车停后开门让乘客上下车。因此，司机启动车辆的动作必须与售票员关车门的动作取得同步；售票员开车门的动作也必须与司机停车取得同步。应设置两个信号量：s1、s2；s1表示是否允许司机启动汽车(其初值为0)；s2表示是否允许售票员开门(其初值为0)。用P、V原语描述如下：vars1，s2：semaphore；s1=0；s2=0;cobegin{driver();busman();}coend37 《操作系统教程》（第三版）CH1应用题参考答案driver()beginwhile(1){P(s1)启动车辆；正常行车；到站停车；V(s2);}endbusman()beginwhile(1){关车门；，V(s1)售票；P(s2)开车门；上下乘客；}end2在信号量S上作P、V操作时，S的值发生变化，当S＞0、S=0、S<0时，它们的物理意义是什么？答：S的值表示它代表的物理资源的使用状态：S>0表示还有共享资源可供使用。S=0表示共享资源正被进程使用但没有进程等待使用资源。S<0表示资源已被分配完，还有进程等待使用资源。3(1)两个并发进程并发执行，其中，A、B、C、D、E是原语，试给出可能的并发执行路径。ProcessPProcessQbeginbeginA；D；B；E；C；end；end；(2)两个并发进程P1和P2并发执行，它们的程序分别如下：P1P2repeatrepeatk:=k×2;printk;k:=k+1;k:=0;untilfalse;untilfalse;若令k的初值为5，让P1先执行两个循环，然后，P1和P2又并发执行了一个循环，写出可能的打印值，指出与时间有关的错误。答：(1)共有10种交错执行的路径：A、B、C、D、E；A、B、D、E、C；A、B、D、C、E；37 《操作系统教程》（第三版）CH1应用题参考答案A、D、B、E、C；A、D、B、C、E；A、D、E、B、C；D、A、B、E、C；D、A、B、C、E；D、A、E、B、C；D、E、A、B、C。(1)把语句编号，以便于描述：P1P2repeatrepeatk:=k×2;①printk;③k:=k+1;②k:=0;④untilfalse;untilfalse;1)K的初值为5，故P1执行两个循环后，K=23。2)语句并发执行有以下情况：①、②、③、④，这时的打印值为：47③、④、①、②，这时的打印值为：23①、③、②、④，这时的打印值为：46①、③、④、②，这时的打印值为：46③、①、②、④，这时的打印值为：23③、①、④、②，这时的打印值为：23由于进程P1和P2并发执行，共享了变量K，故产生了‘结果不唯一’。2另一个经典同步问题：吸烟者问题(patil，1971)。三个吸烟者在一个房间内，还有一个香烟供应者。为了制造并抽掉香烟，每个吸烟者需要三样东西：烟草、纸和火柴，供应者有丰富货物提供。三个吸烟者中，第一个有自己的烟草，第二个有自己的纸和第三个有自己的火柴。供应者随机地将两样东西放在桌子上，允许一个吸烟者进行对健康不利的吸烟。当吸烟者完成吸烟后唤醒供应者，供应者再把两样东西放在桌子上，唤醒另一个吸烟者。试采用：(1)信号量和P、V操作，(2)管程编写他们同步工作的程序。答：(1)用信号量和P、V操作。varS,S1,S2,S3;semaphore;S:=1;S1:=S2:=S3:=0;flag1,flag2,flag3:Boolean;flag1:=flag2:=flag3:=true;cobegin{process供应者beginrepeatP(S);取两样香烟原料放桌上，由flagi标记;/*flage1、flage2、flage3代表烟草、纸、火柴ifflag2&flag3thenV(S1);/*供纸和火柴elseifflag1&flag3thenV(S2);/*供烟草和火柴elseV(S3);/*供烟草和纸untilefalse;endprocess吸烟者1beginrepeatP(S1);取原料;做香烟;37 《操作系统教程》（第三版）CH1应用题参考答案V(S);吸香烟;untilefalse;process吸烟者2beginrepeatP(S2);取原料;做香烟;V(S);吸香烟;untilefalse;process吸烟者3beginrepeatP(S3);取原料;做香烟;V(S);吸香烟;untilefalse;}coend.2系统有同类资源m个，被n个进程共享，问：当m＞n和m≤n时，每个进程最多可以请求多少个这类资源时，使系统一定不会发生死锁?答：当m≤n时，每个进程最多请求1个这类资源时，系统一定不会发生死锁。当m>n时，如果m/n不整除，每个进程最多可以请求”商+1”个这类资源，否则为”商”个资源，使系统一定不会发生死锁?3N个进程共享M个资源，每个进程一次只能申请/释放一个资源，每个进程最多需要M个资源，所有进程总共的资源需求少于M+N个，证明该系统此时不会产生死锁。答：设max（i）表示第i个进程的最大资源需求量，need(i)表示第i个进程还需要的资源量，alloc(i)表示第i个进程已分配的资源量。由题中所给条件可知：max(1)+┅+max(n)=(need(1)+┅+need(n))+((alloc(1)+┅+alloc(n))2)<1,25>3)<1,14>4)<2,200>5)<3,500>6)<4,100>。答：1)6802)9153)9044)越界5)17506)越界。28请页式存储管理中，进程访问地址序列为：10,11,104,170,73,305,180,240,244,445,467，366。试问1)如果页面大小为100，给出页面访问序列。2)进程若分得3个页框，采用FIFO和LRU替换算法，求缺页中断率?答：1)页面访问序列为1，1，2，2，1，4，2，3，3，5，5，4。2)FIFO为5次，缺页中断率为5/12=41.6%。LRU为6次，缺页中断率为6/12=50%。LRU反比FIFO缺页中断率高。37 《操作系统教程》（第三版）CH1应用题参考答案29假设计算机有2M内存，其中，操作系统占用512K，每个用户程序也使用512K内存。如果所有程序都有70%的I/O等待时间，那么，再增加1M内存，吞吐率增加多少?答：由题意可知，内存中可以存放3个用户进程，而CPU的利用率为：1-(70%)3=1-(0.7)3=65.7%。再增加1M内存，可增加2个用户进程，这时CPU的利用率为：1-(70%)5=1-(0.7)5=83.2%。故再增加1M内存，吞吐率增加了：83.2%÷65.7%-100%=27%。30一个计算机系统有足够的内存空间存放4道程序，这些程序有一半时间在空闲等待I/O操作。问多大比例的CPU时间被浪费掉了?答：(50%)4=(1/2)4=1/16。31如果一条指令平均需1微秒，处理一个缺页中断另需n微秒，给出当缺页中断每k条指令发生一次时，指令的实际执行时间。答：(1+n/k)微秒。32一台计算机的内存空间为1024个页面，页表放在内存中，从页表中读一个字的开销是500ns。为了减少开销，使用了有32个字的快表，查找速度为100ns。要把平均开销降到200ns需要的快表命中率是多少?答：设快表命中率是x，则内存命中率为1-x。于是：500(1-x)+100x=200,解方程得x=75%。CH5应用题参考答案1旋转型设备上信息的优化分布能减少为若干个I/O服务的总时间。设磁鼓上分为20个区，每区存放一个记录，磁鼓旋转一周需20毫秒，读出每个记录平均需用1毫秒，读出后经2毫秒处理，再继续处理下一个记录。在不知当前磁鼓位置的情况下：（1）顺序存放记录1、……，记录20时，试计算读出并处理20个记录的总时间；（2）给出优先分布20个记录的一种方案，使得所花的总处理时间减少，且计算出这个方案所花的总时间。答：定位第1个记录需10ms。读出第1个记录，处理花2ms，这时已到了第4个记录，再转过18个记录(花18ms)才能找到记录2，所以，读出并处理20个记录的总时间：10+3+(1+2+18)×19=13+21×19=412ms如果给出优先分布20个记录的方案为：1，8，15，2，9，16，3，10，17，4，11，18，5，12，19，6，13，20，7，14。当读出第1个记录，花2ms处理后，恰好就可以处理记录2，省去了寻找下一个记录的时间，读出并处理20个记录的总时间：10+3+3×19=13+247=260ms2现有如下请求队列：8，18，27，129，110，186，78，147，41，10，64，12；试用查找时间最短优先算法计算处理所有请求移动的总柱面数。假设磁头当前位置下在磁道100。答：处理次序为：100-110-129-147-186-78-64-41-27-18-12-10-8。移动的总柱面数：264。3上题中，分别按升序和降序移动，讨论电梯调度算法计算处理所有存取请求移动的总柱面数。答：升序移动次序为：100-110-129-147-186-78-64-41-27-18-12-10-8。移动的总柱面数：264。降序移动次序为：100-78-64-41-27-18-12-10-8-110-129-147-186。移动的总柱面数：270。4某文件为连接文件，由5个逻辑记录组成，每个逻辑记录的大小与磁盘块大小相等，均为512字节，并依次存放在50、121、75、80、63号磁盘块上。现要读出文件的1569字节，问访问哪一个磁盘块?答：80号磁盘块5对磁盘存在下面五个请求：37 《操作系统教程》（第三版）CH1应用题参考答案请求柱面号磁头号扇区号172827253712430535366假如当前磁头位于1号柱面。试分析对这五个请求如何调度，可使磁盘的旋转圈数为最少？答：使磁盘的旋转圈数为最少的调度次序为：5、3、2、1、和4。1有一具有40个磁道的盘面，编号为0~39，当磁头位于第11磁道时，顺序来到如下磁道请求：磁道号：1、36、16、34、9、12；试用1）先来先服务算法FCFS、2）最短查找时间优先算法SSTF、3）扫描算法SCAN等三种磁盘驱动调度算法，计算出它们各自要来回穿越多少磁道？答：1)FCFS为111。2)SSTF为61。3)SCAN为60(先扫地址大的请求)，为45(先扫地址小的请求)。2假定磁盘有200个柱面，编号0~199，当前存取臂的位置在143号柱面上，并刚刚完成了125号柱面的服务请求，如果请求队列的先后顺序是：86，147，91，177，94，150，102，175，130；试问：为完成上述请求，下列算法存取臂移动的总量是多少？并算出存取臂移动的顺序。(1)先来先服务算法FCFS；(2)最短查找时间优先算法SSTF；(3)扫描算法SCAN。(4)电梯调度。答：(1)先来先服务算法FCFS为565，依次为143-86-147-91-177-94-150-102-175-130。(2)最短查找时间优先算法SSTF为162，依次为143-147-150-130-102-94-91-86-175-177。(3)扫描算法SCAN为169，依次为143-147-150-175-177-199-130-102-94-91-86。(4)电梯调度为125(先向地址大的方向)，依次为143-147-150-175-177-102-94-91-86。为148(先向地址小的方向)依次为143-130-102-94-91-86-147-150-175-177。3除FCFS外，所有磁盘调度算法都不公平，如造成有些请求饥饿，试分析：(1)为什么不公平？(2)提出一种公平性调度算法。(3)为什么公平性在分时系统中是一个很重要的指标？答：(1)对位于当前柱面的新请求，只要一到达就可得到服务，但对其他柱面的服务则不然。如SSTF算法，一个离当前柱面远的请求，可能其后不断有离当前柱面近的请求到达而得不到服务(饥饿)。(2)可划定一个时间界限，把这段时间内尚未得到服务的请求强制移到队列首部，并标记任何新请求不能插到这些请求前。对于SSTF算法来说，可以重新排列这些老请求，以优先处理。(3)可避免分时进程等待时间过长而拉长响应时间。4若磁头的当前位置为100柱面，磁头正向磁道号减小方向移动。现有一磁盘读写请求队列，柱面号依次为：190，10，160，80，90，125，30，20，29，140，25。若采用最短寻道时间优先和电梯调度算法，试计算出各种算法的移臂经过的柱面数？答：采用SSTF处理次序为：100-90-80-125-140-160-190-30-29-25-20-10，总柱面数为：310。采用电梯调度处理次序为：100-90-80-30-29-25-20-10-125-140-160-190，总柱面数为：270。5若磁头的当前位置为100柱面，磁头正向磁道号增加方向移动。现有一磁盘读写请求队列，柱面号依次为：23，376，205，132，19，61，190，398，29，4，18，40。若采用先来先服务、最短寻道时间优先和扫描算法，试计算出各种算法的移臂经过的柱面数？答：采用先来先服务处理次序为：100-23-376-205-132-19-61-190-398-29-4-18-40，总柱面数为：1596。采用SSTF处理次序为：100-132-190-205-61-40-29-23-19-18-4-376-398，总柱面数为：700。37 《操作系统教程》（第三版）CH1应用题参考答案采用SCAN处理次序为：100-132-190-205-376-398-61-40-29-23-19-18-4，总柱面数为：692。CH6应用题参考答案1.磁带卷上记录了若干文件，假定当前磁头停在第j个文件的文件头标前，现要按名读出文件i，试给出读出文件i的步骤。答：由于磁带卷上的文件用“带标”隔开，每个文件的文件头标前后都使用了三个带标。文文件件…*头*文件体*尾*标标文文件件…*头*文件体*尾*标标…正常情况磁头应停在文件头标的前面，所以，只要计算带标的个数，就可找到所要文件。1)当i≧j时，要正走磁带，步1组织通道程序正走磁带，走过“带标”个数为3×(i-j)个。步2组织通道程序读文件i的文件头标。步3根据文件i的文件头标信息，组织读文件信息。2)当i400时，空白文件目录大于位示图。2.某磁盘共有100个柱面，每个柱面有8个磁头，每个盘面分4个扇区。若逻辑记录与扇区等长，柱面、磁道、扇区均从0起编号。现用16位的200个字(0-199)来组成位示图来管理盘空间。现问：(1)位示图第15个字的第7位为0而准备分配给某一记录，该块的柱面号、磁道号、扇区号是多少?(2)现回收第56柱面第6磁道第3扇区，这时位示图的第几个字的第几位应清0?答：(1)位示图第15个字的第7位对应的块号=15×16(字长)+7=247，而块号247对应的：柱面号=247/(8×4)=7(从0编号，向下取整)磁头号=(247MOD32)/4=5扇区号=247MOD32MOD4=3(2)块号=柱面号×柱面扇区数+磁道号×盘扇区+盘扇区=56×(8×4)+6×4+3=1819字号=1819/16=113位号=1819MOD16=11所以，回收第56柱面第6磁道第3扇区时，位示图的第113字的第11位应清0。3.如果一个索引节点为128B，指针长4B，状态信息占用68B，而每块大小为8KB。问在索引节点中有多大空间给指针？使用直接、一次间接、二次间接和三次间接指针分别可表示多大的文件？答：由于索引节点为128B，而状态信息占用68B，故索引节点中用于磁盘指针的空间大小为：128-68=60字节。一次间接、二次间接和三次间接指针占用三个指针项，因而直接指针项数为：60/4-3=12个。每块大小为8KB。所以，直接指针时：12×8192=98304B。一次间接指针时：8192/4=2048，即一个磁盘块可装2048个盘块指针，2048×8192=16MB。二次间接指针时：2048×2048=4M，即二次间接可装4M个盘块指针，4M×8192=32GB。三次间接指针时：2048×2048×2048=8G，即三次间接可装8G个盘块指针，8G×8192=16TB。4.设一个文件由100个物理块组成，对于连续文件、连接文件和索引文件，分别计算执行下列操作时的启动磁盘I/O次数(假如头指针和索引表均在内存中)：(1)把一块加在文件的开头；(2)把一块加在文件的中间(第51块)；(3)把一块加在文件的末尾；(4)从文件的开头删去一块；(5)从文件的中间(第51块)删去一块；(6)从文件的未尾删去一块。答：操作名称连续文件链接文件索引文件加一块到文件开头20111加一块到文件中间101511加一块到文件末尾121从文件头删去一块011删去文件中间块98521从文件尾删去一块0100137 《操作系统教程》（第三版）CH1应用题参考答案37'