不落辰

知不可乎骤得,托遗响于悲风

0%

操作系统_并发05-死锁

发表于 更新于 分类于
本文字数： 2.7k 阅读时长 ≈ 2 分钟
  • 死锁
    • 理论以及学校考试上
      • 四个条件:互斥 不可剥夺 请求与保持 循环等待
      • 措施:预防,避免,检测/恢复,忽略
      • 死锁避免中的 银行家算法实现
    • 实际
      • AA-Deadlock
        • Thread自己等待自己释放锁 : funcA持有lock , funcA调用funcB , funcB也需要lock
      • AB-BA-Deadlock
        • T1先拿A后等B，T2先拿B后等A
        • 应当严格按照固定的顺序获得所有锁

死锁

  • A deadlock is a state in which each member of a group is waiting for another member, including itself, to take action.

发生死锁的必要条件

  • 互斥（mutual exclusion）: 资源不能被共享，一个资源每次只能被一个进程使用
  • 不可剥夺（no preemption）：进程已获得的资源，在未使用完之前，不能强行剥夺
  • 请求与保持（hold and wait）：一个进程因请求资源而阻塞时，对已获得的资源保持不放
  • 循环等待（circular wait）：若干进程之间形成一种头尾相接的循环性资源等待关系
  • 破坏其中一个，就不会形成死锁.

“理解了死锁的原因，尤其是产生死锁的四个必要条件，就可以最大可能地避免、预防和解除死锁。所以，在系统设计、进程调度等方面注意如何不让这四个必要条件成立，如何确定资源的合理分配算法，避免进程永久占据系统资源。此外，也要防止进程在处于等待状态的情况下占用资源。因此，对资源的分配要给予合理的规划。” ——Bullshit.

死锁预防

  • 互斥和不可剥夺一般很难破坏,死锁预防主要是破坏请求与保持和循环等待这两个必要条件.
  • 方法一 : 破坏请求与保持
    • (要么不请求,要么不保持)
    • 一次性申请所有资源
      • 缺点
      • 需要预先计算程序所需资源,这很难做到
      • 在很远的未来会用到的资源需要早早地预留下来,这会造成资源的极大浪费.
      • …
  • 方法二 : 破坏循环等待
    • 存在环路–>死锁
    • 不让资源等待形成环路.
    • 资源按序申请
      • 资源按序申请就一定不会出现环路,因此也就一定不会出现死锁.

死锁避免

  • 死锁预防:对进程申请资源做出限制,不能随意的发出申请.
  • 死锁避免:
    • 进程可以随意申请资源,但是需要有一个机制来
      • 判断这次请求是否可能造成死锁.
      • 存在这种死锁危险就拒绝此次申请.
      • (死锁危险实际上不一定会造成死锁)
    • 这样,就能保证进程对资源的占用和申请总处于安全状态.

银行家算法 bank’s algorithm

  • 思路: 遇到一个资源请求时,首先假设允许此次资源请求,

    • 如果发现允许该请求以后os上仍能找到安全序列,说明此次请求安全.可以分配资源
    • 如果找不到,虽然不是一定会发生死锁,但还是拒绝请求
    • 银行家算法是一个充分性算法(满足算法就必定安全),对资源的访问控制保守.
    • 例子

  • 时间复杂度:O(m * n^2). m:资源数量 n:进程数量

  • 代码地址

  • 缺点

    • 保守:本来不会导致死锁的请求不被允许.资源浪费,用户进程拖延.因为进程所占用的资源不是在进程结束之后一起释放的,而是使用完立即释放.
    • 效率不高 : 首先时间复杂度O(m * n^2),其次在进程的每一次请求时都需要执行一次银行家算法.
      • 对于P12..N各个进程的申请释放动作,判定系统执行状态S是否会引起死锁,这是个NPC问题.只能容忍bank的时间复杂度
    • 参数难以获得:需要知道进程执行完毕所需要的资源总量

死锁检测 + 死锁恢复

  • 死锁检测算法 + 死锁恢复机制
  • 思路:通过一种算法检测哪些进程死锁,并通过机制将陷入死锁的进程恢复.

死锁检测算法

  • 死锁检测算法(银行家算法变形:

    • 遍历n个进程,check每个进程拿到其所请求的资源后(不是所需的全部资源,只是该进程此时请求的资源)是否可以运行,
    • 如果此时的系统状态下,不能满足任何一个等待运行的进程的请求
      • 那么,此时即发生了死锁.即这些不能运行,等待资源的进程就陷入了死锁.记录下这些陷入死锁的进程.之后将这些进程恢复

  • 时间复杂度: O(m * n^2)

  • 死锁检测算法 vs 银行家算法

    • 死锁检测算法: 定时调用 或是 需要检查死锁时才调用. (调用频率低)
    • 银行家算法: 每次进程申请资源都要调用 (为了避免死锁发生)

  • 缺点:死锁恢复机制不好实现

    • 死锁检测算法的系统开销可以接收,但是 死锁恢复 不好实现.例如如何回滚
    • 因此死锁检测/恢复 对 资源的访问没有限制,但是不好处理出现的死锁.

死锁忽略

  • 对死锁不做任何处理
  • PC机上的Linux Window都这样.
    • 死锁概率低 + 重启代价小

排查死锁 线程池

死锁实际

AA-DeadLock

  • Thread自己等待自己

    • 如：funcA 获得lockA , 在unlockA之前调用funcB , funcB需要lockA。

  • 假设你的 spinlock 不小心发生了中断

    • 在不该打开中断的时候开了中断
    • 在不该切换的时候执行了 yield()
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      void os_run() {
        spin_lock(&list_lock);
        spin_lock(&xxx);
        spin_unlock(&xxx); // ---------+
      }                          //    |
                                //    |
      void on_interrupt() {      //    |
        spin_lock(&list_lock);   // <--+
        spin_unlock(&list_lock);
      }

  • 死锁避免

    • AA 型的死锁容易检测，及早报告，及早修复
    • spinlock-xv6.c 中的各种防御性编程
      • if (holding(lk)) panic(); 检查，如果已经获得A锁了，此时还想获得，那么直接报错。而不是让死锁发生。

AB-BA-DeadLock

  • T1先拿A后等B，T2先拿B后等A

    • T1 拿到A。T2拿到B。T1等待B。T2等待A
      1
      2
      3
      4
      5
      6
      7
      8
      void swap(int i, int j) {
        spin_lock(&lock[i]);
        spin_lock(&lock[j]);
        arr[i] = NULL;
        arr[j] = arr[i];
        spin_unlock(&lock[j]);
        spin_unlock(&lock[i]);
      }

  • 上锁的顺序很重要……

  • swap 本身看起来没有问题

    • swap(1, 2); swap(2, 3), swap(3, 1) → 死锁。
      • swap(1,2) lock 1
      • swap(2,3) lock 2
      • swap(3,1) lock 3 (该thread应当调用swap(1,3) , 来先获取lock 1 而不是lock 3. 这样才做到和swap(1,2) , swap(2,3)保持上锁顺序一致)
      • swap(1,2) wait for 2
      • swap(2,3) wait for 3
      • swap(3,1) wait for 1

  • 死锁避免

    • 任意时刻系统中的锁都是有限的
    • 严格按照固定的顺序获得所有锁 (lock ordering; 消除 “循环等待”)
      • “在任意时刻总是有获得 “最靠后” 锁的可以继续执行”