操作系统习题答案

1、精选优质文档-倾情为你奉上习题一(前三章)1、 系统如何由目态转为管态？如何由管态转为目态？目态到管态的转换(中断，trap)：修改处理机状态字指令属于特权指令，只能在管态执行，目态程序无法直接控制处理机状态的转换。处理机状态由目态转换为管态的唯一途径是中断，中断发生时，中断向量中的PSW标识处于管态，这个标识一般由操作系统初始化程序设置的。管态到目态的转换(置程序状态字)：通过修改程序状态字(置PSW)来实现，操作系统运行于管态，该状态转换伴随着由操作系统程序到用户程序的转换。2、 为什么有硬件时钟，有时还要设置软件时钟？解：硬件时钟由硬件提供，保存在硬件寄存器中，开机由电源供电，关机由机内

2、电池供电，可由程序设定和修改，一般通过特权指令完成，应用程序可读取该值。不发生中断。间隔时钟：定时发生中断，一般间隔单位为“毫秒”。中断发生后，操作系统获得系统的控制权，以便运行系统管理和实现程序并发。是实现多道程序的基础保证操作系统获得控制权。软件时钟：利用间隔时钟实现，主要用于定时启动一些服务，如定时备份，软件时钟通过赋内存的一个单元一个初值，通过间隔时钟中断，对该单元值减一，减到0就启动相应的服务，这是间隔时钟做不到的。3、 通过一个案例分析进程的状态转换过程。 比如用播放器播放音乐，当启动播放器，产生播放器进程，进入挂起就绪状态，当用户点击播放按钮时，进入就绪状态，当被处理机调度时，处

3、于运行态，当需要听歌曲，且歌曲还在外存时，该进程启动磁盘读进程，然后自己进入等待态，当磁盘读进程将相应歌曲读进内存时，向处理机发出中断，该中断进程将播放器进程送入就绪队列，当被处理机调度时，开始播放歌曲，处于运行态，如此反复，直到关闭播放器，进程结束。 单击暂停键，进入挂起就绪队列4、 通过一个案例描述可以由用户处理的中断的处理过程。比如在一个C语言程序中发生除零错误（1）发生出除零中断（2）保存旧PSW和PC(入系统栈)（3）取中断向量（4）转到中断处理程序（5）访问中断续元表（假定非0）（6）系统栈中现场转移到用户栈（7）中断续元入口送寄存器（OS中断处理完成）（8）执行中断续元 中断续元

4、的执行同目态子程序 （9）用户栈PSW和PC送寄存器 （10）中断执行完，遇RET指令由用户栈弹出现场信息送入处理机 （11）返回中断断点 5、下表列出了四个进程到达时间和执行时间，使用先来先服务算法、循环（时间片2）、短作业优先、响应比高者优先的调度算法的调度过程，分别计算每个调度算法的周转时间、平均周转时间、带权周转时间、带权平均周转时间. 画出相应的Gantt图进程到达时间执行时间A03B16C44D62解：先来先服务算法A B C D 0 3 9 13 15进程 到达时间 运行时间 开始时间 完成时间 周转时间 带权周转时间 A0 3 0 3 31 B1 6 3 98 8/6 =1.3

5、3C 44 9 13 9 9/4 =2.25D62131599/2=4.5平均周转时间 =(3+8+9+9)/4=7.25 平均带权周转时间 =(1+1.33+2.25+4.5)/4=2.27 循环（时间片2）A B C D A B C B0 2 4 6 8 9 11 13 15周转时间: 由就绪开始时刻到处理完毕时刻的时间带权周转时间：周转时间/运行时间等待时间(waiting time)：周转时间与处理时间之差进程 到达时间 运行时间 开始时间 完成时间 周转时间 等待时间带权周转时间 A0 3 0 9 969/3=3 B1 6 21514 814/6 =2.33C 44 4 13 9 5

