第三章 死锁[1]名词解释1死锁是指在一个进程集合中的每个进程都在等待仅由该集合中的另一个进程才能引发的事件而无限期地僵持下去的局面。2饥饿在系统中,每个资源占有者都在有限时间内释放它所占有的资源,但资源中存在某些申请者由于某种原因却永远得不到资源的一种错误现象。3死锁防止要求进程申请资源时遵循某种协议,从而打破产生死锁的四个必要条件中的一个或几个,保证系统不会进入死锁状态。4死锁避免[2]对进程所发出的每一个申请资源命令加以动态地检查,并根据检查结果决定是否进行资源分配[3]。就是说,在资源分配过程中若预测有发生死锁的可能性,则加以避免。这种方法的关键是确定资源分配的安全性。5安全序列针对当前分配状态来说,系统至少能够按照某种次序为每个进程分配资源(直至最大需求),并且使他们依次成功地运行完毕,这种进程序列(p1,p2,…,pn)就是安全序列。简答题1计算机系统中产生死锁的根本原因是什么?死锁发生的四个基本条件是什么?答: 计算机系统中产生死锁的根本原因是:资源有限且操作不当 。死锁发生的四个基本条件有互斥条件、请求保持条件(占有且等待条件)、非剥夺条件(不可抢占条件)和环路条件(循环等待条件) 。2简述发生死锁的四个必要条件?答: 四个必要条件是:互斥条件、占有且等待条件(请求保持条件)、不可抢占条件(非剥夺条件)和循环等待条件(环路条件)。互斥条件——某个资源在一段时间内只能由一个进程占有,不能同时被两个及其以上的进程占有。占有且等待条件——进程至少已经占有一个资源,但又申请新的资源。不可抢占条件——一个进程所占有的资源再用完之前,其他进程不能强行夺走资源,只能由该进程用完之后主动释放。循环等待条件——存在一个进程等待序列(P1,P2,…,Pn),其中,P1等待P2所占有的某个资源,P2等待P3所占有的某个资源,……,而Pn等待P1所占有的某个资源,从而形成一个进程循环等待。3什么是死锁?解决死锁的方法一般有那几种?答: 死锁是指在一个进程集合中的每个进程都在等待仅由该集合中的另一个进程才能引发的事件而无限期地僵持下去的局面。解决死锁问题的一般方法为:死锁的预防、死锁的避免、死锁的检测和恢复。4死锁预防[4]的基本思想是什么?死锁避免的基本思想是什么?答:死锁预防的基本思想是:要求进程申请资源是遵循某种协议,从而打破产生思索的四个必要条件中的一个或几个,保证系统不会进入死锁状态.死锁避免的基本思想是:对进程所发出的每一个申请资源命令加以动态地检查,并根据检查结果决定是否进行资源分配.就是说,在资源分配过程中若预测有发生死锁的可能性,则加以避免.这种方法的关键是确定资源分配的安全性.5什么是死锁的安全序列?何谓系统是安全的?答:进程的安全序列(P,P,…,P)是这样组成的:若对于每个进程Pi(1<=I<=n),它需要的附加资源可以被系统中当前可用资源加上所有进程Pj(j<i)当前占有资源之和所满足,则( P,P,…,P )为一个安全序列。“系统是安全的”是指系统中的所有进程能够按照某种次序分配资源,并且依次运行完毕。即系统中的进程处于安全序列中。6资源按序分配法为什么能够预防死锁?证明:采用反证法来证明。若存在循环等待,设在环路上的一组进程为(P0,P1,P2,…,Pn),这里Pi等待进程Pi+1占有资源Ri(下角标取模运算,从而,Pn等待p0占有的资源)。由于Pi+1占有资源Ri,又申请资源Ri+1,从而一定存在F(i)<F(i+1), 该式对所有的i都成立。于是就有:F(R0)<F(R1)<…<F(Rn)<F(R0)由传递性得到:F(R0)<F(R0)显然,这是不可能的,因而,上述假设不成立,表明不会出现循环等待条件。7死锁和“饥饿”之间的主要差别是什么?答:死锁:多个并发进程[5]相互等待对方占用的资源而产生的错误现象。饿死:在系统中,由于系统采用的资源分配算法不当,虽然每个资源占有者都在有限时间内释放它所占的资源,但仍然使一些进程永远得不到资源的一种错误现象。综合题1设系统中有三种类型的资源(A,B,C)和五个进程(P1,P2,P3,P4,P5),A资源的数量为17,B资源的数量为5,C资源的数量为20。在T0时刻系统状态如表3-9所试。系统采用银行家算法来避免死锁。T0时刻是否为安全状态?若试,请给出安全序列。在T0时刻,若进程P2请求资源(0,3,4),能否实现资源分配?为什么?在的基础上,若进程P4请求资源(2,0,1),能否实现资源分配?为什么?在的基础上,若进程P1请求资源(0,2,0),能否实现资源分配?为什么?表3-9 T0时刻系统状态进程 最大资源需求量 已分配资源数量 系统剩余资源数量A B C A B C A B CP1 5 5 9 2 1 2 2 3 3P2 5 3 6 4 0 2P3 4 0 11 4 0 5P4 4 2 5 2 0 4P5 4 2 4 3 1 4
题目解答
答案
解:
T0时刻是安全状态,因为存在一个安全序列{P4,P5,P1,P2,P3} (2’)
不能实现资源分配,因为所剩余的资源数量不够。 (2’)
可以分配。当分配完成后,系统剩余的资源向量为(0,3,2),这时,仍可找到一个安全序列{P4,P5,P1,P2,P3} (3’)
不能分配。如果分配的话,则系统剩余的资源向量为(0,1,2),这时无法找到一个安全序列。(3’)
2在银行家算法中,系统有5个进程和3个资源。若出现以下资源分配情况:
进程 资源最大请求 已分配资源
p0 7, 5, 3 0, 1, 0
p1 3, 2, 2 2, 1, 0
p2 9, 0, 2 3, 0, 2
p3 2, 2, 2 2, 1, 1
p4 4, 3, 3 0, 0, 2
系统剩余资源数量为(3,2,2)。
1) 该状态是否安全(给出详细的检查过程)?
2) 如果进程依次有如下资源请求
p1:资源请求Request(1,0,2)?
p4:资源请求Request(3,3,0)?
p0:资源请求Request(0,1,0)?
则系统如何进行资源分配,才能避免死锁?
解:
1)该系统状态是否安全,主要看能否找到一个进程完成序列.若能找到,系统只要按照这个序列为进程分配资源,所有进程就都可顺利完成;若找不到,系统状态就是不安全的.为此,可先求出进程的剩余请求矩阵.
进程 资源最大需求 已分配资源 剩余资源请求
P0 7, 5, 3 0, 1, 0 7, 4, 3
P1 3, 2, 2 2, 1, 0 1, 1, 2
P2 9, 0, 2 3, 0, 2 6, 0, 0
P3 2, 2, 2 2, 1, 1 0, 1, 1
P4 4, 3, 3 0, 0, 2 4, 3, 1
系统剩余资源向量A=(3,2,2),在进程剩余资源请求矩阵中找,是否有一行,其值都小于或等于A.若有,选进程P1,满足它的全部资源请求,它在有限时间内能释放全部资源,并标记它为完成使系统剩余资源向量A=(5,3,2).之后再重复上述过程,从而找到了一个进城完成序列为:P1,P3,P4,P2,P0 (2’)。由此可见,系统状态是安全的(2’)。
操作系统总复习及相关习题