操作系统第七章

1、第第7章章 死锁死锁死锁的特征死锁的特征用于预防或者处理死锁的各种方法。用于预防或者处理死锁的各种方法。u系统拥有一定数量的资源，分布在若干竞争进程系统拥有一定数量的资源，分布在若干竞争进程之间。之间。u资源：资源：u物理资源：物理资源：内存、内存、CPU、I/O设备（打印机和设备（打印机和磁带机等）磁带机等）u逻辑资源：逻辑资源：文件、信号量等文件、信号量等u资源分成多种类型，每种类型有相同数量的资源分成多种类型，每种类型有相同数量的实例实例。如果系统中有两个。如果系统中有两个CPU，那么资源类型那么资源类型CPU就有就有2个实例。个实例。u正常操作模式下，进程按如下顺序使用资源正常操作模式

2、下，进程按如下顺序使用资源u申请（获得资源或者等待）使用释放申请（获得资源或者等待）使用释放u死锁定义：死锁定义：一组进程中，每个进程都一组进程中，每个进程都无限等待无限等待被被该组进程中另一进程所占有的资源，因而永远无该组进程中另一进程所占有的资源，因而永远无法得到资源，这种现象称为法得到资源，这种现象称为进程死锁进程死锁，这一组进，这一组进程就称为程就称为死锁进程死锁进程。u产生死锁的原因产生死锁的原因u资源不足资源不足导致的资源竞争：导致的资源竞争：多个进程所共享的资源不足多个进程所共享的资源不足，引起它们对资源的竞争而产生死锁。，引起它们对资源的竞争而产生死锁。u 并发执行并发执行的顺

3、序不当。进程运行过程中，请求和释放资的顺序不当。进程运行过程中，请求和释放资源的顺序不当，而导致进程死锁源的顺序不当，而导致进程死锁. 如如P,V操作的顺序不当操作的顺序不当u死锁死锁u可能涉及同一种类型的资源可能涉及同一种类型的资源u可能涉及不同资源类型可能涉及不同资源类型u可重用资源可重用资源u一次只能供一个进程安全地使用一次只能供一个进程安全地使用, 且不会由于且不会由于使用而耗尽使用而耗尽u例子例子: CPU、 I/O通道、主存和辅存、通道、主存和辅存、 设备、设备、文件、数据库、信号量等数据结构文件、数据库、信号量等数据结构u可消费资源可消费资源u可以可以创建创建并且可以并且可以销毁

4、销毁的资源的资源u数目没有限制数目没有限制, 当一个进程得到一个可消费资当一个进程得到一个可消费资源时源时, 这个资源就不再存在了这个资源就不再存在了u例子例子: 中断、信号、中断、信号、 消息、消息、 I/O缓冲区中的信缓冲区中的信息息u两个进程：一个访问磁盘文件两个进程：一个访问磁盘文件D，一个访问磁带设备一个访问磁带设备Tu如果执行序列为如果执行序列为:P0、P1、q0、q1、P2、q2，则发生死锁则发生死锁P2:receive(P1);send(P1, M2);P1:receive(P2);send(P2, M1);u每个进程试图从另一个进程接收消息，然后再给它发送每个进程试图从另一个

5、进程接收消息，然后再给它发送一条消息。一条消息。u如果是如果是receive阻塞接收（接收进程被阻塞直到收到消息阻塞接收（接收进程被阻塞直到收到消息），则可能发生死锁。），则可能发生死锁。u互斥条件互斥条件u指进程对所分配到的资源进行排它性使用指进程对所分配到的资源进行排它性使用, 即在一段时间内某资源即在一段时间内某资源只能由一个进程占有。如果此时还有其它进程申请该资源只能由一个进程占有。如果此时还有其它进程申请该资源,则它只能则它只能阻塞阻塞, 直至占有该资源的进程释放。直至占有该资源的进程释放。u占有且等待（请求和保持条件）占有且等待（请求和保持条件）u进程已经保持了至少一个资源进程已经

