OS

死锁

Operating System Notes

Posted by AH on November 30, 2019

第8章 死锁

8.1 系统模型

系统拥有一定数量的资源，类型为$R_1$, $R_2$, …, $R_m$

​ e.g. CPU周期、内存空间、I/O设备

每种资源类型$R_i$有$W_i$个实例

每个进程应用资源的顺序如下：

  1. 申请（request）
  2. 使用（use）
  3. 释放（release）

其中申请和释放是系统调用

8.2 多线程应用中的死锁

一个Pthread例子：

// 初始化两个mutex
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，分别执行do_work_one()和do_work_two()。若thread_onelock了first_mutex，同时thread_twolock了second_mutex，则会发生死锁。

/* thread one runs in this function */
void *do_work_one(void *param)
{
	pthread_mutex_lock(&first_mutex);
    pthread_mutex_lock(&second_mutex);
	/**
	* Do some work
	*/
	pthread_mutex_unlock(&second_mutex);
	pthread_mutex_unlock(&first_mutex);
	pthread_exit(0);
}

/* thread two runs in this function */
void *do_work_two(void *param)
{
	pthread_mutex_lock(&second_mutex);
    pthread_mutex_lock(&first_mutex);
	/**
	* Do some work
	*/
	pthread_mutex_unlock(&first_mutex);
	pthread_mutex_unlock(&second_mutex);
	pthread_exit(0);
}

8.2.1 Livelock

和死锁类似，都阻止了两个或以上线程继续工作，但是在livelock里线程是因为不同的原因不能继续工作。

livelock发生在很多线程同时不停尝试执行某个操作却失败的时候。

像两个人在马路上迎面相遇，一个往左一个就往右，谁也走不了。但他们不是被堵住了，只是没有进展。

所以livelock可以通过让每个线程随机次重试失败的操作来避免。

8.3 死锁特征（Deadlock Characterization）

8.3.1 必要条件

若在同一系统中四个条件同时满足，就会产生死锁：

  1. 互斥（mutual exclusion）：某一时刻某个资源只能被一个进程使用

  2. 占有并等待（hold and wait）：一个进程必须占有至少一个资源，并等待一个资源，而该资源被其他进程占有
  3. 非抢占（no preemption）：资源只能在进程完成任务后自动释放（不能被抢占）
  4. 循环等待（circular wait）：有一组等待进程{$P_0, P_1, …, P_n$}，$P_0$等待的资源被$P_1$占有，$P_1$等待的资源被$P_2$占有，$P_{n-1}$等待的资源被$P_n$占有，$P_n$等待的资源被$P_0$占有

8.3.2 资源分配图（Resource-Allocation Graph）

顶点集合$V$，边集合$E$

$V$分为两类：

  • 系统中所有进程：$P = {P_0, P_1, …, P_n}$

  • 系统中所有资源类型：$R = {R_0, R_1, …, R_m}$

$E$：

  • 申请边（request edge）：有向边$P_i \rightarrow R_j$表示进程$P_i$已经申请了资源类型$R_j$的一个实例
  • 分配边（assignment edge）：有向边$R_j \rightarrow P_i$表示资源类型$R_j$的一个实例已经分配给了进程$P_i$

e.g.

有死锁的资源分配图：

有环但是没有死锁的资源分配图：

基本事实：

  1. 若图里没有环 -> 无死锁
  2. 若图里有环 ->
    • 若每个资源类型只有一个实例，则死锁
    • 若每个资源类型有多个实例，可能死锁

8.4 死锁处理方法

  • 使用协议预防或避免死锁，确保系统不会进入死锁状态
    • 死锁预防（deadlock prevention）：见8.5
    • 死锁避免（deadlock avoidance）：见8.6
  • 可允许系统进入死锁状态，然后检测并修复
  • 可忽视这个问题，认为死锁不可能在系统内发生
    • 被绝大多数OS采用，包括UNIX和Windows

8.5 死锁预防（Deadlock Prevention）

只要四个必要条件有一个不成立，就可以预防死锁

8.5.1 互斥

对于非共享资源，必须要有互斥条件

共享资源不要求互斥，所以不会涉及死锁。e.g. 多个进程可以同时打开只读文件

通常不能通过否定互斥条件来预防死锁

8.5.2 占有并等待

必须保证：当一个进程申请一个资源时，不能占有其他资源（i.e. 不能吃着碗里的看着锅里的）

  • 一种协议：每个进程在执行前申请并获得所有资源。

  • 另一种协议：允许进程在没有资源时才能申请资源。

缺点：

  1. 资源利用率（resource utilization）可能比较低
  2. 可能发生饥饿（starvation）

8.5.3 非抢占

