读书频道 > 系统 > 其他综合 > 新编操作系统习题与解析
3.3.1 要点归纳
2013-06-03 08:24:53     我来说两句 
收藏    我要投稿   

本文所属图书 > 新编操作系统习题与解析

本书按照操作系统教学大纲的要求,并参照全国联考大纲编写。全书共6章,主要内容包括:操作系统概述、处理器管理、进程同步、通信和死锁、存储器管理、文件管理及设备管理。每章按知识点分节,每节先总结核心概念...  立即去当当网订购
3.3  知识点3:进程死锁

3.3.1  要点归纳

1.死锁的概念

死锁是指多个进程因竞争系统资源或相互通信而处于永久阻塞状态,若无外力作用,这些进程都将无法向前推进。例如,某计算机系统中只有一台打印机和一台输入设备,进程P1正占用输入设备,同时又提出使用打印机的请求,但此时打印机正被进程P2所占用,而P2在未释放打印机之前,又提出请求使用正被P1占用着的输入设备。这样两个进程相互无休止地等待下去,均无法继续执行,此时两个进程陷入死锁状态。
归纳起来,产生死锁的两个原因如下:
l       系统资源不足。这是根本原因,设计操作系统的目的就是使并发进程共享系统资源。
l       进程推进顺序不当。当多个并发进程在运行中提出对多个不可抢占资源的请求时,若申请和释放资源的顺序恰当,则不会产生死锁;若申请和释放资源的顺序不当,则会产生死锁。
“饥饿”和死锁的主要区别是:“饥饿”并不表示系统一定死锁,进入“饥饿”的进程可能只有一个,而由于循环等待条件而进入死锁的进程却必须大于或等于两个;处于“饥饿”的进程可以是一个就绪进程,而处于死锁的进程则必定是阻塞进程。
2. 死锁的处理策略
目前,用于处理死锁的方法主要有以下几种:
l       忽略死锁。这种处理方式又称鸵鸟算法,是指像鸵鸟一样对死锁视而不见。不同的人对死锁现象有不同的反应。例如,数学家认为死锁现象完全不能容忍,应不惜代价地防止死锁的发生。而工程师则会问估计多长时间才会出现一次死锁,其他原因的系统故障又是多长时间出现一次,如果死锁平均每5年出现一次,而其他系统故障每月出现一次,那么大多数工程师就不愿意以高昂的代价来消除死锁。对用户来说,他们宁愿仍然出现一次死锁,也不愿有许多条条框框捆住他们的手脚。
l       预防死锁。通过设置某些限制条件,去破坏产生死锁的4个必要条件中的一个或几个来防止发生死锁。
l       避免死锁。在资源的动态分配过程中,用某种方法防止系统进入不安全的状态,从而避免死锁。
l       检测及解除死锁。通过系统的检测机构及时地检测出死锁,然后采取某种措施解除死锁。
3. 死锁的预防
要想防止死锁的发生,只须破坏产生死锁的4个必要条件之一即可。下面具体分析与这4个条件相关的技术。
(1)互斥条件
为了破坏互斥条件,就要允许多个进程同时访问资源。但是这会受到资源本身固有特性的限制,有些资源根本不能同时访问,只能互斥访问,如打印机就不允许多个进程在其运行期间交替打印数据,打印机只能互斥使用。由此看来,企图通过破坏互斥条件防止死锁的发生是不大可能的。
(2)不剥夺条件
为了破坏不剥夺条件,可以制定这样的策略:一个已获得了某些资源的进程,若新的资源请求不能立即得到满足,则它必须释放所有已获得的资源,以后需要资源时再重新申请。这意味着,一个进程已获得的资源在运行过程中可以被剥夺,从而破坏了不剥夺条件。
该策略实现起来比较复杂,释放已获得的资源可能造成前一段工作的失效,重复申请和释放资源会增加系统开销,降低系统吞吐量。这种方法常用于状态易于保存和恢复的资源,如CPU的寄存器及内存资源,一般不能用于打印机之类的资源。
(3)请求和保持条件
为了破坏请求和保持条件,可以采用静态资源分配法。静态资源分配法要求进程在其运行之前一次申请它所需要的全部资源,在它的资源未满足前,不把它投入运行。一旦投入运行后,这些资源就一直归它所有,也不再提出其他资源要求,这样就可以保证系统不会发生死锁。
这种方法既简单又安全,但降低了资源利用率。采用这种方法必须事先知道作业(或进程)需要的全部资源,即使有的资源只在运行后期使用,甚至有的资源在正常运行中根本不用,也不得不预先统一申请,结果使得系统资源不能充分利用。以打印机为例,一个作业可能只在最后完成时才需要打印计算结果,但在作业运行前就把打印机分配给了它,那么在作业整个执行过程中打印机基本处于闲置状态。
(4)循环等待条件
为了破坏循环等待条件,可以采用有序资源分配法。有序资源分配法的实现思想是将系统中的所有资源都按类型赋予一个编号(如打印机为1,磁带机为2等),要求每一个进程均严格按照编号递增的次序来申请资源,同类资源一次申请完。也就是说,只要进程提出申请分配资源Ri,则该进程在以后的资源申请中,只能申请资源编号排在Ri后面的那些资源(i为资源编号),不能再申请资源编号低于Ri的资源。对资源申请作了这样的限制后,系统中不会再出现几个进程对资源的请求形成环路的情况。
这种方法存在的主要问题是各种资源编号后不宜修改,从而限制了新设备的增加;尽管在为资源编号时已考虑到大多数作业实际使用这些资源的顺序,但也经常会发生作业使用资源的顺序与系统规定顺序不同的情况,造成资源的浪费。
4. 死锁的避免
预防死锁的方法中所采取的几种策略,总的说来都对资源的使用施加了较强的限制条件,虽然实现起来较为简单,但却严重地损害了系统性能。在死锁的避免方法中,不对进程申请资源施加限制条件,而是检查进程的资源申请是否会导致系统进入不安全状态,只要能使系统始终处于安全状态,便可以避免死锁的发生。由于该方法对进程使用资源所施加的限制条件较弱,从而可能获得较好的系统性能。
(1)系统安全状态
在避免死锁的方法中,允许进程动态地申请资源,系统在进行资源分配之前,先计算资源分配的安全性。若此次分配不会导致系统进入不安全状态,便将资源分配给进程,否则进程等待。
如果在某一时刻,系统能按某种顺序如<P1,P2,…,Pn>来为每个进程分配其所需要的资源,直至最大需求,使每个进程都可以顺利运行完成,则称此时的系统状态为安全状态,称序列<P1,P2,…,Pn>为安全序列。若某一时刻系统中不存在一个安全序列,则称此时的系统状态为不安全状态。
虽然并非所有的不安全状态都是死锁状态,但当系统进入不安全状态后,便可能进入死锁状态;反之,只要系统处于安全状态,便可以避免进入死锁状态。
(2)银行家算法
具有代表性的死锁避免算法是Dijkstra给出的银行家算法,其主要思想是避免系统进入不安全状态,在每次进行资源分配时,首先检查系统是否有足够的资源满足要求,如果有则先进行分配,并对分配后的新状态进行安全性检查,如果新状态安全,则正式分配上述资源,否则就拒绝上述资源,这样它保证系统始终处于安全状态,从而避免死锁现象的发生。为实现银行家算法,系统中必须设置若干数据结构。假定系统中有n个进程(P1,P2,…,Pn),m类资源(R1,R2,…,Rm),银行家算法中使用的数据结构如下:
l       可利用资源向量Available。这是一个含有m个元素的数组,其中的每一个元素代表一类资源的空闲资源个数,其初始值是系统中所配置的该类资源的个数,其数值随该类资源的分配和回收而动态地改变。如果Available(j)=k,表示系统中现有空闲的Rj类资源k个。
l       最大需求矩阵Max。这是一个n×m的矩阵,它定义了系统中每一个进程对各类资源的最大需求个数。如果Max(i,j)=k,表示进程Pi需要Rj类资源的最大个数为k。
l       分配矩阵Allocation。这是一个n×m的矩阵,它定义了系统中当前已分配给每一个进程的各类资源个数。如果Allocation(i,j)=k,表示进程Pi当前已分到Rj类资源的个数为k。Allocationi表示进程Pi的分配向量,由矩阵Allocation的第i行构成。
l       需求矩阵Need。这是一个n×m的矩阵,它定义了系统中每一个进程还需要的各类资源个数。如果Need(i,j)=k,表示进程Pi还需要Rj类资源k个,才能完成其任务。Needi表示进程Pi的需求向量,由矩阵Need的第i行构成。
上述3个矩阵间存在关系:
Need(i,j)=Max(i,j)-Allocation(i,j)
银行家算法的实现思想如下:设Requesti是进程Pi的请求向量,Requesti(j)=k表示进程Pi请求分配Rj类资源k个。当Pi发出资源请求后,系统按下述步骤进行检查:
* 如果Requesti≤Needi,则转向②;否则出错,因为进程所需要的资源个数已超过它所宣布的最大值。
* 如果Requesti≤Available,则转向③;否则,表示系统中尚无足够的资源满足进程Pi的申请,Pi必须等待。
Adobe Systems 系统试着把申请的资源分配给进程Pi,并修改下面数据结构中的数值:
Available = Available-Requesti;
Allocationi = Allocationi + Requesti;
Needi = Needi-Requesti;
Adobe Systems 系统执行安全性算法,检查此次资源分配后系统是否处于安全状态。若安全,才正式将资源分配给进程Pi,以完成本次分配;否则,将试分配作废,恢复原来的资源分配状态,让进程Pi等待。
系统所执行的安全性算法描述如下:
* 设置如下两个向量。
l       Work:表示系统可提供给进程继续运行的各类资源的空闲资源个数,它含有m个元素,执行安全性算法开始时,Work=Available。
l       Finish:表示系统是否有足够的资源分配给进程,使之运行完成。开始时,Finish(i)=false;当有足够资源分配给进程Pi时,令Finish(i)=true。
* 从进程集合中找到一个能满足下述条件的进程:
Finish(i) == false;
Needi≤Work;
如找到则执行③;否则执行④。
Adobe Systems 当进程Pi获得资源后,可顺利执行直到完成,并释放出分配给它的资源,故应执行:
Work=Work + Allocationi ;
Finish(i)=true;
然后转向②。
Adobe Systems 若所有进程的Finish(i)都为true,则表示系统处于安全状态;否则,系统处于不安全状态。
【例3.2】 假定系统中有4个进程P1、P2、P3、P4,3种类型的资源R1、R2、R3,数量分别为9、3、6,在T0时刻的资源分配情况如表3.2所示。试问:
(1)T0时刻是否安全?
(2)T0时刻以后,若进程P2发出资源请求Request2(1,0,1),系统能否将资源分配给它?
(3)在进程P2申请资源后,若P1发出资源请求Request1(1,0,1),系统能否将资源分配给它?
(4)在进程P1申请资源后,若P3发出资源请求Request3(0,0,1),系统能否将资源分配给它?

