P(S1) P(S2) 放苹果 V(S2) V(S3) P(S1) P(S2) 放桔子 V(S2) V(S4) P(S3) P(S2) 取苹果 v(S2) V(S1) P(S4) P(S2) 取桔子 v(S2) V(S1)

(4) 在公共汽车上，司机和售票员的活动分别是 司机：启动车辆；正常行车；到站停车； 售票员：关车门；售票；开车门；

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

解答：根据常识，车门关好后司机方可启动车辆，到站停车后售票员方可打开车门，即门的开、关与车的停、开存在着相互制约的同步关系。定义信号量 run，表示司机是否可以启动车辆，也就是车门的状态（0表示门开，1表示门关），初值为0。定义信号量stop表示售票员是否可以开车门，即车是否停好（0表示车停，1表示车开），初值为0。初始状态为车停门开。

售票员： 上乘客； 关车门； V(run); 车门关好后，run 加1，表明司机可以启动车辆。 售票； P(stop); 判断是否可以开车门；若司机已停车，stop为1，继续； 开车门； 若司机未停车，stop为0，阻塞，无法开车门。 下乘客；

司机：

P(run); 判断是否可以启动车辆；若售票员已关门run为1，继

续；

启动车辆； 若售票员未关门run为0，阻塞，无法启动车辆。 正常行车； 到站停车； V(Stop); 停车后，stop加1，表明售票员可以开车门。

(5) 某寺庙，有小、老和尚若干，有一水缸，由小和尚提水入缸供老和尚引用。水缸可容12

桶水,水取自同一井中。水井径窄，每次只能容一个桶取水。水桶总数为4个。每次入、取缸水仅为一桶，且不可同时进行。试给出有关取水、入水的算法描述。

解答：分析题目可知，小和尚负责用桶到井中取水并将水倒入缸中，其操作依次为拿桶、井中取水、倒水入缸。水桶只有4个，只有拿到桶后方可继续，否则需要等桶，因水井径窄，每次只能容一个桶取水，故取水的小和尚对水井的访问必须是互斥的。老和尚负责用桶从缸中取水，其操作依次为拿桶、缸中取水。只有拿到桶后方可继续，否则需要等桶。每次入、取缸水仅为一桶，且不可同时进行，表明小和尚倒水入缸、老和尚取水必须互斥。同时，缸中没水，老和尚不能取水，要等待小和尚倒水入缸；水缸满，小和尚不能倒水入缸，要等待老和尚取水，也就是说，小和尚倒水入缸和老和尚取水必须同步。设置互斥信号量和同步信号量： m1=1，表示小和尚从水井取水时，对水井的互斥访问，即一次只能有一个水桶进出水井；

m2=1，表示小和尚倒水入缸、老和尚取水时对水缸的互斥访问，即每次入、取缸水只能一个桶；

count=4，表示是否有桶可以供小和尚、老和尚使用； full=0满缓冲，表示缸内有水的桶数，控制老和尚取水；

empty=12，空缓冲，缸内还能放水的桶数，控制小和尚倒水入缸； P(empty) 判断缸中是否有倒水的位置，若有，水位-1，继续； P(count) 判断是否有水桶可以使用，若有，可用水桶数目-1，继续； P(m1) 判断能否对水井访问，即是否有其他小和尚从水井取水 从井中取水 互斥控制一个水桶从水井取水； V(m1) P(m2) 判断能否对水缸访问，即是否有其他和尚取水或倒水 送水入缸 互斥地将水倒入水缸； V(m2) V(count) 水入缸后，水桶空闲，可供其他和尚使用。可用水桶数目+1 V(full) 水入缸后可供老和尚取水，可取水的桶数+1

此题特别要注意P操作的次序，例如：如果P(empty)和P(count)操作次序颠倒，就有可能产生死锁。

若某时刻水缸水满（empty=0; full=12），而四个小和尚依次拿水桶去井中取水，此时P(count)均执行减1操作，count 的值变为0，但继续执行P(empty)时，empty-1，empty<0，阻塞；此时老和尚想取水，执行P(full) ，继续，执行P(count)，此时couunt-1，count<0，阻塞，即老和尚没有水桶可以取水。老和尚无法取水，小和尚无法倒水，形成僵局，死锁发生。所以，P操作的顺序不可颠倒。 小和尚从水井取水入缸 老和尚从缸中取水

