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

《现代操作系统 第3章 死锁.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、死锁第3章13.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)死锁有可能出现,当…进程

2、对设备、文件等取得了排他性访问权时我们把这类需要排他性使用的对象称为资源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(

3、s1)…同类资源分配不当若系统中有m个资源被n个进程共享，当每个进程都要求K个资源，而m

4、由该进程集合中的其他进程才能引发的事个，那么该进程集合就是死锁在大多数情况下，每个进程所等待的事件是释放该进程集合中其他进程所占有的资源没有一个进程可以…运行释放资源被唤醒11死锁的正式定义假设1：任意一个进程要求资源的最大数量不超过系统能提供的最大量假设2：如果一个进程在执行中所提出的资源要求能够得到满足，那么，它一定能在有限的时间内结束假设3：一个资源在任何时间最多只有一个进程所占有假定4：一个进程一次申请一个资源，且只在申请资源得不到的满足时才处于等待状态。（即不考虑人工干预，等待外设的情况

5、）死锁的正式定义假定5：一个进程结束时释放它占有的全部资源假定6：系统具有有限个进程和有限个资源定义：如果一个进程集合中的每个进程都在等待只能由该集合中的其他一个进程才能引发的事件，则称一组进程或系统此时发生了死锁。竞争资源引起进程死锁可剥夺和非剥夺性资源竞争非剥夺性资源竞争临时性资源永久性资源：可以被多个进程多次使用（可再用资源）可抢占资源不可抢占资源临时性资源：只可使用一次的资源；如信号量,中断信号，同步信号等（可消耗性资源）“申请--分配--使用--释放”模式死锁的四个条件互斥条件每个资源要

6、么已经分配给了一个进程，要么就是可用的占有和等待条件已经得到了某个资源的进程可以再请求新的资源不可抢占条件已经分配给一个进程的资源不能强制性地被抢占，它只能被占有它的进程显式地释放环路等待条件一定有由两个或两个以上的进程组成的一条环路该环路中的每个进程都在等待着下一个进程所占有的资源15死锁建模(2)有向图建模（资源分配图）资源R分配给进程A进程B请求或等待资源S进程C和D为得到资源T和U处于死锁16死锁建模(3)处理死锁的策略忽略问题检测并恢复动态避免仔细对资源分配防止破坏引起死锁的四个必要条件

7、之一17死锁建模(4)死锁是如何发生的18ABC死锁建模(5)死锁是如何避免的19(o)(p)(q)驼鸟算法假装根本没有问题发生可以接受，如果如果死锁发生频率低防止死锁的成本太高了UNIX和Windows采用此算法它是下面两者的折衷方便性正确性20每种类型一个资源的死锁检测(1)注意资源的所属和请求关系如果图中包含一个或一个以上的环，那么死锁就存在21资源分配图化简化简：一个进程的所有资源要求均能被满足，则该进程得到其所需全部资源从而不断取得进展，直至完成全部任务并释放出全部资源。在有向图中找到既

8、非阻塞又非孤立的结点，分配它所需的全部资源后，当它继续执行并完成然后释放其全部资源而使之成为孤立结点。把孤立结点释放的资源分配给阻塞进程，使之能继续运行，并且在有限时间后完成，再释放其全部资源而成为新的鼓励结点。经过一系列上述步骤，若能消去图中所有的边，使所有进程都成为孤立结点，则图可完全化简。否则为不可完全化简。死锁定理：当且仅当系统某状态S所对应的资源分配图是不可化简的，则S是死锁状态。而不可被化简的进程即是被死锁的进程。反之，若状态S所对应的资源分配图是可化简的，则S是安全状