6、9/4 =2.25D6268202/2=1平均周转时间 =(9+14+9+2)/4=8.5 平均等待时间 = (6+8+5+0)/4=4.75平均带权周转时间 =(3+2.33+2.25+1)/4=2.145 短作业优先进程到达时间执行时间A03B16C44D62A B D C 0 3 9 11 15 进程 到达时间 运行时间 开始时间 完成时间 周转时间 带权周转时间 A0 3 0 3 33/3=1 B1 6 398 8/6 =1.33C 44 11 15 11 11/4 =2.75D6291155/2=2.5平均周转时间 =(3+8+11+5)/4=6.75 平均带权周转时间 =(1+1.

7、33+2.75+2.5)/4=1.895 响应比高者优先RR=1+WT/BT在 9时刻出现了D和CC的响应比=1+5/4=2.25D的响应比=1+3/2=2.5A B D C 0 3 9 11 15 进程 到达时间 运行时间 开始时间 完成时间 周转时间 带权周转时间 A0 3 0 3 33/3=1 B1 6 398 8/6 =1.33C 44 1115 11 11/4 =2.75D6291155/2=2.5平均周转时间 =(3+8+11+5)/4=6.75 平均带权周转时间 =(1+1.33+2.75+2.5)/4=1.895 7、在一个使用多级反馈队列的系统中，一个只使用CPU的进程的执行

8、时间为40秒，如果第1队列时间片为2，每级时间片增加5个时间单元，那么这个作业运行结束前会被中断多少次，结束时处于哪级队列？解3：进程被中断的情况有：在时刻2（第1队列），在时刻2+7（第2队列），在时刻9+12（第3队列），在时刻21+17（第4队列），当该进程结束时位于第5队列，中断4次。练习二 互斥、同步与通信1、 设有3个进程R、W1和W2，共享缓冲区B，B中每次只能存放一个数，当B中无数据时，可以从输入设备上读数据到B中，若数为奇数时允许W1取出打印，否则允许W2取出打印，W1和W2每次仅能打印一次，它们不能从空的B中取数据。解：设信号量sr表示是否可读，初值为1 设信号量sp1表示

9、w1进程是否可打印，初值为0 设信号量sp2表示w2进程是否可打印，初值为0cobegin sr, sp1, sp2 :semaphore :=1,0,0; x :integer; process reader process w1 process w2 begin begin begin repeat repeat reapet p(sr); p(sp1); p(s2p); 读入一个数放入x; 打印x1; 打印x1; if x mod 2 = 0 then v(sp2) v(sr); v(sr); else until false; until false; v(sp1); end; end

10、; until false; end;end;2、 有3个好朋友预定在一个地方集合，然后一起去看电影，请用PV描述他们的同步操作。解： 定义一个计数器，统计到达的人数：count，初值为0 定义三个同步信号量s1，s2，s3，表示是否可以去看电影，初值都不可以看，为0 定义一个互斥信号量mutex，用于对count的互斥访问 var count :integer :=0; s1,s2,s3,mutex :semaphore :=0,0,0,1;P1进程 P2进程 P3进程P(mutex) p(mutex) p(mutex)Count := count+1; count := count+1;

11、count := count+1V(mutex); v(mutex) v(mutex)If count=3 then if count=3 then if count=3 thenBegin begin begin V(s2); v(s1); v(s1); V(s3); v(s3); v(s2);End end endElse else else P(s1); p(s2); p(s3);练习三 互斥、同步与通信1、两进程PA，PB通过两FIFO缓冲区队列连接（如图），每个缓冲区长度等于传送消息长度。进程PA，PB之间的通信满足如下条件： buf0 buf1(1) 至少有一个空缓冲区存在时，相应

12、的发送进程才能发送一个消息。(2) 当缓冲队列中至少存在一个非空缓冲区时，相应的接收进程才能接收一个消息。试描述发送过程send(i,m)和接收过程receive(i,m)。这里i代表缓冲区。解：bufempty0、bufempty1表示缓冲区是否空，初值为nbuffull0、buffull1 表示缓冲区是否满，初值为0buf0、buf1表示两个缓冲区     Send(i,m)     Begin          loca

13、l x          P(bufemptyi)          按FIFO方式选择一个空缓冲区          bufi(x)=m          bufi(x)置满标记     

14、     V(buffulli)       End       Receive(i,m)       Begin            Lccal x          

15、;  P(buffulli)            按FIFO方式选择一个装满数据的缓冲区bufi(x)            m=bufi(x)            bufi(x)置空标记     

