四、死锁题型

死锁题型一般以交通题目（如过河问题）为代表。

在讲解生产者---消费者题型时，曾讲过死锁与PV操作的关系，再重复一遍：

在一些PV操作习题里，尤其是生产者---消费者题型，要求给出“无死锁”的解法。PV操作和死锁有什么关系？我们又怎样在PV操作习题中找到死锁的可能呢？

我们在课程第一轮，学习过死锁的四个必要条件：

●资源独占（一个资源不能同时分配给两个以上进程）

●资源非抢占式

●资源保持申请（申请新资源时不释放老资源）

●循环等待（参与死锁的进程互相等待彼此的资源）。

指出：只有上述四个必要条件同时存在，系统才有可能发生死锁。

我们还学习过死锁的预防（资源预先分配、有序分配）、死锁的避免（进程安全序列、银行家算法），这些策略都是针对死锁的四个必要条件，打破或避免其中一个必要条件而进行的。

我们还指出，多道程序环境下死锁是小概率事件，而用专门的算法（比如银行家算法）解决死锁问题开销太大，在实际的操作系统中一般不含有专门的“死锁处理”模块，死锁的解决由各个并发程序自行负责。这就引出了死锁和PV操作的关系。

PV操作是操作系统内核及并发应用程序常用的，本着死锁的分散处理原则，我们在PV操作习题中应该考虑死锁的处理。

PV操作习题中考虑死锁的处理，其理论依据仍是死锁的四个必要条件，但前三个必要条件一般是题目隐含的且不可避免和打破的，所以我们一般只需考虑第四个必要条件“循环等待”，我们要考虑题目中是否存在循环等待资源的进程

并设法避开或打破它。常用的是资源的有序分配方法（给资源编号，按从大到小或从小到大的次序申请）。

一座小桥(最多只能承重两个人)横跨南北两岸，任意时刻同一方向只允许一人过桥，南侧桥段和北侧桥段较窄只能通过一人，桥中央一处宽敞，允许两个人通过或歇息。试用信号灯和PV操作写出南、北两侧过桥的同步算法。

解：把南北两岸换成左右两岸,桥可分成以下区：

2

1 3 4

按题意：左岸过河者同时只能有一个（互斥），过河顺序为1，2，4。右岸过河者同时只能有一个（互斥），过河顺序为4，3，1。

每个区也都是互斥的，过河者走到下一个区时要使上一个区可用。

semaphore s1=1, s2=1; //左右岸过河者的互斥

semaphore a1=1, a2=1, a3=1, a4=1; //四个区的互斥

释放上一区也要发生死锁。

有南北走向的河流如图所示, 河中有用石块搭成的便桥，每个石块上最多容纳一个过河者，两个相邻石块的间距恰好为一步. 西岸过河者经过石块1,2,5,6,4,3到达东岸，东岸过河者经过石块3,4,7,8,2,1到达西岸。试分析可能发生的死锁情况，给出一个无死锁、无饿死、并行度高的解法，并用PV操作实现。

解：

当两岸同时允许过河者的人数为多少时，有可能死锁？即过河者到达不了对岸？

当两个方向同时各有3个人踏上石块时，必将发生死锁，因为两岸过河者允许交叉的位置分别只有2个（8/7和5/6）。另外当两个方向各有1人各自踏上1，2（或3，4石块）时也会“顶牛”--发生死锁。防止死锁发生的最简单方法是规定东西两岸人员不同时过河，但这可能导致饿死，同时也影响并行度。综合考虑死锁处理策略，可以给出更恰当的解法.

根据资源的数量，首先要限定同时过河的人数在5个以内，这时至少有一个方向的过河人数不超过2个，当他们分别踏上5，6或7，8石块上时，对另一方向过河人员便无影响。其次，对两岸竞争的1，2和3，4两对石块，采用有序分配法，即按1，2和3，4的次序申请。如此得到的解法如下：

semaphore Smax; （初值=5）

semaphore S1,S2,S3,S4,S5,S6,S7,S8; (初值=1)

西面过河者的活动: P(Smax);

P(S1); //有序申请

走到石块1;

P(S2); //有序申请

走到石块2;

V(S1);

P(S5);

走到石块5;

V(S2);

P(S6);

走到石块6;

V(S5);

P(S3); //有序申请

P(S4);

走到石块4;

V(S6);

走到石块3;

V(S4);

走到东岸;

V(S3);

V(Smax);东面过河者的活动: P(Smax);

P(S3); //有序申请

走到石块3;

P(S4); //有序申请

走到石块4;

V(S3);

P(S7);

走到石块7;

V(S4);

P(S8);

走到石块8;

V(S7);

P(S1); //有序申请

P(S2);

走到石块2;

V(S8);

走到石块1;

V(S2);

走到西岸;

V(S1);

V(Smax);

注意！两个进程对资源1/2和3/4的申请都是有序的，即先1后2，先3后4。如果西面过河者对资源1/2申请是先1后2，而东面过何者是先2后1，则可能死锁。

西面过河者对资源3/4申请连续用了2个P操作，根据对前述哲学家进餐问题的解，我们知道这不是预先申请，从图上看西面过河者使用资源的顺序是先4后3，但申请资源必需是先3后4，否则，用P(S4)先申请到4，在P(S4)和P(S3)之间，东面过何者抢先进行了P(S3)，则死锁。

对这个题目，如对避免死锁的资源有序分配方法有深入理解，则容易陷入死锁陷井。

假如把此题改为两岸同时只允许一个西岸过河者和一个东岸过何者，在1/2，3/4处发生死锁的可能性也是存在的，解此题只需把Smax换为Smax1和Smax2两个信号量，初值都设为1即可。

设有一个Ｔ型路口，其中A、B、C、D处各可容纳一辆

车，车行方向如下图所示，试找出死锁并用有序分配法

消除之。要求资源编号合理。

解：E方向的车左转依次要走B-A-D三个区；

S方向的车左转依次要走C-B-A二个区；

W方向的车直行依次要走D-C两个区。

这样四个区都有可能造成死锁。

设位置资源C、B、A、D的编号从低到高依次为1、2、3、4，管理四个位置的信号量分别为sc,sb,sa,sd，信号量的初值均为1。车辆活动如下：

semaphore sc=1,sb=1,sa=1,sd=1;

W ：直行P(sc); P(sd); 驶入 D; 驶出D；驶入 C; V(sd); 驶出 C; V(sc); E ：左转

P(sb);

驶入 B;

P(sa) ；

驶入 A;

V(sb)

P(sd) ；

驶入 D;

V(sa) ；

驶出 D;

V(sd);

S ：左转

P(sc);

驶入 C;

P(sb) ；

驶入 B;

V(SC)

P(sa) ；

驶入 A;

V(sb) ；

驶出 A;

V(sa);

这道题的解体现了有序申请，W进程中连续的P操作，不是预先分配（原因前面的题目中已讲过），而是按资源由小到大序号依次申请---释放（有序申请）。

这道题我们要注意W：直行进程对C，D的申请，W直行应先D后C，但有于C的资源号最小，故申请时要先C后D，由于有了C以后不能越过D直接到C，C和D都要得到才能行车，所以出现了连续的P(sc),P(sd)，这个道理与过河问题是一样的。