OS之进程管理 --- 死锁

什么是死锁

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

申请：进程请求资源
使用：进程对资源进行操作
释放：进程释放资源

当一组进程中的每一个进程度在等待一个事件，而这事件只能有一组进程的另一个进程引起，那么这组进程就处于死锁状态。

死锁的特征

我们来看一个例子：互斥锁的死锁
采用互斥锁的多线程Pthreads程序可能发生死锁。函数pthread_mutex_init()将一个互斥锁初始化为未加锁。函数pthread_mutex_lock()和pthread_mutex_unlock()分别获得和释放互斥锁，当一个线程试图获得一个已加锁的互斥锁时，它会堵塞，知道该互斥锁的所有者调用pthread_mutex_unlock()
创建两个互斥锁：

pthread_mutex_t first_mutex;
pthread_mutex_t second_mutex;

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

创建两个线程，即thread_one和thread_two，这些线程都能访问这两个互斥锁,thread_one和thread_two分别运行在do_work_one()和do_work_two()中：

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);
}

void *do_work_two(void *param) {
	pthread_mutex_lock(&second_mutex);
	pthread_mutex_lock(&first_mutex);

	pthread_mutex_unlock(&first_mutex);
	pthread_mutex_unlock(&second_mutex);

	pthread_exit(0);
}

这个例子中因为两个线程获取和释放互斥锁的顺序不同，有可能造成死锁。注意：即使有可能死锁，但是不一定会发生。

必要条件

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

互斥：至少有一个资源必须处于非共享模式，即一次只有一个进程可以使用。
占有并等待：一个进程应占有至少一个资源，并等待另一个资源，而该资源为其他进程所占有。
非抢占：资源不能被抢占，即资源只能被进程完成任务后自愿释放。
循环等待：有一组进程 { $P_0$ ， $P_1$ ，…， $P_n$ }， $P_0$ 等待的资源为 $P_1$ 占有， $P_1$ 等待的资源为 $P_2$ 所占有，…， $P_{n-1}$ 等待的资源被 $P_n$ 所占有。

强调：只有这四个条件同时成立时才会出现死锁。

资源分配图

资源分配图是一种有向图，该图包括一个节点集合V和一个边集合E。节点集合V可以分为两种类型：P={ $P_1$ , $P_2$ ,…, $P_n$ }(系统中所有活动进程的集合)和R={ $R_1$ , $R_2$ ,…, $R_m$ }(系统中所有资源类型的集合).
从进程 $P_i$ 到资源类型 $R_j$ 的有向边记为 $P_i$ $ightarrow$ $R_j$ ，他表示进程 $P_i$ 已经申请了资源类型 $R_j$ 的一个实例，并且正在等待这个资源； $R_j$ $ightarrow$ $P_i$ 表示资源的一个实例已经分配给进程 $P_i$ 了。有向边 $P_i$ $ightarrow$ $R_j$ 称为申请边， $R_j$ $ightarrow$ $P_i$ 称为分配边。

具体的资源分配图详解：资源分配图

根据资源分配图的定义，可以证明：如果分配图没有环，那么系统没有进程死锁。如果分配图中存在环，那么可能存在死锁。
如果每个资源类型刚好有一个实例，那么有环就意味着已经出现死锁。如果环上每个类型只有一个实例，那么就出现了死锁。换上的进程就死锁。在这种情况下图中的环就是死锁存在的充分且必要条件。
如果每个资源类型有多个实例，那么有环并不意味这已经出现了死锁，在这种情况下，图中的环就是死锁存在的必要不充分条件。

死锁的处理方法

一般来说，处理死锁的问题有三种：

通过协议来预防或避免死锁，确保系统不会进入死锁状态。
可以允许系统进入死锁状态，然后检测并加以恢复
可以忽视这个问题，认为死锁不可能在系统内发生。

第三种方法被大多数操作系统所采用，包括Linux和Windows。

死锁预防

互斥

互斥条件必须成立，也就是说，至少一个资源应该是非共享的。实际当中，操作系统中一定需要互斥资源，所有通过解决互斥来打破死锁的四个条件是不合理的。

持有且等待

当每个进程申请一个资源的时候，它不能占有其他资源。
一种可以采用的协议：每个进程在执行前申请并获得所有的资源。即要求进程申请资源的系统调用在其他系统调用之前完成。
另外一种协议：允许进程仅在没有资源时才可申请资源。一个进程可申请一些资源并使用他们，在申请更多的其他资源之前，它应该释放现在已经分配的资源。
两者的差异：第一种要求在进程执行前申请执行所需的所有的资源，在执行过程中不能够在申请，执行完成后释放所占有的所有资源；第二种要求先分配给进程当前可以执行的资源数量，进程执行过程中如果缺少资源进请求，在请求时先释放自己占有的资源。
缺点：

