操作系统原理学习笔记（十六）-预防死锁与避免死锁

操作系统原理学习笔记目录

预防死锁

通过破坏产生死锁的四个必要条件来预防死锁，
但因互斥条件是必须的，所以不能破坏该条件。

预防死锁-破坏“请求和保持”条件

为了破坏该条件，OS需要保证：
当进程请求资源时，不可持有不可抢占资源。
可通过两个协议实现：

第一种协议

进程在开始运行前，一次性申请整个运行过程中所需的全部资源。

缺点：

• 资源严重浪费。
• 进程进程出现饥饿现象。

第二种协议

进程在开始运行前，仅请求初期所需资源，运行时逐步释放不再需要的资源，并请求新的所需资源。

预防死锁-破坏“不可抢占”条件

保持了不可抢占资源的进程，提出新资源申请，但不被满足时，释放所有已得到的资源。

实现复杂，且释放已有资源很可能付出很大代价。

预防死锁-破坏“循环等待”条件

对系统所有资源类型进行排序，并赋予不同序号，进程在请求资源时，必须按序号递增顺序请求资源。如果一个拥有高序号资源的进程，请求低序号资源，则需要先释放高序号资源，再请求低序号资源。

资源利用率与吞吐量相较前两策略改善不少。

缺点：

• 新设备的增加被限制。
• 资源标号困难。
• 限制用户编程思路。

避免死锁

在资源动态分配过程中，防止系统进入不安全状态，限制弱，但成本低。

避免死锁-系统安全状态

死锁避免中，系统状态被划分成安全状态与不安全状态，处于不安全状态时，系统可能进入死锁。

允许进程动态申请资源，但OS进行分配资源前，应先评估资源分配安全性，仅安全状态下可分配。

安全状态，是指OS能按某进程推进顺序为各进程分配资源（包括释放资源），满足各进程对资源的最大需求。
安全状态下不会出现死锁。

安全状态的例子见P119，很简单的一个例子。

避免死锁-利用银行家算法避免死锁

由Dijkstra的银行家算法是一个非常有代表性的避免死锁算法。

为实现银行家算法，每个新进程在进入系统时，先申明各所需资源的最大数目。
OS分配资源时，先确认有足够资源分配给该进程，再确认分配资源后是否会进入不安全状态。

银行家算法的数据结构

• Available[]：可利用资源向量，包含m个元素的数组，表示系统中该类资源的数目。
• Max[][]：n*m矩阵，n个进程对m个资源的最大需求。
• Allocation[][]：n*m矩阵，n个进程已获得m个资源的数量。
• Need[][]：n*m矩阵，n个进程所需的m个资源的数量。

关系：Need[i, j] = Max[i, j] - Allocation[i, j]
书本中的Need等二维向量，仅用一对[]，但为了区分，变量名中我使用两对[]。

银行家算法

Request是进程p的请求向量，
Request[j]=k表示当前p进程对j资源需要k个数量。
如无特别说明，带序号的步骤为顺序步骤。

1. Request[][]<=Need[][]，如果大于，则认为出错，因为超过了它原先宣布的最大值。
2. Request[][]<=Available[]，如果大于，则等待。
3. 将数据结构中各数据修改成分配资源后的值。
4. 执行安全性算法，若安全，则分配数据，若不安全，则本次分配作废，进程等待。

安全性算法

1. 设置两个临时变量Work[]=Available[]、Finish[]=false，分别表示当前可用资源数目、是否已经安全分配资源。
2. 从进程集合中找到一进程i满足：Finish[i]==false，并且Need[i, j]<Work[j]的进程，若找到，进入3，否则进入4.
3. 设置Work[j]+=Available[i, j]，Finish[i]=true，即分配完资源给进程，进程结束后释放资源，Work增加，安全分配，Finish置真。
   步骤3结束后，跳回步骤2.
4. 所有进程Finish[]==true，是则表示处于安全状态，不是则不安全。

银行家算法示例

P121中有银行家算法的例子，太长还带表格，不写了，上面算法看不懂的，评论一下，我拍上来。