deadlocks(死锁)

DeadLocks

死锁的特征

哲学家用餐死锁问题

  • 当所有人同时拿到一侧的筷子时，发生永远等待现象 （即死锁）。
  • 有若种办法可避免死锁：
    • 至多允许四个哲学家同时吃；
    • 奇数号先取左手边的筷子，偶数号先取右手边的筷子；
    • 每个哲学家取到手边的两根筷子才吃，否则一根也不取。
  • 进程访问资源流程：申请 ➠ 使用 ➠ 释放

define

  • In a multiprogramming environment, several(若干) processes may compete for a finite(有限) number of resources.
  • A process requests(请求) resources; if the resources are not available(可用的) at that time, the process enters a waiting state.
  • Sometimes, a waiting process is never again able to change state, because the resources it has requested are held(占有) by other waiting processes.
  • This situation is called a deadlock

死锁与饥饿

  • 饥饿：进程长时间的等待
    • e.g.低优先级进程总是等待高优先级所占有的进程
  • 死锁：循环等待资源

产生死锁的四个必要条件

  • 互斥使用： 一个时刻，一个资源仅能被一个进程占有
  • 不可剥夺： 除了资源占有进程主动释放资源，其它进程都不可抢夺其资源
  • 占有和等待 ：一个进程请求资源得不到满足等待时，不释放已占有资源
  • 循环等待(上面三个条件同时存在产生的结果)： 每一个进程分别等待它前一个进程所占有的资源

死锁的解决方案

  • 死锁的防止 (Prevention)
    • 破坏四个必要条件之一
  • 死锁的避免 (Avoidance)
    • 允许四个必要条件同时存在，在并发进程中做出妥善安 排避免死锁的发生，使用安全算法
  • 死锁的检测和恢复 (Detection & Recovery)
    • 允许死锁的发生，系统及时地检测死锁并解除它

死锁的防止

  • 互斥使用：破坏这个意味者，要使资源共享使用，不是所有的资源都是可以共享使用的，如打印机同时只允许一个人使用，故：这明显是不可行的
  • 不可剥夺：破坏这个条件意味着，资源可以被抢夺，我们只知道CPU可以被抢夺，若共享资源是打印机呢，抢夺打印机明显是不可行的，故：不可行
  • 占有和等待：破坏这个条件意味这，一次性拿到进程所需的所有资源，若A进程需要disk CPU 打印机 ， 当A进程要执行时，他的全部资源就已经被获取了，但是导致了资源的严重浪费，因为A进程可能要在执行的最后才使用打印机，但是A在执行的开始就已经将其占用了，这造成了资源浪费，这是可以的但是效果不太好
  • 循环等待：
    破坏这个条件可以的方法：由程序员自行为资源排序可以将其抽象成一个数组，将资源以一定顺序放入数组中（一般按照优先级顺序）R = {R1,R2,R3,R4}，当要申请一个资源时必须使得全部资源都满足才可申请（当要申请R3时，R1 ，R2资源均要获取），这样解决了循环等待问题，但是这样也存在资源的浪费（当申请R3时，R1与R2可能并不是必要的）而且可操作性差，故可行但是效果不好

死锁的避免

安全状态

  • A state is safe if the system can allocate resources to each process (up to its maximum) in some order and still avoid a deadlock. More formally(正式的), a system is in a safe state only if there exists a safe sequence(序列).
  • If no such sequence exists, then the system state is said to be unsafe.
  • A safe state is NOT a deadlocked state.
  • An unsafe state MAY lead to a deadlock.

死锁的避免

  • 系统对进程的每一次资源申请都进行详细的计算， 根据结果决定是分配资源还是让其等待，确保系统 始终处于安全状态，避免死锁的发生。
  • 银行家算法（Banker’s algorithm）
    • 已知系统中所有资源的种类和数量
    • 已知进程所需要的各类资源最大需求量
    • 该算法可以计算出当前的系统状态是否安全(寻找安全序列)

存在安全序列{ P1,P3,P4,P2,P0 }，系统处于安全状态。

银行家算法就是寻找一个安全分资源的序列使得，避免死锁的发生

  • 优点：允许死锁必要条件同时存在
  • 缺点：缺乏实用价值
    • 进程运行前就要求知道其所需资源的最大数量
    • 要求进程是无关(独立)的，因为分配资源的安全顺序是固定的，若考虑同步情况，可能会打乱安全序列
    • 要求进入系统的进程个数和资源数固定（这不太现实）

死锁检测

死锁的检测与恢复

  • 允许死锁发生，操作系统不断监视系统进展情况， 判断死锁是否发生
  • 一旦死锁发生则采取专门的措施，解除死锁并以最 小的代价恢复操作系统运行
  • 死锁检测的时机
    • 当很多进程等待时检测死锁（系统开销大，资源被分配却没有归还）
    • 定时检测
    • 系统资源利用率下降时检测死锁

资源分配图

方框表示一类资源，里面的黑点表示该类资源的个数
原型表示进程
由进程指向资源表示进程申请资源
由资源指向进程表示系统分配资源给欸进程

资源分配图示例：

死锁发生在申请边

图一：p1申请R1将会等待，P2申请R2将会等待，P3没有申请资源。故P3将会执行完会归还资源R2 R4，这样P2就可执行，P2执行完归还R1,P1即可正常运行

图二：P1申请R1将等待，P2申请R2将等待，P3申请R3将等待，3个进程无一可以执行故死锁

图三：P1申请R1将等待，P2不申请资源，P3申请R2，P2完成后归还R1，P4完成后归还R2，可以正常运行

死锁的解除(recovery)

  • 中止进程，强制回收资源（如我们的windows中，一个进程可能会弹出对话框说进程长时间无响应，询问是否等待还是结束进程，这可能是改进程发生了死锁现象，这里使用可能是因为操作系统只检测了进程在等待队列的时长）
  • 剥夺资源，但不中止进程
  • 进程回退(roll back)
  • 重新启动

参考：https://www.bilibili.com/video/BV1bf4y147PZ

光看视频而不看书是远远不够的，但是由于考试在及，没有过多的时间，暑假立flag：

  • 让自己擅长汇编语言
  • 操作系统真象还原