操作系统第五版费祥林-课后习题答案解析参考|江阴雨辰互联

2023年7月3日发(作者：)

第一章操作系统概论

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 ( 40 ms )

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 < b ＜c，试证明采用短作业优先算法调度能获得最小平均作业周转时间。

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

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 轮转执行。

作业

执行时间

等待时间

周转时间

带权周转时间

3 .66

3. 5

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

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

R1 R3 B2 D2

该指令的功能如下：

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 /decrease R3 ;

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 台，被N 个进程共享，由共享变量C 来代表可用磁带机台数，其初值为3 。现有并发进程P1 和P2 均申请使用磁带机，执行临界区程序。

进程Pl 执行临界区程序

( C ）→R1 ；因（C）=3 ，故（R1) = 3 。

loop2: ( Rl ）→R3 因（R1 ) = 3 ，故（R3 ）当前也＝3 。

decrease R3 ：申请使用磁带机，做减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 ;

巧单道批处理系统中，下列三个作业采用先来先服务调度算法和最高响应比优先算法进行调度，哪一种算法性能较好？请完成下表：

作业

提交时间运行时间开始时间

1 10 : 00 2 : 00

2 10 : 10 1 : 00

3 10 : 25 0 : 25

平均作业周转时间=

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

完成时间周转时带权周间转时间

答：

可见HRRF 比FIFO 要好

16 若有如表所示四个作业进入系统，分别计算在FCFS 、S 开和HRR 卫算法下的平均周转时间与带权平均周转时间。（时间以十进制表示）

答：

17 Kleinrock 提出一种动态优先权算法：进程在就绪队列等待时，其优先权以速率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 运行结束。

各作业周转时间为：作业A 70 ，作业B 30 ，作业C 90 ，作业D 90 。平均作业周转时间为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 运行结束。

第三章同步、通讯与死锁

1、有三个并发进程：R 负责从输入设备读入信息块，M 负责对信息块加工处理；P 负责打印输出信息块。今提供；

l ）一个缓冲区，可放置K 个信息块；

2 ）二个缓冲区，每个可放置K 个信息块；

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

答：

1 ) var B : array [ 0 , k-1 ] of item ;

sread : semaPhore : = k ;

smanage : semaPhore : = 0 ;

swrite : semaphore : = 0 ;

rptr : integer : = O ;

mptr : integer : = O ;

wptr ：integer : = 0 ;

x : item

cobegin

process reader ; process manager ; process writer ;

begin begin begin

LI : read a message intox ; L2 : P ( smanage ) ; L3 : P ( swnte ) ;

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

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

Rptr:=(rptr+1) mod k; manage the message in x; V(sread);

V(smanage); B[mptr]:=x; print the message in x;

Goto L1; V(swrite); goto L3;

End; goto L2; end;

End;

coend

2 ) var A , B :array [ 0 , k -l ] of item ;

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

process reader ; processn manager; process Writer ;

begin begin begin

Ll : read a message into x ; L2 : P ( sgetl ) ; L3 : P ( sgetZ ) ;

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

A [put1]:=x ; get1 ：(get1+1 ) mod k ; get2:=（get2 + l ) mod k ;

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

V(sget1); manage the message into x; print the message in x;

Goto L1; P(sput2); goto L3;

Put2:=(put2+1) mod k;

V(sget2);

Goto L2;

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:

Begin begin

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;

End end

答：现对进程语句进行编号，以方便描述．

P1 : P2 :

begin begin

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；⑧

End end

① 、② 、⑤ 和⑥ 是不相交语句，可以任何次序交错执行，而结果是唯一的。接着无论系统如何调度进程并发执行，当执行到语句⑦ 时，可以得到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 操作：

var name ：array [ l …100]of A ;

A = record

number ：integer ;

name：string ;

end

for i : = 1 to 100 do {A [ i ].number ：i；A [ i ].name :null;}

mutex , seatcount : semaphore ;

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

cobegin

{

process readeri ( var readename：string ) （i=1 , 2 …)

{

P ( seatcount ) ;

P （mutex ) ;

for i : = 1 to 100 do i++

if A [ i ].name＝null then A [ i ].name：readername；

