操作系统死锁.ppt

《操作系统死锁.ppt》由会员分享，可在线阅读，更多相关《操作系统死锁.ppt（62页珍藏版）》请在优知文库上搜索。

1、1提提 纲纲死锁的检测和解除死锁的检测和解除四四死琐的概念和资源分配图死琐的概念和资源分配图一一产生死琐的原因和必要条产生死琐的原因和必要条件件二二死锁的预防和避免死锁的预防和避免三三2死锁的概念和资源分配图死锁现象与例子死锁现象与例子资源分配图资源分配图死锁的定义与结论死锁的定义与结论死锁与竞争饥饿关系死锁与竞争饥饿关系3 死锁现象死锁现象(以过桥为例以过桥为例)1.死锁现象与例子死锁现象与例子4n 申请不同类型资源申请不同类型资源A设系统有一台打印机设系统有一台打印机(R1)(R1)一台扫描仪一台扫描仪(R2)(R2)，两进程共享，两进程共享这两台设备。这两台设备。P1：申请打印机申请打印

2、机申请扫描仪申请扫描仪使用使用释放打印机释放打印机释放扫描仪释放扫描仪P2：申请扫描仪申请扫描仪申请打印机申请打印机使用使用释放打印机释放打印机释放扫描仪释放扫描仪n 申请相同类型资源，如内存申请相同类型资源，如内存1.死锁现象与例子死锁现象与例子5一个结点集合一个结点集合N和边集合和边集合E结点结点N被分为两个互斥子集被分为两个互斥子集进程结点子集进程结点子集P = P1, P2, , Pn资源结点子集资源结点子集R = R1, R2, , RmN=P R=P1, P2, , Pn R1, R2, , Rm圆圈圆圈表一进程，表一进程，方框方框表一类资源，其数目由表一类资源，其数目由方框中的小

3、圆圈数表示方框中的小圆圈数表示边边E 请求边请求边：直接直接Pi Rj ,即即e=(Pi , Rj )分配边分配边：Pi Rj 即即e= (Rj , Pi )进程进程有三个资源有三个资源Pi 请求一个请求一个RjPi 持有一个持有一个Rj2.资源分配图（资源分配图（Resource Allocation Graph）6 死锁：指死锁：指多个进程多个进程因因竞争共享资源竞争共享资源而造成的一种而造成的一种僵局僵局，若无外力作用，这些进程都将永远不能再向前推进。若无外力作用，这些进程都将永远不能再向前推进。R1R2P1P23.死锁的定义与结论死锁的定义与结论7 注意：注意：参与死锁的进程数至少为参

4、与死锁的进程数至少为2参与死锁的所有进程均等待资源参与死锁的所有进程均等待资源参与死锁的进程是系统中当前正在运行进程参与死锁的进程是系统中当前正在运行进程的一部分。的一部分。3.死锁的定义与结论死锁的定义与结论8相同点：二者都是由于竞争资源而引起的。相同点：二者都是由于竞争资源而引起的。差别：差别：(1) 从进程状态考虑，死锁进程都处于等待状态，忙式等待从进程状态考虑，死锁进程都处于等待状态，忙式等待(处于运行或就处于运行或就绪状态绪状态)的进程并非处于等待状态，但却可能被饿死；的进程并非处于等待状态，但却可能被饿死；(2) 死锁进程等待永远不会被释放的资源，饿死进程等待会被释放但却不死锁进程

5、等待永远不会被释放的资源，饿死进程等待会被释放但却不会分配给自己的资源，表现为等待时限没有上界会分配给自己的资源，表现为等待时限没有上界(排队等待或忙式等待排队等待或忙式等待)；(3) 死锁一定发生了循环等待，而饿死则不然。这也表明通过资源分配图死锁一定发生了循环等待，而饿死则不然。这也表明通过资源分配图可以检测死锁存在与否，但却不能检测是否有进程饿死；可以检测死锁存在与否，但却不能检测是否有进程饿死；(4) 死锁一定涉及多个进程，而饥饿或被饿死的进程可能只有一个。死锁一定涉及多个进程，而饥饿或被饿死的进程可能只有一个。(5)在饥饿的情形下，系统中有至少一个进程能正常运行，只是饥饿进程在饥饿的

