《现代操作系统》—— 死锁

前言

在计算机系统中有很多独占性的资源，在任何一个时刻它们都只能被一个进程使用。比如硬件资源：打印机、扫描仪、光驱。也有一些软件资源：数据库表中的某一个记录、文件系统中某些文件等。两个进程同时使用同一个文件系统中的某个文件会引起文件系统的瘫痪，因此操作系统都具有授权一个进程（临时）拍他的访问某一资源的能力。不然可能会因为两个进程同时请求被占用的资源而导致死锁。 本文中的资源可以是硬件资源、软件资源以及一些数据资源（也属于软件资源），死锁可能出现在软件资源和硬件资源上。 本文只讨论进程死锁，至于线程死锁，其原理基本是一样的。

资源

资源分为可抢占资源和不可抢占资源：

• 可抢占资源
  • 可抢占资源指可以从拥有它的进程中抢占而不会产生副作用，存储器就是一类可抢占资源。
• 不可抢占资源
  • 不可抢占资源是指在不引起相关的计算失败的情况下，无法把它从占有它的进程处抢占过来。比如正在执行刻录任务的蓝光光盘刻录机正在被某个进程使用，另一个进程抢占过来必然会导致前者刻录失败甚至划坏光盘。

死锁

死锁的规范定义如下：如果一个进程集合中的每个进程都在等待只能由进程集合中的其他进程才能引发的事件（比如等待由其他进程占有的资源），那么该进程集合就是死锁的。说的通俗一点，就是存在一组进程，他们请求的资源都在被组内对方进程占有，那么他们永远也获取不到对方身上的资源，就形成了死锁。 笔者认为，死锁分为：硬件死锁、进程死锁、线程死锁。

资源死锁的条件

Coffman等人（1971）总结发生了（资源）死锁的四个必要条件：

1. 互斥条件
2. 占有和等待条件
3. 不可抢占条件
4. 环路等待条件

死锁发生时，以上4个条件一定是同时满足的。否则死锁就不会发生。

死锁建模

Holt（1972）使用之处使用有向图建立上述资源死锁的4个条件的模型。

• ○ 表示进程
• □ 表示资源
• □ ——> ○ 即资源节点到进程节点的有向边代表该资源已被请求、授权并被进程占用
• ○ ——> □ 即进程节点到资源节点的有向边代表进程正在请求该资源，且该进程已被阻塞，处于等待资源的状态

如下图：

• 图a代表进程A占有一个资源R
• 图b代表进程B请求一个资源S
• 图c代表发生了死锁：进程C占有资源U & 请求资源T、进程D占有资源T & 请求资源U。

image.png

如下是使用资源分配图的方法（下图中有一个错误，已经用红框纠正），3个进程对3个资源的请求和释放顺序。资源分配图可以用作一种分析工具，考察对一个给定的请求/释放的序列是否会引起死锁。只需要按照请求释放的次序一步步进行，每一步之后都检查图中是否包括了环路。如果有环路，那么就有死锁，反之则没有。

image.png

死锁处理策略

总而言之，有4种处理死锁的策略：

1. 忽略死锁，任其发生。（不可取）
2. 检测死锁，然后恢复。允许产生死锁，通过某些手段检测到死锁并修复。
3. 避免死锁，事前感知。不允许产生死锁，通过某些手段判断是否将要产生死锁，并及时避免。
4. 死锁预防，破坏产生死锁的4个必要条件。

策略1不可取我们直接忽略。本文只描述后3种策略。

死锁检测和死锁恢复

使用这种策略时，系统允许死锁的产生，当检测到死锁发生后，采取措施进行恢复。

每种类型一个资源的死锁检测

如下图，是一张资源分配图，描述了一种复杂的场景：7个进程、6个资源。如果这样图包含了一个或一个以上的环，那么死锁就存在。否则就没有死锁。

image.png

虽然通过观察一张简单的图就能很容易的找出死锁进程，我们仍然需要一个正规的算法来检测死锁。 这种算法给定了一个数据结构L，L代表一些节点的集合。在这个算法中，依次将每一个节点作为一棵树的根节点，并进行深度优先遍历。对已经遍历过的弧（有向边）进行标记，代表已经检查过。如果碰到已经遇到过的节点，那么就算找到了一个环。如果从任何给定的节点出发的弧都被遍历了，那么就回溯到前面的节点。如果回溯到根节点并且不能再深入下去，那么从当前根节点出发的子图就不包含环。如果所有的“根节点”都是如此，那么整个图就不存在环，也就是系统不存在死锁。

每种类型多个资源的死锁检测

如果有多种相同的资源存在，就需要采用另一种方法来检测死锁。 如下图，描述了一种基于矩阵的算法来检测从P_1P1​到P_nPn​这n个进程的死锁。其中E、A、C、R分别代表：

• E 代表现有资源向量 即每种资源总数
• A 代表可用资源向量 即没有被分配的资源
• C 代表当前分配矩阵 即当前分配个各个线程的资源情况
• R 代表请求矩阵 即各个线程还需要的资源情况

其中C、R是数组。C的第i行代表P_iPi​当前线程所持有的每一种类型资源的数量。同理，R的第i行第j列代表P_iPi​所需要的资源j的数量。

image.png

从死锁中恢复

• 利用抢占恢复
• 利用回滚恢复
• 通过杀死进程恢复

死锁避免

安全状态和不安全状态

死锁避免的主要算法是基于一个安全状态的概念。通过下图，方便理解安全状态（虽然不能被直接翻译成算法，但它给出了一个解决问题的直观难受）。下图包括：

• 2个进程：A、B
• 2个资源：打印机、绘图仪

