文档库

最新最全的文档下载
当前位置:文档库 > 死锁题型

死锁题型

四、死锁题型

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

在讲解生产者---消费者题型时,曾讲过死锁与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即可。

设有一个T型路口,其中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),这个道理与过河问题是一样的。