首页 > 编程笔记 > 操作系统笔记

什么是死锁,死锁的原因及解决办法(含四个必要条件)

在多道程序环境中,多个进程可以竞争有限数量的资源。当一个进程申请资源时,如果这时没有可用资源,那么这个进程进入等待状态。有时,如果所申请的资源被其他等待进程占有,那么该等待进程有可能再也无法改变状态。这种情况称为死锁

或许,死锁的最好例证是 Kansas 立法机构在 20 世纪初通过的一项法律,其中说到“当两列列车在十字路口逼近时,它们应完全停下来,并且在一列列车开走之前另一列列车不能再次启动。”

系统模型

有一个系统拥有有限数量的资源,需要分配到若干竞争进程。这些资源可以分成多种类型,每种类型有一定数量的实例。资源类型有很多,如 CPU 周期、文件、I/O 设备(打印机和 DVD 驱动器)等。如果一个系统有两个 CPU,那么资源类型 CPU 就有两个实例。类似地,资源类型打印机可能有 5 个实例。

如果一个进程申请某个资源类型的一个实例,那么分配这种类型的任何实例都可满足申请。否则,这些实例就不相同,并且资源分类没有定义正确。例如,一个系统有两台打印机。如果没有人关心哪台打印机打印哪些输出,那么这两台打印机可定义为属于同样的资源类型。然而,如果一台打印机在九楼,而另一台在底楼,那么九楼的用户就不会认为这两台打印机是相同的,这样每个打印机就可能需要定义成属于单独的类型。

各种同步工具如互斥锁和信号量,也应作为系统资源,它们是常见的死锁源。然而,一个锁通常与保护某个特定的数据结构相关联,即一个锁可用于保护队列的访问,另一个锁保护访问链接列表的访问,等等。由于这个原因,每个锁通常有自己的资源类型,并且这种定义不是一个问题。

进程在使用资源前应申请资源,在使用资源之后应释放资源。一个进程可能要申请许多资源,以便完成指定任务。显然,申请的资源数量不能超过系统所有资源的总和。换言之,如果系统只有两台打印机,那么进程就不能申请三台打印机。

在正常操作模式下,进程只能按如下顺序使用资源:
当进程或线程每次使用内核管理的资源时,操作系统会检查以确保该进程或线程已经请求并获得了资源。系统表记录每个资源是否是空闲的或分配的。对于每个已分配的资源,该表还记录了它被分配的进程。如果进程申请的资源正在为其他进程所使用,那么该进程会添加到该资源的等待队列上。

当一组进程内的每个进程都在等待一个事件,而这一事件只能由这一组进程的另一个进程引起,那么这组进程就处于死锁状态。这里所关心的主要事件是资源的获取和释放。资源可能是物理资源(例如,打印机、磁带驱动器、内存空间和 CPU 周期)或逻辑资源(例如,信号量、互斥锁和文件)。然而,其他类型的事件也会导致死锁(例如 IPC 功能)。

为说明死锁状态,假设一个系统具有三个 CD 刻录机。假定有三个进程,每个进程都占用了一台 CD 刻录机。如果每个进程现在需要另一台刻录机,那么这三个进程会处于死锁状态。每个进程都在等待事件“CD刻录机被释放”,这仅可能由一个等待进程来完成。这个例子说明了涉及同一种资源类型的死锁。

死锁也可能涉及不同资源类型。例如,假设一个系统有一台打印机和一台 DVD 驱动器。假如进程 Pi 占有 DVD 驱动器而进程 P2 占有打印机。如果 Pi 申请打印机而 Pj 申请 DVD 驱动器,那么就会出现死锁。

多线程应用程序的开发人员应始终警惕可能的死锁。多线程应用程序容易死锁,因为多线程可能竞争共享资源。

死锁特征

发生死锁时,进程永远不能完成,系统资源被阻碍使用,以致于阻止了其他作业开始执行。在讨论处理死锁问题的各种方法之前,我们首先深入讨论一下死锁特点。

必要条件

如果在一个系统中以下四个条件同时成立,那么就能引起死锁:
  1. 互斥:至少有一个资源必须处于非共享模式,即一次只有一个进程可使用。如果另一进程申请该资源,那么申请进程应等到该资源释放为止。
  2. 占有并等待:—个进程应占有至少一个资源,并等待另一个资源,而该资源为其他进程所占有。
  3. 非抢占:资源不能被抢占,即资源只能被进程在完成任务后自愿释放。
  4. 循环等待:有一组等待进程 {P0,P1,…,Pn},P0 等待的资源为 P1 占有,P1 等待的资源为 P2 占有,……,Pn-1 等待的资源为 Pn 占有,Pn 等待的资源为 P0 占有。
我们强调所有四个条件必须同时成立才会出现死锁。循环等待条件意味着占有并等待条件,这样四个条件并不完全独立。

资源分配图

通过称为系统资源分配图的有向图可以更精确地描述死锁。该图包括一个节点集合 V 和一个边集合 E。节点集合 V 可分成两种类型:P={P1,p2,…,Pn}(系统所有活动进程的集合)和 R={R1,R2,…,Rm}(系统所有资源类型的集合)。

从进程 Pi 到资源类型 Rj 的有向边记为 Pi->Rj,它表示进程 Pi 已经申请了资源类型 Rj 的一个实例,并且正在等待这个资源。从资源类型 Rj 到进程 Pi 的有向边记为 Rj->Pi,它表示资源类型 Rj 的一个实例已经分配给了进程 Pi。有向边 Pi->Rj 称为申请边,有向边 Rj->Pi 称为分配边

