CoderMrWu

生活诚可期,爱情价更高!

操作系统死锁的定义以及产生的原因!

死锁的产生有其原因并必须满足四个必要条件。

一、死锁的定义

死锁现象并不是计算机操作系统环境下所独有的,在日常生活乃至各个领域中是屡见不鲜的。例如,设一条河上有一座独木桥,过河的人总是沿着自己过河的方向前进而不后退,并且没有规定两岸的人必须谁先过河。则在此独木桥上就有可能发生死锁现象——如果有两个人同时从河的两岸过河。图5-1给出了生活中十字路口交通死锁的例子。

十字路口有向东、南、西、北四个方向行驶的车流,排头的四辆车几乎同时到达该十字路口,并且相互交叉停了下来;若车辆的行进方向都是直行,排头的车辆在等待前行的过程中又挡住了其左方车辆的前进道路,这就产生了死锁。

所谓死锁是指在多道程序系统中的一种现象,一组进程中的每一个进程均无限期地等待被该组进程中的另一个进程所占有且永远不会释放的资源。系统发生这种现象称为系统处于死锁状态,简称死锁。

处于死锁状态的进程称为死锁进程。

当死锁发生后,死锁进程将直等待下去,除非有来自死锁进程之外的某种干预。系统发生死锁时,死锁进程的个数至少为两个;所有死锁进程都在等待资源,并且其中至少有两个进程已占有资源。系统发生死锁不仅浪费了大量的系统资源,甚至会导致整个系统崩溃,带来灾难性的后果。因为,系统中一旦有一组进程陷入死锁,那么要求使用被这些死锁进程所占用的资源或者需要它们进行某种合作的其他进程就可能会相继陷人死锁,最终可能导致整个系统处于瘫痪状态。所以,在操作系统设计中必须高度重视死锁问题。

二、死锁产生的原因

产生死锁的原因主要有两个:一是竞争资源,系统资源在分配时出现失误,进程间对资源的相互争夺而造成僵局;二是多道程序运行时,进程推进顺序不合理。

1.资源的概念

死锁是若干进程因使用资源不当而造成无法推进的现象。按照资源的使用性质,一般把系统中的资源分成两类:永久性资源(可重用资源),是指系统中可供进程重复使用、长期存在的资源,如内存、外部设备、处理器等硬件资源,以及各种数据文件、表格、共享程序代码等软件资源;临时性资源(消耗性资源),是指由某个进程所产生、只为另一个进程使用一次或经过短暂时间后便不再使用的资源,如0和时钟中断信号、同步信号、消息等。

永久性资源和临时性资源都可能导致死锁发生。

2.死锁的例子

下面举几个例子,并通过它们来分析归纳出产生死锁的必要条件。

【例5.1】申请不同类资源产生死锁。

例如,进程P1和P2在运行中都使用输入、输出设备,假定系统中只有一台输入设备台输出设备,则进程P和P2可有如下形式:

P1 P2

①申请一台输入设备; I申请一台输出设备;

②申请一台输出设备; Ⅱ申请一台输入设备;

使用各设备; 使用各设备;

释放输入设备; 释放输入设备;

释放输出设备; 释放输出设备;

当进程P申请并获得了该输入设备后(运行完成①),由于进程切换或某种原因,停止前进。此时P2到达,P2进程完成了对输出设备的申请(运行完成I),接下来再申请输入设备(运行Ⅱ),由于输入设备被P1占用必将导致P2被阻塞且进入等待队列等待。若进程P1重新获得运行机会,接下来便要申请输出设备(运行②),同样,也被阻塞进入等待输出设备的等待队列。进程P1和P2彼此无限地等待对方释放资源从而唤醒自己,于是形成了僵局,如图52所示。

【例5.2】申请同类资源产生死锁。

假设有一类可重用资源R,如内存,它包含有m个页面,由n个进程P1,P2,…,P(2≤m≤n)共享。假定每个进程按下述顺序依次申请和释放页面:

①申请一个页面

②申请一个页面

释放一个页面

释放一个页面

这里每次申请和释放只涉及R的一个分配单元(页面)。因此,当所有单元全部分配完毕时,很容易发生死锁;占有R的单元的所有进程(前m个进程)会永远封锁在第二次申请②上,而有些进程(n-m个进程)类似地会封锁在它们的第一次申请①上。

图5-3说明了n=3、m=2时系统的状态。