P(full) 缸中是否有水供老和尚取用；若有，可取水的桶数-1，

继续；

P(count) 判断是否有水桶可以使用，若有，可用水桶数目-1，继续； P(m2) 判断能否对水缸访问，即是否有其他和尚取水或倒水 从缸中取水 互斥地从水缸中取水； V(m2) V(empty) 取水后，水缸中增加了倒水的位置，水位+1； V(count) 取水后，水桶空闲，可供其他和尚使用。可用水桶数目+1

(6) 设系统中有五个进程、3种资源，总数分别为A 17，B 5，C 20，T0时刻系统状态如

下。 P1 P2 P3 P4 P5 最大资源需求 A 5 5 4 4 4 B 5 3 0 2 2 C 9 6 11 5 4 A 2 4 4 2 3 15 已分配资源 B 1 0 0 0 1 2 C 2 2 5 4 4 17 A 2 剩余资源数 B 3 C 3 i. 完成剩余资源数的计算： ii. T0时刻是否安全？ iii. 若P2请求资源（0，3，4），系统如何处理？ 解答：T0时刻的向量见图中粗体数字。 need[i,j]=max[i,j]-allocation[i,j]

利用银行家算法对此资源分配情况进行分析，可得此时刻的安全性分析情况： P4 P5 P1 P2 P3 Work 2 4 7 9 13 3 3 4 5 5 3 7 11 13 15 Need 2 1 3 1 0 2 1 4 3 0 1 0 7 4 6 Allocation 2 3 2 4 4 0 1 1 0 0 4 4 2 2 5 Work+allocation 4 7 9 13 17 3 4 5 5 5 7 11 13 15 20 Finish True True True True True 因为T0时刻存在安全序列p4,p5,p1,p2,p3，故T0时刻安全。 按照银行家算法，在T0时刻P2请求资源（0，3，4）， 因请求资源数（0，3，4）<最大请求资源数（1，3，4），继续。 请求资源数（0，3，4）>剩余资源数（2，3，3），所以系统没有足够的资源，不能分配。 (7) P1，P2，P3，P4四个进程同时依次进入就绪队列，它们所需要的处理器时间和优先数如

下，若不计调度等所消耗的时间，请回答： 进程 处理器时间（秒） 优先数 P1 20 2 P2 15 3 P3 10 5 P4 12 3

（a） 分别写出采用先来先服务和非抢占式的优先数调度算法时进程执行的次序。 （b） 分别计算每个进程在就绪队列中的等待时间和平均等待时间。 解答：（a）进程执行次序为： （b）

先来先服务法 非抢占式的优先数法 P3、P2、P4、P1 P1、P2、P3、P4 先来先服务法：

每个进程在就绪队列的等待时间分别为 P1：0（秒） P2：0+20=20（秒） P3：20+15=35（秒） P4：35+10=45（秒） 平均等待时间为（0+20+35+45）/4=25（秒）

非抢占式的优先数法：

每个进程在就绪队列的等待时间分别为 P1：25+12=37（秒） P2：0+10=10（秒） P3：0（秒）

P4：10+15=25（秒）

平均等待时间为（37+10+0+25）/4=18（秒）

(8) 系统中有四道作业，分别用先来先服务、短作业优先调度方法和最高响应比优先法调度，

完成表格的计算，并计算平均带权周转时间。 单位：小时 解答：先来先服务： 作业 提交时间 1 2 3 4

1：00 1：10 2：00 2：00 运行时间 2 6 2 1 开始时间 1：00 3：00 9：00 11：00 完成时间 3：00 9：00 11：00 12：00 周转时间 2 7．83 9 10 平均带权周转时间=（2/2+7.83/6+9/2+10/1）/4=4.2 短作业优先调度： 作业 提交时间 1 2 3 4 1：00 1：10 2：00 2：00 运行时间 2 6 2 1 开始时间 1：00 6：00 4：00 3：00 完成时间 3：00 12：00 6：00 4：00 周转时间 2 10．83 4 2 平均带权周转时间=（2/2+10.83/6+4/2+2/1）/4=1.7 最高响应比优先法调度: 1：00 作业1运行