chap3 进程管理.ppt

四、死锁的预防 系统设计时确定资源分配算法,保证不发生死锁。做法是破坏产生死锁的四个必要条件之一。 1. 破坏“不可剥夺”条件 在允许进程动态申请资源前提下规定, 一个进程在申请新的资源不能立即满足而变为等待状态之前, 必须释放已占有的全部资源, 若需要再重新申请。 2.破坏“请求和保持”条件 要求每个进程在运行前必须一次性申请它所要求的所有资源，且仅当该进程所要资源均可满足时才给予一次性分配。 例如：1，2，3，…，10 P1： 申请1 申请3 申请6 … P2： 申请2 申请4 申请8 … P3 …… P10 3.破坏“循环等待”条件 采用资源有序分配法: 把系统中所有资源编号, 进程在申请资源时必须严格按资源编号的递增次序进行,否则操作系统不予分配。 4、破坏“互斥性”条件， 允许一个资源可由多个进程同时使用 缺点：对有的资源行不通，例如打印机 五、避免死锁的算法 系统运行过程中, 对进程发出的每一个资源申请进行动态检查,根据检查结果决定是否分配资源, 若分配可能引起系统死锁, 则不予分配,否则予以分配。 安全序列与安全状态： 如果在某时刻系统中所有进程可以排列一个安全序列: P1,P2,....,Pn ,刚称此时,系统处于安全状态. 所谓安全序列 P1,P2,...,Pn 是指对于Pi 1≤i≤n ,都有它所尚需最大资源数量不超过系统剩余的资源量与所有Pj j i 所占的资源量之和 。 若系统不存在这样一个安全序列, 则称系统处于不安全状态,不安全状态可能引起系统死锁。 进程 最大需求 已分配 尚需要 可用 P1 10 5 5 3 P2 4 2 2 P3 9 2 7 例如： 避免死锁的实质是如何使系统不进入不安全状态。 银行家算法 发贷款先给足能及时还者 数据结构： n：系统中进程的总数; m：资源类总数 可用资源向量 Available: ARRAY[1..m] of integer; 最大需求矩阵Max: ARRAY[1..n,1..m] of integer; 分配矩阵Allocation: ARRAY[1..n,1..m] of integer; 需求矩阵Need: ARRAY[1..n,1..m] of integer; Need[i,j] MAX[i,j]-Allocatin[i,j] 请求矩阵Request: ARRAY[1..n,1..m] of integer; 简记符号： Available, Max[i], Allocation[i], Need[i], Request[i] 算法: 当进程pi提出资源申请时, 系统执行下列步骤: 1 .若Request[i]≤Need[i],转 2 否则错误返回 2 .若Request[i]≤Available, 转 3 否则进程等待 3 .假设系统分配资源, 则有: Available: Available-Request[i]; Allocation[i]: Allocation[i]+Request[i]; Need[i]: Need[i]-Request[i]; 若系统新状态是安全的, 则分配完成 若系统新状态是不安全的, 则恢复原状态, 进程等待 为进行安全性检查, 定义数据结构： 工作向量Work:系统可提供给进程继续运行所需的各 类资源数目,有m个元素, 其初值为多少？ Finish:系统是否有足够的资源分配给进程,使之完成; 安全性检查的步骤： 1 Work: Available; Finish: false; 2 寻找满足条件的i： a.Finish[i] false; b.Need[i]≤Work; 如果不存在，则转 4 3 Work: Work+Allocation[i]; Finish[i]: true; 转 1 4 若对所有i,Finish[i] true,则系统处于安全状态, 否则处于不安全状态 进程 最大需求 已分配 尚需要 可用 P1 10 5 5 3 P2 4 2 2 P3 9 2 7 银行家算法实例 一种资源 ： 安全序列: P2, P1, P3 银行家算法实例 多种资源 ： 假定系统有五个进程 P0, P1, P2, P3, P4 和三类资源 ABC 资源总数为10,5,7, T0时刻资源分配情况为: 1 检查T0时刻的安全性 Max Allocation Need Available 进程 A B C A B C A B C A B C P0 7 5 3 0 1 0 7 4 3 3 3 2 P1 3 2 2 2