6.1 资源

需要排他性使用的对象称为资源（resource），即硬件设备或是一组信息，简单来说就是随着时间的推移必须能获得、使用以及释放的任何东西。

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

资源分两类：可抢占的和不可抢占的。
可抢占资源（preemptable resource）可以从拥有它的进程中抢占而不会产生任何副作用。
不可抢占资源（nonpreemptable resource）是指在不引起相关的计算失败的情况下，无法把它从占有它的进程处抢占过来。
使用一个资源所需要的事件顺序：

  1. 请求资源；
  2. 使用资源；
  3. 释放资源。

若请求时资源不可用，则请求进程被迫等待。当一个进程请求资源失败时，它通常会处于这样一个小循环中：请求资源、休眠、再请求。

6.1.2 资源获取

如果只有一个进程，就没有必要慎重地获取资源，因为不存在资源竞争。
编码风格上的细微差别（哪一个资源先获取）造成了可以执行的程序和不能执行而且无法检测错误的程序之间的差别。

6.2 死锁概述

死锁（deadlock）的定义：如果一个进程集合中的每个进程都在等待只能由该进程集合中的其他进程才能引发的事件，那么，该进程集合就是死锁的。

6.2.1 资源死锁的条件

发生资源死锁（resource deadlock）的四个必要条件：

  1. 互斥条件：每个资源要么已经分配给了一个进程，要么就是可用的；
  2. 占有和等待条件：已经得到了某个资源的进程可以再请求新的资源；
  3. 不可抢占条件：已经分配给一个进程的资源不能强制性地被抢占，它只能被占有它的进程显式地释放；
  4. 环路等待条件：死锁发生时，系统中一定有两个或两个以上的进程组成的一条环路，该环路中的每个进程都在等待着下一个进程所占有的资源。

6.2.2 死锁建模

有四种处理死锁的策略：

  1. 忽略该问题：也许如果你忽略它，它也会忽略你；
  2. 检测死锁并恢复：让死锁发生，检测它们是否发生，一旦发生死锁，采取行动解决问题；
  3. 仔细对资源进行分配：动态地避免死锁；
  4. 通过破坏引起死锁的四个必要条件之一：防止死锁发生。

6.3 鸵鸟算法

如果出现死锁的概率很小，并且出现之后处理死锁会花费很大的代价，还不如不做处理，即鸵鸟算法。

6.4 死锁检测和死锁恢复

6.4.1 每种类型一个资源的死锁类型

依次将资源分配图中每一个节点作为一棵树的根节点，并进行深度优先搜索，如果再次碰到已经遇到过的节点，那么就算找到了一个环。

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

可以用一种基于矩阵的算法来检测P1到Pn这n个进程中的死锁，假设资源类型数为m，E是现有资源向量（existing resource vector），代表每种已经存在的资源总数，C代表当前分配矩阵（current allocation matrix），R代表请求矩阵（request matrix），死锁检测算法如下：1)寻找一个没有标记的进程Pi，对于它而言R矩阵的第i行向量小于或等于A，2)如果找到了这样一个进程，那么将C矩阵的第i行向量加到A中，标记该进程，并转到第1步，3)如果没有这样的进程，那么算法终止，算法结束时，所有没有标记过的进程都是死锁进程。
何时检测死锁：1)每当有资源请求时去检测，2)每隔k分钟检测一次或者当CPU的使用频率降到某一域值时去检测。

6.4.3 从死锁中恢复

  1. 利用抢占恢复:
    临时将某个资源从它的当前所有者那里转移到另一个进程。
  2. 利用回滚恢复：
    周期性地对进程进行检查点检查（checkpointed，即将进程的状态写入一个文件以备以后重启），一旦检测到死锁，就进行恢复，从一个较早的检查点上开始，拥有所需要资源的进程回滚到一个时间点，在该时间点后所作的所有工作都丢失。
  3. 通过杀死进程恢复：
    即杀死一个或若干个进程，一种方法是杀掉死锁环中的一个进程（如果行不通就继续杀死别的进程直到打破死锁环），另一种方法是选一个死锁环外的进程作为牺牲品以释放该进程的资源。

6.5 死锁避免

6.5.1 资源轨迹图

建立平面直角坐标系，上、右两个方向代表两个并发执行可能发生资源死锁的进程的相对于时间的进度，执行某个进程就向相应方向行进相应距离，行进轨迹若部分位于两进程请求同资源的进度重叠区，则会死锁。

6.5.2 安全状态和不安全状态

安全状态和不安全状态的区别是：从安全状态出发，系统能够保证所有进程都能完成；而从不安全状态出发，就没有这样的保证。

6.5.3 单个资源的银行家算法

Dijkstra提出了一种能够避免死锁的调度算法，称为银行家算法（banker' algorithm），能够判断若满足进程对资源的请求是否会进入不安全状态。

6.5.4 多个资源的银行家算法

已分配资源矩阵C存储不同进程已被分配的不同资源数，仍被需要资源矩阵R存储不同进程仍需要的不同资源数，向量E、P、A分别表示现有不同资源数、已分配不同资源数、可用不同资源数，检测一个状态是否安全的算法如下：1)查找C矩阵中是否有一行，其没有被满足的资源数均小于或等于A，如果不存在这样的行，那么系统将会死锁，因为任何进程都无法运行结束，2)假若找到这样一行，那么可以假设它获得所需的资源并运行结束，将该进程标记为终止，并将其资源加到向量A上，3)重复以上两步，直到所有的进程都标记为终止，其初始状态是安全的，或者所有进程的资源需求都得不到满足，此时就是发生了死锁。

6.6 死锁预防

6.6.1 破坏互斥条件

可以使用假脱机技术。

6.6.2 破坏占有和等待条件

一种实现方法是规定所有进程在开始执行前请求所需的全部资源；另一种方案是要求当一个进程请求资源时，先暂时释放其当前占用的所有资源，然后再尝试一次获得所需的全部资源。

6.6.3 破坏不可抢占条件

将资源虚拟化，然后抢占。

6.6.4 破坏环路等待条件

一种方法是保证每一个进程在任何时刻只能占用一个资源；另一种方法是将所有资源统一编号，所有请求必须按照资源编号的顺序提出。

6.7 其他问题

6.7.1 两阶段加锁

两阶段加锁（two-phase locking）：第一阶段，进程试图对所有所需的记录进行加锁，一次锁一个记录，如果第一阶段加锁成功，就开始第二阶段，完成更新然后释放。

6.7.2 通信死锁

两个进程在相互通信中可能因丢失信息而死锁，这种死锁称为通信死锁（communication deadlock）。可以用超时来中断通信死锁。

6.7.3 活锁

运行的进程没有阻塞也没有进展的现象称为活锁（livelock）。

6.7.4 饥饿

饥饿（starvation）即进程因一直得不到资源而阻塞（非死锁的情况下）的现象。
饥饿可以通过先来先服务资源分配策略来避免。

6.8 有关死锁的研究

6.9 小结

资源死锁是进程一直等待其他进程被占用的资源（不可能自行被释放的）释放的事件。
可以忽略小概率死锁；可以检测死锁并解决它；可以通过跟踪安全与不安全状态来避免死锁；可以在设计系统时就不允许死锁发生。

博文补充（转）：
《Linux内核设计与实现》读书笔记（九）- 内核同步介绍
《Linux内核设计与实现》读书笔记（十）- 内核同步方法