V(S13) V(S14) end
Process M2: begin
P(S12) V(26) end
Process M3: begin
P(S13) V(S36) V(S38) end
Process M4: begin
P(S14) V(S47) end
Process M5: begin
V(S57) end
Process M6: begin
P(S26) P(S36) end
Process M7: begin
P(S47) P(S57) P(S78) end
Process M8: begin
P(S38) P(S78) end COEND 12
试用信号量机制来描述下述前趋图
M1 M2 M4 M3 M5 M6
解答：首先定义信号量S12,S13,S24,S25,S56,S46,S36的初值都为0，分别表示相对应的进程是否完成(2’)：
COBEGIN (`6’=1’*6) Process M1: begin
V(S12) V(S13) end
Process M2: begin
P(S12) V(24) V(25) end
Process M3: begin
P(S13) V(S36) end
Process M4: begin
P(S14) V(S46) end
Process M5: begin
P(S25)
V(S56) end
Process M6: begin
P(S36)
P(S46) P(S56) end COEND
13设系统有三个并发进程R,C,P，共享一个能存放n个数据的环形缓冲区buf。进程R负责从输入设备上读数据，每读一个后把它存放在缓冲区buf的一个单元中；进程C负责从缓冲区读数据并进行处理，之后将处理结果再送入缓冲区的一个单元中；进程P负责从缓冲区读进程C处理的结果并打印。请用P、V操作为三进程的正确执行写出同步算法。
解答：解决同步问题需设一个互斥信号量mux，用于控制三个进程互斥使用缓冲区，初值为1；再设三个同步信号量，用于控制对缓冲区的空闲数量和不同数据个数的记录。S0表示缓
冲区空闲个数，初值为n；S1表示缓冲区中输入数据的个数，初值为0；S2表示缓冲区中输出数据的个数，初值为0。(4’) 算法描述如下：(`6’=2’*3)
进程R 进程C 进程P L1: L2: L3:
P(S0) P(S1) P(S2) P(mux) P(mux) P(mux)
读一个数据 从缓冲区中取一个 从缓冲区中读 送缓冲区 数据处理后放回去 输出数据 V(mux) V(mux) V(mux)
V(S1) V(S2) V(S0) 打印 gotoL1: gotoL2: gotoL3:
第三章 死锁
名词解释
1死锁
是指在一个进程集合中的每个进程都在等待仅由该集合中的另一个进程才能引发的事件而无限期地僵持下去的局面。
2饥饿
在系统中，每个资源占有者都在有限时间内释放它所占有的资源，但资源中存在某些申请者由于某种原因却永远得不到资源的一种错误现象。
3死锁防止
要求进程申请资源时遵循某种协议，从而打破产生死锁的四个必要条件中的一个或几个，保证系统不会进入死锁状态。
4死锁避免
对进程所发出的每一个申请资源命令加以动态地检查，并根据检查结果决定是否进行资源分配。就是说，在资源分配过程中若预测有发生死锁的可能性，则加以避免。这种方法的关键是确定资源分配的安全性。
5安全序列
针对当前分配状态来说，系统至少能够按照某种次序为每个进程分配资源（直至最大需求），并且使他们依次成功地运行完毕，这种进程序列{p1,p2,…,pn}就是安全序列。
简答题
1计算机系统中产生死锁的根本原因是什么?死锁发生的四个基本条件是什么？
答: 计算机系统中产生死锁的根本原因是：资源有限且操作不当 。死锁发生的四个基本条件有互斥条件、请求保持条件（占有且等待条件）、非剥夺条件（不可抢占条件）和环路条件（循环等待条件） 。
2简述发生死锁的四个必要条件?
答： 四个必要条件是：互斥条件、占有且等待条件（请求保持条件）、不可抢占条件（非剥夺条件）和循环等待条件（环路条件）。
互斥条件——某个资源在一段时间内只能由一个进程占有，不能同时被两个及其以上的进程占有。
占有且等待条件——进程至少已经占有一个资源，但又申请新的资源。 不可抢占条件——一个进程所占有的资源再用完之前，其他进程不能强行夺走资源，只能由该进程用完之后主动释放。
循环等待条件——存在一个进程等待序列{P1,P2,?,Pn}，其中，P1等待P2所占有的某个资源，P2等待P3所占有的某个资源，??，而Pn等待P1所占有的某个资源，从而形成一个进程循环等待。
3什么是死锁？解决死锁的方法一般有那几种?
答: 死锁是指在一个进程集合中的每个进程都在等待仅由该集合中的另一个进程才能引发的事件而无限期地僵持下去的局面。
解决死锁问题的一般方法为：死锁的预防、死锁的避免、死锁的检测和恢复。
4死锁预防的基本思想是什么?死锁避免的基本思想是什么?
答:死锁预防的基本思想是:要求进程申请资源是遵循某种协议,从而打破产生思索的四个必要条件中的一个或几个,保证系统不会进入死锁状态.
死锁避免的基本思想是:对进程所发出的每一个申请资源命令加以动态地检查,并根据检查结果决定是否进行资源分配.就是说,在资源分配过程中若预测有发生死锁的可能性,则加以避免.这种方法的关键是确定资源分配的安全性.
5什么是死锁的安全序列?何谓系统是安全的？
答：进程的安全序列{P1,P2,?,PN}是这样组成的：若对于每个进程Pi（1<=I<=n），它需要的附加资源可以被系统中当前可用资源加上所有进程Pj（j “系统是安全的”是指系统中的所有进程能够按照某种次序分配资源，并且依次运行完毕。即系统中的进程处于安全序列中。 6资源按序分配法为什么能够预防死锁？ 证明：采用反证法来证明。 若存在循环等待，设在环路上的一组进程为{P0,P1,P2,?,Pn}，这里Pi等待进程Pi+1占有资源Ri（下角标取模运算，从而，Pn等待p0占有的资源）。由于Pi+1占有资源Ri,又申请资源Ri+1,从而一定存在F(i) F(R0) 显然，这是不可能的，因而，上述假设不成立，表明不会出现循环等待条件。 7死锁和“饥饿”之间的主要差别是什么? 答：死锁：多个并发进程相互等待对方占用的资源而产生的错误现象。