死锁

1. 例子

1.1 交通堵塞

一个十字路口有东西南北4个方向的车流，假设没有红绿灯，又没有交警指挥，并且4个方向的排头车辆几乎同时到达十字路口，为了防止撞车都停了下来，形成交通阻塞。
交通死锁的含义就是两辆或两辆以上车辆中，每一辆都占用一条道路，而又等待另外一辆车释放道路资源而无法前进。

1.2 过河

小河中铺了一串垫脚石用于过河，并且两个人在河中相遇且都不退让发生死锁。

2. 定义

2.1 系统资源

• 可抢占式资源

  某进程获得这一类资源后，该资源可以再被系统或其他进程使用；
  CPU
  主存

• 不可抢占式资源

  某进程获得这类资源后，该资源不能被其他进程使用，直到使用完成后才被他主动释放，只能互斥使用；
  打印机
  磁带机

2.2 定义

死锁是指多个进程在并发执行过程中因为争夺不可抢占资源而造成的一种僵局。当这种僵局发生时，相关进程都处于永远等待（阻塞）状态，若无外力作用，这组进程都将永远无法继续向前推进。

2.3 与死循环区别

• 死锁具有偶然性
• 发生死锁时，因为处于阻塞状态，所有没有占用cpu资源，但死循环会一直占用cpu资源
• 死锁是多个进程之间因为争抢不可抢占式资源产生的，与操作系统的管理和资源调度有关；
• 死循环是因为程序设计时的错误

2.4 与饥饿的不同

本质区别：

• 饥饿状态一旦得到所需资源，就可立即运行
• 处于死锁的相关进程都在相互等待对方占用的系统资源而又不释放自己所占资源，所以造成彼此永远无法得到所需资源的现象。

3. 产生原因和必要条件

3.1 产生原因

• 系统资源不足
• 进程推进顺序不当

3.2 必要条件

这几个条件并不是完全独立的

• 互斥条件

  进程对所获的资源进行排他性的使用

• 请求保持条件

  得不到资源而阻塞时，并不释放自己占有的资源

• 不可抢占条件

  进程所获得的资源在未使用结束前不能被其他进程抢占

• 循环等待条件

  隐含着上面三个条件

4. 面对死锁问题

4.1 预防

4.1.1 破坏请求和保持条件

运行之前一次性申请他所需要的全部资源，并且在未获得全部资源前不投入运行，运行后也不再提出新的资源请求。

优点：

• 安全
• 简单
• 易于实现

缺点：

• 系统资源严重浪费。某一资源在被使用完后，并不能被及时释放
• 会加剧作业饥饿的现象
• 进程运行前，系统并不知道它需要多少资源

4.1.2 破坏不可抢占条件

根据需求逐个提出资源请求，当一个已经占有了某些资源的进程，且又提出新的资源请求而得不到满足处于阻塞情况下，必须释放已占有的资源
缺点：

• 某些资源被抢占后可能会引发错误，因为不太容易恢复现场。
• 比较复杂，代价太大
• 可能存在某些进程的资源总是被抢占

适用：

• CPU
• 主存

4.1.3 破坏循环等待条件

采用资源有序分配策略，即将系统中所有资源进行编号，并规定进程申请资源时必须严格按照资源编号顺序进行

缺点：

• 进程实际适用资源顺序不一定和编号一致
• 资源的不同编号方法对资源利用效率有影响
• 资源编号必须相对稳定
• 严格的资源编号使得用户编程的自主性收到限制

4.2 死锁的避免

4.2.1 银行家算法

通过几种预防死锁的方法尽管实现起来比较简单，但基本上都严重影响系统性能或可能会引起致命错误

一个进程提出资源请求后，系统先进行资源的试分配，然后检查本次的试分配是否使系统处于安全状态，若安全则按试分配方案分配资源，否则不分配资源。

银行家算法缺少实用价值：很少有进程能够在运行之前就知道其所需资源的最大值，而且进程数不是固定的，往往在不断变化，况且原本可用的资源也可能突然间变得不可用。

5. 死锁的检测和预防

5.1 死锁检测

• 资源分配图
• 死锁定理
• 死锁检测算法

5.2 死锁解除

• 撤销所有死锁进程
• 让死锁回撤到正常执行状态
• 某顺序逐个撤销死锁进程，直至不发生死锁为止
• 采用抢占资源的策略直到不再发生死锁

5.3 代价最小原则

• 发现时，消耗的CPU资源最小
• 发现时，获得的系统资源最小
• 发现时，产生的输出了最小
• 优先级最低
• 预计进程的剩余时间最长

---

参考
[1]胡元义,黑新宏.操作系统原理. 北京: 电子工业出版社, 2018.