操作系统并发性死锁.ppt

并发性:死锁 1 死锁的概念 2 产生死锁的条件和处理 3 死锁的预防 4 死锁的避免 5 死锁的检测与解除 6 死锁的综合处理策略 1 死锁的概念 死锁: 指多个进程因竞争共享资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前推进。 即：一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称为死锁进程。 1 死锁的概念 死锁例子： 有一台打印机R1和一台卡片阅读机R2，进程P1占用打印机R1，进程P2占用卡片阅读机R2。如果Pl要求阅读机，P2要求打印机，则P1，P2便处于死锁状态。 1 死锁的概念 产生死锁的原因： 1．竞争系统资源 ：如上例所示 2．进程的推进顺序不当 2．进程的推进顺序不当 在进程P1和P2并发执行时，按照左图曲线①②③所示顺序推进时，两进程会顺利完成，我们称这种推进顺序是合法的。若按曲线④的顺序推进时，进入不安全区D内，两进程再推进会产生死锁。 2 产生死锁的条件和处理 互斥条件(资源独占) 请求和保持条件(部分分配，占有申请) 非剥夺条件(不可强占) 循环等待条件 2 产生死锁的条件和处理 1) 互斥使用（资源独占） 一个资源每次只能给一个进程使用 2) 不可强占（不可剥夺） 资源申请者不能强行的从资源占有者手中夺取资源，资源只能由占有者自愿释放 2 产生死锁的条件和处理 3) 请求和保持（部分分配，占有申请） 一个进程在申请新的资源的同时保持对原有资源的占有（只有这样才是动态申请，动态分配） 2 产生死锁的条件和处理 4) 循环等待 存在一个进程等待队列 {P1 , P2 , … , Pn}, 其中P1等待P2占有的资源，P2等待P3占有的资源，…，Pn等待P1占有的资源，形成一个进程等待环路 2 产生死锁的条件和处理 不让死锁发生 预防死锁（静态策略） 避免死锁（动态策略） 让死锁发生 检测死锁 解除死锁 3 死锁的预防 通过破坏死锁的四个必要条件中的一个或多个以确保系统绝不会产生死锁 1．互斥条件 ：无法破环 2．破坏请求和保持条件 ：采用预先分配的策略，详见3.1 3．破坏循环等待条件：采用有序分配的策略，详见3.2 3 死锁的预防 4．破坏非剥夺条件 ：可以收回已分给进程且尚未使用完毕的资源。2个方案： 方案1：进程在申请新的资源不能得到满足，必须释放已占有的全部资源，进入等待队列。 3 死锁的预防 方案2：进程在请求资源得不到满足，则检查这些资源是否分给了某个进程，如果此进程正在等待更多资源，则剥夺等待进程的这些资源以满足请求进程的需要；否则请求进程等待。在等待过程中，它的某些资源也有可能被剥夺。 适用资源：状态容易保存和恢复的，例如CPU寄存器、存储器空间等。 3 死锁的预防 方法有两种： 一种是要求每个进程在运行之前便申请它所需的全部资源 另一种是，规定每个进程在请求新的资源之前必须释放其已占用的全部资源 3 死锁的预防 缺点： 一是资源利用率较低； 二是有可能产生“饥饿”现象，即如果一个进程需要几种竞争较激烈的资源，而总不能完全得到满足的话，则该进程将无限期地等待 所以，这种方法在实际中用得较少 3 死锁的预防 把系统中所有资源编号，进程在申请资源时必须按资源编号的递增次序进行，否则操作系统不予分配 3 死锁的预防 4 死锁的避免 定义:系统运行过程中， 允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程； 否则，令进程等待 最具有代表性的避免死锁算法是银行家算法 4.1 系统安全状态 安全状态：如果系统能按某种顺序（如P4，P1，…,Pn, 称为安全序列）为每个进程分配其所需的资源，直至每个进程都能顺利地完成，称系统处于安全状态。若不存在这样一个安全序列称系统处于不安全状态。 安全状态一定是没有死锁发生的。 4.1 系统安全状态 安全状态之例： 有三个进程p1、p2、p3，有12台磁带机。P1共要求10台，P2共要求4台，P3共要求9台。在T0时刻，p1、p2、p3分别获得5、2、2台，尚有3台空闲。 4.1 系统安全状态 由安全状态向不安全状态的转换：如在T0以后，P3要求1台磁带机，若系统分给它一台，则系统进入不安全状态。 4.2 银行家算法 4.2 银行家算法 （2）最大需求矩阵Max。n*m矩阵，表示n个进程的每一个对m类资源的最大需求。 4.2 银行家算法 （3）分配矩阵Allocation 。n*m矩阵，表示每个进程分配的资源数。 4.2 银行家算法 （4）需求矩阵Need 。n*m矩