OUC 操作系统 第三章 处理机调度与死锁OUC 操作系统 第三章 处理机调度与死锁.ppt

数据结构的小结 Available［j］：目前资源 j可供使用的数量 Max［i,j］：进程i需要资源 j 的最大数量 Allocation［i,j］：进程i当前已获得资源 j的数量 Need［i,j］：进程i还需要多少资源 j，才能执行完 * 所以，Need［i,j］= Max［i,j］- Allocation［i,j］ * 银行家算法 设向量Requesti[1...m] 如果Requesti［j］=K，表示进程Pi需要K个资源 j Pi申请资源时，OS如下进行检查： 如果Requesti［j］≤ Need［i,j］，执行下一步；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。 如果Requesti［j］≤Available［j］，执行下一步；否则， 表示尚无足够资源，Pi须等待。 * OS假设把资源分配给进程Pi，并作如下修改： Available［j］:= Available［j］- Requesti［j］; Allocation［i,j］:= Allocation［i,j］+ Requesti［j］; Need［i,j］:= Need［i,j］- Requesti［j］; 执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才真正把资源分配给进程Pi；否则，本次假设的分配作废，恢复原来的资源分配状态，让进程Pi等待。 安全性算法 作用 查看是否存在一个安全序列 算法 设置两个数组向量 ① 工作向量Work[1..m] OS可提供给进程继续运行所需的各种资源数量 安全性算法初始时，Work := Available; Finish[1..n] 系统是否有足够的资源分配给进程，使之运行完成。 初始时 Finish［i］:=false; 当有足够资源分配给进程 i 时， 便令 Finish［i］:=true * 从所有的进程中找到一个能满足下述条件的进程: Finish［i］=false; Need［i,j］≤ Work［j］; 若找到， 执行步骤3; 否则，执行步骤4 执行以下两步修改 Finish［i］∶= true; Work［j］∶= Work［j］+ Allocation［i,j］; 因为进程Pi获得所需的资源后，便可畅通无阻的执行完，并释放出已分配给它的资源，从而使系统里的可用资源增多。 如果所有进程的Finish［i］= true都满足，则表示系统处于安全状态；否则，系统处于不安全状态 * 银行家算法举例 五个进程｛P0, P1, P2, P3, P4｝和三类资源｛A, B, C｝，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图所示 * * T0时刻的安全性： P1请求资源 P1发出请求向量Request1(1，0，2)，系统按银行家算法进行检查 Request1(1, 0, 2)≤Need1(1, 2, 2) Request1(1, 0, 2)≤Available1 (3, 3, 2) 系统先假定可为P1分配资源，并修改Available, Allocation1和Need1向量，由此形成的资源变化情况如图 中的圆括号所示 再利用安全性算法检查此时系统是否安全 * * P1申请资源时的安全性检查 存在安全序列：(P1，P3，P4，P0，P2) P4请求资源 P4发出请求向量Request4(3，3，0)，系统按银行家算法进行检查 Request4(3, 3, 0)≤Need4(4, 3, 1); Request4(3, 3, 0) Available(2, 3, 0)，让P4等待 P0请求资源 P0发出请求向量Requst0(0，2，0)，系统按银行家算法进行检查 Request0(0, 2, 0)≤Need0(7, 4, 3); Request0(0, 2, 0)≤Available(2, 3, 0); 系统先假定可为P0分配资源，并修改有关数据，如下图所示 * * 为P0分配资源后的有关资源数据 已不能满足任何进程的需要，所以无法进入安全状态， 此时不能分配资源 3.7 死锁的检测与解除 死锁的检测 资源分配图 * 每类资源有多个时的情况 死锁定理 基本思想 通过简化资源分配图, 检测死锁 基本方法 不断寻找既不阻塞又不独立的进程结点Pi 顺利时，Pi可获得所需资源，并执行完 相当于，消去连接Pi的各条边，使之成为孤立结点 死锁定理 S为死锁状态的充分必要条件是，当且仅当S状态的资源分配图是不可完全简化的 * 死锁的解除 两种方法 剥夺资源 从其他进程剥夺足够资源给死锁的进程 撤消进程（有两种方法） 撤销全部死锁进程 按某顺序逐个撤销，直到有足够资源为止 策略 撤销进程数目最小 撤销进程所付代价最小，等等 *