现代操作系统第3章死锁.ppt

死锁,第3章,1,3.1. 资源 3.2. 死锁概述 3.3. 驼鸟算法 3.4. 死锁检测和死锁恢复 3.5. 死锁避免 3.6. 死锁预防 3.7. 其他问题,死锁的概念：可能死锁,我需要A和B道,我需要B和C道,我需要C和B道,我需要D和A道,发生死锁,停止直到B可以通车,停止直到C可以通车,停止直到D可以通车,停止直到A可以通车,资源,一些独占性资源 打印机 磁带 系统内部表中的表项 进程需要一个合理的顺序去访问资源 假设一个进程拥有资源 A 并请求资源 B 同时另一个进程拥有B 并请求A 两个进程都被阻塞,并且一直处于这样的状态,4,资源 (1),死锁有可能出现,当 进程对设备、文件等取得了排他性访问权时 我们把这类需要排他性使用的对象称为资源resources 可抢占资源 可以从拥有它的进程中抢占而不会产生任何副作用 不可抢占资源 指在不引相关的计算失败的情况下，无法把它从占有它的进程处抢占过来,5,进程推进顺序不当产生死锁,进程P 请求读卡机 请求打印机 释放读卡机 释放打印机,进程Q 请求打印机 请求读卡机 释放读卡机 释放打印机,PV操作使用不当产生死锁,进程Q1 . P(S1) P(S2) . 使用r1和r2 V(s1) V(s2) ,进程Q2 . P(S2) P(S1) . 使用r1和r2 V(s2) V(s1) ,同类资源分配不当,若系统中有m个资源被n个进程共享，当每个进程都要求K个资源，而mn*k时，即资源数小于进程所要求的总数时，如果分配不得当就可能引起死锁 例如，m=5 n=5 k=2，分配策略为每个进程轮流分配，首先第一次每个进程都分配一个，在第二轮分配时就会出现死锁,资源 (2),使有一人资源所需要的事件顺序可以用抽象的形式表示如下： 请求资源 使用资源 释放资源 若请求资源不可用，则请求进程被迫等待 请求进程可能被阻塞 资源请求返回一个错误代码,10,死锁的概述,形式化定义: 如果一个进程集合中的每个进程都在等待只能由该进程集合中的其他进程才能引发的事个，那么该进程集合就是死锁 在大多数情况下，每个进程所等待的事件是释放该进程集合中其他进程所占有的资源 没有一个进程可以 运行 释放资源 被唤醒,11,死锁的正式定义,假设1：任意一个进程要求资源的最大数量不超过系统能提供的最大量 假设2：如果一个进程在执行中所提出的资源要求能够得到满足，那么，它一定能在有限的时间内结束 假设3：一个资源在任何时间最多只有一个进程所占有 假定4：一个进程一次申请一个资源，且只在申请资源得不到的满足时才处于等待状态。（即不考虑人工干预，等 待外设的情况）,死锁的正式定义,假定5：一个进程结束时释放它占有的全部资源 假定6：系统具有有限个进程和有限个资源 定义：如果一个进程集合中的每个进程都在等待只能由该集合中的其他一个进程才能引发的事件，则称一组进程或系统此时发生了死锁。,竞争资源引起进程死锁,可剥夺和非剥夺性资源 竞争非剥夺性资源 竞争临时性资源 永久性资源：可以被多个进程多次使用（可再用资源） 可抢占资源 不可抢占资源 临时性资源：只可使用一次的资源；如信号量, 中断信号，同步信号等（可消耗性资源） “申请-分配-使用-释放”模式,死锁的四个条件,互斥条件 每个资源要么已经分配给了一个进程，要么就是可用的 占有和等待条件 已经得到了某个资源的进程可以再请求新的资源 不可抢占条件 已经分配给一个进程的资源不能强制性地被抢占，它只能被占有它的进程显式地释放 环路等待条件 一定有由两个或两个以上的进程组成的一条环路 该环路中的每个进程都在等待着下一个进程所占有的资源,15,死锁建模(2),有向图建模（资源分配图） 资源 R 分配给进程A 进程B 请求或等待资源S 进程 C和D为得到资源T 和U处于死锁,16,死锁建模(3),处理死锁的策略 忽略问题 检测并恢复 动态避免 仔细对资源分配 防止 破坏引起死锁的四个必要条件之一,17,死锁建模 (4),死锁是如何发生的,18,A B C,死锁建模(5),死锁是如何避免的,19,(o) (p) (q),驼鸟算法,假装根本没有问题发生 可以接受，如果 如果死锁发生频率低 防止死锁的成本太高了 UNIX 和Windows 采用此算法 它是下面两者的折衷 方便性 正确性,20,每种类型一个资源的死锁检测 (1),注意资源的所属和请求关系 如果图中包含一个或一个以上的环，那么死锁就存在,21,资源分配图化简,化简：一个进程的所有资源要求均能被满足，则该进程得到其所需全部资源从而不断取得进展，直至完成全部任务并释放出全部资源。 在有向图中找到既非阻塞又非孤立的结点，分配它所需的全部资源后，当它继续执行并完成然后释放其全部资源而使之成为孤立结点。 把孤立结点释放的资源分配给阻塞进程，使之能继续运行，并且在有限时间后完成，再释放其全部资源而成为新的鼓励结点。 经过一系列上述步骤，若能消去图中所有的边，使所有进程都成为孤立结点，则图可完全化简。否则为不可完全化简。,死锁定理：当且仅当系统某状态S所对应的资源分配图是不可化简的，则S是死锁状态。而不可被化简的进程即是被死锁的进程。反之，若状态S所对应的资源分配图是可化简的，则S是安全状态。 资源分配图的化简结果与化简顺序无关，最终结果是相同的,每种类型多个资源的死锁检测(2),死锁检测算法的数据结构,24,每种类型多个资源的死锁检测(3),死锁检测算法的例子,25,从死锁中恢复(1),利用抢占恢复 将某一资源从一个进程强行取走给另一个进程使用 取决于该资源本身的特性。 利用回滚恢复 周期性对进程进程进行检查点检查 使用检查点保存资源状态 如果发现死锁回滚进程,26,从死锁中恢复(2),通过杀死进程恢复 最直接也是最简单的解决死锁的方法 杀掉环中的一个进程 环外的进程释放其资源 杀死可以从头开始重新运行而且不会带来副作用的进程,27,资源轨迹图,替代方案,3.5.2 产生死锁的必要条件,互斥：竞争的资源一次只能被一个进程使用。 请求和保持条件；当一个进程已经占有了一些资源，同时又要申请新的资源，若新资源申请失败，进程将占有资源且阻塞等待。 不剥夺条件（不可强占）:一个资源仅能被占有它的进程所释放,而不能被别的进程强行强占 环路等待条件:若干个进程构成环行请求链,其中每个进程均占有若干种资源中的某一种,同时每个进程还要求(链上)下一进程所占有的资源. 以上前三个条件是死锁存在的必要条件，但不是充分条件。第四个条件是前三个条件同时存在时产生的结果。所以这些条件不是完全 独立的,3.5.2 产生死锁的必要条件,破坏第一个条件（互斥条件），使资源可同时访问而不是互斥使用，是简单的方法。磁盘可以用这种方法管理，但许多资源往往是不能同时访问的，这种做法许多场合行不通,3.5.2 产生死锁的必要条件,采用抢占式的调度方法可以破坏第三个条件（不剥夺条件），但剥夺调度方法目前只适用于对主存资源和处理器资源的分配。 比较实用的方法是破坏第二个条件或第四个条件,3.5.2 产生死锁的必要条件,静态分配策略（破坏占有和等待条件） 层次分配策略（阻止环路等待条件）：一个进程得到某一层的一个资源后，它只能再申请在较高一层的资源。,3.5.3 处理死锁的基本方法,预防死锁(破坏4条件之一，缺点：低效)。 避免死锁(属于事先预防，在资源的动态分配过程中，用某种方法去防止系统进入不安全状态) 。 检测死锁( 不事先采取任何措施，也不必检查是否进入不安全区，而是允许系统在运行的 过程中发生死锁。但可以通过系统所设置的检测机构，实时检测出死锁的发生，并精确的确定与死锁有关的进程和资源；然后，采取适当措施从系统中将已经发生的死锁清除掉) 。 解除死锁(与检验死锁相配套的一套措施) 。,3.5.3 处理死锁的基本方法,1.预防死锁的方法 在系统设计时确定资源分配算法，保证不发生死锁。具体的做法是破坏产生死锁的四个必要条件之一 1)资源一次性分配；(破坏请求和保持条件) 2)可剥夺资源；即当某进程新的资源未满足时，释放已占有的资源(破坏不可剥夺条件) 3)资源有序分配法；做法：系统给每类资源赋予一个编号，每一个进程按编号递增的顺序请求资源，释放则相反(破坏环路等待条件),死锁避免 资源轨迹图,两个进程的资源轨迹图,38,确定是否安全状态,在P2完成之后,P2完成,P1完成,安全状态,不安全状态,假设这时P1申请一个R1和一个R3，状态还是安全吗？是否拒绝P1?,安全状态和不安全状态(1),说明（a）中的状态为安全状态,44,(a) (b) (c) (d) (e),安全状态和不安全状态(2),说明（b）中的状态为不安全状态 safe,45,(a) (b) (c) (d),单个资源的银行家算法,三个资源分配状态 安全 安全 不安全,46,(a) (b) (c),多个资源的银行家算法,多个资源的银行家算法例子,47,银行家算法实例,假定系统中有五个进程P0, P1, P2, P3, P4和三类资源A, B, C，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图 3-15 所示。,T0时刻的安全性：,(2) P1请求资源：P1发出请求向量Request1(1，0，2)，系统按银行家算法进行检查： Request1(1, 0, 2)Need1(1, 2, 2) Request1(1, 0, 2)Available1(3, 3, 2) 系统先假定可为P1分配资源，并修改Available, Allocation1和Need1向量，由此形成的资源变化情况如图 3-16 中的圆括号所示。 再利用安全性算法检查此时系统是否安全。,先看进程已拥有的资源数目以及还需要的资源数目，看系统可提供的资源数目是否满足该进程还需要的资源数目，若可以满足则将资源分配给该进程，该进程用完后释放，释放后系统重新计算可提供的资源数目，再分配给下一个可以满足需求的进程。,(3) P4请求资源：P4发出请求向量Request4(3，3，0)，系统按银行家算法进行检查： Request4(3, 3, 0)Need4(4, 3, 1); Request4(3, 3, 0) Available(2, 3, 0)，让P4等待。 (4) P0请求资源：P0发出请求向量Requst0(0，2，0)，系统按银行家算法进行检查： Request0(0, 2, 0)Need0(7, 4, 3); Request0(0, 2, 0)Available(2, 3, 0); 系统暂时先假定可为P0分配资源，并修改有关数据，如图 3-18 所示。,3.7 死锁的检测,条件：允许死锁必要条件存在，也未采用避免死锁的算法（提高资源利用率）故死锁可能发生，需检测！ 定义：实际地检查系统中是否存在死锁，并标出那些进程和资源被牵扯在死锁中。 应用：允许前三个死锁的必要条件存在的系统中，检查系统中是否存在循环等待条件。 方法：资源分配图,死锁预防 破坏互斥条件,一些设备 (例如打印机) 假脱机 惟一真正请求使用物理打印机的进程是打印机的守护进程 这样消除因打印机产生死锁 并不是所有的设备都可以使用假脱机技术 原理: 避免分配那些不是绝对必需的资源 尽量做到尽可能少的进程可以真正请求资源,55,破坏占有和等待条件,所有进程在开始执行前请求所需的全部资源 一个进程不会因其他资源而等待 问题 很多进程直到运行时才知道它需要多少资源 资源利用率不是最优的 变种: 进程请求先暂时释放其当前占用的所有资源 然后再尝试一次获得所需的全部资源,56,破坏不可抢占条件,破坏第三个条件也是可能的 假若一个进程已分配到一台打印机 正在打印输出 现在强制地把它占有的打印机抢占 !?,57,破坏环路等待条件 (1),对资源排序编号 资源分配图,58,(a) (b),破坏环路等待条件 (1),死锁预防方法汇总,59,其他问题 两阶段加锁,第一阶段 进程试图对所有所需的记录进行加锁，一次锁一个记录 如果第一阶段加锁成功, 就开始第二阶段 (在第一阶段并没有做实际的工作) 如果第一阶段成功，那以开始第二阶段, 执行更新 释放锁 注意这类似于同时请求所有资源 算法只有当程序员仔细安排了程序 使得第一阶段程序在任意一点停下来，并重新开始而不会产生错误,60,通信死锁,两个进程通信可能会导致死锁 每个进程因为等待另外一个进程引发的事件而产生阻塞 通过超时技术解决 书P258例子 通过信号量解决 进程通过含