C++ Concurrency in Action | Dead Locks

资源死锁(resource deadlock)

• 资源分为两类
  • 可抢占资源(preemptable resource): 可以从拥有它的进程中抢占，而不会产生任何副作用，如存储器
  • 不可抢占资源(nonpreemptable resource): 在不引起相关的计算失败的情况下，无法把它从占有它的进程处抢占过来，如光盘刻录机
• 死锁主要关心不可抢占资源
• 如果一个进程集合中，每个进程都在等待集合中的其他进程才能引发的事件，则该进程集合就是死锁的。通常这个事件是其他进程释放自身占有的资源，这种死锁称为资源死锁，这是最常见的死锁类型，但不是唯一的类型
• 发生资源死锁的四个必要条件是:
  • 互斥条件: 每个资源要么分配给一个进程，要么是可用的
  • 占有和等待条件: 已得到某个资源的进程可以再请求新的资源，并且不会释放已有资源
  • 不可抢占条件: 已分配给一个进程的资源不能被强制抢占，只能被占有它的进程显式释放
  • 环路等待条件: 死锁发生时，系统中必然有多个进程组成一条环路，环路中的每个进程都在等待下一个进程所占有的资源

鸵鸟算法

• 最简单的解决方法是，把头埋到沙子里，假装根本没有问题发生。不同人对该方法的看法也不同，数学家认为这种方法完全不可接受，无论代价多大都应该彻底防止死锁发生，工程师认为要根据死锁发生的频率、严重程度、系统崩溃次数来决定，如果死锁每五年发生一次，而系统每个月都会因故障崩溃一次，就没有必要用损失性能和可用性的代价去防止死锁

死锁检测和死锁恢复

• 第二种技术是死锁检测和恢复，使用这种技术时，系统不阻止死锁的产生，而是允许死锁发生，在检测到死锁发生后再恢复
• 用 E 表示现有资源向量(exisiting resource vector)，A 表示可用资源向量(available resource vector)，用 C 表示当前分配矩阵(current allocation matrix)，用 R 表示请求矩阵(request matrix)，死锁检测的算法是
  • 在 R 中查找是否存在某一行(即一个进程)小于等于 A
  • 如果找到这样一行，就将 C 中相同行数的行(即该进程的已分配资源)加到 A 中，然后标记该进程，再转到上一步
  • 如果不存在这样一行，则算法终止。算法结束时，所有没标记过的进程都是死锁进程
• 死锁恢复方法有: 抢占、回滚、终止进程

死锁避免

• 如果当前状态下没有死锁发生，并且存在某种调度次序能使每个进程都运行完毕，则称该状态是安全的

• 对于目前有 3 个空闲资源的如下状态，先分配 2 个资源给 B，B 运行完释放 4 个资源，此时有 5 个空闲资源，接着 5 个资源全分配给 C，C 运行结束后将有 9 个空闲资源，最后将 9 个资源全分配给 A 即可。按 BCA 的分配顺序可以使得所有进程都能完成，因此这个状态是安全的

  进程	已分配资源	最大需求
  A	3	9
  B	2	4
  C	2	7

• 空闲资源数为 2 时的如下状态就是不安全状态。首先只能先运行 B，B 运行结束后共有 4 个空闲资源，无法再运行 A 或 C

  进程	已分配资源	最大需求
  A	4	9
  B	2	4
  C	2	7

• 安全状态和不安全状态的区别是: 从安全状态出发，系统可以保证所有进程都能完成，而从不安全状态出发就没有这样的保证

• Dijkstra 提出了一种避免死锁的调度算法，称为银行家算法(banker’s algorithm)，方法是对每一个请求进行检查，如果满足这一请求会到达安全状态，则满足该请求，否则推迟对该请求的满足

• 之前安全状态的例子考虑的就是单个资源的银行家算法，下面考虑多个资源的银行家算法

• 已分配资源

  进程	资源1	资源2	资源3	资源4
  A	3	0	1	1
  B	0	1	0	0
  C	1	1	1	0
  D	1	1	0	1
  E	0	0	0	0