表3.2  T0时刻的资源分配表
进程 Max Allocation Need Available
R1 R2 R3 R1 R2 R3 R1 R2 R3 R1 R2 R3
P1
P2
P3
P4
3
6
3
4
2
1
1
2
2
3
4
2
1
5
2
0
0
1
1
0
0
1
1
2
2
1
1
4
2
0
0
2
2
2
3
0
1 1 2
 
解:(1)T0时刻的安全性:利用安全性算法对T0时刻的资源分配情况进行分析,可得表3.3所示的T0时刻的安全性分析,从中得知,T0时刻存在着一个安全序列{P2,P1,P3,P4},故系统是安全的。
表3.3  T0时刻的安全性检查
进程 Work Need Allocation Work+Allocation Finish
R1 R2 R3 R1 R2 R3 R1 R2 R3 R1 R2 R3
P2
P1
P3
P4
1
6
7
9
1
2
2
3
2
3
3
4
1
2
1
4
0
2
0
2
2
2
3
0
5
1
2
0
1
0
1
0
1
0
1
2
6
7
9
9
2
2
3
3
3
3
4
6
true
true
true
true
 
(2)P2请求资源:P2发出请求向量Request2(1,0,1),系统按银行家算法进行检查,并执行如下操作。
l       Request2(1,0,1)≤Need2(1,0,2)
l       Request2(1,0,1)≤Available(1,1,2)
系统先假定可为P2分配资源,并修改Available、Allocation2、Need2向量,由此形成的资源变化情况如表3.4所示。
表3.4  P2申请资源后的资源分配表
进程 Max Allocation Need Available
R1 R2 R3 R1 R2 R3 R1 R2 R3 R1 R2 R3
P1
P2
P3
P4
3
6
3
4
2
1
1
2
2
3
4
2
1
6
2
0
0
1
1
0
0
2
1
2
2
0
1
4
2
0
0
2
2
1
3
0
0 1 1
 