6、情形下，系统中有至少一个进程能正常运行，只是饥饿进程得不到执行机会。而死锁则可能会最终使整个系统陷入死锁并崩溃。得不到执行机会。而死锁则可能会最终使整个系统陷入死锁并崩溃。饥饿饥饿是指在预计时间内，某个或某些进程是指在预计时间内，某个或某些进程永远得不到完成工作的机会，因为他们所永远得不到完成工作的机会，因为他们所需的资源总是被别的进程占有或抢占。这需的资源总是被别的进程占有或抢占。这种状况称作种状况称作“饥饿饥饿”或者或者“饿死饿死”（Starvation）。）。4.死锁竞争饥饿死锁竞争饥饿9 竞争是指两个以上进程以显式或隐式方式共享资源的状态。竞争是指两个以上进程以显式或隐式方式共享资源的

7、状态。 死锁与竞争是多道程序一对必然状态死锁与竞争是多道程序一对必然状态 竞争是资源共享的正常现象，系统有能力协调，有利于提高竞争是资源共享的正常现象，系统有能力协调，有利于提高资源的利用率。资源的利用率。 死锁是资源共享的异常现象，会浪费大量系统资源，甚至系死锁是资源共享的异常现象，会浪费大量系统资源，甚至系统崩溃，它是竞争处理不妥造成的。统崩溃，它是竞争处理不妥造成的。4.死锁竞争饥饿死锁竞争饥饿10死锁产生的原因和必要条件资源的分类资源的分类产生死锁的原因产生死锁的原因产生死锁的必要条件产生死锁的必要条件11根据资源本身的性质根据资源本身的性质可剥夺资源可剥夺资源：如主存、：如主存、CP

8、U不可剥夺资源不可剥夺资源：如驱动器、打印机等：如驱动器、打印机等 根据资源使用期限根据资源使用期限永久性资源永久性资源：可再次使用，如所有硬件。：可再次使用，如所有硬件。临时性临时性资源资源：消耗性的资源，如消息、信：消耗性的资源，如消息、信号和数据号和数据1.资源分类资源分类12 竞争资源竞争资源 当系统中供多个进程所共享的资源不足以同当系统中供多个进程所共享的资源不足以同时满足它们的需要时，引起它们对资源的竞时满足它们的需要时，引起它们对资源的竞争而产生死锁；争而产生死锁； 进程推进顺序非法进程推进顺序非法 进程在运行过程中，请求和释放资源的顺序进程在运行过程中，请求和释放资源的顺序不当

9、，导致进程的死锁。不当，导致进程的死锁。2.产生死锁的原因产生死锁的原因131 ) 竞争非剥夺性资源：竞争非剥夺性资源：R1R2P1P2R1R1代表系统中仅有的一台打印机代表系统中仅有的一台打印机R2R2代表系统中仅有的一台磁带机代表系统中仅有的一台磁带机P1P1、 P2P2代表可共享资源的进程代表可共享资源的进程（1）竞争资源）竞争资源2.产生死锁的原因产生死锁的原因14P1S1S3P2P3S22) 竞争临时性资源竞争临时性资源P1：Release(S3);Request(S1)P2：Release(S1);Request(S2)P3：Release(S2);Request(S3)P1：Re

10、quest(S1);Release(S3)P2：Request(S2);Release(S1)P3：Request(S3);Release(S2)S1、S2、S3是临时资源是临时资源不可能发生死锁不可能发生死锁可能发生死锁可能发生死锁（1） 竞争资源竞争资源2.产生死锁的原因产生死锁的原因15 2 ）进程推进顺序不当）进程推进顺序不当（进程并发的异步性）（进程并发的异步性） 无法控制进程之间的推进顺序（固有的），无法控制进程之间的推进顺序（固有的），因此死锁是基本特征的因此死锁是基本特征的“副作用副作用”；进程可能按下述两种顺序向前推进进程可能按下述两种顺序向前推进 进程推进顺序合法进程推进顺

11、序合法 推进顺序非法推进顺序非法2.产生死锁的原因产生死锁的原因16D进程推进顺序对死锁的影响进程推进顺序对死锁的影响 P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1) P1Req(R2) P1Rel(R1) P1Rel(R2)进程进程P1、P2并发执行。并发执行。共享资源共享资源R1、R2曲线4将进入不安全区域（进程推进顺序非法）17 互斥条件互斥条件(Mutual Exclusion) 即资源独占，某资源要求进程互斥地访问。即资源独占，某资源要求进程互斥地访问。 请求和保持请求和保持(Hold and wait) 进程已占用至少一个资源，且又提出资