reader get the seat number=i；/*A[I].number

V ( mutex )

进入阅览室，座位号i ，座下读书；

P ( mutex ) ;

A[i]name：null ;

V （mutex ) ;

V(seatcount);

离开阅览室；

}

coend

2 ）使用管程操作：

TYPE readbook=monitor

VAR R: condition ;

I,seatcount ：integer;

name：array [ l:100] of string ;

DEFINE rcadercome, readerleave ;

USE check , wait , signal , release ;

Procedure readercome ( readername )

begin

check ( IM ) ;

if seatcount≥100 wait ( R,IM )

seatcount : = seatcount + 1 ;

for i=1 to 100 do i++

if name[i] ==null then name[i]:= readername;

get the seat number = i ;

release ( IM ) ;

end

procedure readerleave ( readername )

begin

check ( IM ) ;

seatcount--;

for i = 1 to 1 00 do i++

if name［i ］readername then name［i］:null;

release ( IM ) ;

end

begin

seatcount : = 1OO ; name:＝null ;

end

cobegin

{

process readeri ( i = 1 , 2 ．… ）

begin

readercome ( readername）;

read the book ;

readerleave ( readername）;

leave the readroom;

end

}

coend.

5. 在一个盒子里，混装了数量相等的黑白围棋子· 现在用自动分拣系统把黑子、白子分开，设分拣系统有二个进程P1 和P2 ，其中P1 拣白子；P2 拣黑子。规定每个进程每次拣一子；当一个进程在拣时，不允许另一个进程去拣；当一个进程拣了一子时，必须让另一个进程去拣．试写出两进程P1 和P2 能并发正确执行的程序。

答1 ：实质上是两个进程的同步问题，设信号量s1 和s2 分别表示可拣白子和黑子，不失一般性，若令先拣白子。

var S1 , S2 : semaphore;

S1 : = l; S2 ：=0;

cobegin

{

process P1

begin

repeat

P( S1 ) ;

拣白子

V ( S2 ) ;

until false ;

end

process P2

begin

repeat

P ( S2 ) ;

拣黑子

V (S1 ) ;

until false ;

end

}

coend .

答2 :

TYPE pickup-chess = MONITOR

VAR flag : boolean ;

S-black , s-white : codition ;

DEFINE pickup-black , pickup-white ;

USE wait,signal , check , release ;

procedure pickup-black ;

begin

check(IM ) ;

if flag then wait(s-black,IM ) ;

flag : ＝true;

pickup a black;

signal(S-white,IM);

release ( IM ) ;

end

procedure pickup-white ;

begin

check ( IM ) ;

if not flag then wait(S-white,IM );

flag :=false ;

pickup a white ;

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 ) 表示进程由于条件不满足而应等待，当进程号累加和小于K 时，系统应唤醒该进程工作．

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

司机的活动：启动车辆：正常行车；到站停车。

售票员的活动：关车门；售票；开车门。

在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系？用信号量和P 、V 操作实现它们的同步。

答：在汽车行驶过程中，司机活动与售票员活动之间的同步关系为：售票员关车门后，向司机发开车信号，司机接到开车信号后启动车辆，在汽车正常行驶过程中售票员售票，到站时司机停车，售票员在车停后开门让乘客上下车。因此，司机启动车辆的动作必须与售票员关车门的动作取得同步；售票员开车门的动作也必须与司机停车取得同步。应设置两个信号量：S1 、S2 ;S1 表示是否允许司机启动汽车（其初值为0 ) ;S2 表示是否允许售票员开门（其初值为0 ）。用P 、v 原语描述如下：

var S1 , 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 来协调进程工作。

var S1 , S2 ,S3 , S4 : semaphore ;

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

cobegin

{ process P1

begin

repeat

有顾客到来；

P ( S1 )；

接受顾客点菜；

V ( 52 )；

untile false；

end

process P2

begin

repeat

P (S2 ) ;

准备顾客的饭菜；

v ( S3 ) ;

untile false ;

end

process P3

begin

repeat

P (S3 ) ;

将做好的饭菜打包；

V ( S4 ) ;

untile false ;

end

process P4

begin

repeat

P( 54 ) ;

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

ufltile false ;

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 是原语，试给出可能的并发执行路径。

Process P Process Q

begin begin

A ; D ;

B ; E ;

C ; end :

end ;

( 2 ）两个并发进程P1 和P2 并发执行，它们的程序分别如下：

P 1 P2

repeat repeat

k:=k×2 ; print k ;

k:=k+1 ; k:=0 ;

until false ; until false ;

若令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 ）把语句编号，以便于描述：

P1 P2

repeat repeat

k:=k×2 ；① printk ；③

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

until false ; until false ;

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

2 ）语句并发执行有以下情况：

① 、② 、③ 、④ ，这时的打印值为：47

③ 、④ 、① 、② ，这时的打印值为：23

① 、③ 、② 、④ ，这时的打印值为：46

① 、③ 、④ 、② ，这时的打印值为：46

③ 、① 、② 、④ ，这时的打印值为：23

③ 、① 、④ 、② ，这时的打印值为：23

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

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

( l ）用信号量实现管程；

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

答：( 1 ）用信号量实现管程；

Hoare 是用信号量实现管程的一个例子，详见课文内容。下面介绍另一种简单方法：每一个管程都对应一个mutex ，其初值为1 ，用来控制进程互斥调用管程。再设一个初值为0 的信号量，用来阻塞等待资源的进程。相应的用信号量实现的管程库过程为：

Var mutex,c:semaphore ;

mutex:=1 ; c:=0 ;

void enter-monitor ( ) /*进入管程代码，保证互斥

P ( mutex ) ;

}

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

{

V ( mutex ) ;

}

void leave-with-sigal(c) /*在条件c 上发信号并退出管程，释放一个等待c 条件的进程。｛注意这时没有开放管程，因为刚刚被释放的进程己在管程中。

V ( c ) ;

}

void wait(c) /*等待条件c ，开放管程

{

V ( mutex ) ;

P (c) ;

}

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

TYPE semaphore=monitor

VAR S ; condition ;

C:integer ;

DEFINE P , V ;

USE check , wait , signal , release ;

procedure P

begin

check ( IM ) ;

C:= C-1 :

if C < 0 then wait ( S,IM ) ;

release ( IM ) ;

end

procedure V

begin

check ( IM ) :

C : = C + 1 ;

if C≤0 then signal ( S,IM ) ;

release ( IM ) ;

end

begin

C:=初值;

End.

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

( 1 ）用消息传递实现管程；

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

答：( 1 ）用消息传递实现管程；

用消息传递可以实现信号量（见13 ( 2 ) ) ，用信号量可以实现管程（见11 (1 ) ) ，那么，把两种方法结合起来，就可以用用消息传递实现管程。

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

TYPE mailbox=monitor

VAR r , k , count:integer ;

buffer ：array[0…n-1] of message ;

full , empty:condition ;

DEFINE add , get ;

USE check , wait , signal , release ;

procedure add ( r ) ;

begin

check ( IM ) ;

if count=n then wait ( full,IM ) ;

buffer [r]:=message ;

r:＝(r+1) mod n

count:=count + 1 ;

if count = 1 then sighal ( empty , IM ) ;

release ( IM ) ;

end

procedure get ( m ) ;

begin

check ( IM ) ;

if count = 0 then wait ( empty , IM ) ;

m:=buffer [ k 」；

count : = count-1 ;

if count＝n-1 then signal ( 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 ）见课文ch3 3.5.4 节。（2 ）见课文Ch3 3.4.3 节。

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

var forki:array [0…4] of semaphore ;

forki:=1 ;

cobegin

{

process Pi /* i = 0 , 1 , 2 , 3 */

