死锁

在并发系统中，当多个线程或进程需要同时访问多个共享资源时，如果它们按照不同的顺序请求这些资源，就可能陷入一种特殊的阻塞状态。假设有两个线程都需要使用资源A和资源B，第一个线程按照先A后B的顺序请求，第二个线程按照先B后A的顺序请求。如果第一个线程已经获取了资源A，第二个线程已经获取了资源B，那么第一个线程将等待资源B的释放，而第二个线程将等待资源A的释放。由于两个线程都在等待对方持有的资源，它们都无法继续执行，系统进入死锁状态。

在计算机系统中，死锁是并发编程中的一个经典问题。当多个线程或进程竞争有限的资源时，如果每个线程都在等待其他线程释放资源，而其他线程也在等待，就会形成死锁。死锁是指一组进程或线程互相等待对方释放资源，导致所有相关进程都无法继续执行的状态。

系统模型

为了更好地理解死锁，我们需要先建立一个系统模型。计算机系统可以被抽象为一个资源分配系统，其中包含多种类型的资源，这些资源需要被分配给不同的线程使用。

资源的分类

系统中的资源可以分为不同的类型，每种类型可能有多个相同的实例。 比如CPU时间、文件、网络接口、打印机等都属于资源类型。 如果系统有4个CPU核心，那么CPU资源类型就有4个实例；如果系统有2个网络接口，那么网络资源类型就有2个实例。

在我们的讨论中，最重要的资源类型是同步工具，比如互斥锁和信号量。 这些是当代计算机系统中最常见的死锁来源。每个锁通常与特定的数据结构相关联，比如一个锁保护队列，另一个锁保护链表等。

资源使用的标准流程

线程使用资源必须遵循一个标准的流程：请求、使用、释放。首先，线程必须请求资源；如果资源不可用，线程就必须等待。 然后，线程可以使用资源进行工作。最后，线程必须释放资源，让其他线程可以使用。

这个流程可以用系统调用来实现，比如设备的 request() 和 release()，文件的 open() 和 close()，内存的 allocate() 和 free()。对于互斥锁，我们使用 acquire() 和 release()；对于信号量，我们使用 wait() 和 signal()。

操作系统会维护一个系统表来记录每个资源的状态——是空闲的还是已分配的。对于已分配的资源，表还会记录是哪个线程在使用它。如果线程请求的资源当前被其他线程占用，请求线程就会被添加到等待队列中。

多线程应用中的死锁

让我们通过一个具体的例子来看看死锁是如何在多线程程序中发生的。这个例子使用POSIX线程库的互斥锁。 假设我们有两个互斥锁：first_mutex 和 second_mutex。我们创建两个线程，每个线程都需要同时使用这两个锁。

|
pthread_mutex_t first_mutex;
pthread_mutex_t second_mutex;
 
pthread_mutex_init(&first_mutex, NULL);
pthread_mutex_init(&second_mutex, NULL);

第一个线程按照这样的顺序获取锁：先获取 first_mutex，再获取 second_mutex。第二个线程按照相反的顺序：先获取 second_mutex，再获取 first_mutex。

|
/* 第一个线程执行的函数 */
void *do_work_one(void *param)
{
    pthread_mutex_lock(&first_mutex);    // 获取第一个锁
    pthread_mutex_lock(&second_mutex);   // 获取第二个锁
    
    /* 执行一些工作 */
    
    pthread_mutex_unlock(&second_mutex); // 释放第二个锁
    pthread_mutex_unlock(&first_mutex);  // 释放第一个锁
    pthread_exit(0);
}

如果两个线程同时开始执行，第一个线程可能已经获取了 first_mutex，第二个线程可能已经获取了 second_mutex。这时候，第一个线程在等待 second_mutex，第二个线程在等待 first_mutex，这样就形成了死锁。

死锁的不确定性

值得注意的是，死锁并不总是会发生。如果第一个线程能够快速完成工作并释放所有锁，然后第二个线程才开始执行，那么就不会发生死锁。死锁的发生取决于CPU调度器的调度顺序和线程执行的时序，这使得死锁问题具有不确定性，难以预测和测试。

活锁问题

除了死锁之外，在并发编程中还存在着另一种活跃性问题，称为活锁。活锁与死锁相似，都能导致两个或多个线程无法顺利执行，但两者的本质机制不同。

