HYZ-OS-2013-死锁.ppt

1,2019年9月6日星期五,北京交通大学计算机学院,操作系统（A）,北京交通大学计算机学院 何永忠 副教授,第三章：处理机调度与死锁,2,2019年9月6日星期五,北京交通大学计算机学院,第三章 处理机调度与死锁,3.1 高级、中级与低级调度 3.2 调度队列模型 3.3 调度方式与算法选择准则 3.4 调度算法 3.5 死锁产生及处理策略 3.6 死锁避免与银行家算法,3,2019年9月6日星期五,北京交通大学计算机学院,3.5 死锁产生及处理策略,3.5.1 死锁的基本概念 3.5.2 死锁产生的原因 3.5.3 死锁产生的必要条件 3.5.4 处理死锁的基本方法 3.5.5 死锁的预防 3.5.6 死锁的检测与解除,哲学家进餐问题回顾,0,3,2,1,4,0,4,3,2,1,死锁的基本概念,5,2019年9月6日星期五,北京交通大学计算机学院,死锁的基本概念,哲学家进餐问题死锁分析 哲学家都拿起左手的筷子 都申请右手的筷子无法满足阻塞等待无外界干预所有的哲学家都永远阻塞等待 死锁（Deadlock） 在多道程序系统中，并发执行的多个进程因争夺资源而造成的一种若无外力作用有关进程都将永远不能向前推进的僵持状态或僵局 在多道程序系统中，一组进程中的每一个进程都无限等待被同组的另外一个进程所占有且永远不会释放的资源的状态。,6,2019年9月6日星期五,北京交通大学计算机学院,死锁的相关概念辨析,饿死（Starvation） 资源不被一个进程永久占用的情况下，系统不能保证某个进程等待该资源的时间上界，从而使得该进程长时间等待该资源而无法在规定的时间完成 例如：短进程优先调度算法，不断有更短的进程到达时，长进程将永久等待而饿死。 活锁（Livelock） 除了进程状态可能在不断改变外，与死锁类似没有一个进程能向前执行。 例如：哲学家都拿起左手的筷子，试图拿起右手的筷子不成，等待一段时间后都放下筷子又同时拿起左手的筷子。,7,2019年9月6日星期五,北京交通大学计算机学院,死锁的后果,进程永远无法完成 进程占有的资源永远无法释放 你遇到过死锁吗？ 我的程序怎么不响应我的操作了？ 一个程序怎么一直不能完成？ 一个进程调用winrar解压文件时发生死锁,8,2019年9月6日星期五,北京交通大学计算机学院,3.5 死锁产生及处理策略,3.5.1 死锁的基本概念 3.5.2 死锁产生的原因 3.5.3 死锁产生的必要条件 3.5.4 处理死锁的基本方法 3.5.5 死锁的预防 3.5.6 死锁的检测与解除,9,2019年9月6日星期五,北京交通大学计算机学院,死锁产生原因之一：竞争资源,I/O设备共享时的死锁情况 （A）竞争非剥夺性资源,非剥夺性资源：例如打印机。一旦分配不能随时强行收回。 可剥夺资源：例如CPU。分配后可随时收回。,10,2019年9月6日星期五,北京交通大学计算机学院,死锁产生原因之一：竞争资源,进程间通信时的死锁情况 （ B ）竞争临时性资源,P1,P3,S1,S3,P2,S2,永久资源：例如打印机。始终存在的可重复使用的资源。 临时性资源：例如进程产生的消息。由一个进程产生，被另一个进程临时使用的资源。 P1: request S3; release S1; P2: request S1; release S2; P3: request S2; release S3;,11,2019年9月6日星期五,北京交通大学计算机学院,死锁产生原因之二：进程推进次序非法,P1Request(R1),P1Request(R2),P1Release(R1),P1Release(R2),P2Request(R2),P2Request(R1),P2Release(R2),P2Release(R1),1,2,3,4,12,2019年9月6日星期五,北京交通大学计算机学院,3.5 死锁产生及处理策略,3.5.1 死锁的基本概念 3.5.2 死锁产生的原因 3.5.3 死锁产生的必要条件 3.5.4 处理死锁的基本方法 3.5.5 死锁的预防 3.5.6 死锁的检测与解除,13,2019年9月6日星期五,北京交通大学计算机学院,产生死锁的必要条件,互斥条件 资源排它性使用，其他进程必须等待 请求和保持条件 请求资源未果进程虽阻塞但保持占有资源不放 不剥夺条件 进程已获资源未使用完之前不能被剥夺 环路等待条件 进程-资源环形链 P0R1 P1 R2 P2 Pn Rn P0,14,2019年9月6日星期五,北京交通大学计算机学院,3.5 死锁产生及处理策略,3.5.1 死锁的基本概念 3.5.2 死锁产生的原因 3.5.3 死锁产生的必要条件 3.5.4 处理死锁的基本方法 3.5.5 死锁的预防 3.5.6 死锁的检测与解除,15,2019年9月6日星期五,北京交通大学计算机学院,处理死锁的基本方法,预防死锁 避免死锁 检测死锁 解除死锁,16,2019年9月6日星期五,北京交通大学计算机学院,3.5 死锁产生及处理策略,3.5.1 死锁的基本概念 3.5.2 死锁产生的原因 3.5.3 死锁产生的必要条件 3.5.4 处理死锁的基本方法 3.5.5 死锁的预防与避免 3.5.6 死锁的检测与解除,17,2019年9月6日星期五,北京交通大学计算机学院,预防死锁与避免死锁,如何防止死锁的发生？ 思路：死锁的原因包括竞争资源和推进次序非法两个方面。 竞争资源的环节：用户进程提出申请，系统批准分配资源。 推进次序：调度次序,18,2019年9月6日星期五,北京交通大学计算机学院,预防死锁,预防死锁：设置对用户申请资源环节的限制，如果可以破坏产生死锁的4个必要条件之一，就可以防止死锁的发生。 互斥条件：是资源本身固有的，必须遵守该条件。,19,2019年9月6日星期五,北京交通大学计算机学院,死锁的预防策略之一,一次性申请全部资源 系统要求所有进程在开始运行之前，都必须一次性地申请其在整个运行过程所需的全部资源。 原子操作，只有当每个要求都满足时才进行一次性分配，否则等待。例如AND信号量实现哲学家进餐问题。 Swait (chi, ch(i+1) % 5) 摒弃“请求和保持”条件。,20,2019年9月6日星期五,北京交通大学计算机学院,死锁的预防策略之一,一次性申请全部资源 优点： 简单、安全且易于实现 缺点： 资源浪费：全部资源一次申请，可能部分资源在很晚才会用到。 进程延迟：如果一个将来才用的资源被其他进程占有，本进程也无法执行。,21,2019年9月6日星期五,北京交通大学计算机学院,死锁的预防策略之二,申请失败则释放所有资源 进程在需要资源时才提出请求，且得不到满足时应释放其已占有资源 摒弃“请求保持”与“不剥夺”条件（主动放弃资源） 优点：？资源利用率提高？ 缺点： 实现复杂，代价很大：如何保证已经完成的部分工作不失效 性能下降：反复地申请与释放资源、进程周转时间延长、系统吞吐量降低、系统开销增加,22,2019年9月6日星期五,北京交通大学计算机学院,死锁的预防策略之三,按升序申请资源 所有资源按类型进行线性排队，所有进程对资源的请求按资源序号递增次序提出 例如：打印机R1，磁带机R2, 扫描仪R3 。 P1: request R1; request R2; P2: request R1; request R2； P3: request R2; request R1; request R3；？ 摒弃“环路等待”条件,能证明吗？,23,2019年9月6日星期五,北京交通大学计算机学院,死锁的预防策略之三,资源排序法 优点：资源不是一次申请好，也不需要放弃已有资源，因此比前两种方法的资源利用率、系统吞吐量更好 缺点： 资源浪费不可避免：编号小的后使用。 增加新设备如何编号？临时性资源如何编号？如果是常用设备编号小些更好，但原有的设备必须重新编号。 编程者负担重，给程序员增加了过多限制,24,2019年9月6日星期五,北京交通大学计算机学院,预防死锁法的特点,预防死锁：设置对用户申请资源环节的限制，从而破坏产生死锁必要条件 静态性 进程执行过程中都必须满足相同限制条件 独立性 与当前的系统中其他进程的情况无关 缺点小结：对用户不透明，限制严格，资源利用率低,25,2019年9月6日星期五,北京交通大学计算机学院,第三章 处理机调度与死锁,3.1 高级、中级与低级调度 3.2 调度队列模型 3.3 调度方式与算法选择准则 3.4 调度算法 3.5 死锁产生及处理策略 3.6 死锁避免与银行家算法,26,2019年9月6日星期五,北京交通大学计算机学院,死锁避免,基本思想 允许进程任意申请资源，对用户不做任何限制 操作系统在进行资源分配之前，应首先进行必要的检查，且仅当确认此次分配不会导致系统进入死锁状态时才可分配，否则予以拒绝。 例如：根据车流情况确定红绿灯时间，提高了道路通行率。,27,2019年9月6日星期五,北京交通大学计算机学院,死锁避免,一个简单的方法 分配资源前，操作系统检查：当把该资源分配给申请的进程后该状态是否存在死锁 如果不死锁就分配，否则拒绝。,28,2019年9月6日星期五,北京交通大学计算机学院,死锁避免,不可行，不能一定阻止死锁发生。 两个进程 P1: request R1; request R2; P2: request R2; request R1;,29,2019年9月6日星期五,北京交通大学计算机学院,死锁产生原因之二：进程推进次序非法,P1Request(R1),P1Request(R2),P1Release(R1),P1Release(R2),P2Request(R2),P2Request(R1),P2Release(R2),P2Release(R1),1,2,3,4,可分配吗？,死锁了吗？,30,2019年9月6日星期五,北京交通大学计算机学院,死锁避免,结论：即使在分配资源后的下一状态没有死锁，但是死锁可能已经不可避免，即在将来的某个状态一定会进入死锁。,31,2019年9月6日星期五,北京交通大学计算机学院,死锁避免,迷宫游戏（不准走回头路）,32,2019年9月6日星期五,北京交通大学计算机学院,死锁避免,因此，在决定是否分配资源时，需要有一定的预见性。 需要找到这样一个状态，不论之后进程并发执行次序如何、资源申请情况如何，都不会发生“一定进入死锁” 的状态。 对迷宫来说，就是前方一定存在一条通向出口的道路。 这种状态就是一种安全状态。,33,2019年9月6日星期五,北京交通大学计算机学院,死锁避免,难点： 假如系统完全不知道进程之后的申请资源的情况，是很难确定当前是否是安全状态的。如同迷宫，身处迷宫中的人无法判断当前是否已经进入了一个死胡同。 我们假设： 系统知道每个进程可以申请各类资源的最大数目。那么，进程在之后的执行中申请资源数目就受到这个最大数的限制。,34,2019年9月6日星期五,北京交通大学计算机学院,死锁避免基本概念,安全状态 指系统可按某种进程序列（称之为安全分配序列）来顺序地为每个进程Pi分配其所需资源满足该进程对资源的最大需求，完成并释放资源，最终使每个进程均能顺利完成。 不安全状态 系统无法找到一个安全分配序列的系统状态,35,2019年9月6日星期五,北京交通大学计算机学院,安全状态及向不安全状态的转换,T0时刻存在安全分配序列 若在T0时刻应进程请求将所剩磁带机中的1台分配给P3，则系统进入不安全状态,36,2019年9月6日星期五,北京交通大学计算机学院,死锁避免基本概念,死锁与安全状态的关系 在安全状态下，一定没有死锁 如果死锁，则一定不是安全状态,37,2019年9月6日星期五,北京交通大学计算机学院,死锁避免算法（银行家算法）,检查初始状态是否安全状态 每个进程的资源申请最大数都不超过系统资源数。 每次进程申请资源，操作系统收到申请后分配资源前都进行检查 假设分配后进入安全状态，就分配。 假设分配后进入不安全状态，就不予分配。 该算法能保证系统始终不会死锁吗？,38,2019年9月6日星期五,北京交通大学计算机学院,死锁避免算法正确性,用数学归纳法证明 1）i=0 时系统初始状态是安全的 2）i=k系统是安全的，证明（在进程全部完成前）下一个状态i=k+1是安全的。 THEN 系统不可能发生死锁。,39,2019年9月6日星期五,北京交通大学计算机学院,死锁避免算法正确性,1）i=0成立。 2）i=k系统是安全的，证明系统在进程全部完成前一定转移到第k+1状态是安全状态 首先证明在进程没有全部完成前，第k+1步中一定存在一个安全状态。因为i=k状态是安全的，即存在一个安全序列，所以在进程没有全部完成前，只要按该安全序列的顺序分配资源一次资源，可转换到的第k+1状态是安全状态。 又因为每次分配资源都检查，假设分配后进入不安全状态，就不予分配（状态不变）；只有安全时才分配资源。 所以系统一定转移到状态k+1,且是安全状态。,40,2019年9月6日星期五,北京交通大学计算机学院,银行家算法,如何判定当前状态是否安全 当前可用资源是否可以满足某个未完成进程的剩余需求（最大需求-已分配）？ 如果有多个进程都满足，任选其一 将该进程已分配资源释放，将该进程标识为已完成。 重复上述步骤，如果所有进程都可以完成，当前状态是安全的；否则不安全。,41,2019年9月6日星期五,北京交通大学计算机学院,银行家算法之数据结构,可利用资源向量/请求向量m Availablej=k表示系统现有k个Rj类资源 Requestij=k表示进程Pi请求k个Rj类资源 最大需求矩阵/分配矩阵/需求矩阵n,m Maxi,j=k表示进程Pi最多需要k个Rj类资源 Allocationi,j=k表示进程Pi已有k个Rj类资源 Needi,j=k表示进程Pi尚需k个Rj类资源 工作向量 m / Finish布尔向量 n Workj=k表示系统“可”提供k个Rj类资源 Finishi 表示进程Pi可否拥有足够资源完成运行,42,2019年9月6日星期五,北京交通大学计算机学院,银行家算法之主体算法,1 进程Pi发出资源请求Requesti 2 若非RequestiNeedi，出错返回 3 若非Requesti Available，则应使Pi等待并返回 4 系统试探性地满足Pi请求，并作以下修改： Available = Available Requesti Allocationi = Allocationi + Requesti Needi = Needi Requesti 5 系统调用安全性算法进行资源分配检查，若安全则执行分配，否则恢复试探分配前状态，并使Pi等待,43,2019年9月6日星期五,北京交通大学计算机学院,银行家算法之安全性子算法,1 令Work = Available， Finish=FALSE 2 从进程集合中查找一个满足Finishi=FALSE且 Needi = Work 的进程Pi 。若找到，则可假定Pi能获得所需资源并顺利执行，故有： Work = Work + Allocationi Finishi = True 然后重复执行第2步；否则转至第3步执行 3 如果Finish=TRUE，则表示系统处于安全状态；否则系统处于不安全状态,44,2019年9月6日星期五,北京交通大学计算机学院,银行家算法应用举例之一A(待续),系统资源总量 AvailableA,B,C = 10, 5, 7 T0时刻 AvailableA,B,C = 3, 3, 2 安全分配序列 ?,45,2019年9月6日星期五,北京交通大学计算机学院,银行家算法应用举例之一B(待续),系统资源总量 AvailableA,B,C = 10, 5, 7 T0时刻 AvailableA,B,C = 3, 3, 2 安全分配序列 ?,46,2019年9月6日星期五,北京交通大学计算机学院,银行家算法应用举例之一C(待续),系统资源总量 AvailableA,B,C = 10, 5, 7 T0时刻 AvailableA,B,C = 3, 3, 2 安全分配序列 ?,47,2019年9月6日星期五,北京交通大学计算机学院,银行家算法应用举例之一D(待续),系统资源总量 AvailableA,B,C = 10, 5, 7 T0时刻 AvailableA,B,C = 3, 3, 2 安全分配序列 ?,48,2019年9月6日星期五,北京交通大学计算机学院,银行家算法应用举例之一E(待续),系统资源总量 AvailableA,B,C = 10, 5, 7 T0时刻 AvailableA,B,C = 3, 3, 2 安全分配序列 ?,49,2019年9月6日星期五,北京交通大学计算机学院,银行家算法应用举例之一F(待续),系统资源总量 AvailableA,B,C = 10, 5, 7 T0时刻 AvailableA,B,C = 3, 3, 2 安全分配序列,50,2019年9月6日星期五,北京交通大学计算机学院,银行家算法应用举例之二A(待续),T1时刻 AvailableA,B,C = 3, 3, 2=2, 3, 0 进程P1发出资源请求Request1(1,0,2) Need1(1,2,2) 安全分配序列 ?,3 0 2,0 2 0,51,2019年9月6日星期五,北京交通大学计算机学院,银行家算法应用举例之二B(待续),进程P1发出资源请求Request1(1,0,2)2, 3, 0 安全分配序列 ?,52,2019年9月6日星期五,北京交通大学计算机学院,银行家算法应用举例之二C(待续),进程P1发出资源请求Request1(1,0,2)2, 3, 0 安全分配序列 ?,53,2019年9月6日星期五,北京交通大学计算机学院,银行家算法应用举例之二D(待续),进程P1发出资源请求Request1(1,0,2)2, 3, 0 安全分配序列 ?,54,2019年9月6日星期五,北京交通大学计算机学院,银行家算法应用举例之二E(待续),进程P1发出资源请求Request1(1,0,2)2, 3, 0 安全分配序列 ?,55,2019年9月6日星期五,北京交通大学计算机学院,银行家算法应用举例之二F(待续),进程P1发出资源请求Request1(1,0,2)2, 3, 0 安全分配序列,56,2019年9月6日星期五,北京交通大学计算机学院,银行家算法应用举例之三(待续),T2时刻 AvailableA,B,C = 2, 3, 0 进程P4发出资源请求Request4(3,3,0) Available(2,3,0)，故让P4等待,57,2019年9月6日星期五,北京交通大学计算机学院,银行家算法应用举例之四(续完),T3时刻 AvailableA,B,C = 2, 3, 0 =2, 1, 0 进程P0发出资源请求Request0(0,2,0) Need0(7,4,3) 尝试分配，则系统进入不安全状态,0 3 0,7 2 3,58,2019年9月6日星期五,北京交通大学计算机学院,银行家算法,在一个安全状态下：存在一个安全序列或者多个安全序列。 如果在计算是否存在安全序列时，如果有两个（或者多个）进程的最大资源需求都可以满足，那么任意选择一个不会导致不同的判定结果。,59,2019年9月6日星期五,北京交通大学计算机学院,3.5 死锁产生及处理策略,3.5.1 死锁的基本概念 3.5.2 死锁产生的原因 3.5.3 死锁产生的必要条件 3.5.4 处理死锁的基本方法 3.5.5 死锁的预防 3.5.6 死锁的检测与解除,60,2019年9月6日星期五,北京交通大学计算机学院,资源分配图RAG,G=(PR, E) 资源请求边 e = 资源分配边 e = ,61,2019年9月6日星期五,北京交通大学计算机学院,资源分配图RAG转换规则,申请资源时：之前没有未决申请；可以一次申请一种资源的多个单位；增加一个或者多个申请边。 获取资源时：如果申请的资源空闲，申请边改为占有边。 释放资源时：之前没有未决申请；可以释放部分单位；删除占有边。,62,2019年9月6日星期五,北京交通大学计算机学院,资源分配图RAG转换举例,p1,p1,p1,Request,Acquisition,Release,63,2019年9月6日星期五,北京交通大学计算机学院,死锁检测,死锁：进程子集合中的所有进程都不能执行。 一种思路：检查RAG是否存在环来判定是否死锁？ 如何判定有向图存在环？ 该方法正确吗？,64,2019年9月6日星期五,北京交通大学计算机学院,死锁定理,系统状态S为死锁状态的充要条件是当且仅当该状态下的资源