操作系统第五版费祥林-课后习题答案解析参考

文章描述:-2022年4月14日发(作者:钱朝鼎)第一章操作系统概论1、有一台计算机,具有IMB内存,操作系统占用200KB,每个用户进程各占200KB。如果用户进程等待I/O的时间为80%,若增加1MB内存,则CPU的利用率提高多少?答:设每个进程等待I/O的百分比为P,则n个进程同时等待刀O的概率是Pn,当n个进程同时等待I/O期间CPU是空闲的,故CPU的利用率为1-Pn。由题意可知,除去操作系统,内

-

操作系统第五版费祥林-课后习题答案解析参考
2022年4月14日发
(作者:钱朝鼎)

第一章操作系统概论

1、有一台计算机,具有IMB内存,操作系统占用200KB,每个用户进程各占

200KB。如果用户进程等待I/O的时间为80%,若增加1MB内存,则CPU的

利用率提高多少?

答:设每个进程等待I/O的百分比为P,则n个进程同时等待刀O的概率是

Pn,当n个进程同时等待I/O期间CPU是空闲的,故CPU的利用率为1-Pn。

由题意可知,除去操作系统,内存还能容纳4个用户进程,由于每个用户进程

等待I/O的时间为80%,故:

CPU利用率=l-(80%)4=0.59

若再增加1MB内存,系统中可同时运行9个用户进程,此时:cPu利用率=l-

(1-80%)9=0.87

故增加IMB内存使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的情况?若有,指出发生等待的时刻。

答:画出两道程序并发执行图如下:

(1)两道程序运行期间,CPU存在空闲等待,时间为100至150ms之间(见图

中有部分)

(2)程序A无等待现象,但程序B有等待。程序B有等待时间段为180rns至

200ms间(见图中有部分)

3设有三道程序,按A、B、C优先次序运行,其内部计算和UO操作时间由图

给出。

试画出按多道运行的时间关系图(忽略调度执行时间)。完成三道程序共花多少

时间?比单道运行节省了多少时间?若处理器调度程序每次进行程序转换化时

lms,试画出各程序状态转换的时间关系图。

答:

1)忽略调度执行时间,多道运行方式(抢占式)

:

?

抢占式共用去190ms,单道完成需要260ms,节省70ms。

忽略调度执行时间,多道运行方式(非抢占式)

:

非抢占式共用去180ms,单道完成需要260ms,节省80ms。

2)调度执行时间1ms,多道运行方式(抢占式)

:

调度执行时间ITns,多道运行方式(非抢占式)

:

4在单CPU和两台I/O(I1,12)设备的多道程序设计环境下,同时投入三个

作业运行。它们的执行轨迹如下:

Jobl: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都能并行工作,优先级从高到低为Jobl、Job2和Job3,

优先级高的作业可以抢占优先级低的作业的CPU,但不抢占I1和I2。试求:

(l)每个作业从投入到完成分别所需的时间。(2)从投入到完成CPU的利

用率。(3)I2设备利用率。

答:画出三个作业并行工作图如下(图中着部分为作业等待时间)

:,

(1)Job1从投入到运行完成需110ms,Job2从投入到运行完成需90ms,Job3

从投入到运行完成需110ms.

CPU空闲时间段为:60ms至70ms,80ms至90ms,100ms至110ms。所以CPU

利用率为(110-30)/10=72.7%。

设备I1空闲时间段为:20ms至40ms,90ms至100ms,故I1的利用率为

(110-30)/l10=72.7%。

设备I2空闲时间段为:30ms至50ms,故I2的利用率为(110-20)/110=

81.8%。

5在单CPU和两台I/O(I1,12)设备的多道程序设计环境下,同时投入三个

作业运行。它们的执行轨迹如下:

Jobl:I2(30ms)、CPU(10rns)、I1(30ms)、CPU(10ms)

Job2:I1(20ms)、CPU(20ms)、I2(40ms)

Job3:CPU(30ms)、I1(20ms)

如果CPU、I1和I2都能并行工作,优先级从高到低为Job1、Job2和Job3,

优先级高的作业可以抢占优先级低的作业的CPU。

试求:(l)每个作业从投入到完成分别所需的时间.

(2)每个作业投入到完成CPU的利用率。

(3)I/0设备利用率。

答:画出三个作业并行工作图如下(图中着部分为作业等待时间):

(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%。

6若内存中有3道程序A、B、C,它们按A、B、C优先次序运行。各程序

的计算轨迹为:

A:计算(20)、I/O(30)、计算(10)

B:计算(40)、I/O(20)、计算(10)

c:计算(10)、I/O(30)、计算(20)

如果三道程序都使用相同设备进行I/O(即程序用串行方式使用设备,调度开销

忽略不计)。试分别画出单道和多道运行的时间关系图。两种情况下,CPU的平

均利用率各为多少?

答:分别画出单道和多道运行的时间图

(1)单道运行时间关系图

单道总运行时间为190ms。CPU利用率为(190-80)/190=57.9%

单道运行时间关系图

多道总运行时间为140ms。CPU利用率为(140-30)/140=78.6%

7若内存中有3道程序A、B、C,优先级从高到低为A、B和C,它们单独

运行时的CPU和I/O占用时间为:

如果三道程序同时并发执行,调度开销忽略不计,但优先级高的程序可中断优先

级低的程序,优先级与I/O设备无关。试画出多道运行的时间关系图,并问最

早与最迟结束的程序是哪个?每道程序执行到结束分别用了多少时间?计算三

个程序全部运算结束时的CPU利用率?

答:画出三个作业并发执行的时间图:

(l)最早结束的程序为B,最后结束的程序为C。

(2)程序A为250ms。程序B为220ms。程序C为310ms。

(3)CPU利用率为(310-120)/310=61.3%

有两个程序,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%。

9、在某计算机系统中,时钟中断处理程序每次执行的时间为2ms(包括进程切

换开销)。若时钟中断频率为60HZ,试问CPU用于时钟中断处理的时间比率为

多少?

答:因时钟中断频率为60HZ,所以,时钟周期为:l/60s=50/3ms。在每个时钟周期中,

CPU花2ms执行中断任务。所以,CPU用于时钟中断处理的时间比率为:2(50/3)=6/50=

12%。

第二章处理器管理

1.下列指令中哪些只能在核心态运行?

(l)读时钟日期;(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在按动态优先数调度进程的系统中,每个进程的优先数需定时重新计算。在处

理器不断地在进程之间交替的情况下,重新计算进程优先数的时间从何而来?

答:许多操作系统重新计算进程的优先数在时钟中断处理例程中进行,由于中断

是随机碰到哪个进程,就插入哪个进程中运行处理程序,并把处理时间记在这个

进程的账上。

5若后备作业队列中等待运行的同时有三个作业J1、J2、J3,已知它们各自

的运行时间为a、b、c,且满足a

能获得最小平均作业周转时间。

答:采用短作业优先算法调度时,三个作业的总周转时间为:

Tl==a+(a+b)+(a+b+c)=3a+2b+c①

若不按短作业优先算法调度,不失一般性,设调度次序为:J2、J1、J3。则

三个作业的总周转时间为:

T2=b+(b+a)+(b+a+c)=3b+2a+c②

令②-①式得到:

T2-Tl=b-a>0

可见,采用短作业优先算法调度才能获得最小平均作业周转时间。

6、若有一组作业J1,…,Jn,其执行时间依次为S1,…,Sn。如果这些

作业同时到试出一种作业调度算法到达系统,并在一台单CPU处理器上按单

道方式执行。使得平均作业周转时间最短。

答:首先,对n个作业按执行时间从小到大重新进行排序,则对n个作业:J1

',…,Jn,创门的运行时间满足:S1≤S2≤……≤S(n-l)≤Sn’。那

么有:

由于任何调度方式下,S1'+S2'+S3'+…+Sn’为一个确定的数,而当S1’

≤S2’≤…≤S(n-1)’≤Sn’时才有:0*S1+1*S2+2*S3+…(n-1)Sn

的值最大,也就是说,此时T值最小。所以,按短作业优先调度算法调度时,

使得平均作业周转时间最短。

7、假定执行表中所列作业,作业号即为到达顺序,依次在时刻0按次序1、2、

3、4、5进入单处理器系统。

(1)分别用先来先服务调度算法、时间片轮转算法、短作业优先算法及非强占

优先权调度算法算出各作业的执行先后次序(注意优先权高的数值小);

(2)计算每种情况下作业的平均周转时间和平均带权周转时间。

(1)采用FCFS算法调度作业,运作情况:

(2)采用双算法调度作业,若令时间片长=l,各作业执行情况为:1、2、

3、4、5、l、3、5、1、5、1、5、1、5、1、l、l、1、1。

(3)采用SJF算法调度作业,运作情况:

(4)采用非剥夺优先权算法调度作业,运作情况:

8对某系统进行监测后表明平均每个进程在I/O阻塞之前的运行时间为T。一

次进程‘切换的系统开销时间为S。若采用时间片长度为Q的时间片轮转法,

对下列各种情况算出CPU利用率。

9有5个待运行的作业,各自预计运行时间分别是:9、6、3、5和x,采

用哪种运行次序使得平均响应时间最短?

答:按照最短作业优先的算法可以使平均响应时间最短。x取值不定,按照以下

情况讨论:

10.有5个批处理作业A到E均己到达计算中心,其运行时间分别2、4、6、

8和10分钟:各自的优先级分跳狠掀完为、、飞、飞、氏积5、这里5为最

高级。对于1)时间片轮转算法、2)优先数法、3)短作业优先算法、4)先来

