操作系统第五版答案-费翔林

文章描述:-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(numbe

rsum+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不会改变除自己外的其他进程所对应的fla

g[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每次生产一个产品投入b

uf1,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。使用银行家算法,以确定下面的任何一个请求是否安全。(l)P4进程到达,

-

操作系统第五版答案-费翔林

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

发表评论

评论列表 (有 17 条评论,204人围观)
蓝谷地二手房V铁粉9 minutes ago Google Chrome 93.0.4577.82 Windows 10 x64
00作业C到达
家装壁纸排行榜V铁粉2 minutes ago Google Chrome 93.0.4577.82 Windows 10 x64
便可启动中断服务例程工作
察尔汉盐湖V铁粉15 minutes ago Google Chrome 93.0.4577.82 Windows 10 x64
E);(2)优先级调度算法
结肠扭转V铁粉19 minutes ago Google Chrome 93.0.4577.82 Windows 10 x64
作业B投入运行
炒僵蚕V铁粉20 minutes ago Google Chrome 93.0.4577.82 Windows 10 x64
进后备作业队列等待
民营企业的特点V铁粉16 minutes ago Google Chrome 93.0.4577.82 Windows 10 x64
semaPhore
武汉凡谷电子V铁粉14 minutes ago Google Chrome 93.0.4577.82 Windows 10 x64
它们的提交和估计运行时间由下表给出:系统采用SJF调度算法
qqpcmgrV铁粉20 minutes ago Google Chrome 93.0.4577.82 Windows 10 x64
时间为100至150ms之间(见图中有部分)(2)程序A无等待现象
米兰时装周V铁粉7 minutes ago Google Chrome 93.0.4577.82 Windows 10 x64
一次进程‘切换的系统开销时间为S
何炅代言V铁粉17 minutes ago Google Chrome 93.0.4577.82 Windows 10 x64
作业D到达
香樟路租房V铁粉8 minutes ago Google Chrome 93.0.4577.82 Windows 10 x64
P2的执行完全会造成这种情况)
上地租房V铁粉2 minutes ago Google Chrome 93.0.4577.82 Windows 10 x64
E
人因V铁粉7 minutes ago Google Chrome 93.0.4577.82 Windows 10 x64
C优先次序运行
龙园意境小学V铁粉18 minutes ago Google Chrome 93.0.4577.82 Windows 10 x64
如果:(1)每次只允许一个进程进入互斥段;(2)每次最多允许m个进程(m簇n)同时进入互斥段
52bar游戏网V铁粉7 minutes ago Google Chrome 93.0.4577.82 Windows 10 x64
Job2和Job3
危情交易V铁粉26 minutes ago Google Chrome 93.0.4577.82 Windows 10 x64
=x;mptr