第四章_死锁1

1、 北京工商大学北京工商大学 计信学院计信学院Operating SystemOperating System第四章 死锁 资源 死锁概述 鸵鸟算法 死锁检测 死锁避免 死锁预防 其他问题 北京工商大学北京工商大学 计信学院计信学院Operating SystemOperating System 北京工商大学北京工商大学 计信学院计信学院Operating SystemOperating System 北京工商大学北京工商大学 计信学院计信学院Operating SystemOperating System资源u可抢占资源可抢占资源可以从拥有该资源的进程中抢占而不会产生任何副作用可以从拥有该资源

2、的进程中抢占而不会产生任何副作用处理器、内存处理器、内存u不可抢占资源不可抢占资源不引起相关计算失败的情况下，无法把它从占有它的进程不引起相关计算失败的情况下，无法把它从占有它的进程处抢占过来处抢占过来打印机，打印机，CDCD刻录机（独占型资源）刻录机（独占型资源） 北京工商大学北京工商大学 计信学院计信学院Operating SystemOperating Systemu进程使用资源进程使用资源( (不可抢占不可抢占) )所需要的事件可以表述为所需要的事件可以表述为请求资源请求资源使用资源使用资源释放资源释放资源u不同系统的资源请求、使用及释放过程有所不同。不同系统的资源请求、使用及释放过程

3、有所不同。资源u一般而言，进程间的死锁问题多由不可抢占资源的排他性使一般而言，进程间的死锁问题多由不可抢占资源的排他性使用引起。用引起。u对于可抢占资源，若存在潜在的死锁，可以通过进程间的重对于可抢占资源，若存在潜在的死锁，可以通过进程间的重新资源调配来解决新资源调配来解决. . 北京工商大学北京工商大学 计信学院计信学院Operating SystemOperating System资源-资源获取资源获取typedef int semaphore;semaphore resource_1;void process_A(void) down(&resource_1); use_resource

4、_1(); up(&resourcde_1);typedef int semaphore;semaphore resource_1;semaphore resource_2;void process_A(void) down(&resource_1); down(&resource_2); use_resource_1(); up(&resourcde_2); up(&resource_1);图图. 采用信号量保护资源采用信号量保护资源a). 一个资源一个资源 b). 两个资源两个资源采用互斥信号量对资源进行获取采用互斥信号量对资源进行获取l一个进程的情形一个进程的情形 北京工商大学北京工商大

5、学 计信学院计信学院Operating SystemOperating System资源-资源获取资源获取l 两个进程的情形两个进程的情形typedef int semaphore;semaphore resource_1;semaphore resource_2;void process_A(void) down(&resource_1); down(&resource_2); use_both_resource(); up(&resource_2); up(&resource_1);void process_B(void) down(&resource_1); down(&resource

6、_2); use_both_resouce(); up(&resouce_2); up(&resouce_1);typedef int semaphore;semaphore resource_1;semaphore resource_2;void process_A(void) down(&resource_1); down(&resource_2); use_both_resource(); up(&resource_2); up(&resource_1);void process_B(void) down(&resource_2); down(&resource_1); use_both

7、_resouce(); up(&resouce_1); up(&resouce_2);图图. 左）无死锁的互斥左）无死锁的互斥 右）产生死锁的互斥右）产生死锁的互斥 北京工商大学北京工商大学 计信学院计信学院Operating SystemOperating SystemP、V操作不当产生死锁生产者进程 消费者进程 P(mutex) P(mutex) P(empty) P(full) 缓冲区满后，先后执行生产者进程和消费者进程。 北京工商大学北京工商大学 计信学院计信学院Operating SystemOperating System 死锁概述-死锁定义死锁定义定义一如果一组进程中，每个进程都

8、在等待只能由该进程集合中其他进程才能引发的事件，这个进程集合就是死锁的定义二一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到的资源，这种现象称为死锁，这一组进程就称为死锁进程 北京工商大学北京工商大学 计信学院计信学院Operating SystemOperating System互斥（资源独占）一个资源每次只能给一个进程使用占有等待一个进程在申请新的资源的同时保持对原有资源的占有 非剥夺（不可抢占）资源申请者不能强行的从资源占有者手中夺取资源，资源只能由占有者自愿释放环路等待存在一个进程等待队列 P1 , P2 , , Pn, 其中P1等待P2占有的资源，P2

