OS- -死锁(一)

一、死锁

• 计算机系统中有很多独占性的资源，在同一时刻只能每个资源只能由一个进程使用

• 我们之前经常提 到过打印机，这就是一个独占性的资源，同一时刻能有两个打印机同时输出结果，否则会引起文件系统 的瘫痪。

• 所以，操作系统具有授权一个进程单独访问资源的能力。
• 两个进程独占性的访问某个资源，从而等待另外一个资源的执行结果，会导致两个进程都被阻塞，并且 两个进程都不会释放各自的资源，这种情况就是 死锁(deadlock)
• 死锁可以发生在任何层面，在不同的机器之间可能会发生死锁，在数据库系统中也会导致死锁，比如进 程A对记录R1加锁，进程B对记录R2加锁，然后进程A和B都试图把对象的记录加锁，这种情况 下就会产生死锁。

下面我们就来讨论一下什么是死锁、死锁的条件是什么、死锁如何预防、活锁是什么等。

首先你需要先了解一个概念，那就是资源是什么

1.资源

• 大部分的死锁都和资源有关，在进程对设备、文件具有独占性(排他性)时会产生死锁。我们把这类需 要排他性使用的对象称为资源(resource)。资源主要分为可抢占资源和不可抢占资源

可抢占资源和不可抢占资源

• 资源主要有可抢占资源和不可抢占资源。
• 可抢占资源(preemptable resource)可以从拥有它的进程 中抢占而不会造成其他影响，内存就是一种可抢占性资源，任何进程都能够抢先获得内存的使用权。
• 不可抢占资源(nonpreemtable resource)指的是除非引起错误或者异常，否则进程无法抢占指定资 源，这种不可抢占的资源比如有光盘，在进程执行调度的过程中，其他进程是不能得到该资源的。
• 死锁与不可抢占资源有关，虽然抢占式资源也会造成死锁，不过这种情况的解决办法通常是在进程之间 重新分配资源来化解。所以，我们的重点自然就会放在了不可抢占资源上。

下面给出了使用资源所需事件的抽象顺序

• 如果在请求时资源不存在，请求进程就会强制等待。在某些操作系统中，当请求资源失败时进程会自动 阻塞，当自资源可以获取时进程会自动唤醒。
• 在另外一些操作系统中，请求资源失败并显示错误代码， 然后等待进程等待一会儿再继续重试。
• 请求资源失败的进程会陷入一种请求资源、休眠、再请求资源的循环中。此类进程虽然没有阻塞，但是 处于从目的和结果考虑，这类进程和阻塞差不多，因为这类进程并没有做任何有用的工作。
• 请求资源的这个过程是很依赖操作系统的。在一些系统中，一个request系统调用用来允许进程访 问资源。
• 在一些系统中，操作系统对资源的认知是它是一种特殊文件，在任何同一时刻只能被一个进程 打开和占用。资源通过open命令进行打开。如果文件已经正在使用，那么这个调用者会阻塞直到当 前的占用文件的进程关闭文件为止。

资源获取

• 对于一些数据库系统中的记录这类资源来说，应该由用户进程来对其进行管理。
• 有一种管理方式是使用信号量(semaphore)。这些信号量会初始化为1。互斥锁也能够起到相同的作用。

• 这里说一下什么是互斥锁(Mutexes): 在计算机程序中，互斥对象(mutex)是一个程序对象，它允许多个程序共享同一资源，例如文件访问权限，但并不是同时访问。
• 需要锁定资源的线程都必须在使用资源时将互斥锁与其他线程绑定(进行加锁)
• 当不再需要数据或线程结束时，互斥锁设置为解锁。

• 下面是一个伪代码，这部分代码说明了信号量的资源获取、资源释放等操作，如下所示
  

• 上面显示了一个进程资源获取和释放的过程，但是一般情况下会存在多个资源同时获取锁的情景，这样 该如何处理？如下所示:
  

• 对于单个进程来说，并不需要加锁，因为不存在和这个进程的竞争条件。所以单进条件下程序能够完好运行。

• 现在让我们考虑两个进程的情况，A和B ,还存在两个资源。如下所示
  
  

• 在上述代码中，两个进程以相同的顺序访问资源。在这段代码中，一个进程在另一个进程之前获取资 源，如果另外一个进程想在第一个进程释放之前获取资源，那么它会由于资源的加锁而阻塞，直到该资 源可用为止。

在下面这段代码中，有一些变化

• 这种情况就不同了，可能会发生同时获取两个资源并有效地阻塞另一个过程，直到完成为止。
• 也就是 说，可能会发生进程A获取资源A的同时进程B获取资源B的情况。然后每个进程在尝试获取另一个 资源时被阻塞。
• 在这里我们会发现一个简单的获取资源顺序的问题就会造成死锁，所以死锁是很容易发生的，所以下 面我们就对死锁做一个详细的认识和介绍。

