操作系统原理-死锁

阅读更多

1 死锁的基本概念

死锁的定义

• 一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称为死锁进程
• 如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃
  • 参与死锁的所有进程都在等待资源
  • 参与死锁的进程是当前系统中所有进程的子集

1.1 为什么会出现死锁

原因：资源数量有限、锁和信号量错误使用

资源的使用方式：“申请–分配–使用–释放”模式

可重用资源：可被多个进程多次使用

• 可抢占资源与不可抢占资源
• 处理器、I/O部件、内存、文件、数据库、信号量

可消耗资源：只可使用一次、可创建和销毁的资源

• 信号、中断、消息

1.2 活锁和饥饿

活锁：既无进展，也没有阻塞

• 先加锁
• 再轮询
• Peterson算法可能导致活锁

饥饿：一般由分配策略导致

1.3 产生死锁的必要条件

1. 互斥使用(资源独占)
   • 一个资源每次只能给一个进程使用
2. 占有且等待(请求和保持，部分分配)
   • 进程在申请新的资源的同时保持对原有资源的占有
3. 不可抢占(不可剥夺)
   • 资源申请者不能强行的从资源占有者手中夺取资源，资源只能由占有者自愿释放
4. 循环等待
   • 存在一个进程等待队列 {P1 , P2 , … , Pn},其中P1等待P2占有的资源，P2等待P3占有的资源，…，Pn等待P1占有的资源，形成一个进程等待环路

2 资源分配图（RAG）

用于描述系统资源和进程的状态的有向图，称为资源分配图

二元组G=（V，E）

• V：结点的集合，分为P(进程)，R(资源)两部分
  • P = {P1, P2, ... , Pn}
  • R = {R1, R2, ... , Rm}
• E：有向边的集合，其元素为有序二元组
  • (Pi, Rj) 或 (Rj, Pi)

2.1 资源分配图画法说明

系统由若干类资源构成，一类资源称为一个资源类；每个资源类中包含若干个同种资源，称为资源实例

资源类：用方框表示
资源实例：用方框中的黑圆点表示
进程：用圆圈中加进程名表示

分配边：资源实例 -> 进程
申请边：进程 -> 资源类

2.2 死锁定理

如果资源分配图中没有环路，则系统中没有死锁，如果图中存在环路则系统中可能存在死锁

如果每个资源类中只包含一个资源实例，则环路是死锁存在的充分必要条件

2.3 资源分配图化简

化简步骤：

1. 找一个非孤立、且只有分配边的进程结点。去掉分配边，将其变为孤立结点
2. 再把相应的资源分配给一个等待该资源的进程，即将该进程的申请边变为分配边
3. 重复步骤1和步骤2

类似于BFS遍历有向图

3 死锁预防

3.1 解决死锁的方法

不考虑此问题（鸵鸟算法）

不让死锁发生

• 死锁预防
  • 静态策略：设计合适的资源分配算法，不让死锁发生
• 死锁避免
  • 动态策略：以不让死锁发生为目标，跟踪并评估资源分配过程，根据评估结果决策是否分配

让死锁发生

• 死锁检测与解除

3.2 死锁预防

死锁预防定义：

• 在设计系统时，通过确定资源分配算法，排除发生死锁的可能性
• 具体的做法是：防止产生死锁的四个必要条件中任何一个条件发生

破坏“互斥使用/资源独占”条件

• 资源转换技术：把独占资源变为共享资源
• SPOOLing技术的引入
  • 解决不允许任何进程直接占有打印机的问题
  • 设计一个“守护进程/线程”负责管理打印机，进程需要打印时，将请求发给该daemon，由它完成打印任务

破坏“占有且等待”条件

• 实现方案1：要求每个进程在运行前必须一次性申请它所要求的所有资源，且仅当该进程所要资源均可满足时才给予一次性分配
  • 问题：资源利用率低；“饥饿”现象
• 实现方案2：在允许进程动态申请资源前提下规定，一个进程在申请新的资源不能立即得到满足而变为等待状态之前，必须释放已占有的全部资源，若需要再重新申请

破坏“不可抢占”条件

• 实现方案：
  • 当一个进程申请的资源被其他进程占用时，可以通过操作系统抢占这一资源(两个进程优先级不同)
• 局限性：适用于状态易于保存和恢复的资源（CPU、内存）

破坏“循环等待”条件

• 通过定义资源类型的线性顺序实现
• 实施方案：资源有序分配法
  • 把系统中所有资源编号，进程在申请资源时必须严格按资源编号的递增次序进行，否则操作系统不予分配

4 死锁避免

死锁避免定义：在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统发生死锁或可能发生死锁，则不予分配，否则予以分配

安全状态：如果系统中存在一个由所有进程构成的安全序列P1，…，Pn，则称系统处于安全状态

• 一个进程序列{P1，…，Pn}是安全的，如果对于每一个进程Pi(1≤i≤n）：它以后还需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和，则称系统处于安全状态
• 安全状态一定没有死锁发生

4.1 银行家算法

银行家算法应用条件：

1. 在固定数量的进程中共享数量固定的资源
2. 每个进程预先指定完成工作所需的最大资源数量
3. 进程不能申请比系统中可用资源总数还多的资源
4. 进程等待资源的时间是有限的
5. 如果系统满足了进程对资源的最大需求，那么，进程应该在有限的时间内使用资源，然后归还给系统

详细实现参考：Algorithm-Bank

5 死锁检测与解除

死锁检测：

• 允许死锁发生，但是操作系统会不断监视系统进展情况，判断死锁是否真的发生
• 一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操作系统运行

检测时机：

• 当进程由于资源请求不满足而等待时检测死锁
  • 缺点：系统开销大
• 定时检测
• 系统资源利用率下降时检测死锁

5.1 一个简单的死锁检测算法

算法描述如下

• 每个进程、每个资源指定唯一编号
• 设置一张资源分配表，记录各进程与其占用资源之间的关系
• 设置一张进程等待表，记录各进程与要申请资源之间的关系
• 如果发现环路，就说明产生了死锁

例如有如下分配表，进程之间的资源依赖关系产生了一个环路

5.2 死锁的解除

重要的是以最小的代价恢复系统的运行

方法如下：

• 撤消所有死锁进程
• 进程回退（Roll back）再启动
• 按照某种原则逐一撤消死锁进程，直到处于安全状态
• 按照某种原则逐一抢占资源（资源被抢占的进程必须回退到之前的对应状态），直到处于安全状态

6 参考

• 《MOOC-操作系统原理-陈向群》