16、0;      V(bufemptyi)         End         Pa调用send(0,m)和receive(1,m)         Pb调用send(1,m)和receive(0,m)2、设有三组进程PA，PB，PC，PA进程每次从磁盘中读入一条记录到缓冲区1中，缓冲区1可存放N条记录，P

17、B进程每次只能从缓冲区1中取出一条记录到缓冲区2中，缓冲区2可存放N/2条记录，PC进程每次只能从缓冲区2中取出一条记录来打印，请用管程描述它们之间的同步操作。解：本题中，PA是一个生产者，PB既是生产者又是消费者，PC是消费者， 解：条件变量： notfull1: 表示B1是否满， notfull2： 表示B2是否满 notempty1：表示B1是否空， notempty2：表示B2是否空k1,k2: 分别表示在B1中PA放记录的位置和PB取记录的位置，初值为0。t1,t2: 分别表示在B2中PB放记录的位置和PC取记录的位置，初值为0。count1, count2：分别表示B1存放记录数和

18、B2存放记录数.初值为0。count1>=n： 表示B1已满，这时PA进程不能再读入记录到B1中，将wait(notfull1)count1<n： PA可以放1条记录到B1中，此时看是否有等待B1中记录的，若有则将singal(notempty1)count2>=n/2： 表示B2已满，这时PB进程不能从B1中读记录到B2中，将wait(notfull2)，当count1<=0时表示B1中无记录，PB不能从B1中取记录，将wait(notempty1)count2<n/2并且count1>0：表示PB可以从B1中取1条记录到B2中，此时检查是否有等待B2的记

19、录，若有则将singal(notempty2)count2<=0： 表示B2中无记录，PC不能打印，执行wait(notempty2), 否则从B2中取记录打印，同时检查是否有PB在等待B2中放记录，若有则执行singal(notfull2)。过程： get(item)：PC从B2中取记录put(item)：PA从磁盘读记录到B1中。Getput(item)：PB从B1取记录到B2中。Type procedure PC=moniorVar k1,k2,t1,t2,count1,count2 :integerB1 :array0n-1 of item;B2 :array0n/2-1 of

20、item;notfull1,notfull2,notempty1,notempty2 :condition;procedure entry put(item)begin if count1>=n then wait(notfull1); B1k1 := item; k1 :=(k1+1) mod n; count1:=count1+1; signal(notempty1);end;procedure entry getput(item)begin if count2>=n/2 then wait(notfull2); if count1 <=0 then wait(notem

21、pty1); B2t1 := B1k2; t1 :=(t1+1) mod n/2; k2 :=(k2+1) mod n; signal(notfull1); signal(notempty2);end;procedure entry get(item)begin if count2 <=0 then wait(notempty2); 打印B2t2; t2 := (t2+1) mod n/2; signal(notfull2)end;begin k1=k2=t1=t1=0; count1=-count2=0;end;process PA process PB process PCbegin

22、 begin begin repeat repeat repeatread an item; PC.getput(item); PC.get(item);PC.put(item); untill false; print item; Untill false; end; untill false;End; end;练习四 死锁1、某系统采用死锁检测手段发现死锁，设系统中资源类集合为A，B，C，资源类A中共有17个实例，资源类B中共有5个实例，资源类C中共有20个实例又设系统中进程集合为p1,p2,p3,p4,p5, T0时刻系统状态如下：    

23、0;   Allocation     Need      Available         A B C          A B C       A B C  p1:   2 1 2   

24、0;     3 4 7         p2:   4 0 2          1 3 4  p3:   4 0 5         0 0 6p4:   2 0 4      

25、0; 2 2 1  p5:   3 1 4         1 1 0在T0时刻是否安全，请给出安全系列在T0时刻若进程P2请求资源（0 3 4），能否实现分配，为什么？在(2)的基础上，若进程P4请求资源(2 0 1) ，能否实现分配，为什么？在(3)的基础上，若进程P1请求资源(0 2 0) ，能否实现分配，为什么？解：(1)由已知可知，系统剩余资源为(2 3 3) Allocation     Need   &

26、#160;  Available   Work Finish  A B C          A B C        A B C    A B C p1:  2 1 2         3 4 7       2 3

27、3 p2:  4 0 2          1 3 4  p3:  4 0 5         0 0 6p4:  2 0 4        2 2 1p5:  3 1 4         1 1 0 Work Allocatio

