正在学习操作系统,记录笔记。
参考资料: 《操作系统(精髓与设计原理 第6版) 》
本文的标题为“死锁和饥饿”,但是在接下来的内容中讲述的基本上都是死锁的问题。在这里说明一下原因:
先给结论(当然这个说法并不准确,但可以如此理解):总体来说,从概念上看死锁可以看作是饥饿的子集。
为什么这么讲,那我们就来分析一下二者的区别:
饥饿:一个以上的进程(具备运行条件),遇到某种情况导致一直无法运行。
死锁:可以定义为一组(两个及以上)相互竞争系统资源或进行通信的进程间的“永久”阻塞。如果没有操作系统的干预,死锁无法自己解决问题。
二者的共同点:
二者的差异:
关于死锁的一点补充:死锁的问题有多种,但是并没有一种“万金油”式的通用有效的解决方案。需要根据具体问题具体分析。
造成死锁的问题主要分为两类(后面会有案例):
对于资源的概念,通常可以分为两类:可重用资源以及可消耗资源。
下面将给出涉及可重用资源死锁的例子:
处理这类死锁的一个策略是给系统设计施加关于资源请求顺序的约束。
如果两个进程都前进到它们的第二个请求时,则会发生死锁。解决这类特殊问题的最好办法是,通过使用虚拟内存。
如果Receive阻塞(即接收进程被阻塞直到收到消息),则发生死锁。
为了更有效刻画进程的资源分配情况,引入了资源分配图(如下图)。
下面看一个例子:
分析: 这是一个死锁的例子。资源Ra和Bb都仅拥有一个单位的资源。进程P1持有Rb同时请求Ra,同时,P2进程持有Ra同时又请求Rb。
说明: 第四个条件实际上是前三个条件的潜在结果,即假设前三个条件存在,可能发生的一系列事件会导致不可解的循环等待。这个不可解的循环等待实际上就是死锁的定义。条件4中列出的循环等待之所以是不可解的,是因为有前面三个条件的存在。因此,这四个条件连在一起构成了死锁的充分必要条件。
有了上述对死锁成因的分析,接下来我们将讨论如何解决死锁问题。这里分为两类,其中每一类又可以细分。
死锁的解除方案:
关于鸵鸟算法: 传说中鸵鸟看到危险就把头埋在地底下,使自己看不到危险。所以鸵鸟算法也是一种“不作为”的办法。在死锁问题出现概率很低的情况下,大多数工程师不会以性能损失或者易用性损失的代价来消除死锁,处理死锁问题的办法仅仅是忽略它。因为解决死锁的问题,通常代价很大。所以鸵鸟算法,是平衡性能和复杂性而选择的一种方法。(现在商业大部分都使用此算法)
下面我们重点讨论除鸵鸟算法之外的其他三种解决方法。
简单理解,死锁预防就是通过适当的策略,来消除死锁的四个成因之一,从而避免死锁的发生。
一般来讲,在所列出的四个条件中,第一个条件不可能禁止。如果需要对资源进行互斥访问,那么操作系统必须支持互斥。
为预防占有且等待的条件,可以要求进程一次性地请求所有需要的资源,并且阻塞这个进程直到所有请求都同时满足。
这种方法在两个方面是低效的。首先,一个进程可能被阻塞很长时间,以等待满足其所有的资源请求。而实际上,只要有一部分资源,它就可以继续执行。其次,分配给一个进程的资源可能有相当长的一段时间不会被使用,且在此期间,它们不能被其他进程使用。 另一个问题是一个进程可能事先并不会知道它所需要的所有资源。
下面的方法可以预防这个条件:
循环等待条件可以通过定义资源类型的线性顺序来预防。
如果一个进程已经分配到了R类型的资源,那么它接下来请求的资源只能是那些排在R类型之后的资源类型。 循环等待的预防方法可能是低效的,它会使进程执行速度变慢,并且可能在没有必要的情况下拒绝资源访问。
要注意与死锁避免与死锁预防的差异:
首先需要掌握四种数据结构:
从以上定义中可以得出以下三个关系:
根据以上的关系,就可以定义一个死锁避免的策略:
对于所有的 j ,满足:
Rj≥C(n+1)j+∑i=1nCijR_{j} \ge C_{(n+1)j} + \sum_{i=1}^{n} C_{ij} Rj≥C(n+1)j+i=1∑nCij
才会启动一个进的进程Pn+1。(只有所有当前进程的最大请求量加上新的进程请求可以满足时,才会启动该进程。)
案例分析:如下图,资源1、2、3的总量分别为10、10、9,进程一对三种资源的需求分别为1、4、5,进程二对三种资源的需求分别为3、5、4,如果启动进程P3需要请求三种资源的数量为2、3、1,请分析P3进程能否启动。
分析:
所以进程三不得启动。
在说明银行家算法之前先明确以下三种状态:
下面来看一个例子: 下图(a)显示了一个含有4个进程和3个资源的系统的状态。R1、R2和R3的资源总量分别为9、3和6。在当前状态下资源分配给4个进程,R2和R3各剩下1个可用单元。请问这是安全状态吗? 根据前面的介绍,对于进程 i 下面的条件应该满足对所有的 j,都有: Cij−Aij≤VjC_{ij} - A_{ij} \le V_{j} Cij−Aij≤Vj
显然这对P1是不可能的,但是P2是可行的,因为P2只需要一个R3资源就拥有了它所需要的最大资源,因此P2进程运行。当运行完之后,它的资源回到可用资源池中(如下图(b))
在这种情况下,所有进程都可以完成,假设选择P1运行,结束之后,资源释放并回到可用资源池中,如下图©。
下一步完成P3进程,结束后资源如下图所示(d)。
最后,可以完成P4进程。至此,所有进程运行结束,因此这是一个安全状态。
再考虑下面一种状态:
这种情况没有一个进程是可以运行的,因此这不是一个安全状态。 但是这并不是一个死锁状态,它仅仅是有死锁的可能(这点很重要)。 (如果P1从这个状态开始运行,先释放一个R1单元和一个R3单元,后来又再次需要这些资源,则一旦这样做,系统将到达一个安全状态。因此,死锁避免策略并不能确切地预测死锁,它仅仅是预料死锁的可能性并确保永远不会出现这种可能性。)
下列代码给出了对死锁逻辑的一个抽象描述:
全局数据结构
struct state
{
int resource[m];
int available[m];
int claim[n][m];
int alloc[n][m];
}
资源分配算法
if (alloc [i,*] + request [*] > claim [i,*])
< error >; /*总请求量大于需求*/
else if (request [*] > available [*])
< suspend process >; /*模拟分配*/
else
{
< define newstate by:
alloc [i,*] = alloc [i,*] + request [*];
available [*] = available [*] - request [*] >;
}
if (safe (newstate))
< carry out allocation >;
else
{
<restore original state >;
< suspend process >;
}
测试安全算法(银行家算法)
boolean safe (state S)
{
int currentavail[m];
process rest[<number of processes>];
currentavail = available;
rest = {all processes};
possible = true;
while (possible)
{
< find a process Pk in rest suck that
claim [k,*] - alloc [k,*] <= currentavail;>
if (found) /*模拟Pk的执行*/
{
currentavail = currentavail + alloc [k,*];
rest = rest - {Pk};
}
else
possible = false;
}
return (rest == null);
}
说明: 数据结构
state
定义了系统状态,request[*]
是一个向量,定义了进程 i 的资源请求。 首先,进行一次检测,确保该请求不会超过进程最初声明的要求。如果该请求有效,下一步确定是否可能实现这个请求(即有足够的可用资源)。如果不可能,则该进程被挂起;如果可能,则最后一步是确定完成这个请求是否是安全的。为做到这一点,资源被暂时分配给进程 i 以形成一个newstate。
死锁避免的优点是它不需要死锁预防中的抢占和回滚进程,并且比死锁预防的限制少。但是仍有以下限制:
死锁预防策略是非常保守的,它们通过限制访问资源和在进程上强加约束来解决死锁问题。
死锁检测策略则完全相反,它不限制资源访问或约束进程行为。对于死锁检测来说,只要有可能,被请求的资源就被授权给进程。操作系统周期性地执行一个算法检测“循环等待”条件(上文提到的死锁成因中的条件4)。
该算法使用了上文提到的Allocation矩阵
以及Available向量
,除此之外,还定义了请求(Requset)矩阵Q,其中Qij表示进程 i 请求的类型 j 的资源量。算法主要是一个标记没有死锁的进程的过程。最初,所有的进程都是未标记的,然后执行下列步骤:
下面来看一个例子:
算法的结果是P1、P2、P4未标记,表示这三个进程是死锁的。
一旦检测到死锁,就需要某种策略以恢复死锁。下面按复杂度递增的顺序列出可能的方法:
对于上述的第3、4条,选择原则可以采用下面中的一种:
我们先以表格的形式小结一下前文讲述的解决死锁的策略:
原则 | 资源分配策略 | 不同的方案 | 主要优点 | 主要缺点 |
---|---|---|---|---|
预防 | 保守的;预提交资源 | 一次性请求所有资源 | ·对执行一连串活动的进程非常有效·不需要抢占 | ·低效·延迟进程的初始化·必须知道将来的资源请求 |
预防 | 保守的;预提交资源 | 抢占 | ·用于状态易于保存和恢复的资源时非常方便 | ·过于经常地没必要地抢占 |
预防 | 保守的;预提交资源 | 资源排序 | ·通过编译时检测是可以实施的·既然问题已经在系统设计时解决了,不需要在运行时间计算 | ·禁止增加的资源请求 |
避免 | 处于检测和预防中间 | 操作以发现至少一条安全路径 | ·不需要抢占 | ·必须知道将来的资源请求·进程不能被长时间阻塞 |
检测 | 非常自由;只要可能,请求的资源都允许 | 周期性地调用以测试死锁 | ·不会延迟进程的初始化·易于在线处理 | ·固有的抢占被丢失 |
从上表中可见,所有的解决死锁的策略都各有其优缺点。与其将操作系统机制设计为只采用其中一种策略,还不如在不同情况下使用不同的策略更有效。为此提供了一种方法:
同样移步至下方链接👇👇👇👇
本篇已完结
(如有修改或补充欢迎评论)