读书频道 > 系统 > 其他综合 > 新编操作系统习题与解析
3.3.2 例题解析
2013-06-03 08:34:50     我来说两句 
收藏    我要投稿   

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

本书按照操作系统教学大纲的要求,并参照全国联考大纲编写。全书共6章,主要内容包括:操作系统概述、处理器管理、进程同步、通信和死锁、存储器管理、文件管理及设备管理。每章按知识点分节,每节先总结核心概念...  立即去当当网订购
1. 单项选择题
【例3-3-1】在操作系统中,死锁出现是指      。
A. 计算机系统发生重大故障
B. 资源个数远远小于进程数
C. 若干进程因竞争资源而无限等待其他进程释放已占有的资源
D. 进程同时申请的资源数超过资源总数
解:死锁是指多个进程因竞争系统资源或相互通信而处于永久阻塞状态,若无外力作用,这些进程都将无法向前推进。本题答案为C。
【例3-3-2】在      的情况下,系统出现死锁。
A. 计算机系统发生了重大故障
B. 有多个封锁的进程同时存在
C. 若干进程因竞争资源而无休止地相互等待他方释放已占有的资源
D. 资源数远远小于进程数或进程同时申请的资源数远远超过资源总数
解:解释同上例。本题答案为C。
【例3-3-3】当出现      情况下,系统可能出现死锁。
A. 进程释放资源                                                                       B. 一个进程进入死循环
C. 多个进程竞争资源出现了循环等待       D. 多个进程竞争共享型设备
解:循环等待是出现死锁的条件之一。本题答案为C。
【例3-3-4】为多道程序提供的可共享资源不足时可能出现死锁。但是在进程之间不适当的      也可能产生死锁。
A. 进程优先权                                          B. 资源的线性分配
C. 进程推进顺序                                                                       D. 分配队列优先权
解:产生死锁的原因是系统资源不足及进程推进顺序不正确。本题答案为C。
【例3-3-5】采用资源剥夺法可以解除死锁,还可以采用      方法解除死锁。
A. 执行并行操作                                                                       B. 撤销进程
C. 拒绝分配新资源                                   D. 修改信号量
解:解除死锁有资源剥夺法和撤销进程法,本题答案为B。
【例3-3-6】若系统在分配资源时不加以特别的限制,则可采用死锁检测的方法来解决死锁问题。所以该系统      。
A. 提高了资源利用率                               B. 不会发生死锁
C. 有时要抢夺某进程的资源进行再分配   D. 能加快进程的执行速度
解:其中破坏死锁的条件之一只有选项C。本题答案为C。
【例3-3-7】死锁产生的原因之一是      。
A. 系统中没有采用SPOOLing技术          B. 使用的P、V操作过多
C. 有共享资源存在                                   D. 资源分配不当
解:资源分配不当是死锁产生的原因之一。本题答案为D。
【例3-3-8】产生死锁的4个必要条件是:互斥、      、循环等待和不剥夺。
A. 请求与阻塞    B. 请求与保持               C. 请求与释放           D. 释放与阻塞
解:产生死锁的4个必要条件是互斥、请求与保持、不剥夺和循环等待。本题答案为B。
【例3-3-9】一个进程在获得资源后,只能在使用完资源后由自己释放,这属于死锁必要条件的      。
A. 互斥条件       B. 请求和释放条件        C. 不剥夺条件           D. 循环等待条件
解:C。
【例3-3-10】死锁的预防是根据      而采取措施实现的。
A. 配置足够的系统资源                           B. 使进程的推进顺序合理
C. 破坏死锁的4个必要条件之一              D. 防止系统进入不安全状态
解:C。
【例3-3-11】资源的有序分配策略可以破坏死锁的      条件。
A. 互斥              B. 请求和保持               C. 不剥夺                  D. 循环等待
解:有序资源分配法的实现思想是将系统中的所有资源都按类型赋予一个编号(如打印机为1,磁带机为2等),要求每一个进程均严格按照编号递增的次序来申请资源,同类资源一次申请完。这样不会造成循环等待。本题答案为D。
【例3-3-12】发生死锁的必要条件有4个,要防止死锁的发生,可以通过破坏这4个必要条件之一来实现,但破坏      条件是不太实际的。
A. 互斥              B. 不可抢占                   C. 部分分配              D. 循环等待
解:互斥条件是设备本身固有的特性,有些设备只能互斥访问。本题答案为A。
【例3-3-13】某系统中有11台打印机,N个进程共享打印机资源,每个进程要求3台。当N的取值不超过      时,系统不会发生死锁。
A. 4                    B. 5                                C. 6                           D. 7
解:当每个进程都获得了2台打印机且系统中剩余打印机不少于1台时,系统不会发生死锁,即11-2N≥1,由此知N≤5。本题答案为B。
【例3-3-14】银行家算法在解决死锁问题中是用于      的。
A. 预防死锁       B. 避免死锁                   C. 检测死锁              D. 解除死锁
解:银行家算法用于避免死锁。本题答案为B。
【例3-3-15】某系统中有3个并发进程,都需要同类资源4个,试问该系统不会发生死锁的最少资源数是      。
A. 9                    B. 10                              C. 11                          D. 12