资源利用率比较低
因为许多资源坑你已经分配，但是很长时间没有使用
可能发生饥饿
一个进程如需要多个常用资源，可能必须永久等待，因为在它所需要的资源中至少有一个已经分配给其他进程。

无抢占

打破“不能抢占已分配的资源”，为了保证这个条件不成立，采用协议：如果一个进程持有资源并申请另外一个不能立即分配的资源(也就是说，这个进程应该等待)，那么他现在分配的资源都可被抢占。可以理解为这些资源都被隐式的释放了。被抢占资源添加到进程等待的资源列表中。只有当进程获得其原有资源和申请的新资源时，他才可以重新执行。

循环等待

确保循环等待条件不成立的一个方法是：对所有资源类型进行完全排序，而且要求每个进程按递增顺序来申请资源。
假设资源类型的集合是R={ $R_1$ , $R_2$ ,…, $R_m$ }，为每个资源类型分配一个唯一整数，这样可以比较两个资源以确定他们的先后顺序。
我们采用如下协议：每个进程只能按递增顺序申请资源。即一个进程开始可申请任何数量的资源类型 $R_i$ 的实例。换句话说，要求当一个进程申请资源类型 $R_j$ 时，他应该先释放所有资源 $R_i$ （F( $R_j$ ) $leq$ F( $R_i$ )）。如果需要同一类型的多个实例，那么应该一起申请。

死锁避免

死锁避免算法动态的检查资源分配状态，以便确保遵化你等待条件不能成立。

安全状态

如果系统能够按一定顺序来为每个进程分配资源，仍然避免死锁，那么系统的状态就是安全的。更正式的说，只有存在一个安全序列，系统才处于安全状态。
进程序列< $P_1$ , $P_2$ , … , $P_n$ >在当前分配状态下为安全序列是指：对于每个 $P_i$ ， $P_i$ 仍然可以申请资源数小于当前可用资源加上所有进程 $P_j$ （j < i）所占有的资源。在这种情况下，进程 $P_i$ 需要的资源即使不能立即可用，那么 $P_i$ 可以等待直到所有 $P_j$ 释放资源。当他们完成后， $P_i$ 可得到需要的所有资源完成给定任务，返回分配的资源，最后终止。当 $P_i$ 终止时， $P_{i+1}$ 可得到他需要的资源，如此进行，如果没有这样的序列存在，那么系统状态就是非安全的。
安全状态不是死锁状态，相反，死锁状态是非安全状态。然而不是所有的非安全状态都能导致死锁状态。非安全状态可能导致死锁。只有在安全状态下，操作系统就能避免非安全(和死锁)状态。在非安全状态下，操作系统不能阻止进程申请资源，因而可能死锁。进程行为控制了非安全状态。

资源分配图算法

除了申请边和分配边，引入需求边，需求边 $P_i$ $ightarrow$ $R_j$ 表示进程 $P_i$ 可能在将来某个时候申请资源 $R_j$ 。当进程 $P_i$ 申请资源时 $R_j$ 时，需求边 $P_i$ $ightarrow$ $R_j$ 变成了申请边，类似当进程 $P_i$ 释放 $R_j$ 时，分配边 $R_j$ $ightarrow$ $P_i$ 变成了需求边 $P_i$ $ightarrow$ $R_j$ 。
现在假设进程 $P_i$ 申请资源 $R_j$ ，只有在将申请边 $P_i$ $ightarrow$ $R_j$ 变成分配边 $R_j$ $ightarrow$ $P_i$ 并且不会导致资源分配图形成环时，才能允许申请。
如果没有环存在，那么资源的分配会使系统处于安全状态。如果有环存在，那么分配会导致系统处于非安全状态，这种情况下，进程 $P_i$ 应该等待资源申请。

银行家算法

设n为系统进程的数量，m为资源类型的种类。定义数据结构：
Available：长度为m的向量，表示每种资源的可用实例数量，如果Available[j]=k,那么资源类型 $R_j$ 有k个可用实例。

Max：n $imes$ m矩阵，定义每个进程的最大需求。如果Max[i][j]=k，那么进程 $P_i$ 最多可申请源类型 $R_j$ 的k个实例

Allocation：n $imes$ m矩阵，定义每个进程现在分配的每种资源类型的实例数量，如果Allocation[i][j]=k，那么进程 $P_i$ 现在已分配了资源类型 $R_j$ 的k个实例。

