并发进程控制讲义-南京大学.PPT

死锁 死锁的定义 为避免与硬件故障以及其他程序性错误混淆，在定义死锁前给定六个假设： 任意一个进程要求资源的最大数量不超过系统能提供的最大量 如果一个进程要求的资源均得到满足，那么，它一定能够在有限时间内结束 一个资源在任何时间最多只被一个进程所占有 一个进程一次申请一个资源，且只有在申请资源得不到满足时才处于等待状态 一个进程结束时释放它占有的全部资源 系统具有有限个进程和有限个资源 一组进程处于死锁状态是指：如果在一个进程集合中得每个进程都在等待只能由该集合中其他一个进程才能引发的事件，则称一组进程或系统此时发生了死锁。 死锁 由于死锁会造成很大的损失，因此必须花费额外的代价解决死锁问题，常见的解决死锁问题的方法： 死锁的防止 死锁的避免 死锁的检测和恢复（解除） 死锁 死锁的防止 死锁产生的四个条件，1971年Coffman 互斥条件 占有和等待条件 不剥夺条件 循环等待条件 破坏死锁的任一条件，可以防止死锁 常见的死锁防止方法 静态分配策略，破坏第二个条件，资源利用率低 层次分配策略，破坏第四个条件 死锁存在的必要条件 死锁 死锁的避免 破坏死锁条件能够防止死锁，但将导致低效的进程运行和资源使用率 死锁的避免不是通过对进程随意强加一些规则，而是通过对每一次资源申请进行认真的分析来判断它是否能够完全的分配，从而避免死锁的发生 常见的方法： 资源轨迹图 银行家算法 死锁 死锁的避免 资源轨迹图 A, B两个进程；打印机、绘图仪两种资源 t时刻，如何分配资源？ B A I8 I7 I6 I5 I1 I2 I3 I4 绘图仪 打印机 打印机 绘图仪 p q r s t ╳ ╳ √ A,B进程同时拥有一个资源 A,B进程同时拥有两个资源 死锁 资源轨迹图的优缺点 优点： 比较直观和简单 缺点： 只适合在两个进程间进行判断 只适合描述只有单个实例的资源 死锁 死锁的避免 银行家算法 前提条件： 每个客户必须预先说明自己所要求的最大资金量； 每个客户每次提出部分资金量申请和获得分配； 如果银行满足了客户对资金的最大需求量，那么，客户在资金运作后，应在有限时间内全部归还； 若一个所要求的最大资金量不超过其资金总量，则银行家一定接纳该客户，并可处理他的资金需求；银行在收到一个客户的资金申请时，可能因资金不足而让客户等待，但保证在有限时间内让客户获得资金。 关键问题是，对资金申请进行判断，又称“资源分配拒绝法” 死锁 银行家对资金申请的判断依据是，如果满足该申请，是否存在一个安全状态序列使所有客户均能得到所有的贷款（所有进程得到其所需的全部资源并执行终止） 例： 银行家有10个单位的资金，共有四个客户需要申请贷款，每个客户均提供了一个贷款额度，如下图所示： 客户 已贷款 最大 张三 1 6 李四 1 5 王五 2 4 赵六 4 7 可用：2 ①是否可满足李四请求1个单位资金？ ②是否可满足王五请求1个单位资金？ 客户 已贷款 最大 张三 1 6 李四 2 5 王五 2 4 赵六 4 7 可用：1 死锁 ①判断是否可以满足李四一个单位的资金申请 如果分配1个单位的资金给李四，则资金分配状态如下： 在该状态下，可用资金无法满足任何一个客户的最大贷款额度，因此该状态是不安全的，应拒绝李四的贷款申请，让李四等待。 客户 已贷款 最大 张三 1 6 李四 1 5 王五 3 4 赵六 4 7 可用：1 死锁 ②判断是否可以满足王五一个单位的资金申请 如果分配1个单位的资金给王五，则资金分配状态如下： 在该状态下，存在一个安全序列，“王五、李四、张三、赵六”。因此该状态是安全的，可以满足王五的资金申请。 死锁 多种资源的银行家算法 定义数据结构描述进程和资源的相关信息 系统每类资源的总数——m个元素的向量，每个分量对应一类资源的总数：Resource = (R1, R2, …, Rm)； 每类资源未分配数量——m个元素的向量，每个分量对应一类资源尚可分配的数量：Available = (V1, V2, …, Vm)； 最大需求矩阵——n*m，行代表n个进程，列代表m类资源，Claim，其中元素Cij表示进程Pi需要Rj类资源最大数； 分配矩阵——n*m，行代表n个进程，列代表m类资源，Allocation，其中元素Aij表示进程Pi已分得Rj类资源得数量； 死锁 安全性测试算法执行举例 设有五个进程{P0, P1, P2, P3, P4}和A, B, C三类资源，A类资源共有10个，B类资源共有5个，C类资源共有7个，在T0时刻系统的资源分配情况如下： Resource = (10, 5, 7) Available = (3, 3, 2) 0 1 0 0 0 0 2 1 1 0 0 2 Claim = 7 5 3 3 2