解:因系统中存在3个进程,且都需要同类资源4个,当系统中资源数等于10时,无论怎样分配资源,其中至少有一个进程可以获得4个资源,该进程可以顺利运行完毕,从而可以将分配给它的资源归还给系统,其他进程也能顺利执行完成。若系统中资源数小于10,不妨设系统中有9个资源且每个进程都已获得3个资源,此时系统中已无空闲资源,当其中的任何一个进程再次申请资源时将进入等待状态,其他进程的情况类似,此时出现死锁。本题答案为B。
【例3-3-16】在下列解决死锁的方法中,属于死锁预防策略的是      。
A. 银行家算法                                          B. 有序资源分配法
C. 死锁检测法                                          D. 资源分配图化简法
解:有序资源分配法是死锁预防策略。本题答案为B。
【例3-3-17】死锁定理是用于处理死锁的      方法。
A. 预防死锁      B. 避免死锁                   C. 检测死锁              D. 解除死锁
解:死锁定理是用于检测死锁的方法。本题答案为C。
【例3-3-18】以下关于预防死锁的论述中正确的是      。
A. 由于产生死锁的基本原因是系统资源不足,因而预防死锁的有效方法是根据系统规模配置足够的系统资源
B. 由于产生死锁的另一种基本原因是进程推进顺序不当,因而预防死锁的有效方法是使进程的推进顺序合法
C. 因为只要系统不进入不安全状态,便不会产生死锁,故预防死锁的有效方法是防止系统进入不安全状态
D. 可以通过破坏产生死锁的4个必要条件之一或其中几个的方法来预防发生死锁
解:D。

2. 填空题

【例3-3-19】计算机系统产生死锁的根本原因是      和      。
解:本题答案为:①资源有限  ②操作不当。
【例3-3-20】目前抢占式的分配策略只适合于      和      。
解:本题答案为:①主存空间 ②CPU。
【例3-3-21】两个进程争夺同一个资源时,      产生死锁。
解:两个进程争夺同一个资源时,不一定产生死锁,这与它们申请资源的顺序有关。本题答案为:不一定。
【例3-3-22】产生死锁的4个必要条件是      、      、      和      。
解:本题答案为:①互斥条件 ②不可剥夺条件 ③请求与保持条件 ④循环等待条件。
【例3-3-23】解决死锁的方法分为      、      、      和      。
解:本题答案为:①死锁的预防 ②死锁的避免 ③死锁的检测 ④死锁的解除。
【例3-3-24】避免死锁的实质是      。
解:本题答案为:如何使系统不进入不安全状态。
【例3-3-25】只要能保持系统处于安全状态就可      的发生。
解:本题答案为:避免死锁。
【例3-3-26】当若干进程需求资源的总数大于系统能提供的资源数时,进程间就会出现竞争资源的现象,如果对进程竞争的资源      就会引起死锁。
解:本题答案为:管理或分配不当。
【例3-3-27】如果资源分配图中有环路,且每个资源类中只有一个资源,则环路中的进程都      。
解:本题答案为:处于死锁状态。
【例3-3-28】如果操作系统能保证所有的进程在有限时间内得到需要的全部资源,则称系统处于      。
解:本题答案为:安全状态。
【例3-3-29】设系统有N(N>2)个进程,则系统中最不可能的是有      个进程处于死锁状态。
解:在系统中两个或多个进程无限期地等待永远不会发生的条件,称此系统处于死锁状态,不可能只有一个进程处于死锁状态。本题答案为:1。
【例3-3-30】可以证明,m个同类资源被n个进程共享时,只要不等式      成立,则系统一定不会出现死锁,其中x为每个进程申请该类资源的最大数。
解:本题答案为:n(x-1)+1≤m。
【例3-3-31】操作系统中要兼顾资源的使用效率和安全可靠,对不同的资源采用不同的分配策略,往往采用死锁的   ①   、避免和   ②   的混合策略。
解:本题答案为:①防止 ②检测。
【例3-3-32】解除死锁的方法有两种,一种是   ①   一个或几个进程的执行以破坏循环等待,另一种是从涉及死锁的进程中   ②  
解:本题答案为:①终止 ②抢夺资源。
【例3-3-33】如果资源分配图中无环路,则系统中      发生。
解:本题答案为:没有死锁。

3. 判断题

【例3-3-34】判断以下叙述的正确性。
(1)当进程数大于资源数时,进程竞争资源必然产生死锁。
(2)死锁预防是排除死锁的静态策略。
(3)产生死锁后,系统未必处于不安全状态。
(4)系统处于不安全状态不一定是死锁状态。
(5)系统存在安全序列时,一定不会有死锁发生。
(6)系统进入不安全状态时,必定会产生死锁。
(7)导致死锁的4个必要条件在死锁时会同时发生。
(8)若想预防死锁,4个必要条件必须同时具备。
(9)银行家算法是防止死锁发生的方法之一。
(10)一旦出现死锁,所有进程都不能运行。
(11)所有进程都阻塞时系统一定陷入死锁。
(12)有m个进程的操作系统出现死锁时,死锁进程的个数为1<k≤m。
(13)参与死锁的进程至少有两个已经占有资源。
(14)如果资源分配图中存在环路,则系统一定存在死锁。
解:(1)错误。当进程数大于资源数时,进程竞争资源不一定产生死锁。
(2)正确。
(3)错误。产生死锁后,系统必然处于不安全状态。
(4)正确。
(5)正确。
(6)错误。系统进入不安全状态时,不一定产生死锁。
(7)正确。
(8)错误。若想预防死锁,只须破坏4个必要条件之一即可。
(9)错误。银行家算法是避免死锁的方法之一。
(10)错误。部分进程出现死锁,其他进程仍可运行。
(11)错误。所有进程都阻塞时,系统不一定陷入死锁,可能是由于所有进程等待某一I/O事件引起的。
(12)正确。
(13)正确。
(14)错误。资源分配图中存在环路,整个系统不一定存在死锁

