产生死锁的必要条件

虽然进程在运行过程中可能发生死锁,但死锁的发生也必须具备一定的条件。综上所述不难看出,死锁的发生必须具备下列四个必要条件。

(1) 互斥条件:指进程对所分配到的资源进行排它性使用,即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求该资源,则请求者只能等待,直至占有该资源的进程用毕释放。

(2) 请求和保持条件:指进程已经保持了至少一个资源,但又提出了新的资源请求,而该资源又已被其它进程占有,此时请求进程阻塞,但又对自己已获得的其它资源保持不放。

(3) 不剥夺条件:指进程已获得的资源,在未使用完之前,不能被剥夺,只能在使用完时由自己释放。

(4) 环路等待条件:指在发生死锁时,必然存在一个进程——资源的环形链,即进程集合{P0,P1,P2,…,Pn}中的P0正在等待一个P1占用的资源; P1正在等待P2占用的资源,……,Pn正在等待已被P0占用的资源。

处理死锁的基本方法

为保证系统中诸进程的正常运行,应事先采取必要的措施,来预防发生死锁。在系统中已经出现死锁后,则应及时检测到死锁的发生,并采取适当措施来解除死锁。目前,处理死锁的方法可归结为以下四种:

(1) 预防死锁。这是一种较简单和直观的事先预防的方法。该方法是通过设置某些限制条件,去破坏产生死锁的四个必要条件中的一个或几个条件,来预防发生死锁。预防死锁是一种较易实现的方法,已被广泛使用。但由于所施加的限制条件往往太严格,因而可能会导致系统资源利用率和系统吞吐量降低。

(2) 避免死锁。该方法同样是属于事先预防的策略,但它并不须事先采取各种限制措施去破坏产生死锁的四个必要条件,而是在资源的动态分配过程中,用某种方法去防止系统进入不安全状态,从而避免发生死锁。这种方法只需事先施加较弱的限制条件,便可获得较高的资源利用率及系统吞吐量,但在实现上有一定的难度。目前在较完善的系统中常用此方法来避免发生死锁。

(3) 检测死锁。这种方法并不须事先采取任何限制性措施,也不必检查系统是否已经进入不安全区,而是允许系统在运行过程中发生死锁。但可通过系统所设置的检测机构,及时地检测出死锁的发生,并精确地确定与死锁有关的进程和资源; 然后,采取适当措施,从系统中将已发生的死锁清除掉。

(4) 解除死锁。这是与检测死锁相配套的一种措施。当检测到系统中已发生死锁时,须将进程从死锁状态中解脱出来。常用的实施方法是撤消或挂起一些进程,以便回收一些资源,再将这些资源分配给已处于阻塞状态的进程,使之转为就绪状态,以继续运行。死锁的检测和解除措施有可能使系统获得较好的资源利用率和吞吐量,但在实现上难度也最大。

预防死锁的方法

如前所述,预防死锁和避免死锁这两种方法实质上都是通过施加某些限制条件,来预防发生死锁。两者的主要差别在于:为预防死锁所施加的限制条件较严格,这往往会影响进程的并发执行;而为避免死锁所施加的限制条件则较宽松,这给进程的运行提供了较宽松的环境,有利于进程的并发执行。

预防死锁

预防死锁的方法是使四个必要条件中的第2、3、4 个条件之一不能成立,来避免发生死锁。至于必要条件1,因为它是由设备的固有特性所决定的,不仅不能改变,还应加以保证。

1.摒弃“请求和保持”条件

在采用这种方法时,系统规定所有进程在开始运行之前,都必须一次性地申请其在整个运行过程所需的全部资源。此时,若系统有足够的资源分配给某进程,便可把其需要的所有资源分配给该进程,这样,该进程在整个运行期间便不会再提出资源要求,从而摒弃了请求条件。但在分配资源时,只要有一种资源不能满足某进程的要求,即使其它所需的各资源都空闲,也不分配给该进程,而让该进程等待。由于在该进程的等待期间,它并未占有任何资源,因而也摒弃了保持条件,从而可以避免发生死锁。

这种预防死锁的方法其优点是简单、易于实现且很安全。但其缺点却也极其明显:首先表现为资源被严重浪费,因为一个进程是一次性地获得其整个运行过程所需的全部资源的,且独占资源,其中可能有些资源很少使用,甚至在整个运行期间都未使用,这就严重地恶化了系统资源的利用率;其次是使进程延迟运行,仅当进程在获得了其所需的全部资源后,才能开始运行,但可能因有些资源已长期被其它进程占用而致使等待该资源的进程迟迟不能运行。

2.摒弃“不剥夺”条件

在采用这种方法时系统规定,进程是逐个地提出对资源的要求的。当一个已经保持了某些资源的进程,再提出新的资源请求而不能立即得到满足时,必须释放它已经保持了的所有资源,待以后需要时再重新申请。这意味着某一进程已经占有的资源,在运行过程中会被暂时地释放掉,也可认为是被剥夺了,从而摒弃了“不剥夺”条件。

这种预防死锁的方法实现起来比较复杂且要付出很大的代价。因为一个资源在使用一段时间后,它的被迫释放可能会造成前段工作的失效,即使是采取了某些防范措施,也还会使进程前后两次运行的信息不连续,例如,进程在运行过程中已用打印机输出信息,但中途又因申请另一资源未果而被迫暂停运行并释放打印机,后来系统又把打印机分配给其它进程使用。当进程再次恢复运行并再次获得打印机继续打印时,这前后两次打印输出的数据并不连续,即打印输出的信息其中间有一段是另一进程的。此外,这种策略还可能因为反复地申请和释放资源,致使进程的执行被无限地推迟,这不仅延长了进程的周转时间,而且也增加了系统开销,降低了系统吞吐量。

3.摒弃“环路等待”条件

这种方法中规定,系统将所有资源按类型进行线性排队,并赋予不同的序号。例如,令输入机的序号为1,打印机的序号为2,磁带机为3,磁盘为4。所有进程对资源的请求必须严格按照资源序号递增的次序提出,这样,在所形成的资源分配图中,不可能再出现环路,因而摒弃了“环路等待”条件。事实上,在采用这种策略时,总有一个进程占据了较高序号的资源,此后它继续申请的资源必然是空闲的,因而进程可以一直向前推进。

这种预防死锁的策略与前两种策略比较,其资源利用率和系统吞吐量都有较明显的改善。但也存在下述严重问题:

首先是为系统中各类资源所分配(确定)的序号必须相对稳定,这就限制了新类型设备的增加。

其次,尽管在为资源的类型分配序号时,已经考虑到大多数作业在实际使用这些资源时的顺序,但也经常会发生这种情况:即作业(进程)使用各类资源的顺序与系统规定的顺序不同,造成对资源的浪费。例如,某进程先用磁带机,后用打印机,但按系统规定,该进程应先申请打印机而后申请磁带机,致使先获得的打印机被长时间闲置。

第三,为方便用户,系统对用户在编程时所施加的限制条件应尽量少。然而这种按规定次序申请的方法,必然会限制用户简单、自主地编程。

死锁的解除

当发现有进程死锁时,便应立即把它们从死锁状态中解脱出来。常采用解除死锁的两种方法是:

(1) 剥夺资源。从其它进程剥夺足够数量的资源给死锁进程,以解除死锁状态。

(2) 撤消进程。最简单的撤消进程的方法是使全部死锁进程都夭折掉;稍微温和一点的方法是按照某种顺序逐个地撤消进程,直至有足够的资源可用,使死锁状态消除为止。