9、等待P3占有的资源，Pn等待P1占有的资源，形成一个进程等待环路死锁的四个必要条件死锁的四个必要条件 北京工商大学北京工商大学 计信学院计信学院Operating SystemOperating System死锁建模-资源分配图形式化描述资源分配图 G=(V,E),其中顶点集V=PR,P是进程集合：P=P1,P2,Pn资源集R=r1,r2,rm,ri表示系统中的ri类资源E是边的集合，E中有两类边分配边 (rj,Pi)请求边( Pi,rj) 北京工商大学北京工商大学 计信学院计信学院Operating SystemOperating SystemARSRRBB图. 资源分配图a).占有一个资源

10、 b).请求一个资源 c). 死锁如果各类资源数为1，则系统出现死锁的充要条件是资源分配图含圈 PiPP.死锁建模-资源分配图 北京工商大学北京工商大学 计信学院计信学院Operating SystemOperating System 北京工商大学北京工商大学 计信学院计信学院Operating SystemOperating System死锁定理如果资源分配图中没有环路，则系统中没有死锁，如果资源分配图中没有环路，则系统中没有死锁，如果图中存在环路则系统中如果图中存在环路则系统中可能可能存在死锁存在死锁如果每个资源类中只包含一个资源实例，则环路如果每个资源类中只包含一个资源实例，则环路是死锁

11、存在的充分必要条件是死锁存在的充分必要条件有环有死锁有环有死锁有环无死锁有环无死锁 北京工商大学北京工商大学 计信学院计信学院Operating SystemOperating System解决死锁问题的方法按照死锁发生的时间过程，来思考解决思索问题的方法忽略问题鸵鸟算法设计无死锁的系统死锁防止在应用编程时或资源分配管理设计时破坏死锁的必要条件死锁避免进行资源分配时，判断是否存在安全序列，存在情况下进行分配，否则拒绝分配允许死锁、出现排除死锁检测死锁恢复 北京工商大学北京工商大学 计信学院计信学院Operating SystemOperating System鸵鸟算法 鸵鸟算法的思路鸵鸟算法的

12、思路当计算机系统中存在死锁的威胁但是很少出现时当计算机系统中存在死锁的威胁但是很少出现时, ,人们采取的办法是不去管它人们采取的办法是不去管它, ,而是忽略它而是忽略它. .* *如如果系统遇见死锁崩溃果系统遇见死锁崩溃, ,则重新启动系统则重新启动系统; ;* *设计者不会以性能损失和可用性损失为代价去防止死锁设计者不会以性能损失和可用性损失为代价去防止死锁.;.; 北京工商大学北京工商大学 计信学院计信学院Operating SystemOperating System死锁检测和死锁恢复允许死锁发生，然后再恢复-允许死锁发生，操作系统不断监视系统进展情况，判断死锁是否发生-一旦死锁发生则采

13、取专门的措施，解除死锁并以最小的代价恢复操作系统运行（死锁恢复） 北京工商大学北京工商大学 计信学院计信学院Operating SystemOperating System检测时机：检测时机： 当进程等待时检测死锁 定时检测 系统资源利用率下降时检测死锁死锁检测和死锁恢复 北京工商大学北京工商大学 计信学院计信学院Operating SystemOperating System每种类型一个资源的死锁检测资源分配图化简检测有向图环路的算法（P249)每种类型多个资源的死锁检测基于矩阵的算法（例P251)死锁检测 北京工商大学北京工商大学 计信学院计信学院Operating SystemOpera

