操作系统课后习题1-9答案

操作系统课后习题1-9答案

练习1

1.i-i.10题解见书

1.11有一台输入设备和一台输出设备的计算机系统上，运行有两道程序。两道程序投

入运行情况如下：

程序1先开始运行，其运行轨迹为：计算50ms、输出100ms,计算50ms、输出100ms,

结束；

程序2后开始运行，其运行轨迹为：计算50ms、输入100ms、计算100ms、结束。

1.忽略调度时间，指出两道程序运行时，CPU是否有空闲？在哪部分空闲？指出程序1

和程序

2.有无等待CPU的情况？如果有，发生在哪部分？

题解：

由题画出CPU利用图如下:

由图可知，1.CPU有空闲，在100ms-l50nls时间段是空闲的。

2.程序1无等待时间，而程序2在一开始的0ms~50ms时间段会等待。

1.12在计算机系统上.运行三道程序，运行次序为程序1、程序2、程序3。程序1的运

行轨迹为：计算20ms、输入40ms、计算10ms。

程序2的运行轨迹为：计算40ms、输入30ms、计算10ms。

程序3的运行轨迹为：计算60ms、输入30ms、计算20ms。

忽略调度时间，画出三道程序运行的时间关系图；完成三道程序共花多少时间？与单道

程序比较，节省了多少时间？

解答：三道程序运行，完成三道程序共花170ms。与单道程序（260ms）比较，节省了

90mso

（始终按照1-2-3的次序，即程序1一程序2-程序3f程序1-程序2f（在程序3运

行前会停10ms等待输入完成）程序3o

（如果不是按照程序1、2、3的次序完成则会有多种情况。）

1.13在计算机系统上有两台输入/输出设备，运行两道程序。

程序1的运行轨迹为：计算10ms、输入5ms、计算5ms、输出10ms、计算10ms。

程序2的运行轨迹为：输入10ms、计算10ms、输出5ms、计算5ms、输出10ms。

在顺序环境下，先执行程序1,再执行程序2,求总的CPU利用率为多少?

CPU利用率=40ms/80ms*100%=50%

1.14一个计算机系统有足够的内存空间存放3道程序，这些程序有一半的时间在空闲

等待I/O操作。问多大比例的CPU时间被浪费掉了。

题解：由题画图如下:

程序1

程序2

程序3

------------------------------------------------------------------------>t

01/21/41/8--------1

因为每个程序有一半的时间在等待I/O操作，所以在并发状态下，程序1、程序

2、程序3所占时间比依次减半（如上图），所以浪费的时间比例为1/8。

练习2

2.18某系统中进程状态变化如图2.22所示，当对系统中的进程进行观察时，发现某

一进程产生的•次状态变化会引起另一进程发生状态变化。

（1）在什么情况下，一个进程的状态变化3能够立即引起另一进程的状态变化1?

（2）在什么情况下，一个进程的状态变化2能够立即引起另一进程的状态变化1?

（3）进程的状态变化3是否可能引起另一进程的状态变化2?进程的状态变化3是否可

能引起另一进程的状态变化1?

解答：

(1)当就绪队列中还存在其它进程的情况下，一个进程的状态变化3能够立即引起另

一进程的状态变化2。

(2)当就绪队列中还存在其它进程的情况下，一个进程从运行状态变化到就绪状态

后，另一个就绪进程能够从就绪状态变为运行状态。

(3)不可能，可能。

2.19分别写出相应的程序来描述图2.23中的前趋图。

解答

程序：SI:a:=x+lS2:b:=a+2S3:c:=a+3S4:d:=b+4S5:e:=b+cS6:f:=e+5S7:g=e+6

程序：SI:a:=x+lS2:b:=a+2S3:c:=a+3S4:d:=b+4S5:e:=b+cS6:f:=d+eS7:g:=c+e

2.20假设在一个系统中，新进程以每分钟8个进程的速率到达，每个进程请

S4

求服务的平均时间为6s,估计在一个单处理器系统中CPU忙的时间比率。如果新进程

