操作系统-死锁主题讲义
北京大学操作系统课程，主讲教师：赵俊峰
核心内容
死锁概述
死锁（deadlock）是指系统中多个进程无限期等待永远不会发生的条件。一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到资源。
经典案例：导师让小张和小李分别去借扫描仪和刻录机，结果小张拿着刻录机等扫描仪，小李拿着扫描仪等刻录机，形成死锁。
资源分类
- 可抢占资源（如内存、CPU）：可以从进程手中强行拿走，不会造成不良影响
- 不可抢占资源（如光盘刻录机）：强行拿走会导致进程运行失败
- 死锁主要由不可抢占资源引起
死锁产生的四个必要条件
- 互斥条件：任一时刻只允许一个进程使用资源
- 请求和保持：进程在请求其余资源时，不主动释放已占用的资源
- 非剥夺：进程已占用的资源不会被强制剥夺
- 环路等待：环路中的每一条边是进程在请求另一进程已占有的资源
死锁解决方法
死锁预防
- 破坏”不可剥夺”条件
- 破坏”请求和保持”条件（预先静态分配法）
- 破坏”循环等待”条件（有序资源使用法）
死锁避免
- 银行家算法（Dijkstra, 1965）
- 安全状态与不安全状态概念
- 当进程申请资源时，系统检测是否会导致不安全状态
死锁检测与解除
- 资源分配图简化法
- 撤销进程或剥夺资源
哲学家就餐问题
Dijkstra提出的经典死锁示例。五种解决方案及优缺点分析。
关键概念
| 概念 | 说明 |
|---|---|
| 可重用资源 | 如CPU、内存、外设，不耗尽但互斥使用 |
| 临时性资源 | 如中断、信号、消息，可动态生成和消耗 |
| 安全序列 | 存在一个进程排列，使所有进程都能顺利完成 |
| 资源分配图 | 用有向图描述进程-资源关系，环路是死锁的必要条件 |