2016-2017-1_计算机操作系统课后题.doc

操作系统课后题：第一章： 一、3、15、19、23 二、2、52、答：画出两道程序并发执行图如下：处理器输入机打印机程序A程序BA计算B计算计算计算时间(ms)0 50 100 150 180 200 250 300打印计算打印输入计算A打印A打印B输入A计算B计算一(1) 两道程序运行期间，CPU存在空闲等待，时间为100至150ms之间(见图中有色部分)。(2) 程序A无等待现象，但程序B有等待。程序B有等待时间段为180ms至200ms间(见图中有色部分)。5、答：画出三个作业并行工作图如下(图中着色部分为作业等待时间)：CPUI1I2Job1Job2Job3时间(ms)CPU CPU0 10 20 30 40 50 60 70 80 90 I1 I1CPUCPU I2 I2CPU I1CPU Job1 Job2 Job3Job2Job1Job2Job3Job1 Job2 Job1Job3(1) Job1从投入到运行完成需80ms，Job2从投入到运行完成需90ms，Job3从投入到运行完成需90ms。(2) CPU空闲时间段为：60ms至70ms，80ms至90ms。所以CPU利用率为(90-20)/90=77.78%。(3) 设备I1空闲时间段为：20ms至40ms，故I1的利用率为(90-20)/90=77.78%。设备I2空闲时间段为：30ms至50ms，故I2的利用率为(90-20)/90=77.78%。第二章： 一、18、20、26、38、48 二、5、12、16、20、25、285、答：采用短作业优先算法调度时，三个作业的总周转时间为： T1=a+(a+b)+(a+b+c)=3a+2b+c 若不按短作业优先算法调度，不失一般性，设调度次序为：J2、J1、J3。则三个作业的总周转时间为：T2=b+(b+a)+(b+a+c)=3b+2a+c 令-式得到： T2-T1=b-a0可见，采用短作业优先算法调度才能获得最小平均作业周转时间。12、答：(1)FCFS调度算法执行次序 执行时间 等待时间 周转时间 带权周转时间 A 10 0 10 1 B 6 10 16 2.66 C 2 16 18 9 D 4 18 22 5.5 E 8 22 30 3.75作业平均周转时间 T=(10+16+18+22+30)/5=19.2作业平均带权周转时间 W=(1+2.66+9+5.5+3.75)/5=4.38(2)优先级调度算法执行次序 执行时间 等待时间 周转时间 带权周转时间 B 6 0 6 1 E 8 6 14 1.75 A 10 14 24 2.4 C 2 24 26 13 D 4 26 30 7.5作业平均周转时间 T=(6+14+24+26+30)/5=20作业平均带权周转时间 W=(1+1.75+2.4+13+7.5)/5=5.13(3)时间片轮转法(每个作业获得相同的2分钟长的时间片)按次序A B C D E A B D E A B E A E A轮转执行。 作业 执行时间 等待时间 周转时间 带权周转时间 A 10 20 30 3 B 6 16 22 3.66 C 2 4 6 3 D 4 12 16 4 E 8 20 28 3.5作业平均周转时间 T=(30+22+6+16+28)/5=20.4作业平均带权周转时间 W=(3+3.66+3+4+3.5)/5=3.4316、答： FCFS SJF HRRF作业 开始 完成 周转 开始 完成 周转 开始 完成 周转时间 时间 时间 时间 时间 时间 时间 时间 时间1 8.00 10：00 2.00 8:00 10.00 120 8:00 10.00 1202 10.00 10：50 2.00 10:30 11.20 150 10:10 11.00 1303 10.50 11：00 2.00 10:00 10:10 70 10:00 10:10 704 11.00 11：20 1.5 10:10 10:30 40 11:00 11.20 90平均周 T=112.5分 T=95分 T=102.5分转时间=带权平均 W=4.975 W=3.25 W=3.775周转时间=20、答：执行次序 提交时间 执行时间 开始时间 完成时间 周转时间 J1 8:00 60 8:00 9:00 60 J5 8:35 5 9:00 9:05 30 J6 8:40 10 9:05 9:15 35 J3 8:25 20 9:15 9:35 70 J4 8:30 25 9:35 10:00 90 J2 8:20 35 10:00 10:35 135作业平均周转时间T=(60+30+35+70+90+135)/6=70注意，J1被调度运行后，直到它执行结束，才会引出作业调度程序工作。所以，J2至J6虽在J1执行期间进入，但未被调度，均在等待。当J1撤离后，作业调度程序工作，按SJF算法，显然有执行次序：J5、J6、J3、J4、和J2。25、答：每个作业运行将经过两个阶段：作业调度(SJF算法)和进程调度(优先数抢占式)。另外，批处理最多容纳2道作业，更多的作业将在后备队列等待。进程就绪队列作业后备队列时间(分钟) 10:00 10:20 10:30 10:50 11:10 12:00 12:20A B A C DA D D C 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运行结束。作业 进入内存时间 运行结束时间 A 10:00 11:10 B 10:20 10;50 C 11:10 12:00 D 10:50 12:20各作业周转时间为：作业A 70，作业B 30，作业C 90，作业D 90。平均作业周转时间为70分钟。28、答：(1) FIFO算法选中作业执行的次序为：A、B、D、C和E。作业平均周转时间为63分钟。(2) SJF算法选中作业执行的次序为：A、B、D、E和C。作业平均周转时间为58分钟。第三章： 一、3、9、24、25、323、解释并发性与并行性答：计算机操作系统中把并行性和并发性明显区分开，主要是从微观的角度来说的，具体是指进程的并行性（多处理机的情况下，多个进程同时运行）和并发性（单处理机的情况下，多个进程在同一时间间隔运行的）。并行性是指硬件的并行性，两个或多个事件在同一时刻发生。并发性是指进程的并发性，两个或多个事件在同一时间段内发生。24、死锁：所谓死锁是指在多道程序系统中，一组进程中的每一个进程都无限期等待被该组进程中的另一个进程所占有且永远不会释放的资源。如：假如双方都拥有部分资源（P1拥有A，P2拥有B，且A，B均只有一个），但这时P1还需要B，P2还需要A，于是P1与P2都会处在无限等待状态，发生了死锁。饥饿：操作系统在一个分配资源时，当多个进程同时申请某类资源时，由分配策略确定资源分配给进程的次序。当资源分配策略是不公平的(unfair)的情况下，即不能保证等待时间上界的存在，即使系统没有发生死锁，某些进程也可能会长时间等待。当等待时间给进程推进和响应带来明显影响时，称发生了进程饥饿(starvation)。如：考虑一台打印机分配的例子，当有多个进程需要打印文件时，系统按照短文件优先的策略排序，该策略具有平均等待时间短的优点，似乎非常合理，但当短文件打印任务源源不断时，长文件的打印任务将被无限期地推迟，导致饥饿32、当N取不大于3的正整数时，系统没有死锁的危险。因为当N=1或2时，最多需要6台磁带机，系统不会发生死锁。当N=3时，最坏情况是3个进程都需要3个磁带机，且每个进程都已拥有2个磁带机，但此时系统还有2台未分配的磁带，能满足其中两个进程的资源请求，使进程顺利推进后再释放资源，此时另外1个进程因为得到被释放的磁带机而能够获得足够的磁带机，也可以顺利执行，不会发生死锁。 二、5、6、16、23、365、答：1) 使用信号量和P、V操作：var name: array1.100 of A;A=record number:integer; name:string;endfor i:=1 to 100 do Ai.number:=i; A:=null;mutex,seatcount:semaphore;i:integer;mutex:=1;seatcount:=100;cobeginprocess readeri(var readername:string)(i=1,2,) P(seatcount); P(mutex);for i:=1 to 100 do i+ if A=null then A:=readername; reader get the seat number =i; /*Ai.number V(mutex) 进入阅览室，座位号i，座下读书;P(mutex); Ai name:=null; V(mutex); V(seatcount); 离开阅览室; coend.6、答：实质上是两个进程的同步问题，设信号量S1和S2分别表示可拣白子和黑子，不失一般性，若令先拣白子。var S1,S2:semaphore;S1:=1;S2:=0; cobegin process P1 begin repeat P(S1); 拣白子 V(S2); until false; endprocess P2 begin repeat P(S2); 拣黑子 V(S1); until false; endcoend.16、答：(1)用信号量和P、V操作。var S,S1,S2,S3;semaphore; S:=1;S1:=S2:=S3:=0; flag1,flag2,flag3:Boolean; flag1:=flag2:=flag3:=true;cobegin process 供应者begin repeat P(S); 取两样香烟原料放桌上，由flagi标记; /*flage1、flage2、flage3代表烟草、纸、火柴 if flag2&flag3 then V(S1); /*供纸和火柴 else if flag1&flag3 then V(S2); /*供烟草和火柴 else V(S3); /*供烟草和纸 untile false; end process 吸烟者1begin repeat P(S1); 取原料; 做香烟; V(S); 吸香烟; untile false;process 吸烟者2begin repeat P(S2); 取原料; 做香烟; V(S); 吸香烟; untile false;process 吸烟者3begin repeat P(S3); 取原料; 做香烟; V(S); 吸香烟; untile false;coend.23、答：(1) P1，P2，P3，P4的Cki-Aki分别为：(2，2，2)、(1，0，2)、(1，0，3)、(4，2，0)(1) 系统处于安全状态，存在安全序：P2，P1，P3，P4(2) 可以分配，存在安全序列：P2，P1，P3，P4。(3) 不可以分配。36、答：当两个进程都执行完第一步(都占用R1) 时，系统进入不安全状态。这时无论哪个进程执行完第二步，死锁都会发生。可能到达的死锁点：进程P1占有一个R1和一个R2，而进程P2占有一个R1。或者相反。这时己形成死锁。进程-资源图为：P1P2P1P2第四章： 一、1、4、5、9、10、11、1818、答：虚拟存储器是指在具有层次结构存储器的计算机系统中，自动实现部分装入和部分替换功能，能从逻辑上为用户提供一个比物理内存容量大得多的、可寻址的“内存储器”。是一种具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。虚拟存储器的实现方式有两种：请求分页系统和请求分段系统。请求分页系统允许只装入少数页面的程序(及数据)，便启动运行，以后，再通过调页功能及页面置换功能，陆续地把即将要运行的页面调入内存，同时把暂不运行的页面换出到外存上；请求分段系统允许只装入少数段(而非所有的段)的用户程序和数据，即可启动运行。以后再通过调段功能和段的置换功能将暂不运行的段调出，同时调入即将运行的段。 二、3、6、13、15、20、29、303、答：(1) 作业的物理块数为3块，使用FIFO为9次，9/12=75%。使用LRU为7次，7/12=58%。使用OPT为6次，6/12=50%。作业的物理块数为4块，使用FIFO为6次，6/12=50%。使用LRU为6次，6/12=50%。使用OPT为5次，5/12=42%。 (2) 作业的物理块数为3块，使用FIFO为9次，9/12=75%。使用LRU为10次，10/12=83%。使用OPT为7次，7/12=58%。作业的物理块数为4块，使用FIFO为10次，10/12=83%。使用LRU为8次，8/12=66%。使用OPT为6次，6/12=50%。其中，出现了Belady现象，增加分给作业的内存块数，反使缺页中断率上升。6、答：由于32-9-11=12，所以，页面大小为4KB，页面的个数为220 个。13、答：首次适应、最坏适应算法处理这个作业序列可以满足分配，最佳适应算法不行。因为后者会分割出无法使用的碎片，浪费内存，从而，不能满足所有作业的内存需求。15、答：因为逻辑地址长度为16位，而页面大小为4096字节，所以，前面的4位表示页号。把2F6AH转换成二进制为：0010 1111 0110 1010，可知页号为2。故放在14号物理块中，写成十六进制为：EF6AH。20、答：虚地址0AC5H对应的物理地址为：12C5H。而执行虚地址1AC5H会发现页表中尚未有分配的页框而发生缺页中断，由系统另行分配页框。29、答：1)680 2)915 3)904 4)越界 5)1750 6) 越界。30、答：1) 1) 页面访问序列为0，0，1，1，0，3，1，2，2，4，4，3。 2)FIFO为5次，缺页中断率为5/12=41.6%。LRU为6次，缺页中断率为6/12=50%。LRU反比FIFO缺页中断率高。第五章： 一、2、12、21、26、282、（1）轮询方式：（2）中断驱动I/O方式（3）DMA方式：（4）通道方式12、答P26521、答：虚拟设备：为了提高独占设备的利用率，采用SPOOLING技术，用可共享的设备模拟独占设备，使独占设备成为共享设备，使每个作业感到自己分到了速度极高的独占设备。这种模拟的独占设备称为虚拟设备。26 答：在联机的条件下，进行两个方向的操作，在数据输入时，将数据从输入设备传送到磁盘或磁带（块设备），然后把这些块设备与主机相连；反过来，在数据输出时，将输出数据传送到磁盘或磁带上，再从磁盘或磁带传送到输出设备。这样，可以将一台独占的物理设备虚拟为并行使用的多台逻辑设备，从而使该物理设备被多个进程共享。28、答：设备独立性：用户不指定物理设备，而是指定逻辑设备，使得用户作业和物理设备之间分离开来，再通过其他途径建立逻辑设备和物理设备之间的映射，设备的这种特性就是“设备无关性”。 好处：应用程序与具体物理设备无关，系统增减或变更设备时对源程序不必加以修改；易于应对I/O设备故障，提高系统可靠性；增加设备分配的灵活性，更有效地利用逻辑设备资源，实现多道程序设计。 二、1、2、7、161、答：定位第1个记录需10ms。读出第1个记录，处理花2ms，这时已到了第4个记录，再转过18个记录(花18ms)才能找到记录2，所以，读出并处理20个记录的总时间：10+3+(1+2+18)19=13+2119=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+319=13+247=260ms2、答：处理次序为：100-110-129-147-186-78-64-41-27-18-12-10-8。移动的总柱面数：264。7、答：(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。16答： 第六章：