6、保持了至少一个资源, 但又提出了新的资源要求但又提出了新的资源要求, 而该资源而该资源又已被其它进程占有又已被其它进程占有, 此时请求进程阻塞此时请求进程阻塞, 但又对已经获得的其它资但又对已经获得的其它资源保持不放。源保持不放。u非抢占（非剥夺）条件非抢占（非剥夺）条件u进程已获得的资源进程已获得的资源, 在未使用完之前在未使用完之前, 不能被剥夺不能被剥夺, 只能在使用完时只能在使用完时由自己释放。由自己释放。u循环等待条件循环等待条件u在发生死锁时在发生死锁时, 必然存在一个进程必然存在一个进程-资源的封闭的环形链资源的封闭的环形链. 即进程集合即进程集合P0, P1, P2, , Pn

7、中的中的P0正在等待一个正在等待一个P1占用的资源占用的资源; P1正在等待正在等待P2占用的资源占用的资源, , Pn正在等待已被正在等待已被P0占用的资源占用的资源.P1P2资源资源A资源资源B被占有被占有被占有被占有请求请求请求请求u循环等待条件循环等待条件(环路条件环路条件)：与其它三个条件：与其它三个条件有本质的区别有本质的区别:第第1项到第项到第3项起决定作用项起决定作用u预防死锁：预防死锁：通过通过限制如何申请资源限制如何申请资源的方的方法来确保至少有一个条件不成立。法来确保至少有一个条件不成立。u避免死锁：避免死锁：根据有关进程申请资源和使根据有关进程申请资源和使用资源的额外信

8、息，确定用资源的额外信息，确定对于一个申请对于一个申请，进程是否应该等待。，进程是否应该等待。u检测死锁和恢复：检测死锁和恢复：通过算法来检测并恢通过算法来检测并恢复复u忽视此问题：忽视此问题：认为死锁不可能在系统内认为死锁不可能在系统内发生。如发生。如Unix采用这种方法。采用这种方法。u通过通过破坏产生死锁的四个条件中的一个或多个条件破坏产生死锁的四个条件中的一个或多个条件, 保保证不会发生死锁现象证不会发生死锁现象u保证互斥条件保证互斥条件u由设备（非共享资源）的固有特性所决定由设备（非共享资源）的固有特性所决定,不能被破坏不能被破坏, 应加以保证。如打印机。应加以保证。如打印机。u放弃

9、放弃“占有和等待占有和等待”u要求所有进程要要求所有进程要一次性地申请一次性地申请在整个运行过程需的在整个运行过程需的全部全部资源资源;允许进程允许进程在没有资源时才可以申请资源在没有资源时才可以申请资源。u优点优点: 简单、易于实现、安全简单、易于实现、安全u缺点缺点: u一个进程可能被阻塞很长时间，等待资源，发生饥饿一个进程可能被阻塞很长时间，等待资源，发生饥饿u资源严重浪费资源严重浪费, 进程延迟运行进程延迟运行; 如打印机如打印机:最后打印最后打印u放弃放弃“非抢占非抢占”条件条件:u可以剥夺一个进可以剥夺一个进 程占有的资源程占有的资源, 分配给其他进程分配给其他进程u一个已经保持了

10、某些资源的进程一个已经保持了某些资源的进程, 当它再提出新的当它再提出新的资源请求而不能立即得到满足时资源请求而不能立即得到满足时, 必须释放它已经必须释放它已经保持的所有资源保持的所有资源, 待以后需要时再重新申请；待以后需要时再重新申请；u适用条件适用条件u资源的状态可以很容易地保存和恢复，如资源的状态可以很容易地保存和恢复，如CPU寄寄存器、内存空间，不能适用于打印机、磁带机存器、内存空间，不能适用于打印机、磁带机u缺点缺点u实现复杂、代价大实现复杂、代价大, 反复申请反复申请/释放资源释放资源, 系统开销系统开销大大, 降低系统吞吐量降低系统吞吐量u摒弃摒弃“环路等待环路等待” u系统