如果一个进程占有资源并申请另一个不能立即分配的资源，那么其现已分配的资源都可被抢占（隐式释放了）。

抢占资源分配到进程所等待的资源的链表上

只有当进程获得其原有资源和所申请的新资源时，进程才可以重新执行

8.5.4 循环等待

规定一个资源类型的顺序，要求每个进程只能以升序请求资源

8.6 死锁避免（Deadlock Avoidance）

要求系统有额外的先验信息

  • 最简单也是最有用的模型：每个进程事先声明它需要每种资源的最大数量
  • 死锁避免算法动态检查资源分配的状态，确保不会出现循环等待的情况
  • 资源分配状态定义为可用和已分配资源的数量以及进程的最大需求

8.6.1 安全状态（Safe State）

序列$<P_0, P_1, …, P_n>$，若对于每个进程$P_i$来说，前面所有资源释放后可用资源数量能够满足自己需求，则系统处于安全状态

基本事实：

  1. 若系统在安全状态 -> 无死锁
  2. 若系统在不安全状态 -> 可能死锁
  3. 避免(avoidance)：保证系统永远不会进入不安全状态

避免算法：

  • 每种资源类型一个实例：用资源分配图
  • 每种资源类型多个实例：用银行家算法

8.6.2 资源分配图算法（Resource-Allocation-Graph Algorithm）

  • 需求边（claim edge）$P_i \rightarrow R_j$表示进程$P_j$可能请求资源$R_j$，用虚线表示

  • 当进程请求资源时，需求边转换为申请边

  • 当资源分配给进程时，申请边转换成分配边

  • 当资源被进程释放时，分配边重新转换成需求边

  • 资源必须在系统中事先声明

资源分配图：

不安全状态：

若进程$P_j$请求资源$R_j$，若在资源分配图中不形成环，请求才可以通过

8.6.3 银行家算法（Banker’s Algorithm）

  • 每种资源多个实例
  • 每个进程都有事先声明的最大资源使用量
  • 当一个进程请求资源时它只能等待
  • 当一个进程拿到所有它需要的资源后，它必须在有限时间内归还资源

银行家算法的数据：

  • n个进程，m种资源

  • Available：长度为m的向量

    $available [j] = k \Rightarrow$ 资源$R_j$有k个可用实例

  • Max：大小为n*m的矩阵

    $max[i, j] = k \Rightarrow$ 进程$P_j$最多请求资源$R_j$的k个实例

  • Allocation：大小为n*m的矩阵

    $allocation[i, j] = k \Rightarrow$ 进程$P_j$目前已被分配资源$R_j$的k个实例

  • Need：大小为n*m的矩阵

    $need[i, j] = k \Rightarrow$ 进程$P_j$最多需要资源$R_j$的k个实例来完成任务

$Need [i,j] = Max[i,j] – Allocation [i,j]$

8.6.3.1 安全算法（Safety Algorithm）

  1. Work：长度为m的向量；Finish：长度为n的向量

    $Work = Available$ $Finish [i] = false$, for i = 0, 1, …, n- 1​

  2. 找到一个$i$使得下列两个条件都满足：

    • $Finish [i] = false$
    • $Need_i \leq Work$

    若没有这样的$i$，跳到第四步

  3. $Work = Work + Allocation_i$ $Finish[i] = true$

    回到第二步

  4. 若对于所有$i$，$Finish [i] == true$， 系统在安全状态

8.6.3.2 资源请求算法（Resource-Request Algorithm）

Request：进程$P_i$的请求向量

$Request_i[j] = k$则进程$P_i$想要资源$R_j$的k个实例

  1. 若$Request_i \leq Need_i$跳至第二步，否则就报错，因为进程的请求比它声明的最大需求多

  2. 若$Request_i \leq Available_i$跳至第三步，否则$P_i$必须等待，因为资源不可用

  3. 假装给进程$P_i$分配请求的资源：

    $Available = Available – Request_i$ $Allocation_i = Allocation_i + Request_i$ $Need_i = Need_i – Request_i$

    • 若安全，资源真的分配给$P_i$
    • 若不安全，$P_i$必须等待，恢复之前的资源分配状态

8.7 死锁检测（Deadlock Detection）

若一个系统既没用死锁预防也没用死锁避免，则死锁就可能发生。在这种情况下，系统可能会提供：

  • 检测是否进入死锁状态的算法

  • 从死锁状态恢复的算法

对每种资源一个实例或多个实例都适用

检测-恢复算法不仅要包括在运行时维护必要信息以及执行实时检测的开销，还有从死锁中恢复的潜在损失

8.7.1 每种资源类型单个实例

可利用资源分配图的变体——等待图（wait-for graph）

就是把资源分配图里的资源节点删了，然后压缩相应的边