先服务调度算法(按到达次序C、D、B、E、A),在忽略进程切换时间的前

提下,计算出平均作业周转时间。(对l)每个作业获得相同的2分钟长的时间

片;对2)到4)采用单道运行,直到结束。)

答:(l)FCFS调度算法

(2)优先级调度算法

(3)时间片轮转法

按次序ABCDEBCDECDEDEE轮转执行。

(4)SJF调度算法

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分钟长的时间片)。

答:

(1)FCFS调度算法

(2)优先级调度算法

(3)时间片轮转法

按次序ABCDEABDEABEAEA轮转执行。

作业

执行时间

10

6

2

4

8

等待时间

20

l6

4

l2

20

周转时间

30

22

6

16

28

带权周转时间

3

3.66

3

4

3.5

A

B

C

D

E

作业平均周转时间

作业平均带权周转

时间

T=(30+22+6+16+28)/5=20.4

W=(3+3.66+3+4+3.5)/5=3.43

12(l)假定一个处理器正在执行两道作业,一道以计算为主,另一道以输入输

出为主,你将怎样赋予它们占有处理器的优先级?为什么?

(2)假定一个处理器正在执行三道作业,一道以计算为主,第二道以输入输出为

主,第三道为计算与输入输出均匀。应该如何赋予它们占有处理器的优先级使得

系统效率较高?

答:处理器调度算法会考虑以下因素:作业响应时间要求;让CPU尽量和外围

设备并行工作;限制一个计算进程长时间霸占处理器。因而,(1)FO为主作

业优先级高。(2)输入输出为主作业优先级最高,输入输出均匀的作业其次,

而计算为主作业的优先级最低。

13请你设计一种先进的计算机体系结构,它使用硬件而不是中断来完成进程切

换,则CPU需要哪些信息?请描述用硬件完成进程切换的工作过程。

答:该计算机有一个专用硬件寄存器,它始终存放指向当前运行进程的PCB的

指针。当系统中发生了一个事件,如FO结束事件,CPU便可把运行进程的上下

文保存到专用硬件寄存器指针指向的PCB中保护起来,然后,CPU转向中断向

量表,到设备中断处理程序入口,让专用硬件寄存器指针指向(设备)中断服

务例程,于是,便可启动中断服务例程工作。

14设计一条机器指令和一种与信号量机制不同的算法,使得并发进程对共享变

量的使用不会出现与时间有关的错误。

解:

(l)设计机器指令。

设计一条如下的”测试、比较和交换”三地址指令,提供了一种硬件互斥解决方

案:

TC&S

R1R3B2D2

该指令的功能如下:

l)C为一个共享变量,由地址2、即变址(B2)+D2给出,

(2)(Rl)与(C)比较,

(3)如果(Rl)=(C)则(R3)→C,并置条件码为"00",

如果(R1)≠(c)则(C)→Rl,并置条件码为"01".

(2)编写进程访问共享变量的程序。

对每个访问共享变量C的进程,编写访问共享变量的程序段为:

陆界区程序

说明

共享变量C的值保护到RI中。

(C)→Rl;

Rl的值传送到R3中,进程修改共享变量时,先对R3操

loop2:(R1)→R3;

作(不是直接操作C)。

Add/decreaseR3;

R3加1/减1,进程归还/申请由共享变量C代表的

TC&S;

共享资源(假定每次一个)。

R(condition=01)

执行”测试、比较和交换”指令。

loop2;

条件码=01,转向循环loop2;否则离开临界区。

(3)程序执行说明。

此解与互斥使用共享变量的思路绝然不同,并发运行的进程可不互斥地访问它们

的共享变量。此方案认为造成共享变量C值错误的原因在于:一个进程(Pl)

在改变C值的过程中,另一个进程伊2)插进来也改变了C的值,而本进程(Pl)

却不知道,造成了c值结果不正确。如果有办法使本进程口1)能知道C值是

否改变,改变的话在继承改变了的C值的基础上,再作自己的改变操作,则就

不会导致共享变量C值的错误。为此,本解决方案中,当一个进程l)准备改变

C值时,先把C的值保护在Rl中,然后,通过R3来改变共享变量C的值。当

要把新的值(即R3内的值)送C之前,先要判断一下在本进程(P1)工作期

间是否有别的进程口2)插进来也改变了C的值(并发进程P1、P2的执行完

全会造成这种情况),方法是:将扭1)中被保护的C的原来值,与C的当前

值比较,若相等,说明C值未被改变过,则将本进程(Pl)修改过的新值送C(即

(R3)一C);若不相等,说明C值在工作期间被改变过,则应该继承C的

新值(即(C)一Rl)并且返回到loop2处重新对C值计数,以此保证C值的

最终结果的正确性。这里提及”进程工作期间”指的是一个进程从开始至结束对

共享变量C值的操作的这段时间,也就是执行进程,'I晦界区”这段程序的

时间。此外,在进程进入临界区之前,应等待直到C为非。(即有资源可用)

为止。

(4)举例。

假定系统中有静态分配资源磁带机共3台,被个进程共享,由共享变量C来

代表可用磁带机台数,其初值为3。现有并发进程P1和P2均申请使用磁带机,

执行临界区程序。

进程Pl执行临界区程序

(C)→R1;因(C)=3,故(R1)=3。

loop2:(Rl)→R3因(R1)=3,故(R3)当前也=3。

decreaseR3:申请使用磁带机,做减1操作,故(R3)=2.

