C++ Concurrency in Action | Dead Locks

警告
本文最后更新于 2023-12-11,文中内容可能已过时。

资源死锁(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 的分配顺序可以使得所有进程都能完成,因此这个状态是安全的

    进程已分配资源最大需求
    A39
    B24
    C27
  • 空闲资源数为 2 时的如下状态就是不安全状态。首先只能先运行 B,B 运行结束后共有 4 个空闲资源,无法再运行 A 或 C

    进程已分配资源最大需求
    A49
    B24
    C27
  • 安全状态和不安全状态的区别是: 从安全状态出发,系统可以保证所有进程都能完成,而从不安全状态出发就没有这样的保证

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

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

  • 已分配资源

    进程资源1资源2资源3资源4
    A3011
    B0100
    C1110
    D1101
    E0000
  • 仍需要的资源

    进程资源1资源2资源3资源4
    A1100
    B0112
    C3100
    D0010
    E2110
  • 对应的当前分配矩阵 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);
    }
Buy me a coffee~
支付宝
微信
0%