进程死锁

死锁的概念

死锁(deadlock)：一个进程集合中的每个进程都在等待只能由该集合中的其他一个进程才能引发的事件（释放占有资源/进行某项操作）

死锁的形成条件

互斥 资源同一时间只能被一个进程拥有
占有并等待 一个进程必须占有至少一个资源，并等待另一个资源，而该资源为其他进程占有
非抢占 进程不能被抢占，资源只有被拥有资源的进程自愿释放
循环等待 若干进程之间形成头尾相接的资源等待关系

死锁的处理策略

预防死锁，避免死锁，检测死锁，解除死锁，鸵鸟策略

死锁预防

基本思想：使死锁形成条件的一个或多个不成立

• 打破互斥条件，允许多进程同时访问资源

• 打破占有并等待条件 进程运行前申请所有需要资源（无需等待），不满足则不运行，或者只允许进程不占有资源时才能申请资源（不占有） 很多情况下无法预知进程需要的所有资源，会降低资源利用率，降低进程并发性

• 打破非抢占条件 允许进程强行从占有者中夺取资源

• 打破循环等待 实行资源有序分配策略，对所有资源排序编号，所有进程对资源的请求必须严格按资源序号递增的顺序提出，只有占有了小号资源才能申请大号资源

死锁避免

基本思想动态检测资源分配状态，确保循环等待条件不成立，防止系统进入不安全状态。
有两种策略，一种是拒绝启动进程策略，一种是拒绝资源请求策略
银行家算法属于拒绝资源请求策略

• 优点

  比死锁预防限制少
  无须死锁检测中的资源剥夺和进程重启

• 缺点

  必须事先声明每个进程请求的最大资源
  考虑的进程必须是无关的，即它们执行的顺序没有任何同步要求的限制
  分配的资源数目必须是固定的
  在占有资源时进程不能退出

死锁检测

死锁检测没有任何预先限制措施（死锁预防干的事情）,也不会在进程创建或资源分配时检查系统是否会进入不安全状态（死锁避免干的事情），而是周期性地检查系统是否出现死锁，出现死锁后进行恢复

• 检测方法
  单个资源实例：检测资源分配图中是否存在环路（依据——死锁定理）
  多个资源实例：类似银行家算法的安全检查

鸵鸟策略

假设系统不会发生死锁，在发生死锁后手动解锁，比如重启电脑，杀进程。。。

死锁解除

• 死锁解除的策略
  剥夺法：连续剥夺资源直到不再存在死锁
  回退法：把每个死锁进程回滚到前面定义的检查点，并且重新启动所有进程，死锁可能重现
  杀死进程法：杀死所有死锁进程，或连续杀死死锁进程直到不再存在死锁，或杀死一个非死锁进程

• 考虑的问题

  选择牺牲品
  回滚到安全状态
  饥饿状态，避免一个进程多次作为牺牲品* 死锁解除的策略
  剥夺法：连续剥夺资源直到不再存在死锁
  回退法：把每个死锁进程回滚到前面定义的检查点，并且重新启动所有进程，死锁可能重现
  杀死进程法：杀死所有死锁进程，或连续杀死死锁进程直到不再存在死锁，或杀死一个非死锁进程

• 考虑的问题

  选择牺牲品
  回滚到安全状态
  饥饿状态，避免一个进程多次作为牺牲品