ch3-3.6费翔林操作系统第四版PPTch3-3.死锁.ppt

3.6 死锁 3.6.1 死锁产生 3.6.2 死锁防止 3.6.3 死锁避免 3.6.4 死锁检测和解除 3.6.1 死锁产生若干死锁的例子(1) 例１进程推进顺序不当产生死锁 设系统有打印机、读卡机各一台，被进程Ｐ和Ｑ共享。两个进程并发执行，按下列次序请求和释放资源： 进程Ｐ 进程Ｑ 请求读卡机 请求打印机 请求打印机 请求读卡机 释放读卡机 释放读卡机 释放打印机 释放打印机 ? 若干死锁的例子(2)例２ PV操作使用不当产生死锁 进程Q1 进程Q2 ……… ……… P(S1); P(s2); P(s2); P(s1); 使用r1和r2; 使用r1和r2 V(S1); V(s2); V(S2); V(S1); 若干死锁的例子(3)例３ 资源分配不当引起死锁 若系统中有m个资源被n个进程共享，每个进程都要求Ｋ个资源，而m n·K时，即资源数小于进程所要求的总数时，如果分配不得当就可能引起死锁。 若干死锁的例子(4)例４对临时性资源使用不加限制引起死锁 进程通信使用的信件是一种临时性资源，如果对信件的发送和接收不加限制，可能引起死锁。 进程P1等待进程P3的信件S3来到后再向进程P2发送信件S1；P2又要等待P1的信件S1来到后再向P3发送信件S2；而P3也要等待P2的信件S2来到后才能发出信件S3。这种情况下形成了循环等待，产生死锁。 死锁的定义 操作系统中的死锁指：如果在一个进程集合中的每个进程都在等待只能由该集合中的其他一个进程才能引发的事件，则称一组进程或系统此时发生了死锁。 例如，n个进程P1、P2，…，Pn，Pi因为申请不到资源Rj而处于等待状态，而Rj又被Pi+1占有，Pn欲申请的资源被P1占有，此时这n个进程的等待状态永远不能结束，则说这n个进程处于死锁状态。 ? 产生死锁的因素 不仅与系统拥有的资源数量有关，而且与资源分配策略，进程对资源的使用要求以及并发进程的推进顺序有关。 3.6.2死锁防止(1) 系统形成死锁的四个必要条件 互斥条件：进程互斥使用资源 部分分配条件：申请新资源时不释放已占有资源 不剥夺条件：一个进程不能抢夺其他进程占有的资源 环路条件：存在一组进程循环等待资源的 死锁防止(2) 破坏第一个条件 使资源可同时访问而不是互斥使用， 破坏第三个条件 采用剥夺式调度方法， 当进程在申请资源未获准许的情况下,如主动释放资源(一种剥夺式),然后才去等待。 破坏第二个条件或第四个条件 上述死锁防止办法造成资源利用率和吞吐率低。介绍两种比较实用的死锁防止方法。 死锁的防止(3)采用层次分配策略（破坏条件2和4） 资源被分成多个层次 当进程得到某一层的一个资源后，它只能再申请较高层次的资源 当进程要释放某层的一个资源时，必须先释放占有的较高层次的资源 当进程得到某一层的一个资源后，它想申请该层的另一个资源时，必须先释放该层中的已占资源 死锁防止(4)层次策略的变种按序分配策略 把系统的所有资源排一个顺序，例如，系统若共有n个进程,共有m个资源，用ri表示第i个资源，于是这m个资源是： r1,r2……,rm 规定如果进程不得在占用资源ri(1≤i≤m)后再申请rj(ji)。不难证明，按这种策略分配资源时系统不会发生死锁。 3.6.3死锁避免 银行家算法 银行家拥有一笔周转资金 客户要求分期贷款，如果客户能够得到各期贷款，就一定能够归还贷款，否则就一定不能归还贷款 银行家应谨慎的贷款，防止出现坏帐 用银行家算法避免死锁 操作系统（银行家） 操作系统管理的资源(周转资金) 进程（要求贷款的客户） 进程资源轨迹图 ? 银行家算法的数据结构(1) 一个系统有n个进程和m种不同类型的资源,定义包含以下向量和矩阵的数据结构： ?系统每类资源总数--该m个元素的向量为系统中每类资源的数量 Resource=(R1,R2,…,Rm) ?每类资源未分配数量--该m个元素的向量为系统中每类资源尚可供分配的数量 Avilable=(V1,V2,…,Vm) 银行家算法的数据结构(2) 最大需求矩阵--每个进程对每类资源的最大需求量,Cij表示进程Pi需Rj