4. 问答题

【例3-3-35】什么是死锁,产生死锁的原因是什么?
解:所谓死锁是指多个进程因竞争系统资源或相互通信而处于永久阻塞状态,若无外力作用,这些进程都将无法向前推进。
产生死锁的原因:一是由于多进程共享的资源不足而引起竞争资源;二是由于进程在运行过程中具有异步性特征,进程推进顺序非法。
【例3-3-36】产生死锁的必要条件是什么?解决死锁问题常采用哪几种措施?
解:产生死锁的必要条件如下:
l       互斥条件。指在一段时间内某资源仅为一个进程所占有。
l       不剥夺条件。指进程所获得的资源在未使用完毕之前,不能被其他进程强行夺走,而只能由该进程自己释放。
l       请求和保持条件。指进程每次申请它所需要的一部分资源,在等待分配新资源的同时,进程继续占有已分配到的资源。
l       循环等待条件。指存在一种进程资源的循环等待链,链中每一个进程已获得的资源同时被链中下一个进程所请求。
解决死锁问题常采用的措施有:
l       死锁的预防。通过破坏死锁产生的必要条件中的后三条之一来预防死锁的发生。
l       死锁的避免。在资源动态分配过程中,用某种方法防止系统进入不安全状态,从而避免死锁。
l       死锁的检测及解除。通过系统的检测机构及时地检测出死锁的发生,然后采取某种措施解除死锁。
【例3-3-37】在某一时刻,系统中是否可能出现既无运行态进程又无就绪态进程?若可能,在什么情况下会产生?
解:有可能。例如在系统死锁的状态下,进程处于占有等待资源的状态,应当既不属于运行态,也不属于就绪态;或者在进程都处于阻塞状态等待I/O完成时,这些进程既不属于运行态,也不属于就绪态。
【例3-3-38】进程死锁与“饥饿”之间有何相同点和不同点?
解:进程“饥饿”与死锁有一定联系:两者都是由于竞争资源而引起的,但又有明显差别,主要表现在如下几个方面:
l       从进程状态考虑,死锁进程都处于等待状态,忙而等待(处于运行或就绪状态)的进程并非处于等待状态,但却可能被“饿死”。
l       死锁进程等待永远不会被释放的资源,“饥饿”进程等待会被释放但却不会分配给自己的资源,表现为等待时限没有上限(排队等待或忙而等待)。
l       死锁一定发生了循环等待,而“饥饿”则不然。这也表明通过资源分配图可以检测死锁存在与否,但却不能检测是否有进程“饿死”。
l       死锁一定涉及多个进程,而“饥饿”或被“饿死”的进程可能只有一个。
进程“饥饿”和“饿死”与资源分配策略有关,因而防止“饥饿”与“饿死”可从公平性考虑,确保所有进程不被忽视,如FCFS分配算法。
【例3-3-39】简述防止死锁的分配策略中各自存在哪些缺点。
解:在防止死锁的分配策略中,有的只适用于某些资源的分配,有的则会影响资源的使用效率。例如,抢占式分配目前只适合于对CPU和主存资源的分配;静态分配策略把资源预先分配给进程,而这些进程占用了资源但可能在一段时间内并不使用它,这时其他想使用这些资源的进程又因得不到而等待,降低了资源的利用率;采用按序分配时各进程要求使用资源的次序往往不能与系统安排的次序一致,但申请资源时必须按编号的次序来申请,可能出现先申请到的资源很长一段时间闲置不用,也降低了资源的利用率。
【例3-3-40】为什么说不能通过破坏“互斥条件”来预防死锁。
解:破坏互斥条件,即允许多个进程同时访问资源。但这受到资源本身的使用方法所决定,有些资源必须互斥访问,不能同时访问,如几个进程同时使用打印机,而打印机的使用必须是互斥的。所以企图通过破坏互斥条件来防止死锁是不太实际的。
【例3-3-41】下面关于死锁问题的叙述哪些是正确的,哪些是错误的?说明原因。
(1)参与死锁的所有进程都占有资源。
(2)参与死锁的所有进程中至少有两个进程占有资源。
(3)死锁只发生在无关进程之间。
(4)死锁可发生在任意进程之间。
解:(1)是错误的,应该是参与死锁的所有进程都等待资源。如图3.37所示,参与的进程有P1、P2、P3和P4,尽管P3、P4不占有资源,但也陷入死锁。
(2)是正确的。参与死锁的进程至少有两个,设为P1和P2,典型的死锁情况是P1占有资源R1而等待资源R2,P2占有资源R2而等待资源R1
(3)是错误的。死锁也可能发生在相关进程之间,如死锁的两个进程P1和P2也可能是相关进程(如同步或互斥)。
(4)是正确的。死锁既可能发生在相关进程之间,也可能发生在无关进程之间,即死锁可发生在任意进程之间。

