2022年《操作系统教程》孙仲秀第四版习题及解答 .pdf

习题一（操作系统概论）二应用题1 有一台计算机，具有1MB 内存，操作系统占用200KB，每个进程各占用200KB 。如果用户进程等待I/O 的时间为80%，若增加 1MB 内存，则CPU 的利用率提高多少？答:设每个进程等待I/O 的百分比为P,则 n 个进程同时等待I/O 的概率是nP,当 n 个进程同时等待 I/O 期间 CPU 是空闲的 ,故 CPU 的利用率为1-nP.由题意可知 ,除去操作系统,内存还能容纳4 个用户进程 ,由于每个用户进程等待I/O 的时间为80%,故: CPU 利用率 =1-4%)80(=0.59 若再增加1MB 内存 ,系统中可同时运行9 个用户进程 ,此时 : CPU 利用率 =1-9%)80(=0.87 故增加 1MB 内存使 CPU 的利用率提高了47%: 87%/59%=147% 147%-100%=47% 2 一个计算机系统，有一台输入机和一台打印机,现有两道程序投入运行,且程序 A 先开始做 ,程序 B 后开始运行 .程序 A 的运行轨迹为 :计算 50ms,打印 100ms,再计算 50 ms,打印 100 ms,结束 .程序 B 的运行轨迹为 :计算 50 ms,输入 80 ms,再计算 100 ms,结束 .试说明(1)两道程序运行时,CPU 有无空闲等待?若有 ,在哪段时间内等待?为什么会等待?(2)程序 A,B 有无等待CPU 的情况 ?若有 ,指出发生等待的时刻. 答:(1)两道程序运行期间,CPU 存在空闲等待 ,时间为 100 至 150ms 之间(2)程序 A 无等待现象 ,但程序 B 有等待 .程序 B 有等待时间段为180ms 至 200ms 间. 3.设有三道程序,按 A,B,C 优先次序运行 ,其内部计算和I/O 操作时间由图给出. A B C 11C=30 ms 21C=60 ms 31C=20 m12I=40 ms 22I=30 ms 32I=40 ms 13C=10 ms 23C=10 ms 33C=20 ms 试画出按多道运行的时间关系图(忽略调度执行时间).完成三道程序共华多少时间?比单道名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 12 页 - - - - - - - - - 运行节省了多少时间?若处理器调度程序每次进行程序转换花时1 ms,试画出各程序状态转换的时间关系图. 答:(图略 ) 1)忽略调度执行时间,多道运行方式 (抢占式 ): 抢占式共用去190 ms,单道完成时间需要260 ms,节省 70 ms 忽略调度执行时间,多道运行方式 (非抢占式 ): 非抢占式共用去180 ms,单道完成时间需要260 ms,节省 80 ms 2)(略) 7. 单道时 CPU 的利用率为： （19080）/19057.9多道时 CPU 的利用率为： （14030）/140=78.6% 11. 应时钟中断频率为60HZ ， 所以时钟频率为： 1/6050/3 ms. 在每个时钟周期CPU 花 2ms执行中断任务。所以CPU 用于时钟中断处理的时间比率为：2/(50/3)=12% 习题二（处理器管理）二应用题1 下列指令中哪些只能在核心态运行？（1）读时钟日期； （2）访管指令； （3）设时钟日期； （4）加载特殊寄存器； （6）改变存储器映象图； （7）启动 I/O 指令。答: (3),(4),(5),(6),(7). 8对某系统进行监测后表明平均每个进程在I/O 阻塞之前的运行时间为T。一次进程切换的系统开销时间为S。若采用时间片长度为Q 的时间片轮转法，对下列各种情况算出CPU 利用率。1）Q=无穷大2）QT 3)SQT CPU 利用率 =T/(T+S) 3)SQ0 9.按照最短作业优先的算法可以使平均相应时间最短。X 的取值不定， 按照以下情况讨论：1)x=3 次序为x , 3 , 5 , 6 , 9 2)3x=5 次序为3 , x , 5 , 6 , 9 3)5x=6 次序为3 , 5 , x , 6 , 9 4)6x=9 次序为3 , 5 , 6 , x , 9 5)9x 次序为3 , 5 , 6 , 9 , x 11有 5 个批处理作业A 到 E 均已到达计算中心，其运行时间分别为10，6，2， 4 和 8分钟；各自的优先级分别规定为3，5，2，1 和 4，这里5 为最高级。若不考虑系统切换开销，计算出平均作业周转时间。（1）按 FCFS（按 A，B，C，D，E） ； （2）优先级调度算法， （3）时间片轮转法。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 12 页 - - - - - - - - - 答: (1) FCFS 调度算法执行次序执行时间等待时间周转时间带权周转时间A B C D E 10 6 2 4 8 0 10 16 18 22 10 16 18 22 30 1 2.66 9 5.5 3.75 3 5 2 1 4 作业平均周转时间作业平均带权周转时间T=(10+16+18+22+30)/5=19.2 W=(1+2.66+9+5.5+3.75)/5=4.38 (2) 优先级调度算法执行次序执行时间等待时间周转时间带权周转时间A B C D E 6 8 10 2 4 0 6 14 24 26 6 14 24 26 30 1 1.75 2.4 13 7.5 作业平均周转时间作业平均带权周转时间T=(6+14+24+26+30)/5=20 W=(1+1.75+2.4+13+7.5)/5=5.13 (3) 时间片轮转法按次序 ABCDEABDEABEAEA轮转执行 . 作业执行时间等待时间周转时间带权周转时间A B C D E 10 6 2 4 8 20 16 4 12 20 30 22 6 16 28 3 3.66 3 4 3. 5 作业平均周转时间作业平均带权周转时间T=(30+22+6+16+28)/5=20.4 W=(3+3.66+3+4+3.5)/5=3.43 13请你设计一种先进的计算机体系结构，它使用硬件而不是中断来完成进程切换，则CPU 需要哪些信息？请描述用硬件完成进程切换的工作过程。答:该计算机有一个专用硬件寄存器,它始终存放指向当前运行进程的PCB 的指针 .当系统中发生了一个事件,如 I/O 结束事件 ,CPU 便可把运行进程的上下文保存到专用硬件寄存器指针指向的PCB 中保护起来 ,然后 ,CPU 转向中断向量表,找到设备中断处理程序入口,让专用硬件寄存器指针指向(设备 )中断服务例程 ,于是 ,便可启动中断服务例程工作. 15单道批处理系统中，下列三个作业采用先来先服务调试算法和最高响应比优先算法进行调试，哪一种算法性能较好，请完成下表：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 12 页 - - - - - - - - - 作业提 交 时间运 行 时间开 始 时间完 成 时间周 转 时间带 权 周 转 时间1 2 3 10：00 10：10 10：25 2：00 1：00 0：25 平均作业周转时间= 平均作业带权周转时间W= 答: FIFO 作业提 交 时间运 行 时间开 始 时间完 成 时间周 转 时间带 权 周 转 时间1 2 3 10：00 10：10 10：25 2：00 1：00 0：25 10:00 12:00 13:00 12:00 13:00 13:25 2 2:50 3 120/120 145/60 180/25 平均作业周转时间=2.61 平均作业带权周转时间W=3.54 HRN 作业提 交 时间运 行 时间开 始 时间完 成 时间周 转 时间带 权 周 转 时间1 2 3 10：00 10：10 10：25 2：00 1：00 0：25 10:00 12:25 12:00 12:00 13:25 12:25 2 3:15 2 120/120 195/60 120/25 平均作业周转时间=2.41 平均作业带权周转时间W=3.02 可见 HRRF 比 FIFO 要好 . 19有一个具有两道作业的批处理系统，作业调度采用短作业优先的调试算法，进程调度采用优先数为基础的抢占式调度算法，在下表所示的作业序列，作业优先数即为进程优先数，优先数越小优先级越高。作业名到达时间估计运行时间优先数A B C D 10：00 10：20 10：30 10：50 40 分30 分50 分20 分5 3 4 6 答: 每个作业运行将经过两个阶段:作业调度 (SJF 算法 )和进程调度 (优先数抢占式).另外 ,批名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 12 页 - - - - - - - - - 处理最多容纳2 道作业 ,更多的作业将在后备队列等待. 作业进入内存时间差运行结束时间A B C D 10:00 10:20 11:10 10:50 11:10 10:50 12:00 12:20 各作业周转时间为:作业 A 70, 作业 B 30, 作业 C 90, 作业 D 90.平均作业周转时间为70 分钟24.实时任务可调度应满足：35/50+20/100+10/300+x/2501 x250(1-28/30)=250*0.067=16.75ms 习题三（并发进程）二应用题1 有三个并发进程：R 负责从输入设备读入信息块，M 负责对信息块加工处理；P 负责打印输出信息块。今提供：1） 一个缓冲区，可放置K 个信息块；2） 二个缓冲区，每个可放置K 个信息块；试用信号量和P， V 操作写出三个进程正确工作的流程。答: 1)var B:array0,k-1 of item; sread:semaphore:=k; smanage:semaphore:=0; swrite:semaphore:=0; rptr:integer:=0; mptr:inerger:=0; wptr:inerger:=0; x:item cobegin process reader; begin L1: reader a message into x; P(sread); Brptr:=x; rptr=(rptr +1) mod k; V(smanage); Goto L1; End; process manager; begin L2: P(smanage); x=Bmptr; mptr=(mptr+1) mod k; manager the message in x; Bmptr:=x V(swrite) Goto L2; End; Process writer; Begin L3:P(swrite); x=Bwptr; wptr=(wptr+1) mod k; V(stread); Print the message in x; Goto L3; End; Coend 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 12 页 - - - - - - - - - 2)var A,B:array0,k-1 of intm; sput1:semaphore:=k; sput2:semaphore:=k; sget1:semaphore:=0; sget2:semaphore:=0; put1:integer:=0; put2:integer:=0; get1:integer:=0; get2:integer:=0; cobegin process reader; begin L1: read a message into x; P(sput1); Aput1=x; Put1:=( put1+1) mod k; V(sget1); Goto L1; End; Process manager; Begin L2:P(sget1); X:=Aget1; Get1:=(get1+1) mod k; V(sput1) Manage the message into x; P(sput2); Bput2:=x Put2:=(put2+1) mod k; V(sget2); Goto L2; End; Process writer; Begin L3:P(sget2); X:=Bget2; Get2:=(get2+1) mod k; V(sput2); Print the message in x; Goto L3; End; coend 3.有两个优先级相同的进程P1 和 P2，各自执行的操作如下，信号量 S1 和 S2 初值均为 0。试问 P1,P2 并发执行后， x,y,z 的值各为多少？P1: P2: begin begin y:=1; 1 x:=1; 5 y:=y+3; 2 x:=x+5; 6 V(S1); P(S1); z:=y+1; 3 x:=x+y; 7 P(S2); V(S2); y:=z+y; 4 z:=z+x; 8 end. end. 1,2,5 和 6 是不相交语句，可以任何次序交错执行，而结果是唯一的。接着无论系统如何调度进程并发执行，当执行到语句7 时，可以得到x=10，y=4。按 Bernstein 条件，语句3的执行结果不受语句7 的影响，故语句3 执行后得到z=25。最后，语句4 和 8并发执行，最后结果为：答语句 4 先执行:x=10,y=9,z=15. 语句 8 先执行x=10，y=19， z=15 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 12 页 - - - - - - - - - 5.在一个盒子里， 混装了数量相等的黑白围棋子。现在用自动分拣系统把黑子，白子分开，设分拣系统有二个进程P1 和 P2，其中 P1拣白子， P2拣黑子。 规定每个进程每次拣一子；当一个进程在拣时，不允许另一个进程去拣；当一个进程拣了一子时，必须让另一个进程去拣。试写出两个进程P1 和 P2 能并发正确执行的程序。答:实质上是两个进程的同步问题,设信号量S1和 S2分别表示可拣白子和黑子,不失一般性 ,若令先拣白子 . Var S1,S2:semaphore; S1:=1,S2:=0; Cogegin process P1 begin repeat P(S1); 拣白子V(S2); Until false; End Process p2 Begin Repeat P(S2); 拣黑子 ; V(S1); Until false; End coend. 17吸烟者问题答：用信号量和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） ；取两样香烟原料放桌上，由flag i 标记； flag1/flag2/flag3分别代表烟草，纸、火名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 12 页 - - - - - - - - - If flag2 & flag3 then v(s1) ;、供应纸和火Else if flag1 & flag3 then v(s2);、供应草和火Else v(s3); Untile false ; end Process 吸烟者1 Begin Repeat P(s1) 取原料，做香烟；（ S）; 吸香烟；Untile false; Process 吸烟者2 Begin Repeat P(s2) 取原料，做香烟；（ S）; 吸香烟；Untile false; Process 吸烟者3 Begin Repeat P(s3) 取原料，做香烟；（ S）; 吸香烟；Untile false; Coend 27. 答： (1)系统处于安全状态，存在安全序列：p0,p3,p4,p1,p2; (2)不能分配，否则系统会处于不安全状态。33. （）系统四个进程需要使用的资源数为各台，各台。可见资源数不足。同时各进程申请资源在先，有可能产生死锁发生的四个条件，故系统可能产生死锁。（）当三个进程执行完申请资源，开始申请资源时，第四个进程会因没有资源而被阻塞。当三个进程执行完申请资源后，系统还剩个资源。而这三个进程因执行申请第二个资源而全部被阻塞，系统进入死锁。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 12 页 - - - - - - - - - 习题四（存储管理）二应用题3一个页式存储管理系统使用FIFO，OPT 和 LRU 页面算法，如果一个作业的页面走向为 4，3，2，1， 4，3，5，4，3，2，1，5。当分配给该作业的物理块数分别为3 和 4 时，试计算访问过程中发生的缺页中断次数和缺页中断率。答:作业的物理块数为3 块时 ,使用 FIFO 为 9 次,9/12=75% 使用 LRU 为 10 次,10/12=83% 使用 OPT 为 7 次,7/12=58% 作业的物理块数为4 块时 ,使用 FIFO 为 10 次 ,10/12=83% 使用 LRU 为 8 次,80/12=66% 使用 OPT 为 6 次,6/12=50% 其中 ,出现了 Belady 现象 ,增加分给作业的内存块数,反使缺页中断率上升. 4.在可变分区存储管理下，按地址排列的内存空闲区为：10K，4K，20K，18K，7K ，9K，12K，和 15K。对于下列的连续存储区的请求：（1）12K，10K，9K。 （ 2）12K，10K，15K，18K 试问：使用首次造应算法，最佳造应算法，最差适应算法和下次适应算法，哪个空闲区被使用？答:空闲分区如图所示: 分区号分区长1 2 3 4 5 10KB 4 KB 20 KB 18 KB 7 KB 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 12 页 - - - - - - - - - 6 7 8 9 KB 12 KB 15 KB 1)首次造应算法12KB 选中分区 3,这时分区 3还剩 8KB.10KB 选中分区 1.恰好分配故应删去分区1. 9KB 选中分区 4,这时分区4 还剩 9KB. 2)最佳造应算法12KB 选中分区7, 恰好分配故应删去分区7. 10KB 选中分区1.恰好分配故应删去分区1. 9KB 选中分区6.恰好分配故应删去分区6. 3) 最差适应算法12KB 选中分区 3,这时分区 3还剩 8KB. 10KB 选中分区 4, 这时分区 4还剩 8KB. 9KB 选中分区 8,这时分区8 还剩 6KB. 4) 下次适应算法12KB 选中分区 3,这时分区3 还剩 8KB. 10KB 选中分区4, 这时分区4还剩 8KB. 9KB 选中分区 6.恰好分配故应删去分区6. (2)原理分区情况同上图1) 首次造应算法12KB 选中分区3,这时分区3 还剩 8KB.10KB选中分区1.恰好分配故应删去分区1. 15KB 选中分区 4,这时分区 4 还剩 3KB. 最后无法满足18KB 的申请 ,应该等待 . 2)最佳造应算法12KB 选中分区7, 恰好分配故应删去分区7. 10KB 选中分区1.恰好分配故应删去分区1.15KB 选中分区8.恰好分配故应删去分区8. 18KB 选中分区4.恰好分配故应删去分区4. 3) 最差适应算法12KB 选中分区3,这时分区3 还剩 8KB. 10KB 选中分区4, 这时分区4 还剩 8KB. 15KB 选中分区 8, 恰好分配故应删去分区8. 最后无法满足18KB 的申请 ,应该等待 . 4) 下次适应算法12KB 选中分区3,这时分区3 还剩 8KB. 10KB 选中分区4, 这时分区4还剩 8KB. 15KB 选中分区8, 恰好分配故应删去分区8. 最后无法满足18KB 的申请 ,应该等待 . 5，给定内存空闲分区，按地址从小到大为：100K，500K，200K，300K 和 600K。现有用户进程依次分别为212K， 417K，112K 和 426K， （1）分别用first-fit,best-fit和 worst-fit算法将它们装入到内存的哪个分区？（2）哪个算法能最有效利用内存？答:按题意地址从小到大进行分区如图所示: 分区号分区长1 2 3 4 5 100KB 500KB 200KB 300KB 600KB (1) 1) first-fit 212KB 选中分区 2 ,这时分区 2 还剩 288KB. 417KB 选中分区5, 这时分区5还剩 183KB. 112KB 选中分区 2 ,这时分区 2 还剩 176KB. 426KB 无分区能满足,应该等待 . 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 12 页 - - - - - - - - - 2) best-fit 212KB 选中分区 4 ,这时分区 4 还剩 88KB. 417KB 选中分区2, 这时分区2 还剩 83KB. 112KB 选中分区 3 ,这时分区 3 还剩 88KB. 426KB 选中分区5 ,这时分区 5 还剩174KB. 3) worst-fit 212KB 选中分区 5 ,这时分区 5 还剩 388KB. 417KB 选中分区2, 这时分区2还剩 83KB. 112KB 选中分区 5 ,这时分区 5 还剩 176KB. 426KB无分区能满足 ,应该等待 . (2)对于该作业序列, best-fit 算法能最有效利用内存7内存有3 个和 4 个空闲页框的情况下，页面替换次数为9 次和 10 次，出现了Belady现象。9某计算机有cache,内存，辅存来实现虚拟存储器。如果数据在cache 中，访问它需要20ns；如果在内存但不在cache ，需要 60ns 将其装入缓存，然后才能访问；如果不在内存而在辅存， 需要不是12ms 将其读入内存， 然后， 用 60 ns 再读入 cache，然后才能访问。假设 cache命中率为0.9，内存命中率为0.6，则数据平均访问时间是多少(ns)？答:20*0.9+(60+20)*(1-0.9)*0.6+(20+60+12000)*(1-0.9)*(1-0.6)=506ns 18. 答： t1 时刻的工作集为：1，2，3，6，7，8，9 t2 时刻的工作集为：3 ，4 20答：虚地址0AC5H 对应的物理地址为：12C5H。而执行虚地址1AC5H 会发现页表中尚未有分配的页框而发生缺页中断，由系统另行分配页框。21答：（1）FIFO 淘汰page 2 (2)LRU 淘汰 page 1 (3)二次机会淘汰oage 0 习题五5. 对磁盘存在下面五个请求: 请求柱面号磁头号扇区号1 7 2 8 2 7 2 5 3 7 1 2 4 30 5 3 5 3 6 6 假如当前磁头位于1 号柱面 .试分析对这五个请求如何调度,可使磁盘的旋转圈数为最少? 答:使磁盘的旋转圈数为最少的调度次序为:5,3,2,1 和 4 10.答：采用 FIFO 次序为： 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 采用 SCAN 次序为： 100，132， 190，205，376，398，61，40，29，23，19，18，4 总柱面数是692 15非优化存放，读一块数据需要时间为：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 12 页 - - - - - - - - - 13x6+100+25=203ms 因而传输100 块的文件的时间为：20300ms 优化存放，读一块数据需要时间为：2x6+100+25=137ms 因而传输100 块的文件的时间为：13700ms 16.磁盘请求以10,22,20,2,40,6,38 柱面的次序到达磁盘驱动器,如果磁头当前位于柱面20.若查找移动每个柱面要花6ms.用以下算法计算出查找时间:1)FCFS, 2)最短查找优先, 3)电梯算法 (正向柱面大的方向). 答:1)FCFS 查找时间次序为:20,10,22,20,2,40,6,38,查找时间为 :876 ms 2) 最短查找优先查找次序为:20,20,22,10,6,2,38,40, 查找时间为 :360 ms 3) 电梯算法查找次序为:20,20,22,38,40,10,6,2,. 查找时间为 :348 ms 习题六31）位示图占用字数为500/32=16（向上取整）个字（ 2）第 I 字第 j 位对应的块号N=32*I+j （ 3）11采用成组方式存放，块因子为2，由于共有18 个逻辑纪录，故占用了9 个物理块，而第 15 号逻辑纪录占用的是第15/2=8 物理块。因为是连续文件物理块也是连续的，所以，该逻辑纪录占用的是12+8-1=19 块。所以第15 号逻辑纪录读入内存缓冲区的过程如下：根据块因子，计算占用的相对物理块号8；根据起始地址号为12，计算出绝对物理块号19；把物理块号19 读入内存缓冲区；把所有的逻辑纪录分解出来。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 12 页 - - - - - - - - -