12、源请求，当不进程已占用至少一个资源，且又提出资源请求，当不能满足而阻塞时，保持原资源不释放。能满足而阻塞时，保持原资源不释放。 不剥夺条件不剥夺条件(No preemption) 资源申请者不能强行的从资源占有者手中夺取资源，资源申请者不能强行的从资源占有者手中夺取资源，资源只能由占有者资源只能由占有者自愿释放。自愿释放。 环路等待条件环路等待条件(Circular wait) 必有一进程必有一进程-资源的环形链。环路中的进程形成等待链。资源的环形链。环路中的进程形成等待链。3. 产生死锁的必要条件产生死锁的必要条件18死锁预防与避免处理死锁的基本方法处理死锁的基本方法死锁的预防死锁的预防死锁

13、的避免死锁的避免19 不让死锁发生：不让死锁发生：死锁预防死锁预防(prevention)：是一种是一种静态的静态的策略策略; ;死锁避免死锁避免(Avoidance)：是一种是一种动态的策略动态的策略. . 允许死锁发生：允许死锁发生： 检测和解除死锁检测和解除死锁 忽略这个问题忽略这个问题（鸵鸟算法鸵鸟算法）1.处理死锁的基本方法处理死锁的基本方法20 (1) 预防死锁预防死锁 在系统设计时确定资源分配算法，保证不发生死锁。在系统设计时确定资源分配算法，保证不发生死锁。具体的做法是具体的做法是破坏产生死锁的四个必要条件之一。破坏产生死锁的四个必要条件之一。优点：实现简单；优点：实现简单；缺

14、点：条件严格，降低系统资源利用率和吞吐量。缺点：条件严格，降低系统资源利用率和吞吐量。 (2) 避免死锁避免死锁 在系统运行过程中，对进程发出的每一个系统能够在系统运行过程中，对进程发出的每一个系统能够满足的满足的资源申请资源申请进行进行动态检查动态检查，并根据检查结果决，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配不予分配，否则予以分配优点：条件较弱，较高资源利用率和吞吐量。优点：条件较弱，较高资源利用率和吞吐量。缺点：实现困难缺点：实现困难.1.处理死锁的基本方法处理死锁的基本方法21 (3) (3) 死锁检

15、测与解除：死锁检测与解除： 允许死锁发生，操作系统不断监视系统进允许死锁发生，操作系统不断监视系统进展情况，判断死锁是否发生展情况，判断死锁是否发生; ; 一旦死锁发生则采取专门的措施，解除死一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操作系统运行锁并以最小的代价恢复操作系统运行. .1.处理死锁的基本方法处理死锁的基本方法22 (4)(4) 鸵鸟算法（置之不理）鸵鸟算法（置之不理） 是解决死锁的最简单方法。即像鸵鸟一样，当是解决死锁的最简单方法。即像鸵鸟一样，当遇到危险时，将头埋进沙子里，假装毫无问题。遇到危险时，将头埋进沙子里，假装毫无问题。即不保证死锁从不发生，也不提供死锁检

16、测和恢即不保证死锁从不发生，也不提供死锁检测和恢复的机制。当死锁出现最终导致系统停止工作时，复的机制。当死锁出现最终导致系统停止工作时，手工重新启动。手工重新启动。 当死锁在计算机中很少出现时，比如说每五年当死锁在计算机中很少出现时，比如说每五年或更长时间才出现一次时，人们就不必花费更多或更长时间才出现一次时，人们就不必花费更多的精力去解决它，而是采用类似鸵鸟一样的办法的精力去解决它，而是采用类似鸵鸟一样的办法忽略它。忽略它。 UNIX系统即采用这样的做法。系统即采用这样的做法。1.处理死锁的基本方法处理死锁的基本方法23 因为因为 “互斥条件互斥条件”是是设备的设备的固有属性固有属性决定的，决定的，不仅不能改变，不仅不能改变，还应加以保证。还应加以保证。根据生产死锁的四个必要条件，只要使其中之一根据生产死锁的四个必要条件，只要使其中之一不能成立，死锁就不会出现。不能成立，死锁就不会出现。互斥条件互斥条件请求和保持条件请求和保持条件不剥夺条件不剥夺条件环路等待条件环路等待条件 所以只能所以只能设法破坏另三个必要条件设法破坏另三个必要条件。2.死锁的预防死锁的预防24 (1) 摒弃摒弃“