处理机调度与死锁培训课件.ppt

精品 处理机死锁 第三章 处理机调度与死锁 第三章 处理机调度与死锁 3.1 处理机调度的基本概念 3.2 调度算法 3.3 实时调度 3.4 多处理机系统中的调度 3.5 产生死锁的原因和必要条件 3.6 预防死锁的方法 3.7 死锁的检测与解除 精品 上节回顾 死锁原因：竞争资源，顺序不当 死锁的必要条件：四个，P91 解决死锁的方法： 预防、避免、检测+解除 预防死锁三种方法：P94 避免死锁： 安全状态 银行家算法 安全性检查 精品 3.6.2 系统安全状态 1. 安全状态 所谓安全状态，是指系统能按某种进程顺序(P1, P2, …，Pn)(称〈P1, P2, …, Pn〉序列为安全序列)，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。 精品 2. 银行家算法 （1） 数据元素 可用资源Available 最大需求Max 已分配Allocation 剩余需求Need 当前请求Request 精品 银行家算法流程 1、两个检查： Requesti［j］≤Need［i,j］ Requesti［j］≤Available［j］ 2、模拟分配 Available［j］∶=Available［j］-Requesti［j］; Allocation［i,j］∶=Allocation［i,j］+Requesti［j］; Need［i,j］∶=Need［i,j］-Requesti［j］; 3、安全性检查，通过则执行分配，否则拒绝 精品 3. 安全性算法 1、寻找进程P，Need = Available 若所有 Need Available，非安全状态，返回 2、P的所有资源归还到可用资源，Available + Max，将P加入安全序列，重复步骤1。 3、找到安全序列——出于安全状态——返回 精品 4. 银行家算法之例 假定系统中有五个进程｛P0, P1, P2, P3, P4｝和三类资源｛A, B, C｝，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图 3-15 所示。 精品 (1) T0时刻的安全性： 图 3-16 T0时刻的安全序列 精品 (2) 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向量，由此形成的资源变化情况如图 3-15 中的圆括号所示。 ④ 再利用安全性算法检查此时系统是否安全。 精品 精品 图 3-17 P1申请资源时的安全性检查 精品 (3) P4请求资源：P4发出请求向量Request4(3，3，0)，系统按银行家算法进行检查： ① Request4(3, 3, 0)≤Need4(4, 3, 1); ② Request4(3, 3, 0) = Available(2, 3, 0)，让P4等待。 (4) P0请求资源：P0发出请求向量Requst0(0，2，0)，系统按银行家算法进行检查： ① Request0(0, 2, 0)≤Need0(7, 4, 3); ② Request0(0, 2, 0)≤Available(2, 3, 0); ③ 系统暂时先假定可为P0分配资源，并修改有关数据，如图 3-18 所示。 精品 精品 精品 3.7 死锁的检测与解除 3.7.1 死锁的检测 1. 资源分配图(Resource Allocation Graph) 图 3-19 每类资源有多个时的情况 精品 (2) 凡属于E中的一个边e∈E，都连接着P中的一个结点和R中的一个结点，e={pi, rj}是资源请求边，由进程pi指向资源rj， 它表示进程pi请求一个单位的rj资源。e={rj, pi}是资源分配边，由资源rj指向进程pi, 它表示把一个单位的资源rj分配给进程pi。 精品 2. 死锁定理 图 3-20 资源分配图的简化 精品 3. 死锁检测中的数据结构 (1) 可利用资源向量Available，它表示了m类资源中每一类资源的可用