再利用安全性算法检查此时系统是否安全,可得如表3.5所示的安全性分析。
表3.5  P2申请资源后的安全性检查
进程 Work Need Allocation Work+Allocation Finish
R1 R2 R3 R1 R2 R3 R1 R2 R3 R1 R2 R3
P2
P1
P3
P4
0
6
7
9
1
2
2
3
1
3
3
4
0
2
1
4
0
2
0
2
1
2
3
0
6
1
2
0
1
0
1
0
2
0
1
2
6
7
9
9
2
2
3
3
3
3
4
6
true
true
true
true
 
由所进行的安全性检查得知,可以找到一个安全序列{P2,P1,P3,P4},因此,系统是安全的,可以立即将P2所申请的资源分配给它。
(3)P1请求资源:P1发出请求向量Request1(1,0,1),系统按银行家算法进行检查:
l       Request1(1,0,1)≤Need1(2,2,2)
l       Request1(1,0,1)>Available(0,1,1),让P1等待。
(4)P3请求资源:P3发出请求向量Request3(0,0,1),系统按银行家算法进行检查:
l       Request3(0,0,1)≤Need3(1,0,3)
l       Request3(0,0,1)≤Available(0,1,1)
系统先假定可为P3分配资源,并修改有关数据,如表3.6所示。
再利用安全性算法检查此时系统是否安全。从表3.6中可以看出,可用资源Available(0,1,0)已不能满足任何进程的需要,故系统进入不安全状态,此时系统不能分配资源。
表3.6  P3申请资源后的资源分配表
进程 Max Allocation Need Available
R1 R2 R3 R1 R2 R3 R1 R2 R3 R1 R2 R3  
P1
P2
P3
P4
3
6
3
4
2
1
1
2
2
3
4
2
1
6
2
0
0
1
1
0
0
2
2
2
2
0
1
4
2
0
0
2
2
1
2
0
0 1 0  
 