28、n    Need     Work+ Allocation Finish  A B C A B C       A B C        A   B C p1:  7 4 11 2 1 2       3 4 7       9 5 13

29、 true3p2:  9 5 13 4 0 2       1 3 4  13 5 15 true4 p3:  13 5 15 4 0 5         0 0 6 17 5 20 true5p4:  2 3 3 2 0 4        2 2 1 4 3 7 true1p5:  4 3 7 3 1 4   

30、60;  1 1 0 7 4 11 true2可以找到一个系列p4,p5,p1,p2,p3(2) 在T0时刻若进程P2请求资源（0 3 4），因请求资源大于剩余资源(2 3 3)，不能分配(3) 在(2)的基础上，若进程P4请求资源(2 0 1)，由于请求资源(2 0 1)<需求资源(2 2 1)， 请求资源(2 0 1)< 剩余资源(2 3 3)，进行试分配 Allocation     Need      Available     

31、60;   A B C          A B C       A B C  p1:   2 1 2         3 4 7       0 3 2  p2:   4 0 2   &#

32、160;      1 3 4  p3:   4 0 5         0 0 6p4:   4 0 5        0 2 0  p5:   3 1 4         1 1 0再使用安全性检测算法，得到 Work Allocati

33、on     Need      Work+ Allocation Finish  A B C A B C         A B C       A   B C p1:  7 4 11 2 1 2         3 4 7  

34、    9 5 13 true3p2:  9 5 13 4 0 2         1 3 4  13 5 15 true4 p3:  13 5 15 4 0 5         0 0 6 17 5 20 true5p4:  0 3 2 4 0 5        0 2 0 4 3 7

35、true1p5:  4 3 7 3 1 4         1 1 0 7 4 11 true2可以找到一个系列p4,p5,p1,p2,p3(4) 在(3)的基础上，若进程P1请求资源(0 2 0), 由于请求资源(0 2 0)<需求资源(3 4 7)，请求资源(0 2 0)< 剩余资源(0 3 2)，进行试分配Allocation     Need      Available  &

36、#160;      A B C          A B C        A B C  p1:   2 3 2         3 2 7       0 1 2  p2:   4 0

37、2          1 3 4  p3:   4 0 5         0 0 6p4:   4 0 5        0 2 0  p5:   3 1 4         1 1 0由于资源（0

38、 1 2）不能满足任何进程故不能分配2、有三类资源R1,R2,R3，R1和R2资源数分别为，R3为，有四个进程P1,P2,P3,P4，每个进程占用资源和等待资源的情况如下：进程已占资源类已占用个数 等待的资源P1 R3 , R2 1 ,1 R1P2 R1 1 -P3 R1 1 R2P4 R2 1 R3请画出资源分配图，使用资源分配图的约简证明是否产生死锁。P2 解：R1 P3 R2 P1 P4 R3 (1)该图中非孤立节点且没有请求边的是P2(2)去掉分配边成为孤立节点P2 R1 P3 R2 P1 R3 P4 (3)寻找请求边可以满足的节点，并将请求边改为分配边P2 R1 P3 R2 P1 R

39、3 P4 (4)没有请求边的是P1，去掉分配边成为孤立节点P2 R1 P3 R2 P1 R3 P4 P2 (5)寻找请求边可以满足的节点，并将请求边改为分配边R1 P3 R2 P1 R3 P4 (6)没有请求边的是P3,P4，去掉分配边成为孤立节点P2 R1 P1 P3 R2 R3 P4 (7)最后全部为孤立节点，系统没有死锁3、在A、B两车站之间为单轨，且在中间有一个小站C，小站C为双轨道，给出一个无死锁、无饿死、并发度最高的算法，使用PV实现。 解： C1 A B C2 若AB方向火车在小站C走上边轨道，BA方向走下边轨道，则： 当同时不超过3辆火车时，不会发生死锁 设信号量 train=3 AC、BC为单轨，设信号量 ac=1 bc=1 C站： c1=1 c2=1 A到B B到C P(train) P(train) p(ac) p(bc) ac上行驶 bc上行驶 p(c1) p(c2) 进入C小站 进入C小站 v(ac) v(bc) p(bc)