| title | date | tag | |
|---|---|---|---|
关于死锁的一点笔记 |
2023-04-05 |
|
::: tip 拉个Star
声明：以下内容均来自书籍《现代操作系统》，内容略有改动。
死锁的产生与资源相关，因而先给出资源的定义：在进程对设备、文件等取得排他性访问权时，有可能会出现死锁，为便于讨论，把这类需要排他性使用的对象称为资源（resource）。资源可以是硬件设备（如打印机），或是一组信息（如数据库中一条加锁的记录）。简而言之，资源是随着时间的推移，必须能获得、使用和释放的任何东西。
资源又分为可抢占资源和不可抢占资源。
可抢占资源可以从拥有它的进程中被抢占而不会产生任何副作用，存储器就是一类可抢占的资源。操作系统可以把一个进程从内存中换出，换入另一个进程。
不可抢占资源是指在不引起相关的计算失败的情况下，无法把它从占有它的进程处抢占过来。例如，一个进程使用打印机来打印内容，突然将打印机分配给另一个进程导致打印内容混乱。因此打印机属于不可抢占资源。
总的来说，死锁与不可抢占资源有关。
使用信号量来管理资源，down操作来获取资源，使用资源，up操作来释放资源。如下所示。
tydedef int semaphore;
semaphore resource_1;
void process_A(void) {
down(&resource_1);
use(&resource_1);
up(&resource_1);
}通常，进程需要两个或更多的资源，它们可以顺序获取，如下所示
tydedef int semaphore;
semaphore resource_1;
semaphore resource_2;
void process_A(void) {
down(&resource_1);
down(&resource_2);
use_resources();
up(&resource_2);
up(&resource_1);
}现在考虑两个进程（A和B）以及两个资源的情况。
第一种方式如下：
typedef int semaphore;
semaphore resource_1;
semaphore resource_2;
void process_A(void) {
down(&resource_1);
down(&resource_2);
use_resources();
up(&resource_2);
up(&resource_1);
}
void process_B(void) {
down(&resource_1);
down(&resource_2);
use_resources();
up(&resource_2);
up(&resource_1);
}第二种方式如下：
typedef int semaphore;
semaphore resource_1;
semaphore resource_2;
void process_A(void) {
down(&resource_1);
down(&resource_2);
use_resources();
up(&resource_2);
up(&resource_1);
}
void process_B(void) {
down(&resource_2);
down(&resource_1);
use_resources();
up(&resource_1);
up(&resource_2);
}第一种方式中，两个进程以相同的次序请求资源，第二种方式中，两个进程请求资源的次序不同。这就可能造成不同的结果。
在第一种方式中，一个进程先于另一个进程获取资源，从而能够成功第二个资源并完成它的任务。如果另一个进程想在第一个资源被释放之前获取该资源，则会由于资源被加锁而被阻塞，直到该资源可用为止。然而在第二种方式中，则有产生死锁的风险。可能进程A获取了资源1，进程B获取了资源2，这时两个进程都想请求还未拥有的另一个资源，然而都会因此被阻塞，两个进程都无法继续运行。
死锁的规范定义：如果一个进程集合中的每个进程都在等待只能由该进程集合中的其他进程才能引发的事件，那么该进程集合就是死锁的。
死锁进程集合中的每一个进程都在等待另一个死锁的进程已经占有的资源，但是由于所有进程都不能运行，它们中的任何一个都无法释放资源，所以没有一个进程可以唤醒。进程的数量以及占有或者请求的资源数量和种类都是无关紧要的。这种死锁称为资源死锁（resource deadlock）。资源死锁很常见，但不是唯一类型。
Coffman等人总结了发生资源死锁的四个必要条件：
- 互斥条件。每个资源要么已经分配给了一个进程，要么就是可用的。
- 占有和等待条件。已经得到了某个资源的进程，可以再申请新的资源。
- 不可抢占条件。已经分配给某一个进程的资源，不能被强制性地抢占，它只能由占有它的进程显式地释放。
- 循环等待条件。死锁发生时，系统中一定有两个或以上的进程组成的一条环路，该环路中的每个进程都在等待着下一个进程所占有的资源。
有四种处理死锁的策略：
- 忽略该问题。
- 检测死锁并从中恢复。
- 避免死锁。通过仔细对资源进行分配，可以动态地避免死锁。
- 防止死锁。通过破坏引起死锁的四个必要条件之一，防止死锁的产生。
使用这种技术的系统不试图阻止死锁的产生，而是允许死锁的发生，当检测到死锁发生后，采取措施进行恢复。
死锁检测方法有多种，从简单的例子开始，即每种资源类型只有一个资源。例如，扫描仪、光盘驱动、绘图仪和打印机（仅有一台的情况）。
针对这种系统可以构造一张资源分配图
其中，圆圈指代进程，正方形指代资源
- A进程持有R资源，且需要S资源。
- B进程不持有任何资源，但需要T资源
- C进程不持有任何资源，但需要S资源。
- D进程持有U资源，且需要S资源和T资源。
- E进程持有T资源，且需要V资源。
- F进程持有W资源，且需要S资源。
- G进程持有V资源，且需要U资源。
现在检测死锁的产生。从图中可以看出存在一个环（DTEVGUD），其中D、E、G已经死锁。这样的图虽然可以看出死锁进程，但是我们需要一个正规的算法来检测死锁。有很多检测有向图环路的方法。下面给出一个简单的算法，检测有向图是否存在环。这一算法使用数据结构L，L代表一些节点的集合，通过对已经检测的有向边进行标记，避免重复检查。算法流程如下：
- 对图中的每个节点N，将N作为起始点执行下面五个步骤。
- 将L初始化为空表，并清除所有有向边标记。
- 将当前节点添加到L尾部，检测该节点是否已经在L中出现两次。如果是，那么该图包含了一个环，算法结束。
- 从给定的节点开始，检测是否存在没有标记的从该节点出发的有向边。如果存在的话，进行第5步；如果不存在，跳到第6步。
- 随机选取一条没有标记的从该节点出发的有向边，标记它，然后将该边指向的节点作为新的当前节点，跳到第3步。
- 如果这一节点是起始节点，那么表明该图不存在任何环，算法结束。否则意味着我们走进了死胡同，所以需要移走该节点，返回到前一节点，并作为新的当前节点，跳转到第3步。
这一算法实际上是依次将每一个节点作为一棵树的根节点进行深度
优先搜索，如果碰到已经遇到过的节点，那么就算找到一个环。如果从任何给定的节点出发的有向边都被穷举了，则回溯到前面的节点。如果回溯到根，并且不能再深入下去，那么从当前节点出发的子图中就不存在环。若所有节点都是如此，则整个图不存在环，即系统不存在死锁。
对上图应用这一算法。从R节点开始，依次是A、B、C、S、D、T、E、F，如果遇到一个环，则算法停止。
我们先从R节点开始，将L初始化为空表，将R添加到L中，接着移动到A，A添加到L中，L=[R,A]。从A到达S，L=[R,A,S]。S没有出发的边，所以回溯到A，同理再回溯到R，从而完成了对R为起点的检测。
现在以A为起点进行检测，置L为空表，由上一段分析我们很快就能完成对A的检测。
现在从B节点开始，一路顺着有向边到达D，此时L=[B,T,E,V,G,U,D]。此时随机选择一条边，如果选S，则是死路，将回溯到D。接着选T，此时出现了L=[B,T,E,V,G,U,D,T]，发现了环（检测到两个T），算法结束。
每种类型多种资源的情况下，可以采用基于矩阵的算法来检测死锁。现在检测$P_1$到$P_n$这n个进程中是否存在死锁，假设资源类型有m种，$E_1$代表资源类型1，$E_2$代表资源类型2，$E_i$代表资源类型$i(1\le i\le m)$。$E$是现有资源向量，代表每种已存在的资源总数，比如资源类型1代表打印机，那么$E_1=2$表示系统有两台打印机。在任意时刻，某些资源被分配所以不可用。设A是可用资源向量，那么$A_i$表示当前可供使用的资源数。如果仅有的两台打印机被分配出去，那么$A_i=0$。
另外需要两个矩阵，$C$代表当前分配矩阵，$R$代表请求矩阵。C的第$i$行代表$P_i$当前所持有的每一种类型资源的资源数。所以，$C_{ij}$代表$P_i$所持有的资源$j$的数量。同理，$R_{ij}$代表$P_i$所需要的资源$j$的数量。四种数据结构分别表示如下。 $$ 现有资源\ (E_1,E_2,E_3,...,E_m) $$
这四种数据结构之间满足一个恒等式，即 $$ \sum_{i=1}^nC_{ij} + A_j = E_j $$ 上式表示，将所有已分配的资源$j$数量累加起来，并且加上资源j的可用资源数，等于该类资源的总数。
定义向量A和向量B之间的关系为$A\le B$当且仅当$A_i \le B_i(0 \le i \le m)$。
规定：每个进程初始未被标记，当算法开始后，会对进程做标记，被标记后即表明该进程能够被执行，不会进入死锁。因此，当算法结束时，未被标记的进程都是死锁进程。
死锁检测算法如下：
- 需要一个没有标记的进程$P_i$，对于它而言R矩阵的第$i$行向量小于或等于A，即$R_{i}\le A$.
- 如果找到这样一个进程，那么将C矩阵的第$i$行向量加到A中（因为资源足够该进程运行），标记该进程，并转到第1步。
- 如果没有这样的进程，算法结束。
知道了如何去检测死锁，那么该在何时去检测他们呢。一种方法是每当有资源请求时就去检测，这种方法会占用昂贵的CPU时间；另一种方法是定时检测，可以每个$k$分钟检测一次，又或者在CPU使用率降到某一阈值时去检测，依据是如果死锁进程数达到一定数量，就没有多少进程可运行，那么CPU会空闲下来。
从死锁中恢复有如下方法：
- 利用抢占恢复
- 利用回滚恢复
- 杀死进程恢复
抢占恢复将资源从持有进程A拿走，分配给另一个进程B，待进程B使用完毕后再分配给进程A。
回滚恢复需要对进程设置检查点检查。进程检查点检查就是将进程写入一个文件以备以后重启。该检查点中不仅包括存储映像，还包括了资源状态，即哪些资源分配给了该进程。一旦检测到死锁，就很容易发现需要哪些资源。为了进行恢复，要从一个较早的检查点上开始，这样拥有所需要资源的进程会回滚到一个时间点，再此时间点之前该进程获取了一些其他的资源，而在此时间点之后该进程所做的所有工作都丢失。实际上是将该进程复位到一个更早的状态，那时它还没有取得导致死锁的资源，接着将该资源分配给一个死锁进程。
杀死一个或若干个进程是最直接也是最简单的解决死锁的方法。一种方法是杀掉环中的一个进程，使得其他进程可以继续，如无法继续，则再杀掉一个进程，直到打破死锁循环。另一种方法是选一个环外的进程作为牺牲品，释放该进程的资源。这种方法需要小心选择一个环外进程，它应该正好持有环中某些进程需要的资源。杀死进程这类方法，最好是选择可以从头开始重新运行而不会带来副作用的进程。例如编译程序可以重新运行产生新的目标文件。