在死锁状态下，线程完全阻塞，处于等待状态，无法继续执行。而在活锁状态下，线程并未完全阻塞，而是持续执行某些操作，但这些操作无法使线程取得实际进展。线程不断重试失败的操作，形成一种无效的循环执行模式。

活锁和死锁的共同点是线程都无法完成自己的任务。两者的区别在于：死锁时线程完全停滞，处于阻塞状态；而活锁时线程仍在执行，但执行的操作无法产生有效结果。活锁通常发生在多个线程同时重试失败操作，且重试策略过于同步的情况下。

活锁的代码示例

让我们修改之前的例子，使用 pthread_mutex_trylock() 函数，这个函数尝试获取锁但不会阻塞：

|
/* 第一个线程执行的函数 */
void *do_work_one(void *param)
{
    int done = 0;
    while (!done) {
        pthread_mutex_lock(&first_mutex);
        if (pthread_mutex_trylock(&second_mutex)) {
            /* 执行一些工作 */
            pthread_mutex_unlock(&second_mutex);
            pthread_mutex_unlock(&first_mutex);

如果第一个线程获取了 first_mutex，第二个线程获取了 second_mutex，那么每个线程调用 pthread_mutex_trylock() 都会失败，释放自己的锁，然后重复相同的操作，形成活锁。

避免活锁的方法

活锁通常发生在多个线程同时重试失败操作的时候。避免活锁的一般方法是让每个线程在重试失败操作时使用随机的时间间隔。 这正是以太网网络在发生网络冲突时采用的方法。发生冲突的主机不会立即重传数据包，而是会等待一个随机的时间间隔后再尝试传输。

活锁比死锁更少见，但在设计并发应用程序时同样是一个具有挑战性的问题。和死锁一样，活锁也可能只在特定的调度情况下发生。

死锁的特征

要理解死锁，我们需要明确死锁发生的必要条件。死锁需要同时满足四个条件，这些条件被称为死锁的充分必要条件：

• 互斥条件：至少有一个资源必须以非共享的方式使用。同一时间只能有一个线程使用该资源。如果另一个线程请求该资源，请求线程必须等待，直到资源被释放。例如，互斥锁、打印机等独占资源都满足互斥条件。
• 占有和等待条件：线程必须已经占有了至少一个资源，并且正在等待获取其他被其他线程占有的资源。线程在持有资源的同时请求新的资源，这是死锁形成的关键条件之一。
• 非抢占条件：资源不能被强制性地从占有它的线程那里夺走。资源只能由占有它的线程主动释放，在完成工作之后。这意味着操作系统不能强制回收已分配的资源。
• 循环等待条件：必须存在一个线程的循环等待链。例如，线程T0在等待T1释放资源，T1在等待T2释放资源，T2在等待T3释放资源，而T3又在等待T0释放资源，形成了一个循环等待链。

资源分配图

为了更直观地理解死锁，我们可以使用资源分配图这一工具。资源分配图是一种有向图，用于表示系统中线程和资源之间的关系，以及资源的分配和请求状态。

图的构成

资源分配图由顶点和边组成。顶点分为两类：线程节点（用圆圈表示）和资源节点（用矩形表示）。边表示线程和资源之间的关系。

从线程到资源的边叫做请求边，表示线程正在等待这个资源。从资源到线程的边叫做分配边，表示资源已经被分配给这个线程。 如果资源类型有多个实例，我们用矩形内的点来表示每个实例。

死锁的检测

资源分配图的一个重要性质是：如果图中没有环，那么系统中就没有死锁。如果图中有环，那么可能存在死锁。 如果每个资源类型只有一个实例，那么环的存在就意味着死锁已经发生。如果资源类型有多个实例，那么环的存在只是死锁的必要条件，但不是充分条件。

让我们看一个具体的例子。假设我们有两个线程T1和T2，两个资源R1和R2。T1已经占有了R1，正在等待R2；T2已经占有了R2，正在等待R1。

这个图中存在一个环：T1 → R2 → T2 → R1 → T1，所以存在死锁。

更复杂的例子

让我们看一个更复杂的例子，有三个线程T1、T2、T3和四个资源R1、R2、R3、R4：

在这个图中，T1占有R2，等待R1；T2占有R1和R2，等待R3；T3占有R3。如果T3请求R2，就会形成环，导致死锁。

环与死锁的关系

但是，环的存在并不总是意味着死锁。如果资源有多个实例，那么即使有环，也可能没有死锁。 比如，如果T4释放了R2的一个实例，T3就可以获得这个资源，从而打破环。

死锁处理方法

面对死锁问题，我们主要有三种处理方法：

• 鸵鸟策略：完全忽略死锁问题，假设死锁永远不会发生。大多数操作系统，包括Linux和Windows，都采用这种方法。死锁的预防、避免和检测由内核和应用程序开发者负责实现。
• 预防和避免策略：使用协议来预防或避免死锁，确保系统永远不会进入死锁状态。这种方法在问题发生之前就采取措施，通过限制资源请求的方式或顺序来防止死锁。
• 检测和恢复策略：允许系统进入死锁状态，然后通过检测算法识别死锁并从中恢复。一些系统，比如数据库系统，采用这种方法。

策略的选择

在操作系统中，由于资源类型多样、系统复杂，没有单一的死锁处理方法能够适用于所有场景。实际应用中，我们可以灵活组合这些方法，针对不同类型的资源选择最合适的处理方式，以提高系统效率和实用性。

死锁预防

死锁预防的核心思想是破坏死锁发生的四个必要条件中的至少一个，从而从源头上防止死锁的发生。接下来，我们逐一分析如何破坏这四个条件。

破坏互斥条件

互斥条件要求至少有一个资源必须以非共享的方式使用。某些资源本质上是独占的，例如互斥锁、写文件操作等，这些资源在同一时间只能被一个线程使用。

如果资源可以被多个线程同时共享使用，就不会产生死锁。例如，只读文件可以被多个线程同时打开和读取，互不影响，因此不会导致死锁。然而，许多资源由于其本质特性必须保持互斥性，例如互斥锁、信号量等同步原语。因此，通过破坏互斥条件来预防死锁的方法在实际应用中受到很大限制，因为许多关键资源本身就需要互斥访问。

破坏占有和等待条件

破坏占有和等待条件要求线程在请求新资源时不能持有其他资源。实现这一目标有两种主要方法：

第一种方法是要求线程在开始执行前一次性申请所有需要的资源。这种方法虽然简单，但在实际应用中很难实现，因为线程在执行过程中才能确定需要哪些资源，资源的动态需求使得预先申请所有资源变得不现实。

第二种方法是要求线程只有在不持有任何资源时才能申请新资源。也就是说，线程必须在使用完一批资源并全部释放后，才能申请新的资源。

这两种方法都存在明显的缺点。首先，资源利用率会显著降低。线程可能申请了所有资源但只使用其中一部分，导致其他资源被长时间占用而无法被其他线程使用。其次，容易出现饥饿现象。如果某个线程总是需要被其他线程频繁占用的资源，它可能永远无法获得所需的资源，导致无限期等待。

破坏非抢占条件

非抢占条件要求资源不能被强制性地从占有它的线程那里夺走。要破坏这一条件，我们可以采用资源抢占策略：如果一个线程持有资源并请求新资源，但新资源暂时无法获得，系统可以要求该线程释放所有已持有的资源，等待能够一次性获得所有所需资源时再重新开始执行。

这种资源抢占方法适用于状态容易保存和恢复的资源，例如CPU寄存器、内存页面、数据库事务等。对于这些资源，系统可以保存线程的当前状态，强制回收资源，然后在资源可用时恢复线程状态并重新执行。

然而，对于互斥锁、信号量等同步原语，强制抢占会导致线程状态不一致，破坏同步语义，因此一般不适用。而这些同步原语恰恰是死锁问题最常见的来源。

破坏循环等待条件

前面三种方法在实际应用中存在明显局限性。相比之下，破坏循环等待条件是最实用和常用的死锁预防方法。

实现方法是建立所有资源的全序关系，要求所有线程必须按照这个顺序申请资源。具体来说，我们为每个资源分配一个唯一的序号，线程在申请多个资源时必须按照序号从小到大的顺序进行，不允许逆序申请。

例如，假设我们有多把互斥锁，每把锁都有唯一的编号。线程如果需要使用多把锁，必须按照编号顺序依次获取，不能先获取编号大的锁再获取编号小的锁。在Pthread程序中，我们可以为每个互斥锁定义排序函数：

|
F(first_mutex) = 1
F(second_mutex) = 5

另一种实现方式是：如果线程需要申请一个编号小于当前已持有锁的锁，它必须首先释放所有已持有的锁，然后按照正确的顺序重新申请所有需要的锁。

为什么这种方法能够防止死锁？假设存在一个循环等待链，那么按照资源排序的要求，这个链中的资源编号必须单调递增。然而，循环等待链必须回到起点，这意味着编号必须同时满足递增和回到起点的条件，这在数学上是不可能的。因此，只要所有线程都按照资源排序申请资源，就不可能形成循环等待，死锁也就无法发生。

死锁避免

死锁预防通过限制资源请求的方式或顺序来防止死锁，但这种方法可能会降低资源利用率和系统效率。死锁避免采用了一种不同的策略：系统预先了解每个线程的资源需求模式，在每次资源请求时动态判断是否会导致系统进入不安全状态，从而决定是否批准该请求。

死锁避免要求系统预先知道每个线程的资源请求序列。例如，线程P按照先R1后R2的顺序请求资源，线程Q按照先R2后R1的顺序请求资源。系统在每次资源请求时进行安全性检查：如果批准当前请求会导致系统进入不安全状态，则延迟该请求，直到系统能够安全地满足该请求。通过这种方式，系统可以动态地避免死锁的发生。

安全状态

安全状态是指系统存在一个执行序列，使得所有线程都能获得所需的资源并完成执行。具体来说，如果系统能够找到一个线程执行顺序，使得按照这个顺序，每个线程都能在某个时刻获得它所需的所有资源，完成执行后释放资源，然后下一个线程继续执行，那么系统就处于安全状态。

安全状态的一个重要性质是：如果系统处于安全状态，则不存在死锁。不安全状态是指系统可能无法让所有线程都完成执行，但不安全状态并不等同于死锁。只有当多个线程互相等待对方释放资源，形成循环等待时，才会发生死锁。

为了说明安全状态的概念，考虑一个有十二个资源和三个线程的系统：T0、T1和T2。

假设系统有12个资源，三个线程T0、T1、T2的最大需求分别为10、4、9个资源。当前T0持有5个，T1持有2个，T2持有2个，因此系统中有3个可用资源。

在时刻t0，系统处于安全状态。我们可以找到一个执行序列：首先T1获得所需的剩余资源并完成执行，释放所有资源后系统有5个可用资源；然后T0获得所需的剩余资源并完成执行，释放后系统有10个可用资源；最后T2获得所需资源并完成执行。按照这个序列，所有线程都能完成执行，因此系统是安全的。

如果系统在时刻t1批准了T2的一个额外资源请求，系统可能进入不安全状态。此时只有T1能够完成执行，而T0和T2可能因为资源不足而无法继续。如果T0和T2互相等待对方释放资源，就会发生死锁。问题的根源在于系统过早地批准了T2的请求。如果延迟T2的请求，等待其他线程完成并释放资源后再批准，就可以避免死锁。

死锁避免的核心思想是：系统在每次资源请求时进行安全性检查，如果批准当前请求会导致系统进入不安全状态，则延迟该请求，直到系统能够安全地满足该请求。通过这种方式，系统可以始终保持安全状态，从而避免死锁。这种方法的代价是可能降低资源利用率，因为即使资源可用，如果会导致不安全状态，请求也会被延迟。

银行家算法

资源分配图方法只适用于每种资源类型只有一个实例的情况。在实际系统中，许多资源类型都有多个实例，例如多台打印机、多个数据库连接等。对于这种情况，我们需要使用银行家算法来进行死锁避免。

银行家算法得名于银行放贷的类比：银行在放贷时需要确保无论客户如何取款，银行都不会破产，所有客户都能安全地完成交易。银行家算法借鉴了这一思想，确保系统在分配资源时不会导致所有线程都无法完成执行。

银行家算法的实现要求：每当新线程加入系统时，它必须声明其最大资源需求，即每种资源类型最多需要多少个实例。这个最大需求不能超过系统中该资源类型的总实例数。此后，每当线程请求资源时，系统都会进行安全性检查：如果批准当前请求后系统仍能保持安全状态，则批准请求；否则，延迟该请求直到系统能够安全地满足它。通过这种方式，系统可以始终保持安全状态，从而避免死锁。

银行家算法的数据结构

银行家算法需要维护以下数据结构来跟踪资源分配状态。假设系统中有n个线程和m种资源类型，需要维护以下数据结构：

• Available：长度为m的向量，指示每种类型的可用资源数量。如果Available[j]等于k，那么资源类型Rj的k个实例可用。
• Max：n乘以m矩阵定义每个线程的最大需求。如果Max[i][j]等于k，那么线程Ti最多可以请求资源类型Rj的k个实例。
• Allocation：n乘以m矩阵定义当前分配给每个线程的每种类型的资源数量。如果Allocation[i][j]等于k，那么线程Ti当前被分配了资源类型Rj的k个实例。
• Need：n乘以m矩阵指示每个线程的剩余资源需求。如果Need[i][j]等于k，那么线程Ti可能需要资源类型Rj的k个更多实例来完成其任务。注意Need[i][j]等于Max[i][j]减去Allocation[i][j]。

这些数据结构在大小和值上都随时间变化。

安全算法

我们现在可以看看找出系统是否处于安全状态的算法了。这个算法可以描述如下：

资源请求算法

资源请求算法用于判断一个线程的资源请求是否能够安全地分配。假设Requesti是线程Ti的资源请求向量，其中Requesti[j]等于k表示线程Ti请求资源类型Rj的k个实例。每当线程Ti请求资源时，系统需要检查：如果批准该请求，系统是否仍能保持安全状态。算法步骤如下：

银行家算法示例

为了说明银行家算法的使用，考虑一个有五个线程T0到T4和三个资源类型A、B和C的系统。资源类型A有十个实例，资源类型B有五个实例，资源类型C有七个实例。假设以下快照表示系统的当前状态：

Need矩阵的内容定义为Max减去Allocation，如下所示：

可以验证，当前系统处于安全状态。例如，按照T1、T3、T4、T2、T0的顺序执行，所有线程都能完成执行。 现在假设T1请求一个A资源和两个C资源，即Request1 = (1,0,2)。 首先检查资源可用性：Request1 = (1,0,2) ≤ Available = (3,3,2)，资源充足。 接下来，我们模拟分配这些资源给T1，检查分配后的系统状态：

使用安全性算法检查分配后的系统状态，可以发现按照T1、T3、T4、T0、T2的顺序执行，所有线程都能完成执行，因此系统仍处于安全状态，T1的请求可以立即批准。

需要注意的是，如果T4请求(3,3,0)个资源，系统无法满足，因为可用资源不足。如果T0请求(0,2,0)个资源，虽然可用资源充足，但批准该请求会导致系统进入不安全状态，可能引发死锁，因此该请求必须被延迟。

死锁检测

某些系统不采用死锁预防或避免策略，允许系统进入死锁状态，然后通过检测算法识别死锁并从中恢复。死锁检测和恢复涉及两个主要问题：如何检测系统中是否存在死锁，以及如何从死锁状态中恢复。

死锁检测算法适用于单实例资源和多实例资源两种情况。需要注意的是，死锁检测和恢复需要系统维护额外的状态信息、运行检测算法，并且恢复过程可能导致数据丢失或任务失败。

每个资源类型只有一个实例

对于每种资源类型只有一个实例的系统，可以使用等待图方法进行死锁检测。等待图是资源分配图的简化版本，只保留线程节点，移除资源节点，直接表示线程之间的等待关系。

在等待图中，如果线程Ti正在等待线程Tj释放某个资源，则存在一条从Ti指向Tj的有向边。等待图的一个重要性质是：如果等待图中存在环，则系统处于死锁状态。系统可以定期检查等待图是否存在环来检测死锁。检测环的算法时间复杂度为O(n²)，其中n是线程数。

每个资源类型有几个实例

等待图方案不适用于每个资源类型有多个实例的资源分配系统。我们现在转向适用于这种系统的死锁检测算法。 该算法采用几个时变数据结构，类似于银行家算法中使用的数据结构：

• Available：长度为m的向量，指示每种类型的可用资源数量。
• Allocation：n乘以m矩阵定义当前分配给每个线程的每种类型的资源数量。
• Request：n乘以m矩阵指示每个线程的当前请求。如果Request[i][j]等于k，那么线程Ti正在请求资源类型Rj的k个更多实例。

向量比较的定义是：如果向量X的每个分量都不大于向量Y的对应分量，则X ≤ Y。为了便于描述，我们将Allocation和Request矩阵的每一行视为向量，分别记为Allocationi和Requesti。

死锁检测算法的基本思想是：尝试找到一个执行序列，使得所有未完成的线程都能获得所需资源并完成执行。这个思路与银行家算法中的安全性检查类似，都是通过寻找可行的执行序列来判断系统状态。

算法在判断Requesti ≤ Work后，直接将线程Ti的资源"模拟"归还（第3步）。这里采用了一种乐观假设：如果线程Ti当前请求的资源都能满足，那么它应该能够完成执行并释放所有资源。算法假设线程在获得所需资源后不会请求额外资源。如果这个假设不成立，死锁可能在后续时刻发生，但下次运行死锁检测算法时仍能发现。

为了让大家更直观地理解这个算法，我们举个例子。假设现在有五个线程T0到T4，还有三种资源A、B、C。A有7个，B有2个，C有6个。下面这张表就是系统当前的资源分配情况：

可以验证，当前系统没有死锁。如果按照T0、T2、T3、T1、T4的顺序模拟执行，所有线程都能获得所需资源并完成执行，即所有Finish[i]都变为true。

现在假设T2请求一个C类资源，Request表变为：

此时，虽然T0持有的资源可以被回收，但回收后的可用资源仍不足以满足其他线程的请求。T1、T2、T3和T4形成循环等待，都无法继续执行，系统进入死锁状态。这些线程互相等待对方释放资源，导致所有相关线程都无法取得进展。

检测算法的使用

我们应该何时调用检测算法？答案取决于两个因素：

1. 死锁可能发生的频率如何？
2. 当死锁发生时，有多少线程会受到影响？

如果死锁经常发生，那么应该频繁调用检测算法。分配给死锁线程的资源将保持空闲，直到死锁可以被打破。此外，参与死锁循环的线程数量可能会增长。

死锁只发生在某些线程提出不能立即授予的请求时。这个请求可能是完成等待线程链的最终请求。 在极端情况下，我们可以每次分配请求不能立即授予时调用死锁检测算法。 在这种情况下，我们不仅可以识别死锁的线程集合，而且可以识别"导致"死锁的特定线程。 如果有许多不同的资源类型，一个请求可能在资源图中创建许多循环，每个循环由最近的请求完成并由一个可识别的线程“导致”。

当然，为每个资源请求调用死锁检测算法将在计算时间上产生相当大的开销。 一个更便宜的替代方案是简单地在定义的间隔调用算法——例如，每小时一次或每当CPU利用率下降到40%以下时。 如果检测算法在任意时间点被调用，资源图可能包含许多循环。在这种情况下，我们通常无法告诉许多死锁线程中的哪一个“导致”了死锁。

死锁恢复

当检测算法识别出系统中存在死锁时，可以采用以下几种恢复方法。最直接的方法是通知系统管理员，由管理员手动处理死锁。另一种更自动化的方法是让系统自动从死锁状态中恢复。

死锁恢复主要有两种策略：第一种是终止死锁进程或线程，通过终止操作释放其占有的资源，从而打破死锁循环；第二种是资源抢占，从某些死锁进程或线程中强制回收资源，分配给其他需要的进程或线程，使系统能够继续执行。

进程和线程终止

为了通过中止进程或线程来消除死锁，我们使用两种方法之一。在两种方法中，系统回收分配给被终止进程的所有资源：

• 中止所有死锁进程：这种方法显然会打破死锁循环，但代价很高。死锁进程可能已经计算了很长时间，这些部分计算的结果必须被丢弃，并且可能稍后必须重新计算。
• 一次中止一个进程，直到死锁循环被消除：这种方法产生相当大的开销，因为在每个进程被中止后，必须调用死锁检测算法来确定是否有进程仍然死锁。

中止进程可能不容易。如果进程正在更新文件，终止它可能使该文件处于不正确状态。 类似地，如果进程在持有互斥锁的同时正在更新共享数据，系统必须将锁的状态恢复为可用，尽管不能保证共享数据的完整性。

如果使用部分终止方法，那么我们必须确定应该终止哪个死锁进程（或进程）。这个确定是一个策略决定，类似于CPU调度决定。 问题基本上是经济问题；我们应该中止那些终止将产生最小成本的进程。不幸的是，“最小成本”这个术语并不精确。许多因素可能影响选择哪个进程，包括：

1. 进程的优先级是什么
2. 进程已经计算了多长时间以及进程在完成其指定任务之前还需要计算多长时间
3. 进程已经使用了多少和什么类型的资源（例如，资源是否容易抢占）
4. 进程需要多少更多资源才能完成
5. 需要终止多少个进程

资源抢占

资源抢占方法通过强制回收某些进程占有的资源，并将这些资源分配给其他进程，从而打破死锁循环。系统会反复执行抢占操作，直到所有进程都能继续执行，不再形成循环等待。实现资源抢占需要解决三个关键问题：

• 选择受害者：确定哪些资源和哪些进程需要被抢占。与进程终止策略类似，需要确定抢占顺序以最小化成本。成本因素包括死锁进程持有的资源数量、进程已执行的时间、进程优先级等参数。
• 回滚：从进程抢占资源后，该进程无法继续正常执行，因为它缺少必要的资源。系统必须将进程回滚到某个安全状态，并从该状态重新启动执行。
• 饥饿：需要确保不会发生饥饿现象，即保证资源不会总是从同一个进程被抢占。如果总是选择成本最小的进程作为受害者，同一个进程可能反复被抢占，导致其永远无法完成执行。

小结

死锁是并发系统中的一种经典同步问题，当一组进程或线程互相等待对方释放资源时就会发生。 死锁的发生需要同时满足四个必要条件：互斥条件、占有和等待条件、非抢占条件和循环等待条件。 我们可以使用资源分配图来可视化死锁问题，图中环的存在是死锁的必要条件，但在多实例资源的情况下不是充分条件。

处理死锁有三种主要策略：鸵鸟策略（忽略问题）、预防和避免策略（防止死锁发生）、检测和恢复策略（允许死锁发生然后处理）。 死锁预防通过破坏四个必要条件之一来防止死锁，其中破坏循环等待条件是最实用的方法，通过建立资源的总排序并要求按顺序请求资源。 死锁避免使用银行家算法等方法来确保系统始终保持安全状态，这需要预先知道每个线程的最大资源需求。 死锁检测算法可以识别系统中是否存在死锁，对于单实例资源可以使用等待图，对于多实例资源可以使用基于矩阵的算法。 当检测到死锁时，可以通过终止进程或抢占资源来恢复，选择受害者时需要考虑成本因素并采取措施防止饥饿。

小练习

1. 资源分配图死锁检测

考虑一个系统，有3个线程T0、T1、T2和3个资源R0、R1、R2（每个资源类型只有1个实例）。当前的资源分配情况如下：

• T0占有R0，等待R1
• T1占有R1，等待R2
• T2占有R2，等待R0

请：

1. 画出资源分配图
2. 判断是否存在死锁
3. 如果存在死锁，指出死锁的循环等待链

|
T0 → R1 (请求边)
R0 → T0 (分配边)
T1 → R2 (请求边)
R1 → T1 (分配边)
T2 → R0 (请求边)
R2 → T2 (分配边)

2. 银行家算法安全性检查

考虑一个系统，有5个线程T0到T4和3种资源类型A、B、C。资源总数：A=10，B=5，C=7。

当前资源分配状态如下：

请：

1. 计算Need矩阵（Need = Max - Allocation）
2. 判断当前系统是否处于安全状态
3. 如果安全，给出一个安全执行序列

3. 死锁检测算法应用

考虑一个系统，有5个线程T0到T4和3种资源类型A、B、C。资源总数：A=7，B=2，C=6。

当前资源分配和请求状态如下：

请使用死锁检测算法判断系统是否存在死锁。如果存在死锁，指出哪些线程处于死锁状态。

如果对于某些i，Finish[i]等于false，0小于等于i小于n，那么系统处于死锁状态。此外，如果Finish[i]等于false，那么线程Ti死锁。