图3.37  一个资源分配图
【例3-3-42】设系统中仅有一类数量为M的独占型资源,系统中N个进程竞争该类资源,其中各进程对该类资源的最大需求量为W,当M、N、W分别取下列值时,试判断哪些情况会发生死锁,为什么?
(1)M=2,N=2,W=1
(2)M=3,N=2,W=2
(3)M=3,N=2,W=3
(4)M=5,N=3,W=2
(5)M=6,N=3,W=3
解:在资源分配系统中,死锁发生的原因是由于多个进程共享有限的独占型资源。当多个进程占有了部分资源又需要更多的资源时,就可能形成循环等待链而导致死锁。
假设系统中的某种资源的个数为M,共享该资源的进程数为N,每个进程对该资源的最大需求量为W。最极端的资源分配情况是:每个进程都已经占有了W-1个资源,同时都需要再分配一个资源,这时如果要保证不发生死锁,系统中必须至少还有一个可分配的资源,即M满足关系式:M≥N(W-1)+1。
因此保证系统不会发生死锁的最小M值为:M=N(W-1)+1。
(1)N(W-1)+1=2×0+1=1,而M=3,即M≥N(W-1)+1成立,故不会出现死锁。
(2)N(W-1)+1=2×1+1=3,而M=3,即M≥N(W-1)+1成立,故不会出现死锁。
(3)N(W-1)+1=2×2+1=5,而M=3,即M≥N(W-1)+1不成立,故可能出现死锁。出现死锁的情况是:两个进程一个占用2个资源,一个占用1个资源,同时都需要再分配资源。
(4)N(W-1)+1=3×1+1=4,而M=5,即M≥N(W-1)+1成立,故不会出现死锁。
(5)N(W-1)+1=3×2+1=7,而M=6,即M≥N(W-1)+1不成立,故可能出现死锁。出现死锁的情况是:3个进程都已经占有了2个资源,同时都需要再分配一个资源。
【例3-3-43】一台计算机有8台磁带机。它们由N个进程竞争使用,每个进程可能需要3台磁带机。请问N为多少时,系统没有死锁危险,并说明原因。
解:当N为1、2、3时,系统没有产生死锁的危险。因为,当系统中只有1个进程时,它最多需要3台磁带机,而系统有8台磁带机,其资源个数已足够系统内的1个进程使用,因此绝不可能发生死锁;当系统中有2个进程时,最多需要6台磁带机,而系统有8台磁带机,其资源个数也足够系统内的2个进程使用,因此也不可能发生死锁;当系统中有3个进程时,无论系统如何分配资源,3个进程中必有进程可以获得3台磁带机,该进程已获得了它所需要的全部资源并将顺利运行完毕,从而可将它占有的3个资源归还给系统,这就保证了其余进程能顺利运行完毕。当N>3时,若资源分配及释放顺序不当时,系统有可能出现死锁。
由此可知,当N为1、2、3时,该系统不会由于对这种资源的竞争而产生死锁。
【例3-3-44】回答以下问题:
(1)3个进程共享4个同类型资源,每个进程最大需要两个资源,请问该系统是否会因为竞争该资源而死锁?
(2)n个进程(编号为1~n)共享m个同类资源,若每个进程都需要用该类资源,且各进程最大需求量之和小于m+n,试证明这个系统不会因为竞争该资源而发生死锁。
Max(1)+…+Max(n)=Need(1)+…+Need(n)+Alloc(1)+…+Alloc(n)<m+n
(3)在(2)中,如果没有“每个进程都需要用该类资源”的限制,情况又会如何?
解:(1)该系统不会因为竞争该资源而死锁。因为必有一个进程获得两个资源,故能顺利完成,并释放给其他进程使用,使它们也顺利完成。
(2)根据题意有:Need(i)>0,<m+n
若系统进入死锁状态,则意味有一个以上进程因申请不到资源而无限阻塞,而m个资源已全部分配出去,即:=m。
因此,=-<m+n-m=n,即<n。
这样,至少存在一个进程,其Need(i)≤0,这显然与题意不符,所以该系统不可能因竞争该类资源而进入死锁状态。
(3)此时系统可能发生死锁,如n=4,m=3时,若进程P1的Max为0,而其余3个进程P2、P3、P4的Max都为2,则仍然满足最大需求量之和(即6)小于m+n(即7)的要求,但当除P1以外的其余3个进程P2、P3、P4各得到一个资源时,这3个进程将进入死锁状态。
【例3-3-45】Dijkstra于1965年提出的银行家算法,其主要思想是什么?它能够用来解决实际中的死锁问题吗?为什么?
解:银行家算法是避免死锁的一种方法,其实现思想是:允许进程动态地申请资源,系统在每次实施资源分配之前,先计算资源分配的安全性,若此次资源分配安全(即资源分配后,系统能按某种顺序来为每个进程分配其所需的资源,直至最大需求,使每个进程都可以顺利的完成),便将资源分配给进程,否则不分配资源,让进程等待。
银行家算法具有较好的理论意义,但在实际系统中却难以实施。其原因是:难以预先获得进程申请的最大资源数;运行过程中进程的个数是不断变化的,所以银行家算法难以用来解决实际中的死锁问题。
【例3-3-46】一个系统具有150个存储单元,在T0时刻按表3.7所示分配给3个进程。
表3.7  3个进程分配情况
进程 最大需求存储单元 当前已分配单元数
P1 70 25
P2 60 40
P3 60 45
 
