操作系统第3章处理机调度分析.ppt

* * 3.7.1 死锁的检测 1.资源分配图(Resource Allocation Graph) 由一组结点N和一组边E组成的一个对偶G=(N,E) 把N分为两个互斥的子集,即一组进程结点P={p1,p2,…,pn}和一组资源结点R={r1,r2,…,rn},N=P∪R 凡属于E中的一个边e∈E,都连着P中的一个结点和R中的一个结点,e={pi,rj}是资源请求边,由进程pi指向资源rj,表示进程pi请求一个单位的资源rj。e={rj,pi}是资源分配边,表示把一个单位的资源rj分配给进程pi * * 图3-20 每类资源有多个时的情况 请求 请求 已分配 已分配 已分配 * * 2.死锁定理 图3-21 资源分配图的简化 * * 死锁定理 在资源分配图中找出一个既不阻塞又非孤立的进程结点Pi。在顺利的情况下Pi可获得资源而继续运行,再释放所有资源。相当于消去Pi所有的请求边和分配边,使之成为孤立结点 Pi释放资源后,便可使Pi+1获得资源而继续运行,直至Pi+1完成又释放出所占有资源 在进行一系列化简后若能消去图中所有的边,使所有进程结点成为孤立结点,则称该图是可完全简化的;否则是不可完全简化的 已经证明:所有的化简顺序都得到相同的不可简化图。同样可以证明,S为死锁的充分条件是:当且仅当S状态的资源分配图是不可完全简化的。该充分条件称为死锁定理 * * 3.死锁检测中的数据结构和死锁检测算法 (1)可用资源向量Available,它表示了m类资源中每一类资源的可用数目。 (2)把不占用和不申请资源的进程(向量Allocation=0和Request=0)记入L表中(即孤立结点),即Li∪L。 (3)从进程集合中找到一个Requesti≤Work的进程,做如下处理:①将其资源分配图简化,释放出资源,增加工作向量Work:=Work+Allocationi。②将它记入L表中。 * * (4)若不能把所有进程都记入L表中,便表明系统状态S的资源分配图是不可完全简化的。因此,该系统状态将发生死锁。 Work:=Available; L:={Li|Allocationi=0∩Requesti=0}; for all Li L do begin for all Requesti≤Work do begin Work:=Work+Allocationi; L:=Li∪L; end end deadlock:=﹁ (L={p1, p2, …, pn});{deadlock=true死锁} * * 3.7 死锁的检测与解除 3.7.1 死锁的检测 3.7.2 死锁的解除 * * 3.7.2 死锁的解除 (1)剥夺资源 从其他进程剥夺足够的资源给死锁进程,以解除死锁状态 (2)撤消进程 简单方法:撤消所有死锁进程 温和方法:按照某种顺序逐个地撤消进程,直至有足够的资源可用,使死锁状态消除 撤消进程策略 1)进程的优先级低。 2)撤销代价小。 3)后来的先撤。 * * 本章小结 处理器管理的主要任务是分配处理器 主要目的是提高处理器的使用效率。 主要内容:三大调度(高级、中级、低级)、调度模型、调度算法(3个)、实时调度、多处理机系统中的调度、死锁和死锁处理(银行家算法) * * 处理死锁的基本方法 方法 资源分配策略 各种可能模式 主要优点 主要缺点 预防 Prevention 保守的；宁可资源闲置（从机制上使死锁条件不成立，即摒弃三个必要条件） 一次请求所有资源条件2 适用于作突发式处理的进程；不必剥夺 效率低；进程开始时间可能延长 资源浪费有可能严重 不便灵活申请新资源 资源剥夺 条件3 适用于状态可以保存和恢复的资源 资源按序申请条件4 避免 Avoidance 是“预防”和“检测”的折衷（在运行时判断是否可能死锁） 寻找可能的安全的运行顺序 不必进行剥夺 使用条件：必须知道将来的资源需求；进程可能会长时间阻塞 检测 Detection 宽松的；只要允许，就分配资源 定期检查死锁是否已经发生 进程开始时间不延长；允许对死锁进行现场处理 通过剥夺解除死锁，造成损失 可以在编译时（而不必在运行时）就进行检查 * * 1、在批处理、分时和实时操作系统中,都设置了( ),在批处理系统中还应设置( )。 A.剥夺调度 B.作业调度 C.进程调度 D.中级调度 2、如果为每一个作业,只建立一个进程,则为了照顾短作业用户,应采用( ),为照顾紧急作业的用户,应采用( ),为能实现人机交互作用,应采用( ),