14、ting System死锁检测不做死锁避免，定期检测死锁是否发生采用化简资源分配图的方法可以检测系统中有无进程处于死锁状态资源分配图的简化过程在图中找一个进程顶点在图中找一个进程顶点i i, P, Pi i没有请求边或请求边均能立即满足没有请求边或请求边均能立即满足若找到这样的若找到这样的P Pi i则将与则将与i i相连的边全部删去，转相连的边全部删去，转；否则化简过程结；否则化简过程结束束如果化简后所有的进程顶点都成了如果化简后所有的进程顶点都成了孤立点孤立点，则称该图可完全化简；否则，则称该图可完全化简；否则称该图是不可完全化简的称该图是不可完全化简的系统中有死锁的充分必要条件是资源分配

15、图不可完全化简经过化简后，非孤立点的进程处于死锁状态。 北京工商大学北京工商大学 计信学院计信学院Operating SystemOperating System资源分配图的简化过程资源分配图的简化过程在图中找一个进程顶点在图中找一个进程顶点i i, P, Pi i的请求边均能立即满足的请求边均能立即满足若找到这样的若找到这样的P Pi i则将与则将与i i相连的边全部删去，转相连的边全部删去，转；否则化简过程结束否则化简过程结束如果化简后所有的进程顶点都成了如果化简后所有的进程顶点都成了孤立点孤立点，则称该图可，则称该图可完全化简；否则称该图是不可完全化简的完全化简；否则称该图是不可完全化简

16、的系统中有死锁的系统中有死锁的充分必要条件充分必要条件是是资源分配图不可完全化简资源分配图不可完全化简。经过化简后，非孤立点的进程处于死锁状态。经过化简后，非孤立点的进程处于死锁状态。 北京工商大学北京工商大学 计信学院计信学院Operating SystemOperating System死锁恢复 利用抢占恢复利用抢占恢复 强行剥夺现有运行进程的资源给竞争的进程使用强行剥夺现有运行进程的资源给竞争的进程使用. 利用回退恢复利用回退恢复利用检查点机制利用检查点机制(checkpoint),通过保存检查点内容通过保存检查点内容进行回退到死锁前状态，人工干预资源的使用进行回退到死锁前状态，人工干预

17、资源的使用. 通过杀死进程恢复通过杀死进程恢复杀掉环里的进程杀掉环外部的进程杀死可以从头开始重新执行的进程 北京工商大学北京工商大学 计信学院计信学院Operating SystemOperating Systeml 剥夺哪个进程的哪些资源;l 需要为剥夺资源的进程做些什么（剥夺资源的进程需要重新运行或回退到某一点开始继续运行）l 怎样保证不发生“饿死”现象l 怎么使进程回到原来状态带来的开销最小抢占和回退时需要考虑的问题 北京工商大学北京工商大学 计信学院计信学院Operating SystemOperating System死锁避免基本思想：基本思想：l 在系统运行过程中，对进程发出的每一

18、个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。l 这是一种保证系统不进入死锁状态的动态策略。 北京工商大学北京工商大学 计信学院计信学院Operating SystemOperating System死锁避免p资源轨迹图（P252)p安全状态和不安全状态安全状态和不安全状态设系统中有n个进程，若存在一个序列P1，2n使得Pi(i1，2n)以后还需要的资源可以通过系统现有资源加上所有Pj(ji)占有的资源来满足 ，则称这个系统处于安全状态序列, , ,n称为安全序列p操作方法操作方法在系统处理资源申请时，判断如果满足某个

19、进程的申请时，系统是否还处于安全状态？是则满足本次资源申请 ，否则拒绝 北京工商大学北京工商大学 计信学院计信学院Operating SystemOperating System不安全状态l 不安全状态:不存在一个安全序列l 不安全状态不一定导致死锁 北京工商大学北京工商大学 计信学院计信学院Operating SystemOperating System死锁避免l 只要能使系统总是处于安全状态就可避免死锁的发生.l 每当有进程退出资源申请时,系统可以通过分析各个进程已经占有的资源数目、尚需资源的数目以及系统中可以分配的剩余资源数目，以决定是否为当前的申请进程分配资源。l 如果能使系统处于安全

