hosteons中文网

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

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

系统模型

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

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

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

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

在正常操作模式下，进程只能按如下顺序使用资源：

• 申请：进程请求资源。如果申请不能立即被允许（例如，申请的资源正在被其他进程使用)，那么申请进程应等待，直到它能获得该资源为止。
• 使用：进程对资源进行操作（例如，如果资源是打印机，那么进程就可以在打印机上打印了）。
• 释放：进程释放资源。

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

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

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

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

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

死锁特征

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

必要条件

如果在一个系统中以下四个条件同时成立，那么就能引起死锁：

1. 互斥：至少有一个资源必须处于非共享模式，即一次只有一个进程可使用。如果另一进程申请该资源，那么申请进程应等到该资源释放为止。
2. 占有并等待：—个进程应占有至少一个资源，并等待另一个资源，而该资源为其他进程所占有。
3. 非抢占：资源不能被抢占，即资源只能被进程在完成任务后自愿释放。
4. 循环等待：有一组等待进程 {P₀，P₁，…，P_n}，P₀ 等待的资源为 P₁ 占有，P₁ 等待的资源为 P₂ 占有，……，P_n-1 等待的资源为 P_n 占有，P_n 等待的资源为 P₀ 占有。

我们强调所有四个条件必须同时成立才会出现死锁。循环等待条件意味着占有并等待条件，这样四个条件并不完全独立。

资源分配图

通过称为系统资源分配图的有向图可以更精确地描述死锁。该图包括一个节点集合 V 和一个边集合 E。节点集合 V 可分成两种类型：P={P₁，p₂,…，P_n}（系统所有活动进程的集合）和 R={R₁，R₂，…，R_m}（系统所有资源类型的集合）。

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

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

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

图 1 资源分配图