图中虚线代表进程被调度程序调度的顺序。可以看出进程A先被调度运行，然后再q点处进程B被调度运行，然后再r处调度程序又选择运行了进程A，在s处又开始运行进程B。 如果系统一旦进入I_1I1​、I_2I2​、I_5I5​、I_6I6​组成的矩形区域，最后一定会到达I_2I2​和I_6I6​的交叉点，这是就产生了死锁。在该点处，A请求绘图仪，B请求打印机，而且请求的资源均已被分配，这个矩形区域就是不安全的，因此不能进入这个区域。在点t处的办法是运行进程A直到I_4I4​。 需要注意的是，在点t处，进程B请求资源，调度程序必须决定是否分配，如果把资源分配给B，系统会进入不安全区域，最终发生死锁。要避免死锁，应该将B挂起直到A请求并释放绘图仪。

image.png

所谓安装状态，即如下图6-9所示： 存在一个资源分配序列使得所有进程都能完成任务。也就是说，这个方案可以单独运行进程B，知道他请求并获得了另外2个资源，从而达到了图6-9b的状态。然后B完成所有任务释放4个资源，达到了图6-9c的状态。然后调度程序运行进程C，C申请了5个空闲资源，如图6-9d。直到C完成所有任务并释放7个资源，最终达到了图6-9e的状态。最后调度程序运行进程A。

image.png

所谓不安全状态，即如下图6-10所示： 不存在一个资源分类序列是的所有进程都能完成任务。比如下图6-10a到6-10b，操作系统分配了一个资源你给进程A，然后空闲2个资源，此时空闲的2个资源那只能保证进程B完成，进而流转到了图6-10c，当进程B完成并释放4个资源时，空闲的资源只有4个，无法满足进程A或进程C的资源你要求，此时就发生了死锁。回过头来看A的资源请求不该被满足。我们说图6-10a到6-10b的资源分配方案是从安全状态进入到了不安全状态。

image.png

值得注意的是，不安全状态并不是死锁。从安全状态出发，系统能够保证所有进程都能完成；从不安全状态出发，就没有这样的保证。因为上述资源分配没有考虑释放资源你的情况，如果进程在获取一个资源的同时并释放了其他资源，虽然进入到了不安全状态，但也不一定发生死锁。

银行家算法

银行家算法是对以上论述的死锁避免算法的一种实现。即对安全状态和不安装状态的抽象以及实现。银行家算法分为单个资源的银行家算法和多个资源的银行家算法。

单个资源的银行家算法

Dijkstra(1965)提出的银行家算法（banker's algorithm）。该模型基于一个小城镇的银行家，他向一群客户分别承诺一定的贷款额度。算法要做的是判断对请求的满足是否会导致进入不安全状态。如果是，就拒绝请求，如果满足请求后系统仍然是安全的，就予以分配。如下图4个客户A、B、C、D都被收益一定数量的贷款单位。银行家的算法就是对每一个请求进行检查，如果满足请求后依旧是安全状态就会满足请求，否则推迟这一请求。

image.png

多个资源的银行家算法

image.png

银行家算法虽然很有意义，但缺乏实用价值，因为很少有进程能够在运行前就知道去所需资源的最大值。二期进程数量也不是固定的，往往在不断变化。

死锁预防

• 破坏互斥条件
• 破坏占有并等待条件
• 破坏不可抢占条件
• 破坏环路等待条件

其他问题

通信死锁

资源死锁是竞争性同步的问题。进程在执行过程中如果与竞争的进程无交叉，便会顺利执行，否则需要增等待，如果出现2个进程相互等待，甚至更多个进程形成环路等待的情况，就发生了死锁。 通信死锁是协同同步的问题。通信死锁发生在网络通信中，指2个或2个以上的进程利用网络发送消息来通信时同步阻塞的问题。比如网络中的进程A发送给另一台机器上的进程B时同步等待B的回复，而B则同步等待A消息的到来，一旦信息在网络中丢失，A、B都将一直阻塞下去。在网络协议中对这一问题有一些解决方案，比如超时重传。

活锁

活锁是指当进程意识到它不能获取所需要的下一个锁时，就会尝试礼貌性的释放已经获得的锁，然后等待1ms。从理论上讲，这是用来检测并预防死锁的好方法。但如果另一个进程在相同的时刻也做出了同样的让步，就像两个人在一条路上相向而行并同时给对方让路一样，相同的步调将导致双方都无法前进。

饥饿

与死锁和活锁类似的问题是饥饿（starvation）。饥饿是指某一个进程的资源请求因为无限制的推后，而导致该进程的请求迟迟无法满足。这种情况通常是因为某个进程被无限制的“插队”，而导致迟迟无法获取资源。解决饥饿的方法也很简单，可以通过先来先服务的策略来解决。类似于FIFO（first in first out），在这种机制下，先排队的进程优先被调度而获得资源，这样，所有的进程都有机会完成。

总结

死锁是任何操作系统中都潜在的问题。当一组进程中的每个进程都因等待由该组进程中的另一个进程所占用的资源而导致的阻塞，死锁就发生了。

死锁的另一种可能的情况是一组通信进程都在等待一个消息，而通信信道却是空的，并且也没有采用超时重传机制。

通过跟踪安全状态和不安全状态可以避免资源死锁。安全状态下存在一个事件序列保证所有的进程都能获取资源并完成任务。银行家算法是一种实现，它可以通过拒绝可能引起不安全状态的资源请求预防死锁。

资源死锁不是唯一的一种死锁。活锁、饥饿虽然不是资源死锁，但也是一种“死锁”，也会让进程陷入无线的等待之中。