11、把所有资源按类型进行线性排队。如输系统把所有资源按类型进行线性排队。如输入机入机=1,打印机打印机=2,磁带机磁带机=3,磁盘机磁盘机=4;u 所有进程对资源的请求必须严格所有进程对资源的请求必须严格按资源序号按资源序号递增的顺序提出递增的顺序提出, 从而保证任何时刻的资源分从而保证任何时刻的资源分配图不出现环路配图不出现环路u 即：如果一个进程已经分配了即：如果一个进程已经分配了R类型的资源类型的资源，它接下来请求的资源只能是那些排在，它接下来请求的资源只能是那些排在R类类型之后的资源；型之后的资源；u例：例：A要获得要获得Ri，请求请求Rj，而而B获得获得Rj，请求请求Ri : 这个条件是

12、不可能的，因为当这个条件是不可能的，因为当ij时，资时，资源源Ri排在排在Rj前面前面u摒弃摒弃“环路等待环路等待” 方法的问题方法的问题:u此方法要求资源类型序号相对稳定此方法要求资源类型序号相对稳定, 不便于添不便于添加加新类型的设备新类型的设备.u易造成资源浪费易造成资源浪费, 类型序号的安排只能考虑一类型序号的安排只能考虑一般作业的情况般作业的情况, 限制用户简单、自主地编程限制用户简单、自主地编程u限制进程对资源的请求；限制进程对资源的请求；资源的排序占用系资源的排序占用系统开销；统开销；u不需象死锁预防那样，事先采取限制措施破坏产不需象死锁预防那样，事先采取限制措施破坏产生死锁的必

13、要条件生死锁的必要条件; 在资源的在资源的动态分配过程动态分配过程中中, 采采用某种策略用某种策略防止防止系统进入系统进入不安全状态不安全状态, 从而避免从而避免发生死锁发生死锁u 定义：定义：在系统运行过程中，对进程发出的每一个在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配发生死锁，则不予分配，否则予以分配u如果一个新的进程的资源请求会导致死锁如果一个新的进程的资源请求会导致死锁, 则拒绝启动则拒绝启动

14、这个进程这个进程u如果满足一个进程新提出的一项资源请求会导致死锁如果满足一个进程新提出的一项资源请求会导致死锁, 则拒绝分配资源给这个进程则拒绝分配资源给这个进程u安全状态安全状态: 系统能按某种顺序系统能按某种顺序, 如如, 为每个进程分配所需资源为每个进程分配所需资源, 直到最大需求直到最大需求, 使每个使每个进程都可顺序完成进程都可顺序完成, 称系统处于安全状态。（称系统处于安全状态。（安安全状态一定是没有死锁发生的全状态一定是没有死锁发生的) )u安全序列安全序列: 一个进程序列一个进程序列 P P1 1，P Pn n 是安全的，是安全的，如果对于每一个进程如果对于每一个进程P Pi