Need：n $imes$ m矩阵，表示每个进程还需要的剩余资源。如果Need[i][j]=k，那么进程 $P_i$ 还可能申请k个资源类型 $R_j$ 的实例。
注意：Need[i][j]=Max[i][j] - Allocation[i][j]。

安全算法

通过安全算法以求出系统是否处于安全状态，描述如下：

令Work和Finish分别为长度m和n的向量，对于i=0,1,…,n-1，初始化Work=Available和Finish[i]=false。
查找这样的i使其满足：
a. Finish[i] == false
b. $Need_i$ $leq$ Work
如果没有这样的i存在，那么转到第4步
Work=Work+ $Allocation_i$
Finish[i]=true
返回第2步
如果对所有i，Finish[i]=true，那么系统处于安全状态。

这个算法可能需要m $imes$ $n^2$ 数量级的操作，以确定系统状态是否安全。

资源请求算法

现在描述是否安全允许请求的算法：
设 $Request_i$ 为进程 $P_i$ 的请求向量。如果 $Request_i$ [j]==k，那么进程 $P_i$ 需要的资源类型 $R_j$ 的实例数量为k，当进程 $P_i$ 做出这一资源请求时，采取如下动作：

如果 $Request_i$ $leq$ $Need_i$ ，转到第二步。否则生成出错条件，进程 $P_i$ 已超过了其最大需求。
如果 $Request_i$ $leq$ Available，转到第三步，否则 $P_i$ 应等待，这是因为没有资源可用。
嘉定系统可以分配给 $P_i$ 请求的资源，并案如下方式修改状态：
Available = Available - $Request_i$
$Allocation_i$ = $Allocation_i$ + $Request_i$
$Need_i$ = $Need_i$ - $Request_i$
如果新的资源分配状态是安全的，那么交易完成且进程 $P_i$ 可分配到需要的资源。然而，如果新状态不安全，那么进程 $P_i$ 应等待 $Request_i$ 并恢复到原来的资源分配状态。

死锁检测

如果一个系统既不采用死锁预防算法也不采用死锁避免算法，那么死锁可能出现，在这种情况下，系统可以提供：

一个用来检查系统状态从而确定是否出现死锁的算法
一个用来从死锁状态恢复的算法

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

如果所有资源类型只有单个实例，那么可以通过等待图来作为死锁检测算法。
等待图就是从资源分配图中，删除所有资源类型节点，合并适当边，从而得到等待图
在这里插入图片描述
当且仅当在等待图中有一个环，系统死锁。为了检测死锁，系统需要维护等待图，并周期调用用于搜索图中环的算法。
注意：等待图算法不适用于每种资源类型可有多个实例的资源分配系统

每种资源类型可有多个实例

定义如下数据结构：
Available：长度为m的向量，表示各种资源的可用实例数量

Allocation：n $imes$ m矩阵，表示每个进程的每种资源的当前分配数量

Request：n $imes$ m矩阵，表示当前每个进程的每种资源的当前请求，如果Request[i][j]=k，那么 $P_i$ 现在正在请求资源类型 $R_j$ 的k个实例。

可以看出该算法和银行家算法类似，可以进行比较理解，该算法的描述如下：

令Work和Finish分别为长度m和n的向量，初始化Work=Available。对于i=0,1,…,n-1，如果 $Allocation_i$ 不为0，则Finish[i]=false，否则Finish[i]=true。
找到这样的i，同时满足：
a. Finish[i]=false
b. $Request_i$ $leq$ Work
如果没有这样的i，则转到第4步
Work = Work + $Allocation_i$
Finish[i] = true
转到第2步
如果对某个i(0 $leq$ i $leq$ n)，Finish[i] == false，则系统死锁，并且如果Finish[i] == false，则进程 $P_i$ 死锁。

死锁恢复

进程终止

通过终止进程来消除死锁，有两种方法，都是通过允许系统回收终止进程的所有分配资源：

终止所有死锁进程
这种方法代价很大。这些死锁进程可能已经计算了较长时间，这些部分计算的结果也要放弃，并且以后可能还要重新计算
一次终止一个进程，知道消除死锁循环为止
这种方法的开销相当大，因为每次终止一个进程，都要调用死锁检测算法，以确定是否仍有进程处于死锁。

资源抢占

通过资源抢占来消除死锁，我们不断抢占一些进程的资源以便给其他进程使用，直到死锁循环被打破为止。如果要采用抢占来处理死锁，需要考虑三个问题：

选择牺牲进程
回滚
被抢占的进程不能继续正常执行，我们应将该进程回滚到某个安全状态，以便从该状态重启进程。
饥饿
即如何保证资源不会总是从同一进程中被抢占

参见：《操作系统概念》（第九版）