死锁

要说死锁,先明确一个「资源」的概念。进程对设备,文件等取得独占性访问,这种排他性的对象我们称作资源。资源又分为可剥夺和不可剥夺的。可剥夺的资源不会产生死锁。

死锁有4个条件,任一一个打破即可解除死锁。

1. 互斥条件,一个资源每次只能被一个进程使用。
2. 请求与保持条件: 一个进程因请求资源而阻塞时,对已获得的资源保持不放。
3. 不剥夺条件: 进程已获得的资源,在未使用完之前,不能强行剥夺。
4. 循环等待条件: 若干进程之间形成一种头尾相接的循环等待资源关系。

处理死锁有四种策略:

1. 忽略该问题
2. 检测死锁并恢复
3. 仔细地对资源进行动态分配,以避免死锁。
4. 通过破除所述的四个条件中的任意一个条件,用以防止死锁产生。

死锁的检测:

  • 单资源类型的检测,判断资源分配有向图是否存在环,存在即可能死锁。
  • 多资源类型的检测, 使用资源矩阵分别记录资源总数,可用资源数以及进程申请资源数,然后检测是否有进程满足申请数少于可用数存在则该进程可正常获取资源,并最终释放已占用的资源(即是若找到进程满足,则可用资源数矩阵值应加上该进程的占用值。)如果遍历完了矩阵,没有找到符合条件的,则表示会发生死锁,结束算法。

死锁的恢复:

  • 剥夺法恢复,
  • 回退法恢复,进行恢复时进程回滚到较早的检查点,该检查点之后的所有的工作都将丢失。
  • 杀死进程恢复,

死锁的避免(银行家算法

  • 单资源的银行家算法,银行家算法对每一个请求进行检查,检查如果满足它是否会引起不安全状态。若是则不满足该请求,否的话便满足。检查状态是否安全的方法是看他能否有足够的资源去满足一个距最大需求最近的客户。若可以满足,那么这笔投资被认为是可收回的。然后接着检查下一个距最大需求最近的客户能否满足,如此往复直到所有投资都能被收回那么这个状态是安全的,最初的请求便可批准。
  • 多资源的银行家算法

实际上,银行家算法缺乏实用价值。因为很少有进程能够在运行前就知道其所需资源的最大值,而且进程数也是不固定的。因此在实际中,如果有也是极少的系统使用银行家算法来避免死锁。

两阶段加锁

在第一阶段进程对所有所需要的记录进行加锁,一次锁一个记录。如果第一阶段加锁成功,就进行第二阶段,更新加锁的记录然后释放锁。在第一阶段并没有做实际的工作。如果在第一阶段,某一个待加锁的记录已经被锁,那么所有已被此进程加锁的记录的锁都必须被释放,然后重新开始第一个阶段。如果没有释放就重新加锁,可能产生死锁。

非资源死锁

在此之前都是讲的资源死锁,而死锁还存在另外一种非资源的死锁。例如当两个进程都在等待对方的某种操作。如 TCP 中滑动窗口可能出现死锁,server 方的窗口值不再为1,且发送的这个包在网络中丢失了。client 并不知道 server 的窗口值大于1,可以发包了。server 等待 client 发包,client 等待 server 的窗口值增大,导致死锁。此外使用信号量的时候,也时常产生死锁。

饥饿

一些进程永远也得不到服务的情况。可以通过先来先服务的资源分配策略来避免。

设系统中有 m 个同类资源数,n 为系统中的并发进程数,当 n 个进程共享 m 个互斥资源时,每个进程的最大需求数是 w,当 m > n*(w-1)时不会发生死锁。