20、状态，则可为进程分配资源，否则暂且不为申请进程分配资源。 北京工商大学北京工商大学 计信学院计信学院Operating SystemOperating System银行家算法 把操作系统比作一个银行家 各种资源比作周转资金 申请资源的进程比作向银行贷款的顾客 操作系统的资源分配问题转化为银行家利用其资金发放贷款的问题。 1. 银行家能贷款给顾客，满足顾客对资金的要求。（操作系统能满足每个进程对资源的要求） 2. 银行家可以安全地回收其全部贷款，而不至于破产。（系统不处于死锁） 北京工商大学北京工商大学 计信学院计信学院Operating SystemOperating System为了保证资金

21、的安全，银行家规定：当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客；顾客可以分期贷款，但贷款的总数不能超过顾客对资金的最大需求量；当银行家现有的资金不能满足顾客尚需的贷款数额时，对顾客的贷款可推迟支付，但总能使顾客在有限的时间内得到贷款；当顾客得到所需的全部资金后，一定能在有限的时间内归还所有资金。 北京工商大学北京工商大学 计信学院计信学院Operating SystemOperating System操作系统按照银行家的规定为进程分配资源进程提出对资源的最大需要量。每次申请能时系统需判断该进程的申请之和是否超过它的最大需求量。若没超过，还需测试系统现存的资源能否满足该进

22、程尚需的最大资源量。若满足，则按当前申请分配，否则推迟分配。这样做能保证在任何时刻至少有一个进程可以得到所需要的全部资源而执行结束，结束后归还的资源加入到系统的剩余资源中，这些资源又至少可以满足另一个进程的最大需求。最后保证系统中的所有进程都能在有限地时间内得到需要的全部资源。 北京工商大学北京工商大学 计信学院计信学院Operating SystemOperating System银行家算法-单个资源的银行家算法设银行家有10万贷款，P,Q,R分别需要8,3,9万元搞项目（假设任何人满足资金总额后都会归还所有贷款）如果P已申请到了4万，Q申请2万，R申请2万，则银行家还剩2万此时，如果Q又申

23、请1万显然，如果满足Q的申请，有安全序列 如果Q申请之后，R要申请4万。如果满足R的申请，则不存在安全序列 北京工商大学北京工商大学 计信学院计信学院Operating SystemOperating System资源分配程序的工作过程当进程提出资源申请时系统首先检查该进程对资源的申请量是否超过其最大需求量系统现有资源能否满足进程需要若能则进一步检查若把资源分给该进程系统能否处于安全状态若安全则分配，否则置该进程为等待资源状态 北京工商大学北京工商大学 计信学院计信学院Operating SystemOperating System目前占有量目前占有量最大需求量最大需求量尚需要量尚需要量P12

24、97P25105P3242系统剩余资源量系统剩余资源量3系统处于安全状态系统处于安全状态,安全序列为安全序列为P3 P2 P1例：12个同类资源供3个进程共享 北京工商大学北京工商大学 计信学院计信学院Operating SystemOperating SystemP1提出再申请一个资源目前占有量目前占有量最大需求量最大需求量尚需要量尚需要量P1396P25105P3242系统剩余资源量系统剩余资源量2系统处于不安全状态系统处于不安全状态 北京工商大学北京工商大学 计信学院计信学院Operating SystemOperating Systemn：系统中进程的总数m：资源类总数Availabl

25、e:可使用资源向量 ARRAY1.m of integer;Availablej=k 表示系统中有k个j类资源。Max:最大需求矩阵 ARRAY1.n,1.m of integer;Maxi,j=k 表示进程i最多需要k个j类资源。银行家算法-多个资源的银行家算法 北京工商大学北京工商大学 计信学院计信学院Operating SystemOperating SystemAllocation:分配矩阵ARRAY1.n,1.m of integer;Allocationi,j=k 表示进程i当前已分得k个j类资源。Need:需求矩阵 ARRAY1.n,1.m of integer; Needi,j

26、 表示进程i还需要k个j类资源。Request:进程申请资源向量 ARRAY1.n,1.m of integer; Requesti,j 表示进程i需要申请k个j类资源。银行家算法-多个资源的银行家算法 北京工商大学北京工商大学 计信学院计信学院Operating SystemOperating System简记符号：AvailableMaxiAllocationiNeediRequesti银行家算法-多个资源的银行家算法 北京工商大学北京工商大学 计信学院计信学院Operating SystemOperating System当进程pi提出资源申请时，系统执行下列步骤：（1）若Request

