操作系统笔记整理5——处理机调度与死锁（2）

点此链接可跳转到：操作系统笔记整理——目录索引页

参考书籍：《计算机操作系统》第四版 汤小丹等编著

死锁概述

死锁是多个进程在运行过程中因争夺资源而造成的一种僵局，若无外力作用，这些进程都将无法向前推进。

• 参与死锁的进程数至少为两个
• 参与死锁的所有进程均等待资源
• 参与死锁的进程至少有两个已经占有资源
• 死锁进程是系统中当前进程集合的一个子集

产生死锁的原因

1.竞争不可抢占资源引起死锁 2.竞争可消耗资源引起死锁 3.进程间推进顺序不当引起死锁

产生死锁的四个必要条件

1.互斥条件：进程对分配到的资源进行排他性使用 2.请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程被阻塞，但对自己已经获得的资源保持不放 3.不可剥夺条件：进程已获得的资源，在未使用之前不能被抢占，只能在进程使用完时自己释放 4.环路等待条件：在发生死锁时，必然存在一个进程-资源的循环链，如P0等待一个P1占用的资源，P1等待P2占用的资源，P2等待P0占用的资源

处理死锁的方法

1.鸵鸟方法：忽略死锁 2.预防死锁：通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个 3.避免死锁：在资源的动态分配过程中，用某种方法防止系统进入不安全状态 4.检测死锁：允许系统在运行过程中发生死锁，但可设置检测机构及时检测死锁的发生，并可采取适当措施加以清除 5.解除死锁：检测出死锁后，采取适当措施将进程从死锁中解脱出来

预防死锁

预防死锁是要破坏四个必要条件中的一个或几个，下面逐个条件分析

破坏互斥条件

要想破坏互斥条件，就要允许多个进程同时访问资源，但由于资源本身固有特性的性质，此方法不可行

破坏请求和保持条件

• 第一种协议：全分配，全释放：采用预先静态分配方法，即要求进程在运行之前一次性申请它所需要的全部资源，在它的资源未满足前，不把它投入运行。 摒弃了请求条件：在整个运行期间不会再提出资源请求 摒弃了保持条件：在该进程的等待期间，它并未占有任何资源
• 第二种协议：允许一个进程只获得运行初期所需的资源后，便开始运行。 摒弃保持条件：进程运行过程中必须释放已分配且已用完的资源，然后才能申请新的资源。

破坏不可剥夺条件

• 实施方案1：进程在申请新的资源不能立即得到满足而变为等待状态之前，必须释放已占有的全部资源，若需要再重新申请
• 实施方案2：进程申请的资源被其它进程占用时，可通过操作系统抢占这一资源

破坏环路等待条件

采用有序资源分配方法，即将系统中所有资源都按类型赋予一个编号，要求每个进程均按照资源序号递增的次序来请求资源，从而保证不出现环路。

例如：系统把所有资源按类型进行排队。如输入机 =1，打印机 =2，磁带 机 =3，磁盘机 =4。 如果一个进程已经分配了序号为 i 资源，它接下来请求的资源只能是那些排在 i 之后的资源。 当 iRj 分配边：Rj->Pi 　　　　　　　

如果资源分配图中不存在环路，则系统中不存在死锁；反之，如果资源分配图中存在环路，则系统中可能存在死锁，也可能不存在死锁 　　　　　

资源分配图的化简方法

1. 寻找一个既不阻塞也不孤立的进程节点Pi，若无则算法结束；
2. 去除Pi的所有分配边和请求边，使Pi成为一个孤立结点
3. 转步骤(1)

在进行一系列化简后，若能消去图中所有的边，使所有进程都成为孤立结点，则称该图是可完全简化的；反之，称该图是不可完全简化的 孤立结点：没有请求边和分配边与之相连 阻塞结点：有请求边但资源无法满足其要求 死锁定理：出现死锁的充分条件是资源分配图不可完全简化

可以完全简化 不可完全简化，三个进程结点均为阻塞结点 资源分配图的化简结果与化简顺序无关，最终结果相同

死锁的解除

常用的解除死锁方法有两种：

• 资源剥夺法: 当发现死锁后，从其它进程剥夺足够数量的资源给死锁进 程，以解除死锁状态。
• 撤消进程法: 采用强制手段从系统中撤消一个/一部分死锁进程，并剥夺这些进程的资源供其它死锁进程使用。
  • 撤消全部死锁进程。
  • 按照某种顺序逐个地撤消进程，直至有足够的资源可用，使死锁状态消除 为止。