对下列请求应用银行家算法分析判断是否安全?
(1)第4个进程P4到达,最大需求60个存储单元,当前请求分配25个单元。
(2)第4个进程P4到达,最大需求50个存储单元,当前请求分配35个单元。
如果是安全的,请给出一个可能的进程安全执行序列;如果不是安全的,请说明原因。
解:(1)计算得到T0时刻的资源分配表如表3.8所示,剩余单元数=150- (25+40+45)=40。此时40不小于P4进程请求的单元数25。将25分配给P4进程,还余15个单元,将其分配给P3进程,此时刻的安全性检测表如表3.9所示,得到一个安全序列{P3,P2,P1,P4}(结果不唯一)。
表3.8  T0时刻的资源分配表
进程 Max Allocation Need Available
P1 70 25 45 40
P2 60 40 20  
P3 60 45 15  
P4 60      
 
 

表3.9  安全性检测表
进程 Max Work Need Allocation Work+Allocation Finish
P3 60 15 15 45 60 true
P2 60 60 20 40 100 true
P1 70 100 45 25 125 true
P4 60 125 35 25 150 true
 
(2)此时的剩余单元数=150-(25+40+45)=40。此时40不小于P4进程请求的单元数35,将其35个单元分配给P4进程,余下5个单元,其资源分配表如表3.10所示,4个进程都不够分配,找不到一个安全序列,所以是不安全状态。
表3.10  T0时刻的资源分配表
进程 Max Allocation Need Available
P1 70 25 45 5
P2 60 40 20  
P3 60 45 15  
P4 50 35 15  
 
【例3-3-47】若系统运行中出现如表3.11所示的资源分配情况,该系统是否安全? 如果进程P2此时提出资源申请(1,2,2,2),系统能否将资源分配给它?为什么?
解:(1)利用安全性算法对此刻的资源分配情况进行分析,可得到如表3.12所示的安全性检测情况,从该表中可以看出,此时存在一个安全序列{P0,P3,P4,P1,P2},故该系统是安全的。
表3.11  系统资源分配表
进程 Allocation Need Available
P0 0 0 3 2 0 0 1 2 1 6 2 2
P1 1 0 0 0 1 7 5 0        
P2 1 3 5 4 2 3 5 6        
P3 0 3 3 2 0 6 5 2        
P4 0 0 1 4 0 6 5 6        
表3.12  安全性检测表
进程 Work Need Allocation Work+Allocation Finish
P0 1 6 2 2 0 0 1 2 0 0 3 2 1 6 5 4 true
P3 1 6 5 4 0 6 5 2 0 3 3 2 1 9 8 6 true
P4 1 9 8 6 0 6 5 6 0 0 1 4 1 9 9 10 true
P1 1 9 9 10 1 7 5 0 1 0 0 0 2 9 9 10 true
P2 2 9 9 10 2 3 5 6 1 3 5 4 3 12 14 14 true
 
(2)P2提出请求(1,2,2,2),按银行家算法进行检查:
l       Request2(1,2,2,2)≤Need2(2,3,5,6)
l       Request2(1,2,2,2)≤Available(1,6,2,2)
试分配并修改相应的数据结构,由此形成的资源分配情况如表3.13所示。
表3.13  P2申请资源后的资源分配表
进程 Allocation Need Available
P0 0 0 3 2 0 0 1 2 0 4 0 0
P1 1 0 0 0 1 7 5 0        
P2 2 5 7 6 1 1 3 4        
P3 0 3 3 2 0 6 5 2        
P4 0 0 1 4 0 6 5 6        
 
再利用安全性算法检查系统是否安全,可利用资源Available(0,4,0,0)已不能满足任何进程的需要,故系统进入不安全状态,此时系统不能将资源分配给P2
【例3-3-48】有相同类型的5个资源被4个进程所共享,且每个进程最多需要2个这样的资源就可以运行完毕。试问该系统是否会由于对这种资源的竞争而产生死锁。
解:该系统不会由于对这种资源的竞争而产生死锁。因为每个进程最多需要2个这样的资源,无论系统如何分配资源,4个进程中必有一个进程可以获得2个资源,该进程将顺利运行完毕,从而可以将它占有的2个资源归还给系统,同理其余3个进程也能顺利运行完毕。由此可知,该系统不会由于对这种资源的竞争而产生死锁。
【例3-3-49】现有某类资源12个,供3个进程共享。假定进程A已占1个资源,其最大需求4个,进程B已占4个资源,其最大需求6个,进程C已占5个资源,其最大需求8个。当进程都请求尚需的资源时,系统应按怎样的次序为它们分配以保证不发生死锁,并解释之。
解:资源有12个,已分配10个,还剩下2个,进程B正好还需要2个,应先为进程B分配,进程B执行结束归还资源后,再为进程A和C分配资源。因系统的12个资源已分配了10个,剩下的2个资源不能满足进程A和C的需求,而能满足B的最大需求,故先分配给进程B,当它执行结束归还6个资源后,系统的资源就能满足进程A和C的需求,故均能执行结束,系统不会发生死锁。
【例3-3-50】设系统中有3种类型的资源(A、B和C)和5个进程P1、P2、P3、P4、P5,A资源的数量为17,B资源的数量为5,C资源的数量为20。在T0时刻系统状态如表3.14所示。系统采用银行家算法实施死锁避免策略。
表3.14  T0时刻系统状态
进程 最大资源需求量 已分配资源数量
A B C A B C
P1 5 5 9 2 1 2
P2 5 3 6 4 0 2
P3 4 0 11 4 0 5
P4 4 2 5 2 0 4
P5 4 2 4 3 1 4
剩余资源数 A B C
2 3 3
 
 
(1)T0时刻是否为安全状态?若是,请给出安全序列。
(2)若在T0时刻进程P2请求资源(0,3,4),是否能实施资源分配?为什么?
(3)在(2)的基础上,若进程P4请求资源(2,0,1),是否能实施资源分配?为什么?
(4)在(3)的基础上,若进程P1请求资源(0,2,0),是否能实施资源分配?为什么?
解:由题目所给出的最大资源需求量和已分配资源数量,可以计算出T0时刻各进程的资源需求量Need,Need=最大资源需求量-已分配资源数量,如表3.15所示。
表3.15  T0时刻的资源分配表
进程 Allocation Need Available
A B C A B C A B C
P1 2 1 2 3 4 7 2 3 3
P2 4 0 2 1 3 4      
P3 4 0 5 0 0 6      
P4 2 0 4 2 2 1      
P5 3 1 4 1 1 0      
 