以每分钟10个进程的速率到达，每个进程请求服务的平均时间也为6s,估计在一个单处

理器系统中CPU忙的时间比率。

如果新进程创建以每分钟超过10个进程的速率到达，每个进程请求服务的平均时间为

6s,估计在一个单处理器系统中CPU忙得时间比率，并解释此时的情况。

解答：

因为新进程每分钟8个进程的速率到达，每个进程之间达到的时间间隔为

7.5s。由于每个进程占用6s的CPU时间。所以，1分钟之内CPU的空间时间为

8*1.5s=12soCPU的利用率为48/60=0.8,即805。

因为新进程每分钟10个进程的速率到达，每个进程之间达到的时间间隔为6s。由于每

个进程占用6s的CPU时间。所以，1分钟之内CPU的空间时间为Os。CPU的利用率为

100%。

如果新进程创建以每分钟超过10个进程的速率到达，每个进程请求服务的平均时间为

6s,则请求服务时间会大于1分钟，CPU一直会处于繁忙，所以CPU忙的时间比率同样为

100%。

2.21一个系统中有4个进程，进程P1要求20s后运行，经过40s后再次运行；进程P2

要求25s后运行；进程P3要求35s后运行，经过35s后再次运行；进程P4要求60s后运

行。进程在阻塞队列等待被唤醒后运行，试创建进程的唤醒队列。

解答：进程的唤醒队列为P1-P2-P3-P4-P1-P3

注意：“经过40s后再次运行”表示第1次运行完成后再过40so

2.22如果线程是在用户空间线程库中实现，解释为什么当进程中的一个线程阻塞时，

进程内的所有其它线程都会阻塞？如果线程是在内核空间中实现，而进程内的•个线程阻

塞不会引起进程内的其他线程被阻塞，为什么？

解答：

用户级线程由用户空间运行的用户级线程库实现。当一个应用程序提交给操作系统后，

操作系统首先为该应用程序建立一个内核管理进程，然后用户级线程库为该进程创建一个

或多个用户级线程，但内核并不知道用户空间线程的活动，内核只是以进程为单位，实现

进程状态的转换，因此当进程中的一个线程阻塞时，进程内的所有其它线程都会阻塞。

如果线程是在内核空间中实现的，这些内核级线程都由内核创建和控制管理，内核为整

个进程及进程中的所有线程维护现场信息，内核的调度是在线程的基础上进行的，因而进

程的一个线程阻塞不会引起进程内的其他线程被阻塞。

练习3

3.13证明作业调度算法中短作业优先调度算法具有最小平均等待时间。

证明:假设在作业队列中等待运行的作业有N道,分别为NO,Nl,N2,,,,Nn-1,它们的

运行时间分别为t0,tl,tnT,且满足

由于短作业有限调度算法总是选择最短的作业先调度，故这些作业总的等待时间为：

Tl=0+t0+(t0+tl)+(tO+tl+t2)+„+(tO+tl+t2+„+tn-2)

=(N-1)tO+(N-2)tl+(N-3)t2+„+tn-2(1)

如果不按照短作业优先调度算法，可设调度顺序为：Nl,NO,N2,”，Nn-1,故这些作

业总的等待时间为：

T2=0+tl+(tO+tl)+(tO+tl+t2)+”+(tO+tl+t2+„+tn-2)

=(N-2)tO+(N-1)tl+(N-3)t2+,,+tn-2(2)

(2)-(1)得:

T2T1=tltO>0

说明任何一种作业调度顺序的作业的平均等待时间都大于按照短作业优先的作业的平均

等待时间。

3.14假设在一个处理器上执行5个作业，作业到达的次序和需要执行的时间分别为:

JO(75ms)、JI(15ms)、J2(5ms)、J3(15ms)、J4(45ms),

假定系统中使用FCFS调度算法，作业J3的周转时间是多少？作业的平均等待时间是多

少？

