第三单元 - 死 锁.pptVIP

第3章 死 锁 本章内容提要 资源 死锁概念 死锁的预防 死锁的避免 死锁的检测和恢复 处理死锁的综合方式 3.1 资源 3.1.1 资源使用模式 ●申请 ●使用 ●释放 3.1.2 可剥夺资源与不可剥夺资源 ●按占有方式划分： ▲可剥夺资源 当该资源被某进程拥有后，其它进程仍可以把它剥夺过去为己所用，并且不会产生任何不良影响。例如，内存就是可剥夺资源。 ▲不可剥夺资源 该资源一旦被某进程占有，则其它进程不能强行抢占，必须由拥有者自动释放，否则会引起相关计算的失效。如光盘刻录机。 ◎死锁和不可剥夺资源有关 ●按其它方式划分 3.2 死锁概念 3.2.1 什么是死锁 1．死锁示例 2．死锁定义 死锁 是指在一个进程集合中的每个进程都在等待仅由该集合中的另一个进程才能引发的事件而无限期地僵持下去的局面。 计算机系统产生死锁的根本原因就是资源有限且操作不当 死锁的危害 系统瘫痪 资源浪费 …… 什么是死锁 有两个进程A和B，竞争两个资源R和S，这两个资源都是不可剥夺资源。 进程A 进程B …… …… 申请并占用R 申请并占用S 申请并占用S 申请并占用R …… …… 释放R 释放S 释放S 释放R …… …… 什么是死锁 进程推进顺序对引发死锁的影响 3.2.2 死锁的条件 ●产生死锁的4个必要条件 1．互斥条件 2．占有且等待条件 3．不可抢占条件 4．循环等待条件 ▲只要有一个必要条件不满足，则死锁就可以排除。 3.2.3 资源分配图 1．资源分配图的构成 由结对组成： G = (V, E) V是顶点的集合，E是边的集合。 顶点集合可分为两部分： P={p1, p2, …, pn} 由系统中所有活动进程组成 R={r1, r2, …, rm} 由系统中全部资源类型组成 有向边pi → rj称为申请边 有向边rj → pi 称为赋给边 在资源分配图中，通常用圆圈表示每个进程，用方框表示每种资源类型。 2．资源分配图示例 （1）集合P, R和E如下： P={p1, p2, p3} R={r1, r2, r3, r4} E={p1→r1, p2→r3, r1→p2, r2→p2, r2→p1, r3→p3} （2）资源数量 分别为1，2，1，3 （3）进程状态 该图不含环路，没有死锁 3．环路与死锁 ① 如果每类资源的实体都只有一个，那么图中出现环路就说明死锁了。 环路与死锁 3.2.4 处理死锁的方法 ■利用某些协议预防或避免死锁，保证系统不会进入死锁状态。 ■允许系统进入死锁状态，然后设法发现并克服它。 ■完全忽略这个问题，好像系统中从来也不会出现死锁。 3.3 死锁的预防 3.3.1 破坏互斥条件 3.3.2 破坏占有且等待条件 ●预分资源策略——静态分配 ●“空手”申请资源策略——不占有资源时才可以申请资源 ▲存在以下4个主要缺点 ◎不可预测 ◎利用率低 ◎ 降低并发性 ◎“饥饿” 现象 3.3.3 破坏非抢占条件 隐式抢占方式 抢占等待者资源 3.3.4 破坏循环等待条件 ①资源有序分配策略 ●资源编号 设R={r1, r2, …, rm}，表示一组资源 定义一对一的函数F：R→N，N是一组自然数。 如：F（磁带机）= 1，F（磁盘机）= 5，F（打印机）= 12 ●依序分配 约定：所有进程对资源的申请严格按照序号递增的次序进行。 破坏循环等待条件 ②先弃大，再取小 一个进程申请资源rj，它应释放所有满足F(ri)≥F(rj) 关系的资源ri 3.4 死锁的避免 ●排除死锁的动态策略。关键是确定资源分配的安全性 3.4.1 安全状态 在当前分配状态下，进程的安全序列{P1, P2,…, Pn}是： 若对于每一个进程Pi（1≤i≤n），它需要的附