(1)利用银行家算法对T0时刻的资源分配情况进行分析,可得此时刻的安全性分析情况,如表3.16所示。
表3.16  T0时刻的安全性检测表
进程 Work Need Allocation Work+Allocation Finish
A B C A B C A B C A B C
P5 2 3 3 1 1 0 3 1 4 5 4 7 true
P4 5 4 7 2 2 1 2 0 4 7 4 11 true
P3 7 4 11 0 0 6 4 0 5 11 4 16 true
P2 11 4 16 1 3 4 4 0 2 15 4 18 true
P1 15 4 18 3 4 7 2 1 2 17 5 20 true
 
从T0时刻的安全性分析中可以看出,存在一个安全序列{P5,P4,P3,P2,P1},故T0时刻的状态是安全的。
(2)若在T0时刻进程P2请求资源(0,3,4),因请求资源数(0,3,4)大于剩余资源数(2,3,3),所以不能分配。
(3)在(2)的基础上,若进程P4请求资源(2,0,1),按银行家算法进行检查:
l       P4请求资源(2,0,1)≤ P4资源需求量(2,2,1)
l       P4请求资源(2,0,1)≤ 剩余资源数(2,3,3)
试分配并修改相应的数据结构,由此形成的资源分配情况如表3.17所示。
再利用安全性算法检查系统是否安全,可得到如表3.18所示的安全性检测表。

表3.17  P4请求资源后的资源分配表
进程 Allocation Need Available
A B C A B C A B C
P1 2 1 2 3 4 7 0 3 2
P2 4 0 2 1 3 4      
P3 4 0 5 0 0 6      
P4 4 0 5 0 2 0      
P5 3 1 4 1 1 0      
 
表3.18  P4请求资源后的安全性检测表
进程 Work Need Allocation Work+Allocation Finish
A B C A B C A B C A B C
P4 0 3 2 0 2 0 4 0 5 4 3 7 true
P5 4 3 7 1 1 0 3 1 4 7 4 11 true
P3 7 4 11 0 0 6 4 0 5 11 4 16 true
P2 11 4 16 1 3 4 4 0 2 15 4 18 true
P1 15 4 18 3 4 7 2 1 2 17 5 20 true
 
从表3.23中可以看出,此时存在一个安全序列{P4,P5,P3,P2,P1},故该状态是安全的,可以立即将P4所申请的资源分配给它。
(4)在(3)的基础上,若进程P1请求资源(0,2,0),按银行家算法进行检查:
l       P1请求资源(0,2,0)≤ P1资源需求量(3,4,7)
l       P1请求资源(0,2,0)≤ 剩余资源数(0,3,2)
试分配并修改相应的数据结构,由此形成的资源分配情况如表3.19所示。
再利用安全性算法检查系统是否安全,可用资源Available(0,1,2)已不能满足任何进程的资源需求,故系统进入不安全状态,此时系统不能将资源分配给P1
表3.19  P1请求资源后的资源分配表
进程 Allocation Need Available
A B C A B C A B C
P1 2 3 2 3 2 7 0 1 2
P2 4 0 2 1 3 4      
P3 4 0 5 0 0 6      
P4 4 0 5 0 2 0      
P5 3 1 4 1 1 0      
 
【例3-3-51】某系统有R1、R2和R3共3种资源,在T0时刻P1、P2、P3和P4这4个进程对资源的占用和需求情况如表3.20所示,此时系统的可用资源向量为(2,1,2)。试问:

表3.20  T0时刻4个进程对资源的占用和需求情况
进程 最大资源需求量 已分配资源数量
R1 R2 R3 R1 R2 R3
P1 3 2 2 1 0 0
P2 6 1 3 4 1 1
P3 3 1 4 2 1 1
P4 4 2 2 0 0 2
 