5. 死锁检测和解除
前面介绍的死锁预防和死锁避免算法,都是在系统为进程分配资源时施加限制条件或进行检测,若系统为进程分配资源时不采取任何措施,则应该提供死锁检测和死锁解除的方法。
(1)资源分配图
检测死锁的基本思想是在操作系统中保存资源的请求和分配信息,利用某种算法对这些信息加以检查,以判断是否存在死锁。为此,将进程和资源间的申请和分配关系描述成一个有向图,即资源分配图。
资源分配图又称进程资源图,该图由一组节点N和一组边E所构成,具有下述形式的定义和限制:
l       N被分成两个互斥的子集,一个是进程节点子集P={p1,p2,…,pn},另一个是资源节点子集R={r1,r2,…,rm},N=P∪R。在如图3.35所示的例子中,P={p1,p2},R={r1,r2},N={p1,p2}∪{r1,r2}。
l       凡属于E中的一条边e∈E,都连接着P中的一个节点pi和R中的一个节点rj,e={pi,rj}是资源请求边,由进程节点pi指向资源节点rj,它表示进程pi请求一个单位的rj资源。e={rj,pi}是资源分配边,由资源节点rj指向进程节点pi,它表示把一个单位的rj资源分配给进程pi。在图3.35中,有两条资源请求边和4条资源分配边。
通常,用圆圈代表一个进程,用方框代表一类资源。由于一种类型的资源可能有多个,用方框中的一个小圆圈代表一类资源中的一个资源。此时,资源请求边由进程指向方框中的一个资源,分配边始于方框中的一个资源。

