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

​​点击阅读更多查看文章内容

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

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

@[toc]

死锁概述

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

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

产生死锁的原因

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 之后的资源。
当 i<j 时，进程 A 获得 Ri，可以请求 Rj，而进程 B 获得 Rj 再请求 Ri不可能发生，因为资源 Ri 排在 Rj 前面。

避免死锁

在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，从而避免发生死锁。
安全状态：在某一时刻，系统能按照某种资源顺序来为每个进程分配其资源，直到满足每个进程对资源的最大需求，若不存在这样一个安全序列，则称此时的状态为不安全状态
如果一个系统处于安全状态，就不会死锁
如果一个系统处于不安全状态，就有可能死锁
避免死锁的实质：确保系统不进入不安全状态

安全状态实例
例：假定系统中有三个进程 P1、P2 和 P3，共有 12 台打印机，三个进程
对打印机的需求和占有情况如下表所示：

T0时刻，存在一个安全序列（P2,P1,P3）
首先分配P2两个资源，P2满足需求释放资源，此时有五个可用资源，再将这五个可用资源分配给P1，P1满足需求释放资源，此时有十个可用资源，再分配给P3七个，P3满足需求，至此，满足了每个进程的需求。
安全序列可能不唯一
如果将上例改为下图则进入不安全状态

P2得到两个资源满足需求，释放资源后还有四个可用资源，此时这四个可用资源不能满足P1和P2的需求

银行家算法

实质

设法保证系统动态分配资源后不进入不安全状态

前提

进程必须预先提出自己的最大资源请求数量，这一数量不能超过系统资源的数量，系统资源的总量是一定的

数据结构

假定系统中有n个进程（P1,P2,…,Pn）,m类资源（R1,R2,…,Rm）

• 可利用资源向量：Available[j]=k，表示Rj类资源有k个可用
• 最大需求矩阵：Max[i,j]=k，进程Pi最大请求k个Rj类资源
• 分配矩阵：Allocation[i,j]=k，进程Pi已经分配到k个Rj类资源
• 需求矩阵：Need[i,j]=k，进程Pi还需要k个Rj类资源

Need[i,j]=Max[i,j]-Allocation[i,j]

算法描述

资源分配算法

假定进程Pi请求分配Rj类资源k个，设Request[i,j]=k，当进程Pi发出资源请求后，系统按如下步骤进行检查：

1. 如果Request[i,j]≤Need[i,j]，转(2)；否则出错，因为进程申请资源量超过它声明的最大量
2. 如果Request[i,j]≤Available[j]，转(3)；否则表示资源不够，需等待
3. 系统试分配资源给进城Pi，并做如下修改
   1.Available[j]=Available[j]-Request[i,j]
   2.Allocation[i,j]=Allocation[i,j]+Request[i,j]
   3.Need[i,j]=Need[i,j]-Request[i,j]
4. 系统执行安全性算法。若安全，则正式进行分配，否则恢复原状态让进程Pi等待

安全性算法

为了进行安全检查，需要定义如下数据结构
1.工作变量Work[m]：记录可用资源。开始时，Work=Available
2.finish[n]：记录系统是否有足够的资源分配给进程，使之运行完成。开始时，finish[i]=false；当有足够资源分配给进程Pi时，令finish[i]=true

执行过程：

1. Work:=Available;Finish[i]=false
2. 寻找满足如下条件的进程Pi
   Finish[i]=false
   Need[i,j]≤Wrok[j]，如果找到，转(3)，否则转(4)
3. 当进程Pi获得资源后，可顺利执行完，并释放分配给它的资源，故执行：Work[j]:=Work[j]+Allocation[i,j];Finish[i]:=true,转(2)
4. 若所有进程的Finish[i]=true，则表示系统处于安全状态，否则处于不安全状态

例题

这里就以计算T0时刻的安全性为例

这里提一下，建议大家做题的时候也像上图一样画一个表格，注意每一列所对应的内容，首先根据初始的Work也就是Available找到Need小于Work的进程，然后记录下出Work+Allocation的值，并将Finish改为true，再计算下一个的时候直接用刚刚计算的Work+Allocation代替Work继续寻找小于该值的Need，以此类推，这样做起来逻辑比较清楚，不容易出错。

死锁的检测和解除

如果在一个系统中，既未采用死锁预防方法，也未采用死锁避免方法，而是直接为进程分配资源，则系统中便有可能发生死锁
检测死锁的基本思想：在操作系统中保存资源的请求和分配信息，利用某种算法对这些信息加以检查，以判断是否存在死锁

资源分配图

资源分配图又称进程-资源图，它是描述进程和资源间的申请和分配关系的一种有向图
圆圈：进程节点P
方框：资源节点R，方框中的小黑点数表示资源数
请求边：Pi->Rj
分配边：Rj->Pi
　　　　　　　

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

资源分配图的化简方法

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

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

可以完全简化

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

死锁的解除

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

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