ch3同步、通信与死锁1.ppt

一种具体的死锁检测方法，检测算法步骤如下： 1)currentavail=available； 2)如果allocation[k,*]!=0，令finish[k]=false;否则finish[k]=true； 3)寻找一个k，它应满足条件：(finish[k]==false)(request[k,*]=currentavail[*]);若找不到这样的k，则转向5)； 4)修改currentavail[*]=Currentavail[*]+allocation[k,*]; finish[k]=true;然后转向3)； 5)如果存在k(1≤k≤n),finish[k]=false,则系统处于死锁状态，并且finish[k]=false的Pk为处于死锁的进程。 * 结束所有进程的执行，重新启动操作系统。方法简单，但以前工作全部作废，损失很大。 撤销陷于死锁的所有进程，解除死锁继续运行。 逐个撤销陷于死锁的进程，回收其资源重新分派，直至死锁解除。 * 剥夺陷于死锁的进程占用的资源，但并不撤销它，直至死锁解除。可仿照撤销陷于死锁进程的条件来选择剥夺资源的进程 根据系统保存的检查点，让所有进程回退，直到足以解除死锁，这种措施要求系统建立保存检查点、回退及重启机制。 当检测到死锁时，如果存在某些未卷入死锁的进程，而随着这些进程执行到结束，有可能释放足够的资源来解除死锁。 * * * * * * * 进程通信使用的信件是一种临时性资源，如果对信件的发送和接收不加限制，可能引起死锁。 进程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个进程处于死锁状态。 ? * 不仅与系统拥有的资源数量有关，而且与资源分配策略，进程对资源的使用要求以及并发进程的推进顺序有关。 * 系统形成死锁的四个必要条件 互斥条件：进程互斥使用资源 占有和等待条件（部分分配)：申请新资源时不释放已占有资源 不剥夺条件：一个进程不能抢夺其他进程占有的资源 环路条件：存在一组进程循环等待资源的 * 破坏第一个条件 使资源可同时访问而不是互斥使用， 破坏第三个条件 采用剥夺式调度方法， 当进程在申请资源未获准许的情况下,如主动释放资源(一种剥夺式),然后才去等待。 破坏第二个条件或第四个条件 上述死锁防止办法造成资源利用率和吞吐率低。 * 采用层次分配策略(破坏条件2和4) 资源被分成多个层次 当进程得到某一层的一个资源后，它只能再申请较高层次的资源 当进程要释放某层的一个资源时，必须先释放占有的较高层次的资源 当进程得到某一层的一个资源后，它想申请该层的另一个资源时，必须先释放该层中的已占资源 * 层次策略的变种按序分配策略 把系统的所有资源排一个顺序，例如，系统若共有n个进程,共有m个资源，用ri表示第i个资源，于是这m个资源是： r1,r2……,rm 规定如果进程不得在占用资源ri(1≤i≤m)后再申请rj(ji)。不难证明，按这种策略分配资源时系统不会发生死锁。 * 银行家算法（Dijkstra,1965） 银行家拥有一笔周转资金 客户要求分期贷款，如果客户能够得到各期贷款，就一定能够归还贷款，否则就一定不能归还贷款 银行家应谨慎的贷款，防止出现坏帐 用银行家算法避免死锁 操作系统(银行家) 操作系统管理的资源(周转资金) 进程(要求贷款的客户) * 一个系统有n个进程和m种不同类型的资源,定义包含以下向量和矩阵的数据结构： ?系统每类资源总数--该m个元素的向量为系统中每类资源的数量 Resource=(R1,R2,…,Rm) ?每类资源未分配数量--该m个元素的向量为系统中每类资源尚可供分配的数量 Available=(V1,V2,…,Vm) * 最大需求矩阵--每个进程对每类资源的最大需求量,Cij表示进程Pi需Rj类资源最大数 Claim = C11 C12 C1m C21 C22 C2m Cn1 Cn1 Cnm … … … * 分配矩阵—表示进程当前已分得的资源数,Aij表示进程Pi已分到Rj类资源的个数 Allocation= A11 A12 A1m A21 A21 A21 An1