图3.35  资源分配图
(2)死锁的定理
可以使用将资源分配图简化的方法,来检测系统状态S是否是死锁状态。简化方法如下:
* 在资源分配图中,找出一个既不阻塞又非孤立的进程节点pi(即从进程集合中找到一个有边与它相连,且资源申请数量小于系统中已有空闲资源数量的进程)。因进程pi获得了它所需要的全部资源,它能继续运行直至完成,然后释放它所占有的所有资源。这相当于消去pi的所有请求边和分配边,使之成为孤立的节点。在图3.35中,进程p1是一个既不阻塞又非孤立的进程节点,将p1的两条分配边和一条请求边消去,便形成了如图3.36(a)所示的情况。
* 进程pi释放资源后,可以唤醒因等待这些资源而阻塞的进程,原来阻塞的进程可能变为非阻塞进程。图3.35中的进程p2原为阻塞进程,但在图3.36(a)中变成了非阻塞进程。根据①中的化简办法,消去两条分配边和一条请求边,就形成了如图3.36(b)所示的情况。
Adobe Systems 重复上述过程对资源分配图进行化简,直到找不出一个既不阻塞又非孤立的进程节点为止。若能消去图中所有的边,使所有进程节点都成为孤立节点,则称该图是可完全化简的,否则称该图是不可完全化简的。

图3.36  资源分配图的化简
可以证明所有的化简顺序将得到相同的不可化简图。S为死锁状态的条件是:S状态的资源分配图不可完全化简,该定理称为死锁定理。
(3)死锁的检测算法
死锁检测的思想是考查某一时刻的系统状态是否合理,即是否存在一组可以实现的系统状态,能使所有进程都得到它们所申请的资源而运行结束,其实现算法的思想如下:获得某时刻t系统中各类可利用资源的个数w(t),对于系统中的一组进程{P1,P2,…,Pn},找出那些对各类资源请求个数均小于系统现有的各类可利用资源个数的进程,这样的进程可以获得它们所需要的全部资源并运行结束,当它们运行结束后将释放所占有的全部资源,从而使可用资源个数增加,将这样的进程加入到可运行结束的进程序列L中(检测开始时,L为空),然后对剩下的进程再作上述考查。如果一组进程{P1,P2,…,Pn}中有几个进程不属于序列L中,那么它们将陷入死锁状态。
从死锁检测算法的实现思想中可以看出,死锁检测算法比较复杂,因而需要确定何时进行死锁检测。一种实现方法是每次分配资源后进行死锁检测,这样能尽早发现死锁,但会花费大量的CPU时间。另一种方法是定期检查,如每隔一段时间检查一次,或者当CPU使用率下降到某个下限值时进行检查。
(4)死锁的解除
一旦检测出系统中出现了死锁,就应将陷入死锁的进程从死锁状态中解脱出来,常用的解除死锁方法有如下两种:
l       资源剥夺法:当发现死锁后,从其他进程那里剥夺足够数量的资源给死锁进程,以解除死锁状态。
l       撤销进程法:最简单的方法是撤销全部死锁进程,使系统恢复到正常状态,但这种做法付出的代价太大。另一方法是按照某种顺序逐个撤销死锁进程,直到有足够的资源供其他未被撤销的进程使用,消除死锁状态为止。
点击复制链接 与好友分享!回本站首页
分享到: 更多
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力  
上一篇:3.2.2 例题解析
下一篇:3.3.2 例题解析
相关文章
图文推荐
2.7.12 使用仿真器查
2.7.11 栈和寄存器组
2.7.8 出栈
2.7.7 压栈
排行
热门
文章
下载
读书

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训
版权所有: 红黑联盟--致力于做最好的IT技术学习网站