begin

L1 :

思考：

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

P(fork[i+1] mod 5) / * i =4P（fork [4]）* /

吃通心面；

V (fork[i] ;

V (fork([i+1] mod 5 ) ;

goto L1 ;

end ;

}

coend ;

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

var flag ：array[0…n] of (idle,want-in ，in_cs ) ;

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

process Pi(i=0,1，…,n-1)

var j ; integer ;

begin

repeat

flag [i] :want_in ;

while turn≠1 do

if flag[turn]==idle then turn:=i ;

flag[i]:= ip_cs ;

j:=0 ;

while (j < n ) & (j==1 or flag[j] ≠in_cs )

do j:=j + 1 ;

until j≥n :

critical section ;

flag [i]:=idle ;

……

until false ;

end .

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

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

repeat

flag[i]:=want_in ；①

while turn≠i do ②

if flag[trun]==idle then turn:=i ；③

flag[i]: = in_cs ；④

j:= O ;

while(j < n ) & (j==1 or flag[j] ≠in_cs ）⑤

do j:=j + 1 ; @

until j≥n ;

critical section ;

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 代表烟草、纸、火柴

if flag2 & flag3 then V(S1) ; / ＊供纸和火柴

else if flag1 & fiag3 then V(S2 ) ; / ＊供烟草和火柴

else V(S3) ; / ＊供烟草和纸

untile false ;

end

process 吸烟者1

begin

repeat

P(S1) ;

取原料；

做香烟；

V(S) ;

吸香烟；

untile false ;

process 吸烟者2

begin

repeat

P (S2 ) ;

取原料；

做香烟；

V(S) ;

吸香烟；

untile false ;

process 吸烟者3

begin

repeat

P (S3 ) ;

取原料；

做香烟；

V ( S ) ;

吸香烟；

untile false ;

coend .

( 3 ）用管程。

TYPE mskesmoke=moonitor

VAR S, S1 ,S2 ,S3 : condition ;

flag1 , flag2, flag3 : boolean

DEFINE give , take1 , take2 , take3 ;

USE check , wait , signal , release ;

procedure give

begin

check ( IM ) ;

准备香烟原料；

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

if fiag2 & flag3 then signal ( S1 ,IM）;

if flag1 & flag3 then signal ( S2 ,IM ) ; else signal (S3 , IM ) ;

release ( IM ) ;

end

procedure take1

begin

check(IM):

if 桌上没有香烟原料then wait ( S1 ,IM）;

else 取原料；

signal ( S , IM ) ;

release ( IM ) ;

end

procedure take2

begin

check ( IM ) :

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

else 取原料；

signal ( S , IM ) ;

release （IM）;

end

procedure take3

begin

check ( IM ) :

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

else 取原料

signal ( S ,IM ) ;

release ( IM ) ;

end

begin

flag1:=flag2:=flag3:=true;

end.

cobegin

{

process 供应者

begin

repeat

Call ();

……

until false ;

end

process 吸烟者1

begin

repeat

Call 1() ;

做香烟，吸香烟；

until false ;

end

process 吸烟者2

begin

repeat

Call 2() ;

做香烟，吸香烟；

until false ;

end

process 吸烟者3

begin

repeat

Call 3();

做香烟，吸香烟；

until false ;

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）的同步工作算法

答：

var mutexl , 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

{

process P0

begin

repeat

P(full0);

P(mutex0);

从M0[out0]取一条消息；

out0:=(out0+1) mod 3 ;

V(mutex0);

V(empty0) ;

加工消息；

P(empty1) ;

P(mutex1) ;

消息已M1[in1];

In1:=(in1+1) mod 3;

V(mutex1) ;

V(full1 ) ;

untile false ;

end

process P1

begin

repeat

P ( full1 ) ;

P ( mutex1 ) ;

从M1[out1]取一条消息；

Out1:=(out1+1) mod 3 ;

V(mutex1);

V(empty1);

加工消息;

P(empty2);

P(mutex2 ) ;

消息己M2[in2];

In2:=(in2+1) mod 2;

V(mutex2 ) ;

v ( full2 ) ;

untile false ;

end

process P2

begin

repeat

P(full2) ;

P(mutex2 ) ;

从M2[out2]取一条消息；

out2:=(out2 + l ) mod 2;

V(mutex2) ;

V(empty2) ;

加工消息；

P(empty3) ;

P(mutex3) ;

消息己M3[in3];

in3:=(in3+1) mod 2 ;

V(mutex3) ;

V(full3) ;

untile false ;

end

process P3

begin

repeat

P(full3) ;

P(mutex3) ;

从M3[out3] 取一条消息;

out3:=(out3+1)mod 2;

V (mutex3) ;

V (empty3) ;

加工消息；

P ( empty0 ) ;

P ( mutex0 ) ;

消息己MO[in0];

In0:=(in0+1) mod 3 ;

V(mutex0) ;

V(full0) ;

untile false ;

end

{

coend

19、有三组进程Pi 、Qj、Rk ，其中Pi 、Qj构成一对生产者和消费者，共享一个由M1个缓区构成的循环缓冲池buf1 。Qj、Rk凡构成另一对生产者和消费者，共享一个由M2 个缓冲区构成的循环缓冲池buf2 。如果Pi每次生产一个产品投入buf1,Qj每次从中取两个产品组装成一个后并投入buf2，Rk每次从中取三个产品包装出厂. 试用信号量和P 、V操作写出它们同步工作的程序。

答：

var mutex1 , mutex2 , mutex3 : semaphore;

empty1 , empty2 , full1 , full2 ; semaphore ;

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

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

empty1:=M1 ; empty:=M2;

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

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

cobegin

{

process Pi

begin

L1:

P(empty1) ;

P(mutex1 ) ;

put an item into buffer [in1] ;

in1:=(in1+1) mod M1 ;

counter++;

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

V(mutex) ;

goto L1;

end

process Qj

begin

L2:

P ( full2) ;

P ( mutex1 ) ;

take an item from buffer1[out1];

out1:=(out1+1) mod M1;

take an item from buffer1[out1] ;

out1:=(out1 + 1) mod M1 ;

V ( mutex1 ) ;

V ( empty1 ) ;

Process the products ;

P ( emPty2) ;

P ( mutex2 ) ;

put an item into buffer2 [ in2 ] ;

in2:=( in2 + l ) mod M2 ;

counter2 + + ;

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

V ( mutex2) ;

goto L2 ;

process Rk

begin L3 :

P ( full2 ) ;

P ( mutex2 ) ;

take an item from buffer2 [out2];

out2: = ( out2 + 1 ) mod M2 ;

take an item from buffer2 [out2] ;

out2:=( out2 + 1) mod M2 ;

take an item from buffer2 [out2];

out2:=(out2 + 1 ) mod M2 ;

v ( mutex2 ) ;

V ( empty2 ) ;

packet the products ;

goto L3 ;

end

}

coend

20 在一个实时系统中，有两个进程P 和Q ，它们循环工作。P 每隔1 秒由脉冲寄存器获得输入，并把它累计到整型变量W 上，同时清除脉冲寄存器。Q 每隔1 小时输出这个整型变量的内容并将它复位。系统提供了标准例程创PUT 和OUT 卫UT

供拍，提供了延时系统调用Delay ( seconds ）。试写出两个并发进程循环工作的算法。

答：

Var W ,V:integer;

Mutex:semaphore;

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

cobegin {

process P

begin

repeat

P(mutex) ;

delay (1) ;

V＝INPUT ;

W:=W + V ;

清除脉冲寄存器；

V (mutex) ; untile false ;

end

process Q

begin

repeat

P ( mutex ) ;

delay ( 60 ) ;

OUTPUT ( W ) ;

W : = 0 ;

V ( mutex ) ;

untile false ;

}

coend .

21 系统有同类资源m 个，被n 个进程共享，问：当m > n 和m≤n 时，每个进程最多可以请求多少个这类资源时，使系统一定不会发生死锁？

答：当m≤n 时，每个进程最多请求1 个这类资源时，系统一定不会发生死锁。当m > n 时，如果m/n 不整除，每个进程最多可以请求”商＋1 ”个这类资源，否则为”商”个资源，使系统一定不会发生死锁？

22 N个进程共享M 个资源，每个进程一次只能申请释放一个资源，每个进程最多需要M个资源，所有进程总共的资源需求少于M+N 个，证明该系统此时不会产生死锁。

答卜设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 个进程还需要的资源量之和小于n ，这意味着此刻至少存在一个进程i , need ( i ) = 0 ，即它已获得了所需要的全部资源。既然该进程已获得了它所需要的全部资源，那么它就能执行完成并释放它占有的资源，这与前面的假设矛盾，从而证明在这个系统中不可能发生死锁。

答2 ：由题意知道，n×m < m + n 是成立的，

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

即n×(m-1) < m

于是有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 。可用两个信号量同步车、船通过两座桥的动作。

var Sa , 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

24 Jurassic公园有一个恐龙博物馆和一个花园，有m 个旅客租卫辆车，每辆车仅能乘一个一旅客。旅客在博物馆逛了一会，然后，排队乘坐旅行车，挡一辆车可用喊飞它载入一个旅客，再绕花园行驶任意长的时间。若n 辆车都己被旅客乘坐游玩，则想坐车的旅客需要等待。如果一辆车己经空闲，但没有游玩的旅客了，那么，车辆要等待。试用信号量和P 、V 操作同步m 个旅客和n 辆车子。

答：这是一个汇合机制，有两类进程：顾客进程和车辆进程，需要进行汇合、即顾客要坐进车辆后才能游玩，开始时让车辆进程进入等待状态

var sc1 , 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 ) ; /* 释放一辆车 ,即顾客找到一辆空车