(1)将系统中各种资源总数和此刻各进程对各资源的需求个数用向量或矩阵表示出来。
(2)如果此时P1和P2均发出资源请求向量Request(1,0,1),为了保证系统的安全性,应该如何分配资源给这两个进程?说明你所采用策略的原因。
(3)如果(2)中两个请求立即得到满足后,系统此刻是否处于死锁状态?
解:(1)系统中资源总量为某时刻系统中可用资源量与各进程已分配资源量之和,即:
(2,1,2)+(1,0,0)+(4,1,1)+(2,1,1)+(0,0,2)=(9,3,6)
各进程对资源的需求量为各进程对资源的最大需求量与进程已分配资源量之差,即:
-=
(2)若此时P1发出资源请求Request1(1,0,1),按银行家算法进行检查:
l       Request1(1,0,1)≤Need1(2,2,2)
l       Request1(1,0,1)≤Available(2,1,2)
试分配并修改相应的数据,由此形成的资源分配情况如表3.21所示。
表3.21  P1请求资源后的资源分配表
进程 Allocation Need Available
R1 R2 R3 R1 R2 R3 R1 R2 R3
P1 2 0 1 1 2 1 1 1 1
P2 4 1 1 2 0 2      
P3 2 1 1 1 0 3      
P4 0 0 2 4 2 0      
 
再利用安全性算法检查系统是否安全,可用资源Available(1,1,1)已不能满足任何进程,系统进入不安全状态,此时系统不能将资源分配给P1
若此时P2发出资源请求Request2(1,0,1),按银行家算法进行检查:
l       Request2(1,0,1)≤Need2(2,0,2)
l       Request2(1,0,1)≤Available(2,1,2)
试分配并修改相应的数据结构,由此形成的资源分配情况如表3.22所示。再利用安全性算法检查系统是否安全,可得到如表3.23所示的安全性检测情况,从该表中可以看出,此时存在一个安全序列{P2,P3,P4,P1},故该状态是安全的,可以立即将P2所申请的资源分配给它。
表3.22  P2请求资源后的资源分配表
进程 Allocation Need Available
R1 R2 R3 R1 R2 R3 R1 R2 R3
P1 1 0 0 2 2 2 1 1 1
P2 5 1 2 1 0 1      
P3 2 1 1 1 0 3      
P4 0 0 2 4 2 0      
 
表3.23  P2请求资源后的安全性检测表
进程 Work Need Allocation Work+Allocation Finish
R1 R2 R3 R1 R2 R3 R1 R2 R3 R1 R2 R3
P2 1 1 1 1 0 1 5 1 2 6 2 3 true
P3 6 2 3 1 0 3 2 1 1 8 3 4 true
P4 8 3 4 4 2 0 0 0 2 8 3 6 true
P1 8 3 6 2 2 2 1 0 0 9 3 6 true
 
(3)如果(2)中两个请求立即得到满足,此刻系统并没有立即进入死锁状态,因为这时所有进程没有提出新的资源申请,全部进程均没有因资源请求没得到满足而进入阻塞状态。只有当进程提出资源申请且全部进程都进入阻塞状态时,系统才处于死锁状态。
【例3-3-52】现有5个进程A、B、C、D、E,有4种类型的资源R1、R2、R3、R4。在T0时刻系统状态如表3.24所示。R1、R2、R3、R4的剩余资源数依次为3、3、0、3。若采用银行家算法避免死锁,回答下列问题:
(1)T0时刻是否为安全状态?
(2)若这时D提出申请(1,2,0,3),是否能实施资源分配?
表3.24  T0时刻5个进程对资源的占用和需求情况
进程 已占资源数 最大需求数
R1 R2 R3 R4 R1 R2 R3 R4
A 0 0 1 2 0 0 1 2
B 2 0 0 0 2 7 5 0
C 0 0 3 4 6 6 5 6
D 1 1 5 1 4 3 5 6
E 0 3 3 2 0 6 5 2
解:(1)利用安全性算法对此时刻的资源分配情况进行分析,可得到如表3.25所示的安全性检测情况。从中可以看出,存在一个安全序列{A,D,E,B,C},故T0时刻处于安全状态。
 
 
表3.25  T0时刻的安全性检测情况
进程 Work Need Allocation Work+Allocation Finish
R1 R2 R3 R4 R1 R2 R3 R4 R1 R2 R3 R4 R1 R2 R3 R4
A  3  3  0  3  0  0  0  0  0  0  1  2   3  3  1  5 true
D  3  3  1  5  3  2  0  5  1  1  5  1   4  4  6  6 true
E  4  4  6  6  0  3  2  0  0  3  3  2   4  7  9  8 true
B  4  7  9  8  0  7  5  0  2  0  0  0   6  7  9  8 true
C  6  7  9  8  6  6  2  2  0  0  3  4   6  7  12  12 true
 
(2)进程D提出申请(1,2,0,3),按银行家算法进行检查:
l       RequestD(1,2,0,3)<NeedD(3,2,0,5)
l       RequestD(1,2,0,3)<Available(3,3,0,3)
此时存在一个安全序列{A、D、E、B、C},如表3.26所示,故该状态是安全的,可以立即将D进程所申请的资源分配给它。
表3.26  D进程请求资源后的安全性检测表
进程 Work Need Allocation Work+Allocation Finish
R1 R2 R3 R4 R1 R2 R3 R4 R1 R2 R3 R4 R1 R2 R3 R4
A 2  1  0  0 0  0  0  0 0  0  1  2 2  1  1  2 true
D 2  1  1  2 2  0  0  2 2  3  5  4 4  4  6  6 true
E 4  4  6  6 0  3  2  0 0  3  3  2 4  7  9  8 true
B 4  7  9  8 0  7  5  0 2  0  0  0 6  7  9  8 true
C 6  7  9  8 6  6  2  2 0  0  3  4 6  7  12  12 true
 
