第11课进程间的制约关系(死锁问题).pptVIP

操作系统 Lecture 11 死锁 今日目标 死锁 死锁的基本概念 死锁产生的必要条件 死锁的预防 死锁的避免 死锁的定义 一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到资源，这种现象称为进程死锁，这一组进程就称为死锁进程。 关于死锁的一些概念 参与死锁的进程最少是两个 （两个以上进程才会出现死锁） 参与死锁的进程至少有两个已经占有资源 参与死锁的所有进程都在等待资源 注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。 回顾:生产者-消费者问题中产生的死锁 P、V信号量解法中，为什么把同步的p和互斥的p交换顺序后会产生死锁? 生产者-消费者问题 P： 生产产品; P(S1); P(mutex) 送产品到缓冲区； V(mutex) V(S2); Q： P(S2); P(mutex) 取缓冲区中产品; V(mutex) V(S1); 消费产品; 生产者-消费者问题 P： 生产产品; P(mutex)；  P(S1); 送产品到缓冲区； V(mutex) V(S2); Q： P(S2); P(mutex) 取缓冲区中产品; V(mutex) V(S1); 消费产品; 当缓冲区满时 生产者-消费者问题 P： 生产产品; P(mutex)；  P(S1); 送产品到缓冲区； V(mutex) V(S2); Q： P(S2); P(mutex) 取缓冲区中产品; V(mutex) V(S1); 消费产品; 死锁产生的必要条件 互斥条件 非剥夺条件 占用并等待 循环等待 解决死锁的方法 不考虑此问题: 忽略死锁(鸵鸟政策) 不让死锁发生： 静态策略 设计合适的资源分配算法，不让死锁发生---预防死锁 动态策略 即将进入不安全状态时才加以限制---避免死锁。 让死锁发生：检测死锁并恢复 死锁预防 在系统设计时确定资源分配算法，保证不发生死锁。具体的做法是破坏产生死锁的四个必要条件之一 互斥条件 非剥夺条件 占用并等待 循环等待 破坏“部分分配（占用并等待）条件” 采用的办法是系统对进程实行一次性分配方案，即一个进程总是合盘提出总的资源需求，系统要么分配给它所需要的全部资源，要么一个也不给它。 缺点: 在许多情况下，一个进程在执行之前不可能提出它所需要的全部资源。 资源利用率可能比较低（许多资源可能已分配很长时间都没有用。） 无论所需资源何时用到，一个进程只有在所有要求资源都得到满足之后才开始执行，所以可能发生饥饿（一个进程如果需要多个常用资源则可能永久等待） 降低了进程的并发性 破坏“非剥夺条件” 采用的办法是允许别的进程从占用进程手中强抢所占用的资源。 破坏“循环等待条件” 采用的办法是把系统中所有资源编号，进程在申请资源时必须严格按资源编号的递增次序进行，否则操作系统不予分配. 假定把不同编号的资源i和j分配给了进程A和B。那么如果ij，A就不允许再申请资源j；如果ij，B就不允许再申请资源 i 。这样就形成不了资源申请的循环等待环路 。 （哲学家就餐问题） 死锁的避免 基本思想：一般情况下它对进程的资源申请不加限制，只是在即将进入不安全状态时才加以限制。采取一种动态策略。 死锁避免算法：银行家算法 死锁避免定义 在系统运行过程中，接到一个进程的资源请求时，总是根据当时资源的使用情况，按照一定的算法去模拟分配，探测分配的结果。只有在探测结果表明绝对不会出现死锁时，才真正接受进程的这次资源请求 安全状态和不安全状态 若能在有限时间内，保证所有进程得到自己需要的全部资源，那么称系统此时处于“安全状态”；否则称系统处于“不安全状态”。很明显，在系统处于安全状态时，绝对不会发生死锁；在系统处于不安全状态时，系统有可能发生死锁。 银行家算法 银行家算法对进程的要求 必须预先说明自己对资源的最大需求量； 只能一次一个地申请所需要的资源； 若已获得了资源的最大需求量，那么应在有限时间内使用完毕，并归还系统。 实施银行家算法时系统的承诺 若进程对资源的最大需求量没超过该资源的总量，应保证接纳这个进程，不得拒绝它； 在接到一个进程对资源的请求时，有权根据当前资源的使用情况暂时加以拒绝（即阻塞该进程）。但应保证在有限的时间内让它得到所需要的资源。 单种资源银行家算法的基本思想 在安全状态下，系统接到进程的资源请求后，先假定接受这一请求，把需要的资源分配给这个进程。 在这一假设下，检查每个进程对资源的还需要数。看能否找到一个进程，其还需数