TC&S执行”测试、比较和交换,,TC&S指令。

如果R1=(C)则(R3)→C,即(C)=2,并置条件码为”00",跳出临界区

程序,去使用磁带机。

如果(Rl)≠(C),例如,(C)=2,说明进程P2抢先申请了磁带机,所以,

C与保护在R1中的值不一样了(C的值必

小于Rl的值),应以C的当前值为准,执行(C)Rl(R1此时变为2),

并置条件码为”01",转向foopZ。于是伍1)=2,跟着(R3卜2。接着

卿)减1后应=l了。再执行TC&S时,由于伍1卜(C)=2,会使C变

为1。

r(conditio二01)loop2;

巧单道批处理系统中,下列三个作业采用先来先服务调度算法和最高响应比优先

算法进行调度,哪一种算法性能较好?请完成下表:

作业

提交时间运行时间开始时间110:002:00

210:101:00

310:250:25

平均作业周转时间=

平均作业带权周转时间W=

完成时间周转时带权周

间转时间

答:

可见HRRF比FIFO要好

16若有如表所示四个作业进入系统,分别计算在FCFS、S开和HRR卫算法下

的平均周转时间与带权平均周转时间。(时间以十进制表示)

答:

17Kleinrock提出一种动态优先权算法:进程在就绪队列等待时,其优先权以

速率a变化;当进程在处理器上运行,时其优先权以速率p变化。给参数a,b赋

以不同值可得到不同算法。(l)若a>b>c是什么算法?(2)若a<b<c

是什么算法

答:(l)是先进先出算法。因为在就绪队列中的进程比在CPU上运行的进程

的优先数提高得快,故进程切换时,先进入就绪队列的进程优先权就越高。

(2)是后进先出算法。因为在就绪队列中的进程比在CPU上运行的进程的优

先权下降得快,故后进入就绪队列的进程此先进入的进程的优先权高。

18有一个四道作业的操作系统,若在一段时间内先后到达6个作业,它们的提

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

系统采用SJF调度算法,作业被调度进入系统后中途不会退出,但作业运行时

可被更短作业抢占。(l)分别给出6个作业的执行时间序列、即开始执行时

间、作业完成时间、作业周转时间。(2)计算平均作业周转时间。

说明:

(1)J2到达时抢占J1;J3到达时抢占J2。

(2)但J4到达时,因不满足SJF,故J4不能被运行,J3继续执行5分钟。

(3)由于是4道的作业系统,故后面作业不能进入主存而在后备队列等待,

直到有作业结束。

(4)根据进程调度可抢占原则,J3第一个做完。而这时J5、J6均己进入后

备队列,而J5可进入主存。

(5)因J5最短,故它第二个完成。这时J6方可进入主存。因J6最短,故

它第三个完成。

(6)然后是:J4、J2和J1

(7)T=(155+95+20+55+15+20)/6=60

19、有一个具有两道作业的批处理系统,作业调度采用短作业优先的调度算法,

进程调度采用以优先数为基础的抢占式调度算法,在下表所示的作业序列,作业

优先数即为进程优先数,优先数越小优先级越高。

(1)列出所有作业进入内存时间及结束时间。

(2)计算平均周转时间。

答:每个作业运行将经过两个阶段:作业调度(SJF算法)和进程调度(优先数

抢占式)。另外,批处理最多容纳2道作业,更多的作业将在后备队列等待。

(l)10:00,作业A到达并投入运行。

(3)10:2O,作业B到达且优先权高于作业A,故作业B投入运行而作业

A在就绪队列等待。

(4)10:30,作业C到达,因内存中已有两道作业,故作业C进入作业后

备队列等待。

(5)10:50,作业B运行结束,作业D到达,按SJF短作业优先算法,作

业D被装入内存进入就绪队列。而由于作业A的优先级高于作业D,故作业A投

入运行

(6)11:10,作业A运行结束,作业C被调入内存,具作业c的优先级高

于作业D,故作业C投入运行。

(7)12:00,作业c运行结束,作业D投入运行。

(8)12:20,作业D运行结束。

各作业周转时间为:作业A70,作业B30,作业C90,作业D90。平均作

业周转时间为70分钟。

20、某多道程序设计系统供用户使用的主存为100K,磁带机2台,打印机1台。

采用可变分区内存管理,采用静态方式分配外围设备,忽略用户作业FO时间。

现有作业序列如下:

作业调度采用FCFS策略,优先分配主存低地址区且不准移动已在主存的作业,

在主存中的各作业平分CPU时间.现求:(l)作业被调度的先后次序?(2)

全部作业运行结束的时间?(3)作业平均周转时间为多少?(4)最大作业周

转时间为多少?

答:(l)作业调度选择的作业次序为:作业1、作业3、作业4、作业2和

作业5.

(2)全部作业运行结束的时间9:30。

(3)周转时间:作业1为30分钟、作业2为55分钟、作业3为40分钟、

作业4为40分钟和作业5为55分钟。

(4)平均作业周转时间=44分钟。

(5)最大作业周转时间为55分钟。

分析:本题综合测试了作业调度、进程调度、及对外设的竞争、主存的竞争。8:

oo作业1到达,占有资源并调入主存运行。

8:20作业2和3同时到达,但作业2因分不到打印机,只能在后备队列等

待。作业3资源满足,可进主存运行,并与作业1平分CPU时间。

8:30作业1在8:30结束,释放磁带与打印机。但作业2仍不能执行,因

不能移动而没有30KB的空闲区,继续等待。作业4在8:30到达,并进入主

存执行,与作业3分享CPU

8:35作业5到达,因分不到磁带/打印机,只能在后备队列等待。

9:00作业3运行结束,释放磁带机。此时作业2的主存及打印机均可满足,

投入运行。作业5到达时间晚,只能等待。

9:10作业4运行结束,作业5因分不到打印机,只能在后备队列继续等待。

9:15巧作业2运行结束,作业5投入运行。

9:30作业全部执行结束。

21、某多道程序设计系统采用可变分区内存管理,供用户使用的主存为200K,

磁带机5台。采用静态方式分配外围设备,且不能移动在主存中的作业,忽略

用户作业I/O时间。现有作业序列如下:

现求:(l)FIFO算法选中作业执行的次序及作业平均周转时间?(2)SJF算

法选中作业执行的次序及作业平均周转时间?(进程调度也采用FCFS)

答:(1)FIFO算法选中作业执行的次序为:A、B、D、C和E作业平均周

转时间为63分钟

(2)SJF算法选中作业执行的次序为:A、B、D、E和C。作业平均周转

时间为58分钟

详细说明:

1.先来先服务算法。说明:

(1)8:30作业A到达并投入运行。注意它所占用的资源。

(2)8:50作业B到达,资源满足进主存就绪队列等CPu。

(3)9:00作业C到达,主存和磁带机均不够,进后备作业队列等待。

(4)9:05作业D到达,磁带机不够,进后备作业队列等待。后备作业队列

有C、D。(5)9:10作业A运行结束,归还资源磁带,但注意主存不能移

动(即不能紧缩)。作业B投入运行。作业C仍因主存不够而等在后备队列。

这时作业E也到达了,。也由于主存不够进入后备作业队列。此时作业D因资

源满足(主存磁带均满足),进主存就绪队列等待。后备作业队列还有C、E。

(6)9:35作业B运行结束,作业D投入运行。这时作业C因资源满足而

调入主存进就绪队列等CPU。而作业E因磁带机不够继续在后备作业队列等待。