在图形上,用圆表示进程 Pi,用矩形表示资源类型 Rj。由于资源类型 Rj 可能有多个实例,所以矩形内的点的数量表示实例数量。注意申请边只指向矩形 Rj,而分配边应指定矩形内的某个圆点。

当进程 Pi 申请资源类型 Rj 的一个实例时,就在资源分配图中加入一条申请边。当该申请可以得到满足时,那么申请边就立即转换成分配边。当进程不再需要访问资源时,它就释放资源,因此就删除了分配边。

资源分配图
图 1 资源分配图

图 1 的资源分配图表示了如下情况:
  1. 集合 P、R 和 E:
    • P={P1,P2,P3}
    • R={R1,R2,R3,R4}
    • E={P-> R1,P-> R3,R-> P2,R-> P2,R-> P1,R3 -> P3}
  2. 资源实例:
    • 资源类型 R1 有 1 个实例;
    • 资源类型 R2 有 2 个实例;
    • 资源类型 R3 有 1 个实例;
    • 资源类型 R4 有 3 个实例;
  3. 进程状态:
    • 进程 P1 占有资源类型 R2 的 1 个实例,等待资源类型 R1 的 1 个实例。
    • 进程 P2 占有资源类型 R1 的 1 个实例和资源类型 R2 的 1 个实例,等待资源类型 R3 的 1 个实例。
    • 进程 P3 占有资源类型 R3 的 1 个实例。

根据资源分配图的定义,可以证明:如果分配图没有环,那么系统就没有进程死锁。如果分配图有环,那么可能存在死锁。

如果每个资源类型刚好有一个实例,那么有环就意味着已经出现死锁。如果环上的每个类型只有一个实例,那么就出现了死锁。环上的进程就死锁。在这种情况下,图中的环就是死锁存在的充分且必要条件。

如果每个资源类型有多个实例,那么有环并不意味着已经出现了死锁。在这种情况下,图中的环就是死锁存在的必要条件而不是充分条件。

为了说明这点,下面回到图 1 所示资源分配图。假设进程 P3 申请了资源类型 R2 的一个资源。由于现在没有资源实例可用,所以就增加了有向边 P-> R2(图 2)。

存在死锁的资源分配图
图 2 存在死锁的资源分配图

这时,系统有两个最小环:

P1—> R1 —> P2 一> R3 —> P3 —> R2 —> P1
P2 —> R3 —> P3 —> R2 —> P2

进程 P1、P2 和 P3 死锁了。进程 P2 等待资源类型 R3,而它又被进程 R3 占有。进程 P3 等待进程 P1 或进程 P2 以释放资源类型 R2。另外,进程 P1 等待进程 P2 释放资源 R1。

具有环的并未死锁的资源分配图
图 3 具有环的并未死锁的资源分配图

现在考虑图 3 所示的资源分配图。在这个例子中,也有一个环:

P1 —> R1 —> P3 —> R2 —> P1

然而,并没有死锁。注意,进程 P4 可能释放资源类型 R2 的实例。这个资源可分配给进程 P3,从而打破环。

总而言之,如果资源分配图没有环,那么系统就不处于死锁状态。如果有环,那么系统可能会也可能不会处于死锁状态。在处理死锁问题时,这点是很重要的。

死锁处理方法

一般来说,处理死锁问题有三种方法:
  1. 通过协议来预防或避免死锁,确保系统不会进入死锁状态。
  2. 可以允许系统进入死锁状态,然后检测它,并加以恢复。
  3. 可以忽视这个问题,认为死锁不可能在系统内发生。

第三种解决方案为大多数操作系统所采用,包括 Linux 和 Windows。因此,应用程序开发人员需要自己编写程序,以便处理死锁。

接下来,我们简要阐述每种死锁处理方法。在进行之前,我们应该提一下,有些研究人员认为,这些基本方法不能单独用于处理操作系统的所有资源分配问题。然而,可以将这些基本方法组合起来,为每种系统资源选择一种最佳方法。

为了确保死锁不会发生,系统可以采用死锁预防或死锁避免方案。死锁预防方法确保至少有一个必要条件不成立。这些方法通过限制如何申请资源的方法来预防死锁。

死锁避免要求,操作系统事先得到有关进程申请资源和使用资源的额外信息。有了这些额外信息,系统可以确定对于每个申请,进程是否应等待。为了确定当前申请是允许还是延迟,系统应考虑现有的可用资源、已分配给每个进程的资源及每个进程将来申请和释放的资源。

如果系统不使用死锁预防或死锁避免算法,那么死锁情况可能发生。在这种情况下,系统可以提供一个算法来检查系统状态以确定死锁是否发生,提供另一个算法来从死锁中恢复(如果死锁确实已经发生)。

当没有算法用于检测和恢复死锁时,可能出现这样的情况,系统处于死锁,而又没有方法检测到底发生了什么。在这种情况下,未被发现的死锁会导致系统性能下降,因为资源被不能运行的进程占有,而越来越多的进程会因申请资源而进入死锁。最后,整个系统会停止工作,且需要人工重新启动。

虽然这看起来似乎不是一个解决死锁问题的可行方法,但是它却为大多数操作系统所采用,许多系统死锁很少发生,因此与使用频繁的并且开销昂贵的死锁预防、死锁避免和死锁检测与恢复相比,这种方法更为便宜。

此外,在有些情况下,系统处于冻结状态而不是死锁状态。例如,一个实时进程按最高优先级来运行(或其他进程在非抢占调用程序下运行),并且不将控制返回到操作系统。因此,系统应有人工方法可从这些状态中恢复过来,这些方法也可用于死锁恢复。

所有教程

优秀文章