HYZ-OS-2013-死锁.ppt

哲学家进餐问题回顾 * * 北京交通大学计算机学院 死锁检测 死锁：进程子集合中的所有进程都不能执行。 一种思路：检查RAG是否存在环来判定是否死锁？ 如何判定有向图存在环？ 该方法正确吗？ * * 北京交通大学计算机学院 死锁定理 系统状态S为死锁状态的充要条件是当且仅当该状态下的资源分配图是不可完全化简的 P1 P2 ○○○ R2 R1 ○○ P1 P2 ○○○ R2 R1 ○○ P1 P2 ○○○ R2 R1 ○○ * * 北京交通大学计算机学院 死锁定理说明 RAG描述了进程当前的申请资源和已分配资源的情况。不考虑将来资源申请情况。与银行家算法不同！ RAG化简的次序不影响最后结果。 如果可同时化简P1、P2，任意选择一个先化简不会导致是否“可完全化简”结论改变。 * * 北京交通大学计算机学院 死锁定理 死锁则一定存在环，反之不一定。例如： 上述例子中有空闲资源。如果假设可以满足的申请都立刻分配资源，还能找到反例吗？ p1 p2 * * 北京交通大学计算机学院 死锁定理 存在环，但不死锁 p1 p2 p3 NO * * 北京交通大学计算机学院 死锁定理 如果所有资源都只有一个单位，那么死锁当且仅当存在环。 * * 北京交通大学计算机学院 死锁检测算法 1 令Work = Available IsolatedSet={Pi∣Allocation[i] = 0∧Requesti = 0 } 2 for all Pi ? IsolatedSet do begin for all Requesti ≦ Work do begin Work = Work + Allocation[i] ; IsolatedSet = IsolatedSet ∪ {Pi } end end 3 deadlock = ～ (IsolatedSet = = {P1 , P2 , … , Pn}); * * 北京交通大学计算机学院 死锁的解除 基本方法 剥夺其它进程足够数量资源给死锁进程 撤消死锁进程（全部撤销或逐个撤销） 死锁解除策略评价指标 为解除死锁所需撤消的进程数目最小 撤消死锁进程所付出的代价最小 * * 北京交通大学计算机学院 死锁解除策略实例评析 S P1(CU1) U1 U2 Uk P2(CU2) Pk(CUk) … P1 V21 V23 V2k P3 Pk … P1 Vk1 Vk2 Vkk-1 P2 Pk-1 … P2 V12 V13 V1k P3 Pk … P3 W123 W124 W12k P4 Pk … … P1 W231 W234 W23k P4 Pk … … … P1 Wkk-11 Wkk-12 Wkk-1k-2 P2 Pk-2 … … 两种死锁解除策略评析 Cost = AverageCostForCancelProcess ×∏K Cost = ∑min{CostForCancelProcessi} * * 北京交通大学计算机学院 作业题 3.3 死锁、资源分配图有环、非安全状态之间是什么关系？ 3.4 有N个进程，每个进程访问M个资源。一定不会导致死锁的最少资源数是多少？ * * * 北京交通大学计算机学院 死锁避免 迷宫游戏（不准走回头路） * * 北京交通大学计算机学院 死锁避免 因此，在决定是否分配资源时，需要有一定的预见性。 需要找到这样一个状态，不论之后进程并发执行次序如何、资源申请情况如何，都不会发生“一定进入死锁” 的状态。 对迷宫来说，就是前方一定存在一条通向出口的道路。 这种状态就是一种安全状态。 * * 北京交通大学计算机学院 死锁避免 难点： 假如系统完全不知道进程之后的申请资源的情况，是很难确定当前是否是安全状态的。如同迷宫，身处迷宫中的人无法判断当前是否已经进入了一个死胡同。 我们假设： 系统知道每个进程可以申请各类资源的最大数目。那么，进程在之后的执行中申请资源数目就受到这个最大数的限制。 * * 北京交通大学计算机学院 死锁避免基本概念 安全状态 指系统可按某种进程序列P1, P2, …, Pn（称之为安全分配序列）来顺序地为每个进程Pi分配其所需资源满足该进程对资源的最大需求，完成并释放资源，最终使每个进程均能顺利完成。 不安全状态 系统无法找到一个安全分配序列的系统状态 * * 北京交通大学计算机学院 安全状态及向不安全状态的转换 T0时刻存在安全分配序列 P2, P1, P3 若在T0时刻应进程请求将所剩磁带机中的1台分配给P3，则系统进入不安全状态 资源名称 资源总数 可用资源量 可用资源量 磁带机 12 3 2 进程 最大需求 已分配(尚需) 已分配(尚需)