周转时间(ms)等待时间(ms：

J0750

J19075

129590

J311095

J4155110

平均等待时间(ms)74

3.15在单道批处理系统中，三个作业的提交时间分别为：10：00、10：10、10：20,需

要执行时间分别为：2小时、1小时、0.5小时，分别按照短作'也优先调度算法和高响应比

优先调度算法进行调度，比较哪一种调度算法更好？解：

(1)不抢占：

执行顺序为A,C,B

平均周转时间：(120+130+200)/3=150(min)

平均带劝周转时间：(120/120+130/30+200/60)/3=26/9

抢占：

A(10：10),B(10：20),C(10:50),B(ll:40),A(13:30)

平均周转时间：(210+90+30)/3=110(min)

平均带劝周转时间：(210/120+90/60+30/30)/3=510/360=17/12

(2)响应比高者优先调度算法不会抢占，因此，只存在这样一种情况:

执行顺序为A,C,B

平均周转时间：(120+130+200)/3=150(min)

平均带劝周转时间：(120/120+130/30+200/60)/3=26/9所以，如果要比较哪一种算

法好自然针对不抢占的情况。根据比较结果，它们的平均周转时间和平均带权周转相同，

这主要是该应用正好发生了这样凑巧的情况。

3.16假设在具有一个处理器的系统上执行下面的作业，假如采用抢占式短作业优先调度

算法，作业需要处理时间T和到达时间A分别如下：那么：

IT到达时间A

0500

13510

22010

32555

41095

作业1答：

1,执行顺序为：0(10),2(30),1(65),3(90),0(130),4(170)作业0

的周转时间为：130,

作业1的周转时间为：55,

作业2的周转时间为：20,

作业3的周转时间为：35

作业4的周转时间为：65

平均周转时间=305/5=61

作业0的等待时间为：130-50=80,

作业1的等待时间为：55-35=20,

作业2的等待时间为：10T0=0,

作业3的等待时间为：，35-25=10

作业4的等待时间为：，65-40=25

3.17假如在具有一个处理器系统中，采用优先级高者优先的进程调度算法，优

IT优先级

0753

1151

254

3155

4452

T、优先数分别如下：

(12的周转时间是多少？进程的平均等待时间是多少？

(3)有优先级抢占情况下，写出进程的执行先后序列，进程2的周转时间是多少？进

程的平均等待时间是多少？

答：

(1)无抢占：

执行顺序为：1(15),4(60),0(135),2(140),3(155)

进程0的周转时间为：135

进程1的周转时间为：15

进程2的周转时间为：140

进程3的周转时间为：155

进程4的周转时间为：60

进程的平均等待时间=((135-75)+(15-15)+(140-5)+(155-15)+(60-45))/5

=70

(2)有抢占：

优先级抢占同上一样。

3.18假如在具有一个处理器的系统中，采用时间片轮转调度算法，时间片大小为10。

进程需要处理时间T和到达时间A分别如下：

IT到达时间A

0500

13510

22010

31580

4-1085

写出进程的执行序列，进程3的周转时间是多少？进程的平均等待时间是多少？

答：

进程的执行序列为：0，1,2,0,1,2,0,1,3,4,0,1,3,4,0,4进程0的周

转时间T0=140

进程1的周转时间Tl=105

进程2的周转时间门=50

进程3的周转时间Tl=40

进程4的周转时间Tl=75

进程的平均等待时间为：((140-50)+(105-35)+(50-20)+(40-15)+(75-

40))/5=50

3.18在时间片轮转调度算法中，有n个进程共享CPU。

(1)如果进程切换的时间不可忽略，每次进程切换用去时间为s秒，在保证每个进程

至少每t秒内能够在CPU上轮回一次的前提下，确定时间片大小q使得进程切换所造成的

负载最小。

(2)如果n=100,t=l,s=0.001,那么q的大小应该是多少？

答：

(1)时间片大小q=(t-ns)/n

(2)q=(1-100*0.001)/100=0.009

3.19有一个四道作业的操作系统，若在一段时间内先后到达6个作'也，它们的提交时

间和估计运行时间由下表给出：

作业提交时间估计运行时间（分钟）

18：0060

28：2035

38：2520

48：3025

58：355

68：4010

系统采用短作'也优先调度算法，作'也被调度进入系统后中途不得退出。但作'也运行时可

被更短的作业抢占。分别给出6个作、业的执行时间序列，作业的周转时间，平均周转时

间。

答:

作业的执行顺序为：1（8：20）,2（8：25）,3（8：45）,5（8：50）,6（9：

00）,4（9：25），2（9：55），1（10：35）

作业1的周转时间=155min

作业2的周转时间二95min

作业3的周转时间二20min

作业4的周转时间二55min

作业5的周转时间二15min

作业6的周转时间二20min

作业的平均周转时间为：360/6=60

3.20在一个实时系统中有4个周期性事件，周期分别为50、100、150、200mso假设其

处理时间分别需要30、25、20和xms,则该系统可调度允许的x值最大为多少？

解:

30/50+25/100+150/20+200/x=1

X=10/3

3.21某系统的进程状态变化如图3.23所示，该系统的进程调度为非抢占方式，根据该

状态图叙述系统的调度策略、调度效果。

图3.23状态变化图

答：首先采用优先权高者优先调度算法，然后采用时间片为100ms的调度算法。该调

度算法如果调度效果考虑更周到的话，应该让阻塞队列上的进程唤醒后进入低优先级就绪

队列，这样能够保证优先级高的进程及时调度，优先级低的进程能够合理的得到调度。

第4章

4.13如果有n个进程共享一个互斥段

(1)如果每次只允许一个进程进入互斥段。

(2)如果每次最多允许m个进程同时进入互斥段(m〈n)。

问采用的信号量初值是否相同？信号量值的变化范围如何？

答：所采用互斥信号量的初值不同。

(1)互斥信号量初值为1,变化范围为bn+1,1］。

当没有进程进入互斥段时，信号量值为1;

当有1个进程进入互斥段时，但没有进程等待进入互斥段时，信号量值为0；当有1个

进程进入互斥段，有,1个进程等待进入互斥段时，信号量值为-1;最多可有n-1个进程

等待进入互斥段，故此时信号量的值为-(n-1)。

(2)互斥信号量初值为m,变化范围为［m-n,m］。

当没有进程进入互斥段时，信号量值为m；

当有1个进程进入互斥段时，但没有进程等待进入互斥段时，信号量值为mT；当有m

个进程进入互斥段，但没有进程等待进入互斥段时，信号量值为0；当有m个进程进入互

斥段，有1个进程等待进入互斥段时，信号量值为T;最多可有n-m个进程等待进入互

斥段，故此时信号量的值为-(n-m)。

4.14在两条双向道路的交叉路口，没有行人通过，只有汽车通过。交通情况如下：

(1)任何给定的时刻只能有一辆车过马路；

(2)当一辆车到达交叉路口并且另一条街道上没有车来到的时候，应该允许此车通

过；

(3)当两个方向上都有车到达的时候，它们应该轮流通过，以防止在其中一个方向上

的无限期延迟。

用信号量操作实现道路交通问题。

解：

semphoreSl=0,S2=0;//有无车到达，为0时无到达

semphoreMl=l,M2=0;〃路中被占

Pl:

if(车到达)

v(Sl);

while(!S2);

if(!S2)

过一辆车；

else

p(M2);p(Ml);

过一辆车；

v(Ml);

}

P2:

if(车到达)

v(S2);

while(!S2);

if(!Sl)

过一辆车；

else

(

p(Ml);

P(S2);

过一辆车；

v(M2);

)

4.15在哲学家进餐问题中，假设5个哲学家中第i个执行下面的代码段p(mutex);

p(fork[i]);

p(fork[i+l%5]);

v(mutex);

eat;

v(fork[i]);

v(fork[i+l%5]);

(1)说明这段代码是否满足哲学家进餐问题的所有需求。

(2)如果V(mutex)语句改在第二个V()操作之后，或者在两个P()操作之间，说明这两

种解决方法是改进了算法还是变坏了算法。

答：

(a)满足

(b)都不行

4.16有两个优先级相同的进程P1和P2,各自执行的操作如下，信号量S1和S2的初

值都为0,试问Pl、P2并发执行后，x、y、z的值各为多少？

Pl：P2：

beginbegin

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:=y+z;(4)z:=x+z;(8)

end;end;答：语句(1)(2)(5)(6)不相交，任何执行顺序，结果相同。

情况1：语句(4)先执行x=10,y=9,z=15；

情况2：语句(8)先执行x=10,y=19,z=15；

情况3：语句(3)推迟到语句(8)之后，x不定，y=4,z不定;

4.17两个进程A、B,考虑下面的信号量编码

semaphores=1;

intx=10,y=2;

fork(A,0);

fork(B,0);

A(){BO{

(1)x++;(4)if(x>10)

(2)V(s);(5)x——;

(3)y=x—2;(6)else{P(s);

}x---;}

}

分别说明(1)、(2)、(3)、(4)、(5)、(6)语句之后的x、y值为多少？

答：

(1)x=ll,y=2(2)x=ll,y=2(3)x=ll,y=9

(4)x=ll,y=9(5)x=10,y=9(6)x=10,y=8

4.18三个进程：输入、计算、输出。它们通过两个缓冲区传递数据，如图4.11所示。

每个缓冲区次只能放入一条数据。写出用信号量进行同步。

(7)U公共缓冲区1卜——(p)

解：varemptyl,fulll,empty2,ful12:semaphore:=1,0,1,0;

begin

parbegin

I:begin

repeat

wait(empty1);

puttobufferl;

signal(fulll);

untilfalse;

end;P:begin

repeat

wait(fulll);

getfrombufferl;

signal(emptyl);

wait(empty2);

puttobuffer2;

signal(full2);

untilfalse;

end;

0:begin

repeat

wait(full2)

getfrombuffer2;

signal(empty2);

untilfalse;

end;

parend;

end;

第5章

5.1什么是死锁？引起死锁的原因和必要条件是什么？

死锁是指多个进程因为竞争资源造成的一种僵局。

原因：并发进程对临界资源的竞争和并发进程推进顺序不当。

必要条件：互斥条件，占有并请求条件，不剥夺条件，环路等待条件。

5.2比较解决死锁的方法中，那种方法最容易实现？那种方法使得资源的利用率最高？

解决死锁的方法：预防死锁，避免死锁，检测死锁，解除死锁。

预防死锁是通过设计协同资源管理程序，在进程运行期间，柏怀死锁产生的四个条件之

中的任何一个，是指不成立。是最容易实现的方法。

解除死锁是在发现死锁后，解除死锁，释放资源。是资源利用率最高的方法。

5.3预防死锁的方法有哪些？

破坏互斥条件，破坏占有并请求，阻止环路等待，允许剥夺

5.8系统中有3个进程共享4个资源，每个进程每次只能申请或释放一个资源，每个进

程最多需要2个资源，给进程是否会发生死锁，为什么？

解：

不会发生死锁。3个进程共享4个资源，每个进程最多需要2个资源。总有一个进程的

请求会满足，运行并释放资源。不会形成环路等待。

5.9系统中有20个进程，每个进程最多使用3个资源，每个进程逐个申请并竞争使用

60个同类资源。一旦某进程获得所需要的资源，完成后立即释放全部资源。系统是否会发

生死锁？为什么？

系统不会发生死锁。以最坏的情况来考虑，20个进程都需要使用3个资源。当前，每个

进程都持有2个资源。(20*2=40).都在申请第3个资源(60-40=20)对于剩余的20个

资源，每个进程多会得到一个资源。不会形成环路等待。

5.10一台计算机有8台打印机，被N个进程竞争使用，每个进程最多需要3台。请

问N为多少时，系统没有死锁的危险，说明原因。解：

N=3时，没有死锁的危险。

对于N个进程，都持有2台打印机时，申请第3台打印机，只要有一台的多余的打印机

能被申请到，则系统就没有死锁的危险。即N*2+l<=8,得N<=3。

5.11考虑图5.9所示的资源分配图，哪个进程会发生死锁？

进程P3,P4会发生死锁。

对于进程Pl,P2,进程的推进不需要等待其他进程的完成。

进程P3,P4。P3要等P4完成并释放资源后方能推进。而P4要等到P3完成后才能。结

果是P3,P4都不能完成。形成死锁。

5.12假定有3个人排队等候上电梯。当电梯门打开的时候，3个人都朝门口冲去，但是

门不够大，他们3人不能同时进门。描述解决这种死锁的方法，可以让3个人都上电梯。

说明你的解决方案清除了哪个死锁的必要条件。答：让3个人轮流进电梯。

破坏了死锁发生的4个必要条件中的“不剥夺条件”。

5.13假定一个系统具有四种资源类型，分别为：R={3,7,2,3},最大资源需求数表

如图5.10所示。资源分配器根据图5.11中的表来分配资源，这个状态安全吗？为什么？

图5.10图5.11

答：这个状态安全。存在安全执行序列｛P4,PO,P1,P3,P2｝；

6.9如果一个分页系统能够向用户提供的逻辑地址最大为16页，页面大小为2K,内存

总共有8个存储块。请问逻辑地址应该为多少位？内存空间为多大？

解：逻辑地址应该为4+11=15(位)

内存空间为8*2K=16K

6.10如果一个分页系统的页表存放在内存。

(1)若对内存的一次存取需要L2s,请问一次页面访问的存取需要花多少时间？

(2)若系统配置了联想寄存器，对快表的命中率为70%,假如查询联想寄存器的时间

忽略不计，请问实现一次页面访问的存取时间是多少？

解：(1)访问一次页面的存取需要花费的时间为2*1.2s=2.4s

(2)实现一-次页面访问的存取时间=0.3*1.2s+1.2s=L56s

6.11如果一个分页系统逻辑地址长度为16位，页面大小为4KB,第0、1、2页对应

10、12、14号物理块，请问逻辑地址为2F6AH对应的物理地址为多少？解：逻辑地址为

2F6AH对应的二进制码为：0010111101101010,页号为：2,页内偏移为F6AH。

查询页表2号页面对应14号块，所以，物理地址为1110111101101010,最终物理

地址为:EF6AH

6.12如果内存中有4个空闲块，每个空闲块的大小为10MB。有10个请求，每次请求

1MB的内存大小，对于下面列出的内存分配方法中的每一种，确定所有10个请求都被满足

之后剩余空闲块的大小。

(a)首次适应算法

(b)循环首次适应算法

(c)最佳适应算法

(d)最坏适应算法

解：(a)首次适应算法：块1用完，块2,3,4剩余10MB。

(b)循环首次适应算法：块1,2余7MB,块3.4余8MB。

(c)最佳适应算法：块1用完，块2,3,4余10MB。

进程RiR2思

P。3411

P.2512

p23223

P33113

P40312

进程K.RiR2R3

P。2100

Pi0201

P20100

P30010

P40101

(d)最坏适应算法：块1,2余7MB,块3,4余8MB。

段号始址段长

0200510

190030

|210080

31200500

4180080

｛0,380｝、｛1,20｝、｛1,24｝、｛2,200｝、｛3,500｝、｛4,120｝。

解：｛0,380｝表示为0段，段内偏移为380,物理地址为580；

｛1,20｝表示为1段，段内偏移为20,物理地址为920；

｛1,24｝表示为1段，段内偏移为24,物理地址为924：

｛2,200｝表示为2段，段内偏移为200,已经越界；

（3,500｝表示为3段，段内偏移为500,物理地址为1700；

｛4,120｝表示为4段，段内偏移为120,已经越界。

7.5在分页虚拟存储器管理中，如果已知时间利用率为：CPU20%、分页磁盘92乐外设

50%,请问采取哪些措施可以改善CPU的利用率？解：增大分页磁盘空间。

7.6-个32位地址的计算机系统使用二级页表，虚拟地址为9位顶级页表，11位二级

页表和偏移。请问：页面长度为多少？虚拟地址空间有多少个页面？

解