27、iNeedi,转（2）； 否则错误返回（2）若RequestiAvailable, 转（3）；否则进程等待银行家算法-多个资源的银行家算法 北京工商大学北京工商大学 计信学院计信学院Operating SystemOperating System(3）假设系统分配了资源，则有：Available:=Available-Requesti;Allocationi:= Allocationi+Requesti;Needi:=Needi-Requesti若系统新状态是安全的，则分配完成若系统新状态是不安全的，则恢复原状态，进程等待银行家算法-多个资源的银行家算法 北京工商大学北京工商大学 计信学院计信

28、学院Operating SystemOperating System为进行安全性检查，定义数据结构：Work:ARRAY1.m of integer;Worki=k 表示剩余i类资源k个。Finish:ARRAY1.n of Boolean;Finishi=true 表示进程i能获得所需资源执行完毕，并能释放全部获得资源。初值为False.银行家算法-多个资源的银行家算法 北京工商大学北京工商大学 计信学院计信学院Operating SystemOperating System安全性检查的步骤：(1) Work:=Available; Finish:=false;(2) 寻找满足条件的i： a

29、.Finishi=false; b.NeediWork;如果不存在，则转(4)银行家算法-多个资源的银行家算法 北京工商大学北京工商大学 计信学院计信学院Operating SystemOperating System(3) Work:=Work+Allocationi; Finishi:=true; 转(2)(4) 若对所有i,Finishi=true,则系统处于安全状态，否则处于不安全状态银行家算法-多个资源的银行家算法多个资源的银行家算法实例3类资源类资源A、B、C。A=10，B=5，C=7。现有。现有5个进程个进程P1、P2、P3、P4、P5. 资源申请资源申请进程进程目前占有量目前占

30、有量最大需求量最大需求量尚需要量尚需要量 A B CA B CA B CP1 0 1 07 5 37 4 3P2 2 0 03 2 21 2 2P3 3 0 29 0 26 0 0P4 2 1 12 2 20 1 1P5 0 0 24 3 34 3 1系统剩余资源量系统剩余资源量 A B C 3 3 2系统处于安全状态，安全序列系统处于安全状态，安全序列P2、P4、 P5、 P3、 P1P2提出申请，A=1, B=0, C=2后 资源申请资源申请进程进程目前占有量目前占有量最大需求量最大需求量尚需要量尚需要量 A B CA B CA B CP1 0 1 07 5 37 4 3P2 3 0 23

31、 2 20 2 0P3 3 0 29 0 26 0 0P4 2 1 12 2 20 1 1P5 0 0 24 3 34 3 1系统剩余资源量系统剩余资源量 A B C 2 3 0系统处于安全状态，安全序列系统处于安全状态，安全序列P2、P4、 P5、 P1、 P3P5提出申请，A=3, B=3, C=0后 资源申请资源申请进程进程目前占有量目前占有量最大需求量最大需求量尚需要量尚需要量 A B CA B CA B CP1 0 1 07 5 37 4 3P2 3 0 23 2 20 2 0P3 3 0 29 0 26 0 0P4 2 1 12 2 20 1 1P5 0 0 24 3 34 3 1

32、系统剩余资源量系统剩余资源量 A B C 2 3 0申请超出了当前剩余资源数量，不实施分配。申请超出了当前剩余资源数量，不实施分配。P1提出申请，A=0, B=2, C=0后 资源申请资源申请进程进程目前占有量目前占有量最大需求量最大需求量尚需要量尚需要量 A B CA B CA B CP1 0 3 07 5 37 2 3P2 3 0 23 2 20 2 0P3 3 0 29 0 26 0 0P4 2 1 12 2 20 1 1P5 0 0 24 3 34 3 1系统剩余资源量系统剩余资源量 A B C 2 1 0预分配后，系统处于不安全状态，不能给预分配后，系统处于不安全状态，不能给P1实施

33、资源分配。实施资源分配。 北京工商大学北京工商大学 计信学院计信学院Operating SystemOperating System银行家算法的缺点算法花费时间多要求每类资源的数量固定不变事先知道资源的最大需求量资源利用率有时会降低 北京工商大学北京工商大学 计信学院计信学院Operating SystemOperating System死锁预防死锁避免从本质上来说是不可能的因为需要预先知道未来请求的最大资源量实际中，使用死锁避免的方法思想：思想：在设计系统时，通过确定资源分配算法，排除发生死锁的可能性具体的做法破坏产生死锁的四个必要条件中的任一个 北京工商大学北京工商大学 计信学院计信学院O

34、perating SystemOperating System破坏“互斥使用/资源独占”条件资源转换技术：把独占资源变为共享资源SPOOLing技术 解决不允许任何进程直接占有打印机的问题设计一个“精灵deamon”进程/线程负责管理打印机，进程需要打印时，将请求发给该daemon，由它完成打印任务 北京工商大学北京工商大学 计信学院计信学院Operating SystemOperating System破坏“占有且等待”条件l 实施方案1：静态资源分配策略 要求每个进程在运行前必须一次性申请它所要求的所有资源，且仅当该进程所要资源均可满足时才给予一次性分配 优点：优点：简单、安全、容易实施

35、缺点：缺点：严重浪费资源；一些进程长期占用资源，会导致其他使用该资源的进程得不到运行（饥饿）。 北京工商大学北京工商大学 计信学院计信学院Operating SystemOperating System破坏“互斥使用/资源独占”条件实现方案2：动态资源分配在允许进程动态申请资源前提下，一个进程在申请新的资源不能立即得到满足而变为等待状态之前，必须释放已占有的全部资源，若需要再重新申请缺点：缺点：会使进程处于等待状态 北京工商大学北京工商大学 计信学院计信学院Operating SystemOperating System破坏“不可抢占”条件实现方案：虚拟化资源抢占资源当一个进程申请的资源被其他

36、进程占用时，可以通过操作系统抢占这一资源(两个进程优先级不同)局限性：适用于状态易于保存和恢复的资源CPU、内存 北京工商大学北京工商大学 计信学院计信学院Operating SystemOperating System破坏“环路等待”条件采用资源有序分配策略采用资源有序分配策略把系统中所有资源编号进程在申请资源时必须严格按资源编号的递增次序进行，否则操作系统不予分配。资源编号原则资源编号原则紧缺、稀少的资源编号较大。 北京工商大学北京工商大学 计信学院计信学院Operating SystemOperating SystemR=r1,r2,r3,rm表示一组资源，定义函数表示一组资源，定义函数

37、F(R)=N,其中，其中，N是一组自然数是一组自然数,表示资源的编号。假定表示资源的编号。假定m=4,r1,r2,r3,r4分别分别为磁盘机、磁带机、扫描仪和打印机。并且为磁盘机、磁带机、扫描仪和打印机。并且F(扫描仪）扫描仪）=1，F(磁盘机）磁盘机）=5，F(磁带机）磁带机）=4，F(打印机）打印机）=2。证明：证明：假设采用该策略后，系统仍存在环路，环路中的进程假设采用该策略后，系统仍存在环路，环路中的进程为为P1,P2,P3Pn,其中其中Pi等待等待Pi+1的资源，的资源，Pn等待等待P0占有的占有的资源。由于资源。由于Pi占有资源占有资源ri,又要申请又要申请ri+1,因此存在因此存

38、在F(ri)F(ri+1),该式对所有该式对所有F都成立，即：都成立，即： F(r0)F(r1)F(r2).F(rn)F(r0)利用利用反证法反证法证明该策略能破坏循环等待条件证明该策略能破坏循环等待条件 北京工商大学北京工商大学 计信学院计信学院Operating SystemOperating System其他问题两阶段加锁数据库应用中使用第一阶段：进程试图对所需记录加锁；如果成功，就开始第二阶段；如果不成功，就释放所有加锁的记录，重新开始第一阶段第二阶段：真正读写记录，完成更新后释放锁通信死锁A和B通信过程中，A发送消息给B，但由于网络原因，B并没有收到A在等待B回复，而B在等待A发送信息，造成死锁不是典