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

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

预防死锁

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

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

为了破坏该条件,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中有银行家算法的例子,太长还带表格,不写了,上面算法看不懂的,评论一下,我拍上来。

You may also like...

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注