15、i(1(1i in n），），它以后尚需它以后尚需要的资源量不超过系统当前剩余资源量与所有进要的资源量不超过系统当前剩余资源量与所有进程程P Pj j (j i ) (j i )当前占有资源量之和，系统处于安当前占有资源量之和，系统处于安全状态。全状态。 安全序列可以不唯一安全序列可以不唯一!u不安全状态不安全状态: 系统中不存在安全序列。系统中不存在安全序列。不安全状不安全状态不一定导致死锁。态不一定导致死锁。u关系关系u只要系统处于安全状态只要系统处于安全状态, 必定不会进入死锁状态；死锁状必定不会进入死锁状态；死锁状态是不安全状态态是不安全状态u不安全状态不一定是死锁状态（不安全状态不一

16、定是死锁状态（不安全状态可能导致死不安全状态可能导致死锁）；锁）；u银行家算法的设计思想：银行家算法的设计思想：当用户申请一当用户申请一组资源时，系统必须做出判断：如果把组资源时，系统必须做出判断：如果把这些资源分出去，系统是否还处于安全这些资源分出去，系统是否还处于安全状态。若是，就可以分配这些资源；否状态。若是，就可以分配这些资源；否则，暂时不分配。则，暂时不分配。设系统中有设系统中有m种种不同资源不同资源, n个个进程进程uAvailable向量向量: 系统中尚未分配的每种资源的总量系统中尚未分配的每种资源的总量uAvailablej: 尚未分配的资源尚未分配的资源j的数量的数量uMax

17、矩阵矩阵: 各个进程对每种资源的最大需求量各个进程对每种资源的最大需求量(进程事进程事先声明先声明)uMaxi, j（ClaimI,j): 进程进程i 对资源对资源j 的最大需的最大需求量求量uAllocation矩阵矩阵: 当前资源分配状况当前资源分配状况uAllocationi, j: 进程进程i获得的资源获得的资源j的数量的数量uNeed矩阵矩阵: 每个进程还需要的剩余资源的数量每个进程还需要的剩余资源的数量uNeedi, j: 进程进程i尚需的资源尚需的资源j的数量的数量对所有的对所有的i , j (i = 1, 2, , n; j = 1, 2, , m), 有有:uResource

18、j = Availablej + (Allocation1, j + Allocation2, j + + Allocationn, j)uMaxi, j = ResourcejuAllocationi, j = Maxi, juAllocationi, j + Needi, j =Maxi, j1.设设Work和和Finish 分别是长度为分别是长度为m 和和n 的向量，按如的向量，按如下方式进行初始化下方式进行初始化:Work = AvailableFinish i = false for i - 1,3, , n.2.查找这样的查找这样的i使其满足使其满足: (a) Finish i =

19、 false(b) Needi Work如果没有这样的如果没有这样的i存在，那么就转到第存在，那么就转到第4步步.3.Work = Work + AllocationiFinishi = True返回到第返回到第2步步.4.如果对所有的如果对所有的i，Finish i = True ，那么系统处于那么系统处于安全状态安全状态问：问：T0时刻是否时刻是否为安全状态？为安全状态？u设设Requesti 为进程为进程Pi的请求向量。如果的请求向量。如果Requesti j = k 那么进程那么进程Pi 所需要的资所需要的资源类型源类型Rj.的实例数量为的实例数量为k。当进程当进程pi 做出做出资源请

20、求时，会采取如下动作：资源请求时，会采取如下动作：u 1.如果如果Requesti Needi 转到转到 2. 否则，否则，产生出错条件，因为进程产生出错条件，因为进程Pi请求的数量已超请求的数量已超过了其所需的资源数量请求。过了其所需的资源数量请求。u 2.如果如果 Requesti Available,则转到第则转到第 3步步. 否则否则 Pi 必须等待，这是因为没有足够的必须等待，这是因为没有足够的可用资源可用资源.u3.假定系统可以分配给进程假定系统可以分配给进程Pi 所请求的资所请求的资源，并按如下方式修改状态源，并按如下方式修改状态:uAvailable = Available -

21、 Requesti;uAllocationi = Allocationi + Requesti;uNeedi = Needi Requesti;u4.系统执行安全性算法。查看：系统执行安全性算法。查看：u如果所产生的资源分配是安全的，那么进程如果所产生的资源分配是安全的，那么进程Pi可分配到其所需资源可分配到其所需资源;u如果新状态不安全，那么进程如果新状态不安全，那么进程Pi 必须等待必须等待Requesti并恢复到原先资源分配状态并恢复到原先资源分配状态u假定系统有三个进程假定系统有三个进程P1，P2，P3，共有共有12台磁带机。进程台磁带机。进程P1总共要求总共要求10台磁带机，台磁带机

22、，P2和和P3分别要求分别要求4台和台和9台。设在台。设在T0时刻进程时刻进程P1，P2，P3已分别获得已分别获得5，2，2台，尚有台，尚有3台空台空余未分。余未分。最大需求已分配尚需可用P110553P2422P39273台空闲台空闲可使可使P2结束结束P2运行，运行，并释放并释放资源资源5台空闲台空闲可使可使P1结束结束P1运行，运行，并释放并释放资源资源10台空闲台空闲可使可使P3结束结束P3称称 P2，P1，P3 为安全序列为安全序列u条件同前例，如果：条件同前例，如果：P3提出申请提出申请2台资源，问是否台资源，问是否可以满足要求？可以满足要求？解：解：先假设先假设能够满足要求且分配

23、资源，则系统状态如下：能够满足要求且分配资源，则系统状态如下：最大需求已分配尚需可用P110551P2422P3945只剩余只剩余 1 台资源，不能使任何一个进程执行结束，因而台资源，不能使任何一个进程执行结束，因而不存在安全序列，所以系统不安全，因此拒绝分配资源，不存在安全序列，所以系统不安全，因此拒绝分配资源，撤消开始的假设。撤消开始的假设。假设法假设法AllocationMaxNeedR1R2R3R1R2R3R1R2R3ABCD152001100112363421122342211420022230例：例：R1,R2,R3的数量分别为的数量分别为（9，3，6）；）；Available(1

24、,1,2)WorkNeedAllocationR1R2R3R1R2R3R1R2R3BACD16791223233412140202 2230512010101012WorkallocationR1R2R367992233 3346 FinishTrueTrueTruetrueT0时刻是否为安全状态？时刻是否为安全状态？ 安全！安全！MaxAllocationNeedR1R2R3R1R2R3R1R2R3ABCD363421122342252001101112111420021230进程进程A请求资源请求资源Request（1，0，1），），能够分配？为什么？能够分配？为什么？RequestA（1

25、，0，1）=Need(2,2,2)RequestA（1，0，1） A （2，3，3） 所以不能满足所以不能满足最大资源需求M已分配资源数量U尚需资源NABCABCABCP1P2P3P4P55544453002961154244231000122544310214300174610剩余向量剩余向量A = （2，3，3） 在的基础上，若进程在的基础上，若进程P4请求资源（请求资源（2，0，1），是），是否能实施资源分配？为什么？否能实施资源分配？为什么？解：因为解：因为R（2，0，1）=N4(2, 0, 1) 且且 A （2，3，3） 假设可以满足，则假设可以满足，则N4=(0, 0, 0), A

26、= （0，3，2），），在此基础上，在此基础上，（0, 3, 2）P4（4, 3, 7）P5（7, 4, 11）P1（9, 5, 13）P2（13, 5, 15）P3所以是安全的，因此可以实施分配所以是安全的，因此可以实施分配u优点优点u比死锁预防限制少比死锁预防限制少u无死锁检测方法中的资源剥夺无死锁检测方法中的资源剥夺, 进程重启进程重启u缺点缺点 u必须事先声明每个进程请求的最大资源必须事先声明每个进程请求的最大资源u考虑的进程必须是无关的考虑的进程必须是无关的, 也就是说也就是说, 它们执它们执行的顺序没有任何同步要求的限制行的顺序没有任何同步要求的限制u进程的数量保持固定不变，且分配

27、的资源数进程的数量保持固定不变，且分配的资源数目必须是固定的目必须是固定的u在占有资源时在占有资源时, 进程不能退出进程不能退出u如果一个系统既不采用死锁预防算法也不如果一个系统既不采用死锁预防算法也不采用死锁避免算法，那么可能会出现死锁采用死锁避免算法，那么可能会出现死锁。因此，系统应该提供：。因此，系统应该提供：u一个用来检查系统状态从而确定是否出现了一个用来检查系统状态从而确定是否出现了死锁的死锁的死锁检测算法死锁检测算法u一个用来从死锁状态中恢复的算法。一个用来从死锁状态中恢复的算法。u死锁检测死锁检测u没有任何预先限制措施没有任何预先限制措施u资源分配时不检查系统是否会进入不安全状资

28、源分配时不检查系统是否会进入不安全状态态,被请求的资源都被授予给进程被请求的资源都被授予给进程u系统可能出现死锁系统可能出现死锁u周期性检测是否出现死锁（执行检测算法）周期性检测是否出现死锁（执行检测算法）u在每个资源请求时都进行：尽早地检测，其在每个资源请求时都进行：尽早地检测，其缺点是系统的开销大（缺点是系统的开销大（CPUCPU）u 定时检测定时检测u 系统资源利用率下降时检测死锁系统资源利用率下降时检测死锁1.标记标记Allocation矩阵中一行全为零的进程；矩阵中一行全为零的进程；2.初始化一个临时向量初始化一个临时向量W，令，令W等于等于Available的向量；的向量；3.查找

29、下标查找下标i，使进程，使进程i当前未标记当前未标记且且Q的第的第i行小行小于等于于等于W，也就是说，对所有，也就是说，对所有1=k = m，Qik Wk.如果找不到这样的行，终止算法；如果找不到这样的行，终止算法；4.如果找到这样的行，标记进程如果找到这样的行，标记进程i，并把分配矩，并把分配矩阵中的相应行加到阵中的相应行加到W中，也就是说，对所有的中，也就是说，对所有的1=k=m，令，令Wk= Wk+ Aik，返回步骤，返回步骤3死锁检测方法死锁检测方法-举例举例u1.由于由于P4没有已分配的资源，标记没有已分配的资源，标记P4；u2.令令W=（0 0 0 0 1）；）；u3.进程进程P3

30、的请求小于或者等于的请求小于或者等于W，因此标记，因此标记P3，并，并令令W=W+（0 0 0 1 0）=（00 0 1 1）；）；u4.没有其他未标记的进程在没有其他未标记的进程在Q中的行小于或者等于中的行小于或者等于W，因此终止算法。，因此终止算法。 算法的结果是算法的结果是P1和和P2未标记，表示这两个进程是死未标记，表示这两个进程是死锁的。锁的。u一旦检测到死锁，就需要某种策略以恢复死锁一旦检测到死锁，就需要某种策略以恢复死锁u方法方法1：进程终止：进程终止u终止所有的死锁进程终止所有的死锁进程OS中常用方法中常用方法u一次只终止一个进程直到取消死锁循环为止一次只终止一个进程直到取消死

31、锁循环为止基于某种最基于某种最小代价原则。小代价原则。u选择原则选择原则u已消耗已消耗CPU时间最少时间最少u到目前为止产生的输出量最少到目前为止产生的输出量最少u预计剩余的时间最长预计剩余的时间最长u目前为止分配的资源总量最少目前为止分配的资源总量最少u优先级最低优先级最低u终止进程需要做很多工作终止进程需要做很多工作u方法方法2：资源抢占：资源抢占：逐步从进程中强占资源给其逐步从进程中强占资源给其它进程使用，直到死锁环被打破为止它进程使用，直到死锁环被打破为止 。考虑如。考虑如下问题：下问题：u选择一个牺牲品：选择一个牺牲品：抢占哪些资源和哪个进程，确定抢占哪些资源和哪个进程，确定抢占顺序

32、以使代价最小。抢占顺序以使代价最小。u回滚：回滚：把把每个死锁进程备份到前面定义的某些检查每个死锁进程备份到前面定义的某些检查点点, 并且重新启动所有进程并且重新启动所有进程需要系统构造重新运需要系统构造重新运行和重新启动机制行和重新启动机制u饥饿：饥饿：确保资源不会总是从同一个进程中被抢占确保资源不会总是从同一个进程中被抢占 资源分配图是一个有向图，用于表示某时刻系统资源分配图是一个有向图，用于表示某时刻系统资源与进程之间的状态资源与进程之间的状态uRAG图中有两种节点：方块和圆圈。图中有两种节点：方块和圆圈。u圆圈圆圈代表进程，代表进程，方块方块代表一类资源。代表一类资源。u方框中的点方框中的点：由于一种类型的资源可能有多个，：由于一种类型的资源可能有多个，可用方框中的一个点代表一类资源中的一个资源可用方框中的一个点代表一类资源