2.死锁

如果要对死锁进行一个定义的话，下面的定义比较贴切

• 如果一组进程中的每个进程都在等待一个事件，而这个事件只能由该组中的另一个进程触发，这种情况 会导致死锁。
• 简单一点来表述一下，就是每个进程都在等待其他进程释放资源，而其他资源也在等待每个进程释放资 源，这样没有进程抢先释放自己的资源，这种情况会产生死锁，所有进程都会无限的等待下去。
• 换句话说，死锁进程结合中的每个进程都在等待另一个死锁进程已经占有的资源。但是由于所有进程都 不能运行，它们之中任何一个资源都无法释放资源，所以没有一个进程可以被唤醒。这种死锁也被称 为资源死锁(resource deadlock)

资源死锁的条件

• 针对我们上面的描述，资源死锁可能出现的情况主要有

• •互斥条件：每个资源都被分配给了一个进程或者资源是可用的

• •保持和等待条件：已经获取资源的进程被认为能够获取新的资源

• •不可抢占条件：分配给一个进程的资源不能强制的从其他进程抢占资源，它只能由占有它的进程显 示释放

• •循环等待：死锁发生时，系统中一定有两个或者两个以上的进程组成一个循环，循环中的每个进程 都在等待下一个进程释放的资源。

• 发生死锁时，上面的情况必须同时会发生。如果其中任意一个条件不会成立，死锁就不会发生。可以通 过破坏其中任意一个条件来破坏死锁

死锁模型

Holt在1972年提出对死锁进行建模，建模的标准如下：

• •圆形表示进程
• •方形表示资源

从资源节点到进程节点表示资源已经被进程占用，如下图所示

• 在上图中表示当前资源R正在被A进程所占用
• 由进程节点到资源节点的有向图表示当前进程正在请求资源，并且该进程已经被阻塞，处于等待这个资 源的状态
  
• 在上图中，表示的含义是进程B正在请求资源S。Holt认为，死锁的描述应该如下
  
• 这是一个死锁的过程，进程c等待资源T的释放，资源T却已经被进程D占用，进程D等待请求占 用资源U ,资源U却已经被线程C占用，从而形成环。

• 总结一点：吃着碗里的看着锅里的容易死锁

• 那么如何避免死锁呢？我们还是通过死锁模型来聊一聊
• 假设有三个进程（A、B、C）和三个资源（R、S、T）。三个进程对资源的请求和释放序列如下图所示:
  
• 操作系统可以任意选择一个非阻塞的程序运行，所以它可以决定运行A直到A完成工作；它可以运行 B直到B完成工作；最后运行C。
• 这样的顺序不会导致死锁（因为不存在对资源的竞争），但是这种情况也完全没有并行性。
• 进程除了 在请求和释放资源外，还要做计算和输入/输出的工作。当进程按照顺序运行时，在等待一个I/O时，另 一个进程不能使用CPU。
• 所以，严格按照串行的顺序执行并不是最优越的。
• 另一方面，如果没有进程 在执行任何I/O操作，那么最短路径优先作业会优于轮转调度，所以在这种情况下串行可能是最优越的
• 现在我们假设进程会执行计算和I/O操作，所以轮询调度是一种合理的调度算法。资源请求可能会按 照下面这个顺序进行

下图是针对上面这六个步骤的资源分配图：

• 这里需要注意一个问题，为什么从资源出来的有向图指向了进程却表示进程请求资源呢？解释为进程占用资源比较合适，而进程的有向图指 向资源表示进程被阻塞的意思。
• 在上面的第四个步骤，进程A正在等待资源S；
• 第五个步骤中，进程B在等待资源T；
• 第六个步骤 中，进程c在等待资源R,因此产生了环路并导致了死锁。
• 然而，操作系统并没有规定一定按照某种特定的顺序来执行这些进程。
• 遇到一个可能会引起死锁的线程 后，操作系统可以干脆不批准请求，并把进程挂起一直到安全状态为止。
• 比如上图中，如果操作系统认 为有死锁的可能，它可以选择不把资源S分配给B,这样B被挂起。
• 这样的话操作系统会只运行A和 C,那么资源的请求和释放就会是下面的步骤
  
• 在第六步执行完成后，可以发现并没有产生死锁，此时就可以把资源S分配给B,因为A进程已经执 行完毕，C进程已经拿到了它想要的资源。进程B可以直接获得资源S,也可以等待进程C释放资源 T
• 有四种处理死锁的策略：
• •忽略死锁带来的影响（惊呆了,正常人都不会这样????）
• •检测死锁并回复死锁，死锁发生时对其进行检测，一旦发生死锁后，采取行动解决问题
• •通过仔细分配资源来避免死锁
• •通过破坏死锁产生的四个条件之一来避免死锁