• 仍需要的资源

  进程	资源1	资源2	资源3	资源4
  A	1	1	0	0
  B	0	1	1	2
  C	3	1	0	0
  D	0	0	1	0
  E	2	1	1	0

• 对应的当前分配矩阵 C 和请求矩阵 R 为

  1 2 3 4 5 6

  C R 3011 1100 0100 0112 1110 3100 1101 0010 0000 2110

• 用三个向量表示现有资源 E、已分配资源 P、可用资源 A，计算分配矩阵 C 的每列和得到 P = (5322)，以 E = (6342) 为例，A = E - P = (1020)

• 检测一个状态是否安全的算法是

  • 查找一个使用可用资源即可运行的进程，如果找不到则系统就会死锁
  • 如果找到，则假设该进程获取所需资源并运行结束，将该进程标记为终止，再将其资源加到 A 上
  • 重复上述两步，如果最后所有进程都被标记为终止，则初始状态是安全的

• 对于这个例子

  • 进程 D 仍需要的资源为 (0010)，均小于 (1020)，因此运行 D，D 最初的已分配资源为 (1101)，因此结束后 A = (1020) + (1101) = (2121)
  • 进程 A 仍需要的资源为 (1100)，均小于运行 (2121)，运行 A(此时 E 也满足条件，也可以运行 E)，A 最初的已分配资源为 (3011)，结束后 A = (2121) + (3011) = (5132)
  • 运行 B，结束后 A = (5132) + (0100) = (5232)
  • 运行 C，结束后 A = (5232) + (1110) = (6342)
  • 运行 E，结束后 A = (6342) + (0000) = (6342)
  • 所有进程都运行结束，因此这个例子的状态是安全的

死锁预防

• 死锁避免本质上来说是不可能的，因为它需要获取未来的请求，而这些请求是不可知的
• 死锁发生时，四个条件必须同时成立，因此破坏其中条件即可预防发生死锁
  • 破坏互斥条件: 如果资源不被一个进程独占，就一定不会发生死锁。实际情况中，如果允许两个进程同时使用打印机就会造成混乱，解决这个问题的方法是假脱机打印机技术(spooling printer)
  • 破坏占有并等待条件: 禁止已持有资源的进程再等待其他资源即可。一种实现方法是，规定所有进程在开始执行前请求所需的全部资源。这种方法的问题是，很多进程在运行时才知道需要多少资源，实际上如果进程知道需要多少资源就可以使用银行家算法。另一种方法是，当进程请求资源时，先暂时释放其占有的资源，再尝试一次获取所需的全部资源
  • 破坏不可抢占条件: 这种方法是可能的
  • 破坏环路等待条件: 对资源编号，请求必须按编号升序提出，但问题在于，几乎找不出一种使每个人都满意的编号次序

通信死锁(communication deadlock)

• 除了最常见的资源死锁，还有通信死锁。通信死锁发生在通信系统(如网络)中，比如进程 A 向进程 B 发送请求信息并阻塞至 B 回复，如果 A 发送的信息丢失，就会导致 A 和 B 均阻塞，从而导致死锁
• 通信死锁可以通过超时来解决，发送者在发送信息时启动计时器，如果计时器在回复到达前停止，则发送者可以认为信息已丢失，并重新发送

活锁(livelock)

• 活锁不会导致进程阻塞，甚至可以说进程正在活动，因此不是死锁，但实际上进程不会继续往下执行，因此可以称为活锁

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

  void process_A() { acquire_lock(&resource_1); while (!try_lock(&resource_2)) { // 进程 A 尝试获取资源 2 失败 release_lock(&resource_1); // 先释放资源 1，一段时间后再尝试获取资源 2 wait_fixed_time(); // 若 B 此时也在等待，则两者都让出了资源但对方都未获取 acquire_lock(&resource_1); // 两者各自拿回资源，则下次获取对方资源仍会失败 } // 若此过程一直重复就是活锁 use_both_resources(); release_lock(&resource_2); release_lock(&resource_1); } void process_B() { acquire_lock(&resource_2); while (!try_lock(&resource_1)) { release_lock(&resource_2); wait_fixed_time(); acquire_lock(&resource_2); } use_both_resources(); release_lock(&resource_1); release_lock(&resource_2); }