(7)9:55作业D运行结束,作业C投入运行。这时作业E因资源满足而

调入主存进就绪队列等CPU。

(8)10:30作业C运行结束,、作业E投入运行。

(9)10:40作业E运行结束。

2.短作业优先算法。说明:

(1)8:30作业A到达并投入运行。注意它所占用的资源。

(2)8:50作业B到达,资源满足进主存就绪队列等CPU。

(3)9:00作业C到达,主存和磁带机均不够,进后备作业队列等待。

(4)9:05作业D到达,磁带机不够,进后备作业队列等待。后备作业队列

有C、D.

(5)9:10作业A运行结束,归还资源磁带,但注意主存不能移动(即不能

紧缩)。作业B投入运行。作业C仍因主存不够而等在后备队列。这时作业E也

到达了,虽然该作业最短,也由于主存不够进入后备作业队列.此时作业D因

资源满足(主存磁带均满脚,进主存就绪队列等待。后备作业队列还有C、E。

(6)9:35作业B运行结束,作业D投入运行。这时作业C和E资源均满

足,但按SJF应把作业E调入主存进就绪队列等CPU。而作业C因磁带机不够

继续在后备作业队列等待。

(7)9:55作业D运行结束,作业C调入主存进就绪队列等CPU.

(8)10:05作业E运行结束,作业C投入运行.

(9)10:40作业C运行结束。

上题中,若允许移动己在主存中的作业,其他条件不变,现求:(l)FIFO算

法选中作业执行的次序及作业平均周转时间?(2)SJF算法选中作业执行的次

序及作业平均周转时间?

第三章同步、通讯与死锁

1、有三个并发进程:R负责从输入设备读入信息块,M负责对信息块加工处理;

P负责打印输出信息块。今提供;

l)一个缓冲区,可放置K个信息块;

2)二个缓冲区,每个可放置K个信息块;

试用信号量和P、V操作写出三个进程正确工作的流程。

答:

1)varB:array[0,k-1]ofitem;

sread:semaPhore:=k;

smanage:semaPhore:=0;

swrite:semaphore:=0;

rptr:integer:=O;

mptr:integer:=O;

wptr:integer:=0;

x:item

cobegin

processreader;processmanager;processwriter;

beginbeginbegin

LI:readamessageintox;L2:P(smanage);L3:P(swnte);

P(sread);x:=B[mptr];x:=B[swrite];

B[rptr]:=x;mptr:=(mptr+1)modk;wptr:=(wptr+1)modk;

Rptr:=(rptr+1)modk;managethemessageinx;V(sread);

V(smanage);B[mptr]:=x;printthemessageinx;

GotoL1;V(swrite);gotoL3;

End;gotoL2;end;

End;

coend

2)varA,B:array[0,k-l]ofitem;

sPut1:semaphore:=k;

SPut2:semaPhore:=k;

sget1:semaPhore:=0;

sget2:semaphore:=0;

put1:integer:=O;

put2:integer:=0;

get1:integer:=O;

get2:integer:=O;

cobegin

processreader;processnmanager;processWriter;

beginbeginbegin

Ll:readamessageintox;L2:P(sgetl);L3:P(sgetZ);

P(SPut1);x:=A[get1];x:=B[get2];

A[put1]:=x;get1:(get1+1)modk;get2:=(get2+l)modk;

Put1:=(put1+1)modk;V(sput1);V(sput2);

V(sget1);managethemessageintox;printthemessageinx;

GotoL1;P(sput2);gotoL3;

Put2:=(put2+1)modk;

V(sget2);

GotoL2;

End;

Coend

2设有n个进程共享一个互斥段,如果:

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

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

试问:所采用的信号量初值是否相同?信号量值的变化范围如何?

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

1)互斥信号量初值为1,变化范围为[-n+l,1]。

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

等待进入互斥段时,信号量值为O;当有1个进程进入互斥段且有一个进程等待

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

时信号量的值应为-(n-1)也就是-n+1。

2)互斥信号量初值为m,变化范围为[-n+m,m]。

当没有进程进入互斥段时,信号量值为m;当有1个进程进入互斥段但没有进程

等待进入互斥段时,信号量值为m-1:当有m个进程进入互斥段且没有一个进

程等待进入互斥段时,信号量值为0:当有m个进程进入互斥段且有一个进程等

待进入互斥段时,信号量值为一l;最多可能有n-m个进程等待进入互斥段,

故此时信号量的值应为-(n-m)也就是-n+m.

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

均为0。试问Pl、P2并发执行后,x、y、z的值各为多少?

P1:P2:

Beginbegin

Y:=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+y;z:=z+x;

Endend

答:现对进程语句进行编号,以方便描述.

P1:P2:

beginbegin

y:=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+y;④z:=Z+X;⑧

Endend

①、②、⑤和⑥是不相交语句,可以任何次序交错执行,而结果是唯一的。接

着无论系统如何调度进程并发执行,当执行到语句⑦时,可以得到x=10,y=

4。按Bernstein条件,语句③的执行结果不受语句⑦的影响,故语句③执行

后得到z=5。最后,语句④和⑧并发执行,这时得到了两种结果为:

语句④先执行:x=10,y=9,z=150

语句⑧先执行:x=10,y=19,z=15

此外,还有第三种情况,语句③被推迟,直至语句⑧后再执行,于是依次执行以

下三个语句:

7:二z+X:

z:=y+1;

y:=Z十y;

这时z的值只可能是y+1=5,故y=Z+Y=5+4=9,而x=10。

第三种情况为:x=10,Y=9,Z=5。

4有一阅览室,读者进入时必须先在一张登记表上登记,该表为每一座位列出一个

表目,包括座号、姓名,读者离开时要注销登记信息;假如阅览室共有100个座

位。试用:l)信号量和P、V操作;2)管程,来实现用户进程的同步算法。

答:1)使用信号量和P、v操作:

varname:array[l…100]ofA;

A=record

number:integer;

name:string;

end

fori:=1to100do{A[i].number:i;A[i].name:null;}

mutex,seatcount:semaphore;

i:integer;mutex:=l;seatcount:=100;

cobegin