下面我们分别介绍一下这四种方法

3.鸵鸟算法

• 最简单的解决办法就是使用鸵鸟算法(ostrich algorithm),把头埋在沙子里，假装问题根本没有发 生。
• 每个人看待这个问题的反应都不同。数学家认为死锁是不可接受的，必须通过有效的策略来防止死 锁的产生。
• 工程师想要知道问题发生的频次，系统因为其他原因崩溃的次数和死锁带来的严重后果。如 果死锁发生的频次很低，而经常会由于硬件故障、编译器错误等其他操作系统问题导致系统崩溃，那么 大多数工程师不会修复死锁。

4.死锁检测和恢复

• 第二种技术是死锁的检测和恢复。这种解决方式不会尝试去阻止死锁的出现。
• 相反，这种解决方案会希 望死锁尽可能的出现，在监测到死锁出现后，对其进行恢复。

下面我们就来探讨一下死锁的检测和恢复 的几种方式

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

• 每种资源类型都有一个资源是什么意思？我们经常提到的打印机就是这样的，资源只有打印机，但是设 备都不会超过一个。

可以通过构造一张资源分配表来检测这种错误，比如我们上面提到的

• 如果这张图包含了一个或一个以上的环，那么死锁就存在，处于这个环中任意一个进程都是死锁的进 程。

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

• 如果有多种相同的资源存在，就需要采用另一种方法来检测死锁。可以通过构造一个矩阵来检测从P1 - >Pn这n个进程中的死锁。
• 现在我们提供一种基于矩阵的算法来检测从P1到Pn这n个进程中的死锁。
• 假设资源类型为m, E1 代表资源类型1, E2表示资源类型2 , Ei代表资源类型i (1 <= i <= m)
• E表示的是 现有资源向量 (existing resource vector)，代表每种已存在的资源总数。
• 现在我们就需要构造两个数组：C表示的是当前分配矩阵(current allocation matrix) , R表示 的是 请求矩阵(request matrix)
• Ci表示的是Pi持有每一种类型资源的资源数。所以，Cij表示Pi 持有资源j的数量。Rij表示Pi所需要获得的资源j的数量
  
• 一般来说，已分配资源j的数量加起来再和所有可供使用的资源数相加二该类资源的总数。
• 死锁的检测就是基于向量的比较。每个进程起初都是没有被标记过的，算法会开始对进程做标记，进程 被标记后说明进程被执行了，不会进入死锁，当算法结束时，任何没有被标记过的进程都会被判定为死 锁进程。
• 上面我们探讨了两种检测死锁的方式，那么现在你知道怎么检测后，你何时去做死锁检测呢？一般来 说，有两个考量标准：
• •每当有资源请求时就去检测，这种方式会占用昂贵的CPU时间。
• •每隔k分钟检测一次，或者当CPU使用率降低到某个标准下去检测。考虑到CPU效率的原因， 如果死锁进程达到一定数量，就没有多少进程可以运行，所以CPU会经常空闲。

从死锁中恢复

上面我们探讨了如何检测进程死锁，我们最终的目的肯定是想让程序能够正常的运行下去，所以针对检 测出来的死锁，我们要对其进行恢复，下面我们会探讨几种死锁的恢复方式

• 通过抢占进行恢复

• 在某些情况下，可能会临时将某个资源从它的持有者转移到另一个进程。比如在不通知原进程的情况 下，将某个资源从进程中强制取走给其他进程使用，使用完后又送回。这种恢复方式一般比较困难而且 有些简单粗暴，并不可取。

• 通过回滚进行恢复

• 如果系统设计者和机器操作员知道有可能发生死锁，那么就可以定期检查流程。

• 进程的检测点意味着进 程的状态可以被写入到文件以便后面进行恢复。

• 检测点不仅包含存储映像(memory image),还包含 资源状态(resource state)

• —种更有效的解决方式是不要覆盖原有的检测点，而是每出现一个检测点都要把它写入到文件中，这样当进程执行时，就会有一系列的检查点文件被累积起来。

• 为了进行恢复，要从上一个较早的检查点上开始，这样所需要资源的进程会回滚到上一个时间点，在这 个时间点上，死锁进程还没有获取所需要的资源，可以在此时对其进行资源分配。

• 杀死进程恢复

• 最简单有效的解决方案是直接杀死一个死锁进程。但是杀死一个进程可能照样行不通，这时候就需要杀 死别的资源进行恢复。

• 另外一种方式是选择一个环外的进程作为牺牲品来释放进程资源。