【例3-3-53】假定某计算机系统有R1和R2两类可再使用资源(其中R1有两个单位,R2有一个单位),它们被进程P1和P2所共享,且已知两个进程均以下列顺序使用两类资源:
→申请R1→申请R2→申请R1→释放R1→释放R2→释放R1
试求出系统运行过程中可能到达的死锁点,并画出死锁点的资源分配图(或称进程-资源图)。
解:在本题中,当两个进程都执行完第1步后,即进程P1和进程P2都申请到了一个R1类资源时,系统进入不安全状态。随着两个进程的向前推进,无论哪个进程执行完第2步,系统都将进入死锁状态。可能到达的死锁点是:进程P1占有一个单位的R1类资源及一个单位的R2类资源,进程P2占有一个单位的R1类资源,此时系统内已无空闲资源,而两个进程都在保持已占有资源不释放的情况下继续申请资源,从而造成死锁;或进程P2占有一个单位的R1类资源及一个单位的R2类资源,进程P1占有一个单位的R1类资源,此时系统内已无空闲资源,而两个进程都在保持已占有资源不释放的情况下继续申请资源,从而造成死锁。
假定进程P1成功执行了第2步,则死锁点的资源分配图如图3.38所示。

图3.38  死锁点的资源分配图
【例3-3-54】试化简图3.39中的进程资源图,并利用死锁定理给出相应的结论。

图3.39  两个进程-资源图
解:在图3.39(a)中,系统中共有R1类资源2个,R2类资源3个,在当前状态下仅有一个R2类资源空闲。进程P2占有一个R1类资源及一个R2类资源,并申请一个R2类资源;进程P1占有一个R1类资源及一个R2类资源,并申请一个R1类资源及一个R2类资源。因此,进程P2是一个既不孤立又非阻塞的进程,消去进程P2的资源请求边和资源分配边,便形成了如图3.40(a)所示的情况。当进程P2释放资源后,系统中有2个R2类空闲资源、1个R1类空闲资源,因此系统能满足进程P1的资源申请,使得进程P1成为一个既不孤立又非阻塞的进程,消去进程P1的资源请求边和资源分配边,便形成了如图3.40(b)所示的情况。由死锁定理可知,图3.39(a)中的进程-资源图不会产生死锁。

图3.40  资源分配图的化简
在图3.39(b)中,系统中共有R1类资源1个、R2类资源2个、R3类资源2个、R4类资源1个。在当前状态下仅有一个R3类资源空闲。进程P1占有一个R2类资源,并申请一个R1类资源;进程P2占有一个R1类资源及一个R3类资源,并申请一个R4类资源;进程P3占有一个R4类资源及一个R2类资源,并申请一个R3类资源及一个R2类资源,因此,该资源分配图中没有不孤立又不阻塞的进程节点,即系统中的3个进程均无法向前推进,由死锁定理可知,图3.39(b)的进程-资源图会产生死锁。
【例3-3-55】有3个进程P1、P2和P3并发工作,进程P1需用资源S3和S1,进程P2需用资源S1和S2,进程P3需用资源S2和S3。试回答下面两个问题。
(1)若对资源分配不加限制,会发生什么情况?为什么?
(2)为保证进程正确工作,应采用怎样的资源分配策略?
解:(1)可能会发生死锁现象。例如,进程P1、P2和P3分别获得资源S3、S1和S2后再继续申请资源时都要等待,这是循环等待。
(2)可有以下几种分配策略:
l       采用静态分配,由于执行前已获得所需的全部资源,故不会出现占有资源又等待别的资源的现象(或不会出现循环等待资源现象)。
l       采用按序分配,不会出现循环等待资源现象。
l       采用银行家算法,在分配时,保证了系统处于安全状态。
【例3-3-56】进程资源的使用情况和可用情况如表3.27所示(4个进程和3类资源),回答以下问题:
(1)请画出资源分配图。
(2)分析目前系统中是否会发生死锁。
表3.27  进程资源的使用情况和可用情况
进程 当前已分配资源数量 最大需求量 系统可用资源数量
R1 R2 R3 R1 R2 R3 R1 R2 R3
P1 2 0 0 3 1 0 0 0 0
P2 3 1 0 3 1 0
P3 1 3 0 1 3 1
P4 0 1 1 0 2 1
解:(1)对应的资源分配图如图3.41所示。

图3.41  一个资源分配图
(2)从进程对各类资源的占有量、尚需量和系统中各类资源的剩余量来考虑是否有死锁存在。可以看出进程P2已得到全部资源,能在有限的时间内归还资源,得到可分配的资源数为:
(3,1,0)+(0,0,0)=(3,1,0)
可满足进程P1的申请,P1也能在有限的时间内归还资源,于是可分配的资源数增加为:
(3,1,0)+(2,0,0)=(5,1,0)
接着,对进程P4的申请也能满足,最后让进程P3运行。所以存在一个进程推进的序列为(P2,P1,P4,P3),先后都能完成,目前系统是安全的,没有死锁。
点击复制链接 与好友分享!回本站首页
分享到: 更多
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力  
上一篇:3.3.1 要点归纳
下一篇:Excel 2010办公技巧大全
相关文章
图文推荐
2.7.12 使用仿真器查
2.7.11 栈和寄存器组
2.7.8 出栈
2.7.7 压栈
排行
热门
文章
下载
读书

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