系统存在死锁 iff 等待图有环

所以检测算法：

  • 系统维护等待图，周期性调用算法从图里找环

  • $O(n^2)$，n是图里的顶点数

8.7.2 每种资源类型有几个实例

等待图不适用

新算法：

  • m种资源，n个进程

  • 用几个随时间变化的数据结构，与在银行家算法里用的类似：
    • available：长度为m的向量，表示每种资源有几个实例可用
    • allocation：大小为n*m的矩阵，表示被分配给某个线程的某种资源类型的数量
    • request：大小为n*m的矩阵，表示每个线程当前的request

  • Step 1：

    • work是长度为m的向量，finish是长度为n的向量

      work = available

      若$allocation_i\neq 0$，则finish[i]=false；否则finish[i]=true

  • Step 2：

    找到一个i使得

    • finish[i]=false
    • $request_i\leq$ work

    若没有这样的i，跳到step 4

  • Step 3：

    • work = work + $allocation_i$
    • finish[i] = true

    跳转step 2

  • Step 4：

    若对于某个i，finish[i]==false，则死锁，且$P_i$死锁

  • 复杂度$O(m*n^2)$

8.7.3 检测算法用量

啥时候触发检测算法呢？考虑两个因素：

  1. 死锁大概多久出现一次呢？
  2. 发生死锁的时候，会影响几个线程？

若死锁频繁出现，就得经常触发检测算法。已经分配给死锁里的资源会保持空闲（idle）直到死锁被打破。此外，涉及死锁环的线程数量可能增加。

死锁只在一些线程提交请求却不能立即满足的情况下发生。

若检测算法随机触发，在资源分配图里就可能有好多环，我们无法分辨到底是哪个进程引发了死锁

8.8 从死锁中恢复

当检测算法发现存在死锁时，有几种解决方式

  1. 通知操作者（operator）死锁发生，让操作者手动处理死锁
  2. 让系统自动从死锁中恢复（recover）

有两种方式可以打破死锁：

  1. 单纯中止（abort）一个或几个线程来打破循环等待
  2. 从一个或多个死锁线程手里抢占一些资源

8.8.1 终止进程和线程

两种方法：

  1. 终止所有死锁进程：这种方法当然可以打破死锁环，但代价忒大了点。死锁进程可能算了好久了，把目前的计算结果一下子全扔了，以后还得重算，很可惜
  2. 一次中止一个进程，直到死锁环被打破：这种方法会产生很大的开销，因为每次一个进程中止之后，必须调用死锁检测算法来确定是不是还有进程死锁。

中止进程也不容易。若一个进程正处于文件更新的过程，直接终止它可能会让文件处于错误状态。类似的，若一个进程在有mutex的情况下更新共享数据，系统就得把锁的状态恢复为可用状态，尽管谁也保证不了共享数据的完整性

若采用部分终止方法，我们必须决定终止哪个死锁进程。和CPU调度决策一样，这是一种策略决策。现在的问题是，要用以最小的代价中止进程解决死锁。可惜的是，最小开销并不准确，很多因素都会影响进程的选择，包括：

  1. 进程的优先级
  2. 进程算了多久了，以及还要算多久才能完成任务
  3. 进程用了哪些资源，用了多少（比如说，这些资源抢占起来方便吗？）
  4. 进程还需要多少资源才能结束
  5. 需要终止几个进程

8.8.2 资源抢占

若需要通过抢占来解决死锁，考虑以下三件事：

  1. 选一个受害者（victim）：抢占什么资源？抢占哪些进程？还要决定抢占的顺序，使开销最小。影响开销的因素包括：死锁进程手握多少资源、进程目前用了多少时间了

  2. 回滚（rollback）：如果我们从进程那里抢占到了资源，这个进程后续怎么办呢？显然它不能继续正常执行，因为它缺了一些资源。我们必须把这个进程回滚到某个安全状态，然后让它从这个安全状态重启

    但是，一般来说很难决定安全状态是什么，最简单的方法就是完全回滚（total rollback），即中止这个进程然后重启。尽管让这个进程回滚到最近的、能解开死锁的状态效率最高，但这样就要让系统保存所有运行中进程的更多信息

  3. 饥饿（starvation）：我们怎么保证饥饿不会发生呢？也就是说，我们怎么保证不总从同一个进程那里抢占资源呢？

    在一个系统里，若受害者的选择大多基于开销因素，就可能总选同一个进程当受害者。所以，这个进程就永远完不成它的任务。显然，我们必须保证进程只能有限次（且次数很少）被选为受害者。最常见的做法就是在开销因素里加一个回滚的次数

FEATURED TAGS
OS Data Science AI 杂谈 Cheat Sheet Machine Learning
FRIENDS