这类死锁是相当普遍的。例如,在若干输入和输出进程竞争磁盘空间的 SPOOLing系统中(关于 SPOOLing系统,可以参阅本教材第八章有关章节),如果磁盘空间完全分配给等待装入的进程输入文件和已部分运行的进程输出记录,则系统就有可能发生死锁。

申请同类资源产生死锁的现象也可能发生在申请磁盘的扇区场景下。

例5.3、P、V操作使用不当产生死锁。

进程在相互同步与通信中也可能产生死锁现象。例如,对于第四章描述的生产者和消费者问题,若把生产者和消费者程序中前面两个P操作顺序颠倒,则形成如下所示的两个序列:

生产者进程: 消费者进程:

P(mutex); P(mutex );

P(empty); P( full);

当进行了n次生产后(或n个生产者,每人都送了缓冲区一个产品后),缓冲区被全部占满,此时empy=0。若生产者执行P( mutex)后(此时 mutex=0),又继续执行P(empty),此刻 empty=-1,使生产者因无可用缓冲区而在 empty上等待。若又有一个消费者进程到达,并执行P( mutex),结果使mute=-1。因此,消费者也阻塞,并且在 mutex上等待。此时,生产者、消费者都彼此等待对方来唤醒自己,处于循环等待状态。生产者等待消费者释放一个空缓冲区,而消费者等待生产者释放互斥信号量 mutex。这样便形成了死锁局面

例5.4、对临时性资源的使用不加限制而引起的死锁

进程通信时使用的信件可以看作是一种临时性资源,如果对信件的发送和接收不加限制,则可能引起死锁。比如,进程P1等待进程P3的信件s3到来后再向进程P2发送信件s,P2又要等待P1的信件s到来后再向P3发送信件s2,而P也要等待P2的信件。2来到后才能发岀信件s3。在这种情况就形成了循环等待,永远结束不了,产生死锁。

进程P 进程P2 进程P3

receive(s3); receive(s1); receive(s2);

send(s1); send (s2); send (s3);

三、死锁产生的必要条件

死锁的产生与各并发进程的相对速度有关,一般不可重现,它涉及进程的并发执行、资源共享和资源分配等因素。对于永久性资源,产生死锁有四个必要条件。

1.互斥条件

资源是独占的且排他使用。进程互斥使用资源,即任一时刻一个资源只能给一个进程使用,其他进程若请求一个资源,而该资源被另一进程占有时,则申请者等待,直到资源被占用者释放。

2.不可剥夺条件

又称不可抢占或不可强占。进程所获得的资源在未使用完毕之前,不能被其他进程强行剥夺,而只能由获得该资源的进程自愿释放。

3.请求和保持条件

又称部分分配或占有申请。进程先申请它所需要的一部分资源,得到后再申请新的资源,在申请新的资源的同时,继续占用已分配到的资源。

4.循环等待条件

又称环路等待。在发生死锁时,必然存在一个进程等待队列{P1,P2,…,P},其中P等待P2占有的资源,P2等待P3占有的资源,…,P等待P1占有的资源,形成一个进程等待环路。环路中每一个进程已占有的资源同时被另一个进程所申请,即前一个进程占有后个进程所请求的资源。

以上给出了导致死锁的四个必要条件。只要系统发生死锁,则以上四个条件一定成立。

事实上,第四个条件(即循环等待)的成立蕴含了前三个条件的成立,似乎没有必要全部列出。然而,分别考虑这些条件对于死锁的预防是有利的,因为可以通过破坏这四个条件中的任何一个来预防死锁的发生,这就为死锁预防提供了多种途径。

解决死锁的方法有很多,一类是不让死锁发生;另一类是检测死锁是否发生,再加以解决,以下列出的四种方法对进程的限制由严到宽,并发程度由低到高。

1.预防死锁

通过设置某些严格限制,破坏产生死锁的必要条件以防止死锁发生。这一方法可能会导致系统资源利用率过低。

2.避免死锁

在资源的动态分配过程中,采取某种方法防止系统进入不安全状态,从而避免死锁的发生。这种方法只需以较弱的限制条件为代价,并可获得较高的资源利用。

3.检测与解除死锁

在系统运行过程中,通过在系统中设置检测机构,定时检测死锁是否真的发生,并能精确地确定与死锁有关的进程与资源,然后采取措施解除死锁,将进程从死锁状态下解脱岀来。

4.忽略死锁

对于那些死锁发生的几率极低,而解决死锁的方法代价极大或暂时没有办法解决的死锁问题暂时不予理睬。

更多自考教程请关注ww1.fzydk.com。

点赞