{

processreaderi(varreadename:string)(i=1,2…)

{

P(seatcount);

P(mutex);

fori:=1to100doi++

ifA[i].name=nullthenA[i].name:readername;

readergettheseatnumber=i;/*A[I].number

V(mutex)

进入阅览室,座位号i,座下读书;

P(mutex);

A[i]name:null;

V(mutex);

V(seatcount);

离开阅览室;

}

}

coend

2)使用管程操作:

TYPEreadbook=monitor

VARR:condition;

I,seatcount:integer;

name:array[l:100]ofstring;

DEFIErcadercome,readerleave;

USEcheck,wait,signal,release;

Procedurereadercome(readername)

begin

check(IM);

ifseatcount≥100wait(R,IM)

seatcount:=seatcount+1;

fori=1to100doi++

ifname[i]==nullthenname[i]:=readername;

gettheseatnumber=i;

release(IM);

end

procedurereaderleave(readername)

begin

check(IM);

seatcount--;

fori=1to100doi++

ifname[i]readernamethenname[i]:null;

release(IM);

end

begin

seatcount:=1OO;name:=null;

end

cobegin

{

processreaderi(i=1,2.…)

begin

readercome(readername);

readthebook;

readerleave(readername);

leavethereadroom;

end

}

coend.

5.在一个盒子里,混装了数量相等的黑白围棋子·现在用自动分拣系统把黑子、

白子分开,设分拣系统有二个进程P1和P2,其中P1拣白子;P2拣黑子。规定

每个进程每次拣一子;当一个进程在拣时,不允许另一个进程去拣;当一个进程拣

了一子时,必须让另一个进程去拣.试写出两进程P1和P2能并发正确执行的程

序。

答1:实质上是两个进程的同步问题,设信号量s1和s2分别表示可拣白子和黑

子,不失一般性,若令先拣白子。

varS1,S2:semaphore;

S1:=l;S2:=0;

cobegin

{

processP1

begin

repeat

P(S1);

拣白子

V(S2);

untilfalse;

end

processP2

begin

repeat

P(S2);

拣黑子

V(S1);

untilfalse;

end

}

coend.

答2:

TYPEpickup-chess=MOITOR

VARflag:boolean;

S-black,s-white:codition;

DEFIEpickup-black,pickup-white;

USEwait,signal,check,release;

procedurepickup-black;

begin

check(IM);

ifflagthenwait(s-black,IM);

flag:=true;

pickupablack;

signal(S-white,IM);

release(IM);

end

procedurepickup-white;

begin

check(IM);

ifnotflagthenwait(S-white,IM);

flag:=false;

pickupawhite;

signal(S-black,IM);

release(IM);

end

begin

flag:=true;

end

main()

{cobegin

process-B();

process-W();

coend

}

process-B()

begin

-black();

other;

end

process-W()

begin

-white();

other;

end

6管程的同步机制使用条件变量和wait及signal,尝试为管程设计一种仅仅使

用一个原语操作的同步机制。

答:可以采用形如waituntil<条件表达式>的同步原语。如waituntil

(numbersum+number

和小于K时,系统应唤醒该进程工作.

7设公共汽车上,司机和售票员的活动分别如下:

司机的活动:启动车辆:正常行车;到站停车。

售票员的活动:关车门;售票;开车门。

在汽车不断地到站、停车、行驶过程中,这两个活动有什么同步关系?用信号量和

P、V操作实现它们的同步。

答:在汽车行驶过程中,司机活动与售票员活动之间的同步关系为:售票员关车门

后,向司机发开车信号,司机接到开车信号后启动车辆,在汽车正常行驶过程中售

票员售票,到站时司机停车,售票员在车停后开门让乘客上下车。因此,司机启动

车辆的动作必须与售票员关车门的动作取得同步;售票员开车门的动作也必须与司

机停车取得同步。应设置两个信号量:S1、S2;S1表示是否允许司机启动汽车(其

初值为0);S2表示是否允许售票员开门(其初值为0)。用P、v原语描述如

下:

varS1,S2:semaphore;

S1=0;S2=0;

cobegin

{

driver();

busman();

}

coend

driver()

begin

while(1){

P(S1)

启动车辆;正常行车;到站停车;

V(S2);

}

end

busman()

begin

while(1){

关车门;

V(51)

售票;

P(S2)

开车门;

上下乘客;

}

end

8、一个快餐厅有4类职员:(l)领班:接受顾客点菜;(2)厨师:准备顾客

的饭菜;(3)包工:将做好的饭菜打包;(4)出纳员:收款并提交食品。每个

职员可被看作一个进程,试用一种同步机制写出能让四类职员正确并发运行的程

序。

答:典型的进程同步问题,可设四个信号量51、S2、S3和S4来协调进程工作。

varS1,S2,S3,S4:semaphore;

S1:=1;S2:=S3:=S4:=0;

cobegin

{processP1

begin

repeat

有顾客到来;

P(S1);

接受顾客点菜;

V(52);

untilefalse;

end

processP2

begin

repeat

P(S2);

准备顾客的饭菜;

v(S3);

untilefalse;

end

processP3

begin

repeat

P(S3);

将做好的饭菜打包;

V(S4);

untilefalse;

end

processP4

begin

repeat

P(54);

收款并提交食品;V(51);

ufltilefalse;

end

}

coend.

9、在信号量S上作P、v操作时,S的值发生变化,当S>0、S=0、S<0时,它

们的的物理意义是什么?

答:S的值表示它代表的物理资源的使用状态:S>0表示还有共享资源可供使用。

S阅表示共享资源正被进程使用但没有进程等待使用资源。S<0表示资源已被分

配完,还有进程等待使用资源。

10(1)两个并发进程并发执行,其中,A、B、C、D、E是原语,试给出可

能的并发执行路径。

ProcessPProcessQ

beginbegin

A;D;

B;E;

C;end:

end;

(2)两个并发进程P1和P2并发执行,它们的程序分别如下:

P1P2

repeatrepeat

k:=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;

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。

(2)把语句编号,以便于描述:

P1P2

repeatrepeat

k:=k×2;①printk;③

k:=k+l;②k:=0;④

untilfalse;untilfalse;

l)K的初值为5,故P1执行两个循环后,K=23。

2)语句并发执行有以下情况:

①、②、③、④,这时的打印值为:47

③、④、①、②,这时的打印值为:23

①、③、②、④,这时的打印值为:46

①、③、④、②,这时的打印值为:46

③、①、②、④,这时的打印值为:23

③、①、④、②,这时的打印值为:23

由于进程P1和P2并发执行,共享了变量K,故产生了‘结果不唯一’。

11证明信号量与管程的功能是等价的:

(l)用信号量实现管程;

(2)用管程实现信号量。

答:(1)用信号量实现管程;

Hoare是用信号量实现管程的一个例子,详见课文内容。下面介绍另一种简单方法:

每一个管程都对应一个mutex,其初值为1,用来控制进程互斥调用管程。再设

一个初值为0的信号量,用来阻塞等待资源的进程。相应的用信号量实现的管程

库过程为:

Varmutex,c:semaphore;

mutex:=1;c:=0;

voidenter-monitor()/*进入管程代码,保证互斥

P(mutex);

}

voidleave-monitor-normally()/*不发信号退出管程

{

V(mutex);

}

voidleave-with-sigal(c)/*在条件c上发信号并退出管程,释放一个等待c条

件的进程。{注意这时没有开放管程,因为刚刚被释放的进程己在管程中。

V(c);

}

voidwait(c)/*等待条件c,开放管程

{

V(mutex);

P(c);

}

(2)用管程实现信号量。

TYPEsemaphore=monitor

VARS;condition;

C:integer;

DEFIEP,V;

USEcheck,wait,signal,release;

procedureP

begin

check(IM);

C:=C-1:

ifC<0thenwait(S,IM);

release(IM);

end

procedureV

begin

check(IM):

C:=C+1;

ifC≤0thensignal(S,IM);

release(IM);

end

begin

C:=初值;

End.

12证明消息传递与管程的功能是等价的:

(1)用消息传递实现管程;

(2)用管程实现消息传递。

答:(1)用消息传递实现管程;

用消息传递可以实现信号量(见13(2)),用信号量可以实现管程(见11(1)),

那么,把两种方法结合起来,就可以用用消息传递实现管程。

(2)用管程实现消息传递。

TYPEmailbox=monitor

VARr,k,count:integer;

buffer:array[0…n-1]ofmessage;

full,empty:condition;

DEFIEadd,get;

USEcheck,wait,signal,release;

procedureadd(r);

begin

check(IM);

ifcount=nthenwait(full,IM);

buffer[r]:=message;

r:=(r+1)modn

count:=count+1;

ifcount=1thensighal(empty,IM);

release(IM);

end

procedureget(m);

begin

check(IM);

ifcount=0thenwait(empty,IM);

m:=buffer[k」;

count:=count-1;

ifcount=n-1thensignal(full,IM);

release(IM);

end

begin

r:=0;k:=0;count:=0;

end

13证明信号量与消息传递是等价的:

(1)用信号量实现消息传递;

(2)用消息传递实现信号量。

答:(l)用信号量实现消息传递;

1)把消息队列组织成一个共享队列,用一个互斥信号量管理对该队列的入队操作

和出队操作.

2)发送消息是一个入队操作,当队列存储区满时,设计一个同步信号量阻塞send

操作。

3)接收消息是一个出队操作,当队列存储区空时,设计另一个同步信号量阻塞

receive操作。

(2)用消息传递实现信号量。

l)为每一个信号量建立一个同步管理进程,它包含了一个计数器,记录信号量值;

还为此信号量设立一个等待进程队列

2)应用进程执行P或V操作时,将会调用相应P、V库过程。库过程的功能是:

把应用进程封锁起来,所执行的P、V操作的信息组织成消息,执行send发送给

与信号量对应的同步管理进程,之后,再执行receive操作以接收同步管理进程

的应答。

3)当消息到达后,同步管理进程计数并查看信号量状态。如果信号量的值为负的

话,执行P操作的应用进程被阻塞,挂到等待进程队列,所以,不再要送回答消

息。此后,当V操作执行完后,同步管理进程将从信号量相应队列中选取一个进

程唤醒,并回送一个应答消息。正常情况下,同步管理进程回送一个空应答消息,

然后,解锁执行P、V操作的应用程序。

14使用(1)消息传递,(2)管程,实现生产者和消费者问题。答:(1)见课

文ch33.5.4节。(2)见课文Ch33.4.3节。

15试利用记录型信号量和P、V操作写出一个不会出现死锁的五个哲学家进餐问

题的算法。答:

varforki:array[0…4]ofsemaphore;

forki:=1;

cobegin

{

processPi/*i=0,1,2,3*/

begin

L1:

思考:

P(fork[i]);/*i=4,P(fork[0])*/

P(fork[i+1]mod5)/*i=4P(fork[4])*/

吃通心面;

V(fork[i];

V(fork([i+1]mod5);

gotoL1;

end;

}

coend;

16Dijkstra临界区软件算法描述如下:

varflag:array[0…n]of(idle,want-in,in_cs);

turn:integer;tune:0or1or…or,n-1;

processPi(i=0,1,…,n-1)

varj;integer;

begin

repeat

repeat

flag[i]:want_in;

whileturn≠1do

ifflag[turn]==idlethenturn:=i;

flag[i]:=ip_cs;

j:=0;

while(j

doj:=j+1;

untilj≥n:

criticalsection;

flag[i]:=idle;

……

untilfalse;

end.

试说明该算法满足临界区原则。

答:为方便描述,把Dijkstra程序的语句进行编号:

repeat

flag[i]:=want_in;①

whileturn≠ido②

ifflag[trun]==idlethenturn:=i;③

flag[i]:=in_cs;④

j:=O;

while(j

doj:=j+1;@

untilj≥n;

criticalsection;

flag[i]:=idle;⑦

(l)满足互斥条件

当所有的巧都不在临界区中,满足flag[j]≠in_cs(对于所有j,j≠i)条件时,

Pi才能进入它的临界区,而且进程Pi不会改变除自己外的其他进程所对应的

flag[j]的值。另外,进程Pi总是先置自己的flag[j]为in_cs后,才去判别Pj

进程的flag[j]的值是否等于in_cs所以,此算法能保证n个进程互斥地进入临

界区。

(2)不会发生无休止等待进入临界区

由于任何一个进程Pi在执行进入临界区代码时先执行语句①,其相应的flag[i]

的值不会是idle。注意到flag[i]=in_cs并不意味着turn的值一定等于i。

我们来看以下情况,不失一般性,令turn的初值为0,且P0不工作,所以,

flag[turn]=flag[0]=idle。但是若干个其他进程是可能同时交替执行的,假设让

进程Pj(j=l,2,…n-l)交错执行语句①后(这时flag[j]=want_in),再做

语句②(第一个while语句),来查询flag[turn]的状态。显然,都满足turn

≠i,所以,都可以执行语句③,让自己的turn为j。但turn仅有一个值,该

值为最后一个执行此赋值语句的进程号,设为k、即turn=k(1≤k≤n-1)。接

着,进程Pj(j=1,2,…n-l)交错执行语句④,于是最多同时可能有n-1个进程

处于in_cs状态,但不要忘了仅有一个进程能成功执行语句④,将加m置为自己

的值。

假设{P1,P2,…Pm}是一个己将flag[i]置为in_cs(i=1,2,…,m)(m

≤n-1)的进程集合,并且已经假设当前turn=k(1≤k≤m),则Pk必将在有

限时间内首先进入临界区。因为集合中除了Pk之外的所有其他进程终将从它们执

行的语句⑤(第二个while循环语句)退出,且这时的j值必小于n,故内嵌

until起作用,返回到起始语句①重新执行,再次置flag[i]=want_in,

继续第二轮循环,这时的情况不同了,flag[turn]=flag[k]必定≠idle(而为

in_cs)。而进程Pk发现最终除自身外的所有进程Pj的flag[j]≠in_cs,并

据此可进入其临界区。

17另一个经典同步问题:吸烟者问题(patil,1971)。三个吸烟者在一个房间

内,还有一个香烟供应者。为了制造并抽掉香烟,每个吸烟者需要三样东西:烟草、

纸和火柴,供应者有丰富货物提供。三个吸烟者中,第一个有自己的烟草,第二个

有自己的纸和第三个有自己的火柴。供应者随机地将两样东西放在桌子上,允许一

个吸烟者进行对健康不利的吸烟。当吸烟者完成吸烟后唤醒供应者,供应者再把两

样东西放在桌子上,唤醒另一个吸烟者。试采用:(1)信号量和P、v操作,(2)

管程编写他们同步工作的程序。答:(1)用信号量和P、v操作。

vars,S1,S2,S3;semaphore;

S:=1;S1:=S2:=S3:=0;

fiag1,flag2,fiag3:Boolean;

fiag1:=flag2:=flag3:=true;

cobegin

{

process供应者

begin

repeat

P(S);

取两样香烟原料放桌上,由flagi标记;/*nago1、nage2、nage3代表烟草、

纸、火柴

ifflag2&flag3thenV(S1);/*供纸和火柴

elseifflag1&fiag3thenV(S2);/*供烟草和火柴

elseV(S3);/*供烟草和纸

untilefalse;

end

process吸烟者1

begin

repeat

P(S1);

取原料;

做香烟;

V(S);

吸香烟;

untilefalse;

process吸烟者2

begin

repeat

P(S2);

取原料;

做香烟;

V(S);

吸香烟;

untilefalse;

process吸烟者3

begin

repeat

P(S3);

取原料;

做香烟;

V(S);

吸香烟;

untilefalse;

coend.

(3)用管程。

TYPEmskesmoke=moonitor

VARS,S1,S2,S3:condition;

flag1,flag2,flag3:boolean

DEFIEgive,take1,take2,take3;

USEcheck,wait,signal,release;

proceduregive

begin

check(IM);

准备香烟原料;

if桌上有香烟原料thenwait(S,IM);把准备的香烟原料放桌上;

iffiag2&flag3thensignal(S1,IM);

ifflag1&flag3thensignal(S2,IM);elsesignal(S3,IM);

release(IM);

end

proceduretake1

begin

check(IM):

if桌上没有香烟原料thenwait(S1,IM);

else取原料;

signal(S,IM);

release(IM);

end

proceduretake2

begin

check(IM):

if桌上没有香烟原料thenwait(S2,IM);

else取原料;

signal(S,IM);

release(IM);

end

proceduretake3

begin

check(IM):

if桌上没有香烟原料thenwait(S3,IM);

else取原料

signal(S,IM);

release(IM);

end

begin

flag1:=flag2:=flag3:=true;

end.

cobegin

{

process供应者

begin

repeat

();

……

untilfalse;

end

process吸烟者1

begin

repeat

1();

做香烟,吸香烟;

untilfalse;

end

process吸烟者2

begin

repeat

2();

做香烟,吸香烟;

untilfalse;

end

process吸烟者3

begin

repeat

3();

做香烟,吸香烟;

untilfalse;

end

}

coend.

18、如图所示,四个进程Pi(i=0…3)和四个信箱Mj(j=0…3),进程间

借助相邻信箱传递消息,即Pi每次从Mi中取一条消息,经加工后送入M(i+1)

mod4,其中M0、M1、M2、M3;可存放3、3、2、2个消息。初始状态下,

MO装了三条消息,其余为空。试以P、V为操作工具,写出Pi(i=0…3)的同步

工作算法

答:

varmutexl,mutexZ,mutex3,mutex0:semaphore;

Mutex1=nutex2:=mutex3:=mutex0:=1;

Empty0,empty1,empty2,empty3;semaphore;

empty:=0;empty1:=3;empty:=2:=empty3:=2;

full0,full1,full2,full3:semphore;

full0:=3;full1:=full2:=full3:=0;

in0,in1,in2,in3,out0,out2,out3,;intger;

in0:=in1:=in2:=in3:=out0:=out1:=out2:=out3:=0;

cobegin

{

processP0

begin

repeat

P(full0);

P(mutex0);

从M0[out0]取一条消息;

out0:=(out0+1)mod3;

V(mutex0);

V(empty0);

加工消息;

P(empty1);

P(mutex1);

消息已M1[in1];

In1:=(in1+1)mod3;

V(mutex1);

V(full1);

untilefalse;

end

processP1

begin

repeat

P(full1);

P(mutex1);

从M1[out1]取一条消息;

Out1:=(out1+1)mod3;

V(mutex1);

V(empty1);

加工消息;

P(empty2);

P(mutex2);

消息己M2[in2];

In2:=(in2+1)mod2;

V(mutex2);

v(full2);

untilefalse;

end

processP2

begin

repeat

P(full2);

P(mutex2);

从M2[out2]取一条消息;

out2:=(out2+l)mod2;

V(mutex2);

V(empty2);

加工消息;

P(empty3);

P(mutex3);

消息己M3[in3];

in3:=(in3+1)mod2;

V(mutex3);

V(full3);

untilefalse;

end

processP3

begin

repeat

P(full3);

P(mutex3);

从M3[out3]取一条消息;

out3:=(out3+1)mod2;

V(mutex3);

V(empty3);

加工消息;

P(empty0);

P(mutex0);

消息己MO[in0];

In0:=(in0+1)mod3;

V(mutex0);

V(full0);

untilefalse;

end

{

coend

19、有三组进程Pi、Qj、Rk,其中Pi、Qj构成一对生产者和消费者,共享一

个由M1个缓区构成的循环缓冲池buf1。Qj、Rk凡构成另一对生产者和消费者,

共享一个由M2个缓冲区构成的循环缓冲池buf2。如果Pi每次生产一个产品投入

buf1,Qj每次从中取两个产品组装成一个后并投入buf2,Rk每次从中取三个产品

包装出厂.试用信号量和P、V操作写出它们同步工作的程序。

答:

varmutex1,mutex2,mutex3:semaphore;

empty1,empty2,full1,full2;semaphore;

in1,in2,out1,out2:integer;counter1,counter2:integer;

buffer1:array[0…M1-1]ofitem;buffer2:array[0…M2-1]ofitem;

empty1:=M1;empty:=M2;

in1:=in2:=out1:=out2:=0;counter1:=counter2:=0;

fun1:=full2:=mutex1:=mutex2:=mutex3:=1;

cobegin

{

processPi

begin

L1:

P(empty1);

P(mutex1);

putanitemintobuffer[in1];

in1:=(in1+1)modM1;

counter++;

ifcounter1=2then{counter1:=0;V(full1);}

V(mutex);

gotoL1;

end

processQj

begin

L2:

P(full2);

P(mutex1);

takeanitemfrombuffer1[out1];

out1:=(out1+1)modM1;

takeanitemfrombuffer1[out1];

out1:=(out1+1)modM1;

V(mutex1);

V(empty1);

V(empty1);

Processtheproducts;

P(emPty2);

P(mutex2);

putanitemintobuffer2[in2];

in2:=(in2+l)modM2;

counter2++;

ifcounter2=3then{counter2:=0;V(full2);}

V(mutex2);

gotoL2;

processRk

beginL3:

P(full2);

P(mutex2);

takeanitemfrombuffer2[out2];

out2:=(out2+1)modM2;

takeanitemfrombuffer2[out2];

out2:=(out2+1)modM2;

takeanitemfrombuffer2[out2];

out2:=(out2+1)modM2;

v(mutex2);

V(empty2);

V(empty2);

V(empty2);

packettheproducts;

gotoL3;

end

}

coend

20在一个实时系统中,有两个进程P和Q,它们循环工作。P每隔1秒由脉冲

寄存器获得输入,并把它累计到整型变量W上,同时清除脉冲寄存器。Q每隔1小

时输出这个整型变量的内容并将它复位。系统提供了标准例程创PUT和OUT卫UT

供拍,提供了延时系统调用Delay(seconds)。试写出两个并发进程循环工作

的算法。

答:

VarW,V:integer;

Mutex:semaphore;

W:=0;V:=0;mutex:1;

cobegin{

processP

begin

repeat

P(mutex);

delay(1);

V=IPUT;

W:=W+V;

清除脉冲寄存器;

V(mutex);untilefalse;

end

processQ

begin

repeat

P(mutex);

delay(60);

OUTPUT(W);

W:=0;

V(mutex);

untilefalse;

}

coend.

21系统有同类资源m个,被n个进程共享,问:当m>n和m≤n时,每个进程

最多可以请求多少个这类资源时,使系统一定不会发生死锁?

答:当m≤n时,每个进程最多请求1个这类资源时,系统一定不会发生死锁。当

m>n时,如果m/n不整除,每个进程最多可以请求”商+1”个这类资源,否

则为”商”个资源,使系统一定不会发生死锁?

22个进程共享M个资源,每个进程一次只能申请释放一个资源,每个进程最多

需要M个资源,所有进程总共的资源需求少于M+个,证明该系统此时不会产生

死锁。

答卜设max(i)表示第i个进程的最大资源需求量,need(i)表示第i个

进程还需要的资源量,alloc(i)表示第i个进程已分配的资源量。由题中所

给条件可知:

max(1)+…+max(n)=(need(1)+…+need(n))+((alloc(1)+…+alloc(n))

如果在这个系统中发生了死锁,那么一方面m个资源应该全部分配出去,alloc(1)

+…+alloc(n)=m

另一方面所有进程将陷入无限等待状态。可以推出

need(1)+…+need(n)

上式表示死锁发生后,n个进程还需要的资源量之和小于n,这意味着此刻至少

存在一个进程i,need(i)=0,即它已获得了所需要的全部资源。既然该进

程已获得了它所需要的全部资源,那么它就能执行完成并释放它占有的资源,这与

前面的假设矛盾,从而证明在这个系统中不可能发生死锁。

答2:由题意知道,n×m

等式变换n×(m-1)+n

即n×(m-1)

于是有n×(m-1)+1

或n×(m-1)+1≤m

这说明当n个进程都取得了最大数减1个即(m-1)个时,这时至少系统还有一

个资源可分配。故该系统是死锁无关的。

23一条公路两次横跨运河,两个运河桥相距100米,均带有闸门,以供船只通过

运河桥。运河和公路的交通均是单方向的。运河上的运输由驳船担负。在一驳船接

近吊桥A时就拉汽笛警告,若桥上无车辆,吊桥就吊起,直到驳船尾P通过此桥

为止。对吊桥B也按同样次序处理。一般典型的驳船长度为200米,当它在河上

航行时是否会产生死锁?若会,说明理由,请提出一个防止死锁的办法,并用信号

量来实现驳船的同步。

答:当汽车或驳船未同时到达桥A时,以任何次序前进不会产生死锁。但假设汽

车驶过了桥A,它在继续前进,并且在驶过桥B之前,此时有驳船并快速地通过

了桥A,驳船头到达桥B,这时会发生死锁。因为若吊起吊桥B让驳船通过,则

汽车无法通过桥B;若不吊起吊桥B让汽车通过,则驳船无法通过桥B。可用两

个信号量同步车、船通过两座桥的动作。

varSa,Sb:semaphore;

Sa:=Sb:=1;

cobegin

{

process驳船

begin

P(Sa);

P(Sb);

船过桥A、B;

V(Sa);

V(Sb);

end

process汽车

begin

P(Sa);

P(Sb);

车过桥A、B;

V(Sa);

V(Sb);

end

}

coend

24Jurassic公园有一个恐龙博物馆和一个花园,有m个旅客租卫辆车,每辆车仅

能乘一个一旅客。旅客在博物馆逛了一会,然后,排队乘坐旅行车,挡一辆车可用

喊飞它载入一个旅客,再绕花园行驶任意长的时间。若n辆车都己被旅客乘坐游

玩,则想坐车的旅客需要等待。如果一辆车己经空闲,但没有游玩的旅客了,那么,

车辆要等待。试用信号量和P、V操作同步m个旅客和n辆车子。

答:这是一个汇合机制,有两类进程:顾客进程和车辆进程,需要进行汇合、即顾

客要坐进车辆后才能游玩,开始时让车辆进程进入等待状态

varsc1,sck,sc,Kx,xc,mutex:semaphore;

sck:=kx:=sc:=xc:=0;

sc1:=n;mutex:=1;

sharearea:一个登记车辆被服务乘客信息的共享区;

cobegin

process顾客i(i=1,2,…)

begin

P(sc1);/*车辆最大数量信号量

P(mutex);/*封锁共享区,互斥操作

在共享区sharearea登记被服务的顾客的信息:起始和到达地点,行驶时间

V(sck);/*释放一辆车,即顾客到一辆空车

P(Kx);/*待游玩结束之后,顾客等待下车

V(sc1);/*空车辆数加1

End

Process车辆j(j=1,2,3…)

Begin

L:P(sck);/*车辆等待有顾客来使用

在共享区sharearea登记那一辆车被使用,并与顾客进程汇合;

V(mutex);/*这时可开放共享区,让另一顾客雇车

V(kx);/*允许顾客用此车辆

车辆载着顾客开行到目的地;

V(xc);/*允许顾客下车

GotoL;

End

coend

25今有k个进程,它们的标号依次为1、2、…、k,如果允许它们同时读文

件file,但必须满足条件:参加同时读文件的进程的标号之和需小于K,请使用:

1)信号量与P、v操作,2)管程,编写出协调多进程读文件的程序。

答1:l)使用信号量与P、v操作

varwaits,mutex:semphore;

numbersum:integer:=0;

wait:=0;mutex:=1;

cobegin

{

processreaderi(varnumber:integer;)

begin

P(mutex);

L:ifnumbersum+number≥Kthen{V(mutex);P(waits);gotoL;}

Thennumbersum:numbersum+number;

V(mutex);

Readfile;

P(mutex);

numbersum:=numbersum-number;

V(waits);

V(mutex);

2)使用管程:

TYPEsharefile=MOITOR

VARnumbersum,n:integer;

SF:codition;

DEFIEstartread,endread;

USEwait,signal,check,release;

procedurestartread(varnumber:integer:);

begin

check(IM);

L:if(number+numbersum)≥Kthen{wait(SF,IM);gotoL;}

umbersum:=numbersum+number;

release(IM);

end

procedureendread(varnumber:integer;);

begin

check(IM);

numbersum:=numbersum-number;

signal(SF,IM);

release(IM);

end

begin

numbersum:=0

end.

main()

{cobegin

process-i();

coend

}

process-i()

varnumber:integer;

begin

number:=进程读文件编号;

startread(number);;

readF;

endread(number);

end

26、设当前的系统状态如下:系统此时

Available=(1,1,2):

l)计算各个进程还需要的资源数Cki-Aki

(2)系统是否处于安全状态,为什么?

(3)P2发出请求向量request2(1,o,1),系统能把资源分给它吗?

(4)若在P2申请资源后,若P1发出请求向量req够stl(1,0,l),系统

能把资源分给它吗?

(5)若在P1申请资源后,若P3发出请求向量request3(0,0,l),系统

能把资源分给它吗?

答:(1)P1,P2,P3,P4的分别为:(2,2,2)、(1,0,

2)、(1,0,3)、(4,2,0)(4)系统处于安全状态,存在安全序:

P2,P1,P3,P4

(5)可以分配,存在安全序列:P2,P1,P3,P4.

(6)不可以分配,资源不足。

(7)不可以分配,不安全状态。

27系统有A、B、C、D共4种资源,在某时刻进程PO、Pl、PZ、P3和P4对

资源的占有和需求情况如表,试解答下列问题:

系统此时处于安全状态吗?

若此时P2发出request2(1、2、2、2),系统能分配资源给它吗?为什么?

答:(l)系统处于安全状态,存在安全序列:P0,P3,P4,P1,P2。

(2)不能分配,否则系统会处于不安全状态。

28把死锁检测算法用于下面的数据,并请问:

Available=(1,0,2,0)

(l)此时系统处于安全状态吗?

(2)若第二个进程提出资源请求request2(0,0,1,0)系统能分配资源

给它吗?

(3)执行(2)之后,若第五个进程提出资源请求request5(0,0,1,0)系统能

分配资源给它吗?

答:(l)此时可以出进程安全序列:P4,P1,P5,P2,P3。故系统处于

安全状态。

(2)可以分配,存在安全序列:P4,P1,P5,P2,P3。

(3)不可分配,系统进入不安全状态。

29)考虑一个共有巧0个存储单元的系统,如下分配给三个进程,P1最大需求

70,己占有25;以P2最大需求60,己占有40;P3最大需求60,己占有45。

-

操作系统第五版费祥林-课后习题答案解析参考

发布时间:2022-04-14 09:02:59
文章版权声明:除非注明,否则均为IT技术网-学习WEB前端开发等IT技术的网络平台原创文章,转载或复制请以超链接形式并注明出处。

发表评论

评论列表 (有 19 条评论,215人围观)

最近发表

随便看看

热门文章

标签列表