CH3 处理机调度与死锁1.pptVIP

(2) P1请求资源Request1(1, 0, 2) 系统按银行家算法进行检查： 1) Request1(1, 0, 2) ≤ Need1(1, 2, 2) 2) Request1(1, 0, 2) ≤ Available1(3, 3, 2) 3)系统先假定可为P1分配资源，并修改Available, Allocation1和Need1向量（见下页图）。 4)再利用安全性算法检查此时系统是否安全。 * */97 * */97 P1申请资源时的安全性检查 (3) P4请求资源Request4(3, 3, 0) 系统按银行家算法进行检查： 1) Request4(3, 3, 0) ≤ Need4(4, 3, 1); 2) Request4(3, 3, 0) ≤ Available(2, 3, 0)不成立，让P4等待。 (4) P0请求资源Requst0(0, 2, 0) 系统按银行家算法进行检查： 1) Request0(0, 2, 0) ≤ Need0(7, 4, 3); 2) Request0(0, 2, 0) ≤ Available(2, 3, 0); 3) 系统先暂定可为P0分配资源，并修改有关数据（见下页图）。 (5) 进行安全性检查 可用资源Available(2, 1, 0)已不能满足任何进程的需要，故系统进入不安全状态 * */97 * */97 为P0分配资源后的有关资源数据 * */19 习题：考虑某个系统在下表所示时刻的状态 Allocation Xax Available A B C D A B C D A B C D P0 0 0 1 2 0 0 1 2 1 5 2 0 P1 1 0 0 0 1 7 5 0 P2 1 3 5 4 2 3 5 6 P3 0 0 1 4 0 6 5 6 1、计算Need矩阵；2、系统是否处于安全状态？如果安全，请给出一个安全序列； 3、如果进程P1发来一个请求（0,4,2,0），这个请求能否被满足？如果安全，请给出一个安全序列。 3.1 处理机调度的层次 3.2 调度队列模型和调度准则 3.3 调度算法 3.4 实时调度 3.5 产生死锁的原因和必要条件 3.6 预防死锁的方法 3.7 死锁的检测与解除 * */97 资源分配图(Resource Allocation Graph) 图G=(N, E)，N为结点集合，E为边集合 N分为两个子集：进程结点P、资源节点R E中的一个边e∈E，都连接着一个P结点和一个R结点 e={pi, rj}是资源请求边，由进程pi指向资源rj，它表示进程pi请求一个单位的rj资源。 e={rj, pi}是资源分配边，由资源rj指向进程pi，它表示把一个单位的资源rj分配给进程pi。 死锁的检测 * */97 * */97 死锁定理 利用把资源分配图加以简化的方法，来检测系统处于S状态时是否为死锁状态 * */97 死锁定理 – cont. (1) 找出一个既不阻塞又非独立的进程结点Pi，若能获取所有资源则分配之，使之运行完并释放资源，相当于消去Pi所有的请求边和分配边。 (2) Pi释放资源后，再寻找另一结点Pj，继续之。 (3) 若经过简化后，所有结点都为孤立点，则认为该资源分配图是可完全简化的，否则为不可完全简化的 死锁定理： S为死锁状态的充分条件是：当且仅当S状态的资源分配图是不可完全简化的。 * */97 死锁检测中的数据结构 (1) 可利用资源向量Available 表示了m类资源中每一类资源的可用数目。 (2) 把不占用资源的进程(向量Allocation:=0)记入L表中， 即Li∪L。 (3) 从进程集合中找到一个Requesti ≤ Work的进程，做如下处理： 1) 将其资源分配图简化，释放出资源，增加工作向量Work:=Work+Allocationi。 2) 将它记入L表中。 (4) 若不能把所有进程都记入L表中， 便表明系统状态S的资源分配图是不可完全简化的。 因此，该系统状态将发生死锁。 * */97 * */97 Work := Available; L := {Li|Allocationi=0 ∩ Requesti=0} for all Li L do begin for all Requesti ≤ Work do begin Work := Work + Allocationi; Li∪L; end end deadlock := (L={p1, p2, …, pn}); (1) 剥夺资源。 从其它进程剥夺足够