CH05---Deadlock

第5章死锁问题吕鸣松东北大学计算机科学与工程学院2018年4月《操作系统原理》2018年春季课程内容概述•死锁问题概述•死锁的预防•死锁的避免•死锁的检测与恢复•解决死锁问题的综合方法2020/11/29CH05Deadlock2死锁现象2020/11/29CH05Deadlock3死锁的例子2020/11/29CH05Deadlock4...Request(B);bRequest(A);aRelease(B);Release(A);Q...Request(A);aRequest(B);bRelease(A);Release(B);P死锁的例子2020/11/29CH05Deadlock5死锁的例子2020/11/29CH05Deadlock6死锁的例子2020/11/29CH05Deadlock7死锁的例子2020/11/29CH05Deadlock8死锁的例子2020/11/29CH05Deadlock9死锁的例子2020/11/29CH05Deadlock10不会发生死锁的例子2020/11/29CH05Deadlock11死锁的定义2020/11/29CH05Deadlock12一组进程中，每个进程都无限等待被该组进程中另一进程所占有的、因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称为死锁进程。资源类型•可重用资源（ReusableResources）•每个时刻只有一个进程使用，但不会耗尽，在宏观上各个进程轮流使用。如CPU、主存和辅存、I/O通道、外设、数据结构如文件、数据库和信号量。有可能剥夺资源：由高优进程剥夺低优进程，或OS核心剥夺进程•非可剥夺资源（ConsumableResources）•可以动态生成和消耗，一般不限制数量。但当进程得到一个资源时，该资源就不存在了。如硬件中断、信号、消息、缓冲区内的数据2020/11/29CH05Deadlock13可重用资源上的死锁•例子一•前面所举的例子•例子二•共有内存200K2020/11/29CH05Deadlock14非可剥夺资源上的死锁•两个进程通过消息机制通信•采用阻塞接收的机制•双方都等待对方生成资源2020/11/29CH05Deadlock15...1.Receive(P1,Q);2.Send(P1,R);P2...1.Receive(P2,M);2.Send(P2,N);P1死锁发生的条件•必要非充分条件（潜在死锁）•互斥(Mutualexclusion)：任一时刻只允许一个进程使用资源•请求和保持(Requestandhold)：进程在请求其余资源时，不主动释放已经占用的资源•非剥夺(Nonpreemptive)：进程已经占用的资源，不会被强制剥夺•增加一个重要条件，与上述3个条件共同构成“充要条件”（死锁发生）•环路等待(CircularWait)：环路中的每一条边是进程在请求另一进程已经占有的资源2020/11/29CH05Deadlock16资源分配图•节点•圆形节点表示进程（P）•方形节点表示资源（R），内部“点”的数量表示资源数•边•PR表示进程P请求资源R•RP表示进程P已经占用资源R2020/11/29CH05Deadlock17资源分配图2020/11/29CH05Deadlock18有环有死锁有环无死锁解决死锁问题的思路•几种不同的态度•悲观态度：努力找到一种办法，保证死锁现象永远不会发生•乐观态度：允许系统进入死锁状态，但是想办法打破死锁，从死锁状态恢复•不负责态度：忽略死锁问题，假装死锁从未发生•悲观态度死锁的预防、避免•乐观态度死锁的检测与恢复•不负责态度Windows、Linux等操作系统所采用的办法，由应用程序员处理死锁问题2020/11/29CH05Deadlock19内容概述•死锁问题概述•死锁的预防（Prevention）•死锁的避免•死锁的检测与恢复•解决死锁问题的综合方法2020/11/29CH05Deadlock20什么是死锁的“预防”？•基本思想•通过控制进程对资源的申请（控制资源分配），使得在任何时刻，“上述4个死锁条件至少有一个不成立”•条件一：互斥访问•这一条件一般不能打破2020/11/29CH05Deadlock21死锁的预防•条件二：请求和保持•方法一：进程启动前，预先分配所有的资源•方法二：在进程申请下一个（组）资源之前，必须释放已经占有的所有资源•问题一：降低进程并发度，资源使用率低•问题二：较容易出现饥饿现象•问题三：从编程的角度，很难保证一次性占有全部资源•条件三：不可抢占•如果一个进程占用了资源A且申请资源B得不到，那么进程必须释放资源A2020/11/29CH05Deadlock22死锁的预防•条件四：环路等待•解决办法：有序资源使用法•对所有资源排线性序：R1R2R3…•如果一个进程已经分配了R类型的资源，它接下来请求的资源只能是那些排在R类型之后的资源•A要获得Ri，请求Rj，而B获得Rj，请求Ri－－这个条件是不可能的，因为当ij时，资源Ri排在Rj前面•主要问题：限制了进程对资源的请求，效率低2020/11/29CH05Deadlock23内容概述•死锁问题概述•死锁的预防•死锁的避免（Avoidance）•死锁的检测与恢复•解决死锁问题的综合方法2020/11/29CH05Deadlock24死锁的避免•针对“死锁的预防”方法效率低的问题提出改进•是否可以减弱对资源分配的约束，在系统运行过程中，在每次分配资源之前，判断如果响应该次分配，是否会导致死锁。如果可能，则不分配资源2020/11/29CH05Deadlock25安全状态•安全状态•如果系统按照某种次序给每个进程分配资源，且仍能保证避免死锁的发生，则称系统处于安全状态•一个系统处于安全状态，仅当存在一个安全序列•安全序列•一个进程执行序列P1,P2,...,Pn是安全序列，如果下述条件满足：对于每个进程Pi，如果进程Pi继续申请的资源数不超过当前的空闲资源数+所有Pj进程（ji）所持有的资源数•如果这样的一个安全序列不存在，我们称系统是不安全的2020/11/29CH05Deadlock26安全状态•安全状态与死锁的关系•安全状态一定不是死锁状态•死锁状态一定是不安全状态•但不安全状态不一定是死锁状态•如果资源分配处理不当，系统可能从安全状态变为不安全状态•死锁避免的基本思想•运行时控制资源分配，使得系统永远处于安全状态2020/11/29CH05Deadlock27银行家算法•一个银行家把他的固定资金（capital）贷给若干顾客。只要不出现一个顾客借走所有资金后还不够，银行家的资金应是安全的。银行家需一个算法保证借出去的资金在有限时间内可收回•假定顾客分成若干次进行；并在第一次借款时，能说明他的最大借款额•具体算法•顾客的借款操作依次顺序进行，直到全部操作完成•银行家对当前顾客的借款操作进行判断，以确定其安全性（能否支持顾客借款，直到全部归还）•安全时，借给顾客；否则，不借2020/11/29CH05Deadlock28银行家算法•假定系统有三个进程P1，P2，P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。设在T0时刻进程P1，P2，P3已分别获得5，2，2台，尚有3台空余未分。•是否存在一个执行序列使得3个进程都能完成执行？•如果进程P3申请2个资源，是否可以满足？2020/11/29CH05Deadlock29最大需求已分配尚需可用P110553P2422P3927银行家算法•算法描述•数据结构•n：系统中进程的总数•m：资源类总数•A:ARRAY[1..m]ofinteger;(空闲资源数)•U:ARRAY[1..n,1..m]ofinteger;(已占用资源)•N:ARRAY[1..n,1..m]ofinteger;(尚需资源)•R:ARRAY[1..n,1..m]ofinteger;(本次请求的资源)2020/11/29CH05Deadlock30•主体算法银行家算法2020/11/29CH05Deadlock31(1)IFR[i][j]A[j]ThenGoto(7);//请求数超过空闲数，失败(2)IFR[i][j]N[i][j]Then错误返回;//请求数大于需要数(3)假设为pi分配资源，且修改状态为：A[j]:=A[j]-R[i][j];U[i][j]:=U[i][j]+R[i][j];N[i][j]:=N[i][j]-R[i][j];(4)检测系统目前状态是否安全？(5)如果安全，则pi进程得到资源，返回；否则：(6)恢复系统状态到(3)之前的状态：A[j]:=A[j]+R[i][j];U[i][j]:=U[i][j]-R[i][j];N[i][j]:=N[i][j]+R[i][j];(7)分配失败，pi等待银行家算法•安全检测算法•数据结构•Work:ARRAY[1..m]ofinteger•Finish:ARRAY[1..n]ofBoolean2020/11/29CH05Deadlock321.Work=A;2.For(i=1;i≤n;i++)Finish[i]=False;3.查找满足下列条件的进程i：Finish[i]=False且N[i]≤Work4.i找到了吗？5.如果没找到，则转86.Work=Work+U[i];Finish[i]=True;7.Goto3;8.所有j的Finish[j]=True?9.若是，返回安全状态；10.否则，返回不安全状态银行家算法举例2020/11/29CH05Deadlock33设系统在T0时刻系统状态为：最大资源需求已分配资源数量ABCABCP1P2P3P4P55544453002961154244231000122544剩余资源向量为：A=（2,3,3）1.T0时刻是否为安全状态？若是，请给出安全序列。2.在T0时刻若进程P2请求资源（0，3，4），是否能实施资源分配？为什么？3.若进程P4请求资源（2，0，1），是否能实施资源分配？为什么？银行家算法举例2020/11/29CH05Deadlock34最大资源需求M已分配资源数量U尚需资源NABCABCABCP1P2P3P4P55544453002961154244231000122544310214300174610（2,3,3）P4P5（4,3,7）（2,0,4）P1（7,4,11）（3,1,4）P2（9,5,13）（2,1,2）P3（13,5,15）（4,0,2）剩余资源向量为：A=（2,3,3）1.T0时刻是否为安全状态？若是，请给出安全序列。安全序列是否唯一？银行家算法举例2020/11/29CH05Deadlock35最大资源需求M已分配资源数量U尚需资源NABCABCABCP1P2P3P4P55544453002961154244231000122544310214300174610剩余资源向量为：A=（2,3,3）在T0时刻若进程P2请求资源（0，3，4），是否能实施资源分配？为什么？假设能够分配，则P2还需（1，0，0），但因为R（0，3，4）A（2，3，3）,所以不能满足。银行家算法举例2020/11/29CH05Deadlock36最大资源需求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=(0,3,2)，在此基础上：（0,3,2）P4（4,3,7）P5（7,4,11）P1（9,5,13）P2（13,5,15）P3使用银行家算法的特点•允许互斥、部分分配和不可抢占，可提高资源利用率•要求事先说明最大资源要求，在现实中很困难•考虑的进程必须是无关的，即它们