2013操作系统死锁l

1提纲死锁的检测和解除四死琐的概念一产生死琐的原因和必要条件二死锁的预防和避免三2死锁的概念和资源分配图1死锁现象与例子2死锁的定义与结论3死锁的描述4死锁与竞争饥饿关系3死锁现象(以过桥为例)1.死锁现象与例子4申请不同类型资源设系统有一台打印机(R1)一台扫描仪(R2)，两进程共享这两台设备。P1：…申请打印机申请扫描仪使用释放打印机释放扫描仪…P2：…申请扫描仪申请打印机使用释放打印机释放扫描仪…①④②③申请相同类型资源，如内存1.死锁现象与例子5死锁：指多个进程因竞争共享资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前推进。R1R2P1P22.死锁的定义与结论6注意：参与死锁的进程数至少为2参与死锁的所有进程均等待资源参与死锁的进程是系统中当前正在运行进程的一部分。2.死锁的定义与结论7一个结点集合N和边集合E结点N被分为两个互斥子集进程结点子集P={P1,P2,…,Pn}资源结点子集R={R1,R2,…,Rm}N=P⋃R={P1,P2,…,Pn}⋃{R1,R2,…,Rm}圆圈表一进程，方框表一类资源，其数目由方框中的小圆圈数表示边E请求边：直接PiRj,即e=(Pi,Rj)分配边：PiRj即e=(Rj,Pi)进程有三个资源Pi请求一个RjPi持有一个Rj2.1资源分配图（ResourceAllocationGraph）2.死锁描述8▲如果每类资源的实体都只有一个，那么图中出现环路就说明死锁了。3.死锁描述3.1环路与死琐9有死锁的资源分配图有环路但无死锁的资源分配图▲如果每类资源的实体不止一个，那么资源分配图中出现环路并不表明一定出现死锁。●资源分配图中存在环路是死锁产生的必要条件，但不是充分条件。3.死锁描述3.2环路与死琐10相同点：二者都是由于竞争资源而引起的。差别：(1)从进程状态考虑，死锁进程都处于等待状态，忙式等待(处于运行或就绪状态)的进程并非处于等待状态，但却可能被饿死；(2)死锁进程等待永远不会被释放的资源，饿死进程等待会被释放但却不会分配给自己的资源，表现为等待时限没有上界(排队等待或忙式等待)；(3)死锁一定发生了循环等待，而饿死则不然。这也表明通过资源分配图可以检测死锁存在与否，但却不能检测是否有进程饿死；(4)死锁一定涉及多个进程，而饥饿或被饿死的进程可能只有一个。(5)在饥饿的情形下，系统中有至少一个进程能正常运行，只是饥饿进程得不到执行机会。而死锁则可能会最终使整个系统陷入死锁并崩溃。饥饿是指在预计时间内，某个或某些进程永远得不到完成工作的机会，因为他们所需的资源总是被别的进程占有或抢占。这种状况称作“饥饿”或者“饿死”（Starvation）。4.死锁竞争饥饿11竞争是指两个以上进程以显式或隐式方式共享资源的状态。死锁与竞争是多道程序一对必然状态竞争是资源共享的正常现象，系统有能力协调，有利于提高资源的利用率。死锁是资源共享的异常现象，会浪费大量系统资源，甚至系统崩溃，它是竞争处理不妥造成的。4.死锁竞争饥饿12死锁产生的原因和必要条件1资源的分类与使用2产生死锁的原因3产生死锁的必要条件13根据资源本身的性质•可剥夺资源：当前进程所占有的资源可被另一进程强行抢占如主存、CPU•不可剥夺资源：当前进程所占有的资源不能被另一进程强行抢占如驱动器、打印机等根据资源使用期限•永久性资源：可再次重复使用，如所有硬件、可重入的代码过程。•临时性资源：消耗性的资源，进程同步和通信中出现的如消息、信号和数据1.资源分类与使用14根据资源使用方式•共享资源：资源可为多个进程共同使用如主存、CPU•独享资源：每次只能由一个进程单独使用如刻录机、打印机等资源使用模式顺序使用：申请→使用→释放。使用实现：系统调用，资源分配表1.资源分类与使用15竞争资源当系统中供多个进程所共享的资源不足以同时满足它们的需要时，引起它们对资源的竞争而产生死锁；进程推进顺序非法进程在运行过程中，请求和释放资源的顺序不当，导致进程的死锁。2.产生死锁的原因161)竞争非剥夺性资源：R1R2P1P2R1代表系统中仅有的一台打印机R2代表系统中仅有的一台磁带机P1、P2代表可共享资源的进程（1）竞争资源2.产生死锁的原因17P1S1S3P2P3S22)竞争临时性资源P1：Release(S3);Request(S1)P2：Release(S1);Request(S2)P3：Release(S2);Request(S3)P1：Request(S1);Release(S3)P2：Request(S2);Release(S1)P3：Request(S3);Release(S2)S1、S2、S3是临时资源不可能发生死锁可能发生死锁（1）竞争资源2.产生死锁的原因182）进程推进顺序不当（进程并发的异步性）无法控制进程之间的推进顺序（固有的），因此死锁是基本特征的“副作用”；进程可能按下述两种顺序向前推进•进程推进顺序合法•推进顺序非法2.产生死锁的原因19D进程推进顺序对死锁的影响P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2)③③③③②②①①进程P1、P2并发执行。共享资源R1、R2④曲线4将进入不安全区域（进程推进顺序非法）20互斥条件(MutualExclusion)即资源独占，某资源要求进程互斥地访问。请求和保持(Holdandwait)进程已占用至少一个资源，且又提出资源请求，当不能满足而阻塞时，保持原资源不释放。不剥夺条件(Nopreemption)资源申请者不能强行的从资源占有者手中夺取资源，资源只能由占有者自愿释放。环路等待条件(Circularwait)必有一进程--资源的环形链。环路中的进程形成等待链。3.产生死锁的必要条件21死锁预防与避免1处理死锁的基本方法2死锁的预防3死锁的避免22不让死锁发生：死锁预防(prevention)：是一种静态的策略;死锁避免(Avoidance)：是一种动态的策略.允许死锁发生：检测和解除死锁忽略这个问题（鸵鸟算法）1.处理死锁的基本方法23(1)预防死锁在系统设计时确定资源分配算法，保证不发生死锁。具体的做法是破坏产生死锁的四个必要条件之一。优点：实现简单；缺点：条件严格，降低系统资源利用率和吞吐量。(2)避免死锁在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配优点：条件较弱，较高资源利用率和吞吐量。缺点：实现困难.1.处理死锁的基本方法24(3)死锁检测与解除：允许死锁发生，操作系统不断监视系统进展情况，判断死锁是否发生;一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操作系统运行.1.处理死锁的基本方法25(4)鸵鸟算法（置之不理）是解决死锁的最简单方法。即像鸵鸟一样，当遇到危险时，将头埋进沙子里，假装毫无问题。即不保证死锁从不发生，也不提供死锁检测和恢复的机制。当死锁出现最终导致系统停止工作时，手工重新启动。当死锁在计算机中很少出现时，比如说每五年或更长时间才出现一次时，人们就不必花费更多的精力去解决它，而是采用类似鸵鸟一样的办法忽略它。UNIX系统即采用这样的做法。1.处理死锁的基本方法26因为“互斥条件”是设备的固有属性决定的，不仅不能改变，还应加以保证。根据生产死锁的四个必要条件，只要使其中之一不能成立，死锁就不会出现。互斥条件请求和保持条件不剥夺条件环路等待条件所以只能设法破坏另三个必要条件。2.死锁的预防27(1)摒弃“请求和保持”条件（资源一次性分配）●预分资源策略——静态分配要求每个进程在运行前必须一次性申请它所要求的所有资源，且仅当该进程所要资源均可满足时才给予一次性分配。●“空手”申请资源策略——不占有资源时才可以申请资源，可多次申请分配资源缺点：•1）不可预测•2）资源利用率低对于“紧俏”资源，进程在整个生命周期一直占用，浪费严重；•3）降低并发性-进程延迟运行(starvationpossible)。•4）可能发生讥饿2.死锁的预防28(2)摒弃“不剥夺”条件：资源可剥夺①采取的策略：某进程在申请新资源不能满足时，释放已占用的所有资源，以后需要时再重新申请。意味着：进程已经占有的资源，在运行过程中可能会暂时的释放，也可认为是被剥夺了。缺点：•实现比较复杂•反复地申请和释放资源使进程的执行无限地推迟，延长了周转时间，增加了系统的开销，降低了系统吞吐量。（例如打印机打印的结果不连续）2.死锁的预防29(3)摒弃“环路等待”条件资源有序分配法思想：所有资源按类型进行线性排队，并赋予不同的序号。进程对资源的请求必须按资源序号递增的次序提出。缺点：系统中各种类型的资源序号须相对稳定，这就限制了新设备类型的增加作业实际使用资源的顺序与系统规定的顺序不同而造成资源的浪费；2.死锁的预防30(3)摒弃“环路等待”条件资源有序分配法●资源编号设R={r1,r2,…,rm}，表示一组资源定义一对一的函数F：R→N，N是一组自然数。如：F（磁带机）=1，F（磁盘机）=5，F（打印机）=12●依序分配约定：所有进程对资源的申请严格按照序号递增的次序进行。2.死锁的预防31例如：有序号为1，2，…，10的设备P1：申请1申请3申请9…P2：申请1申请2申请5…P3……2.死锁的预防(3)摒弃“环路等待”条件32②先弃大，再取小一个进程申请资源rj，它应释放所有满足F(ri)≥F(rj)关系的资源ri▲这两种办法都是可行的，都可排除环路等待条件优点：资源利用率和系统吞吐量都有很大提高缺点：▼资源请求受限，合理编号困难，增加系统开销。▼暂不使用的资源也需提前申请，增加资源占用时间。2.死锁的预防333.死锁的避免3.1避免与预防死锁的区别3.2系统安全状态3.3利用银行家算法避免死锁1.4银行家算法实例34避免死锁与预防死锁的区别:预防死锁是对于进程的资源申请命令施加限制。避免死锁是在进程请求分配资源时进行动态检查，并根据检查结果决定是否实施资源分配。避免死锁中，可把系统状态分为安全状态和不安全状态。3.1避免死锁与预防死锁的区别35（1）安全状态定义系统能按某种顺序（如P1,P2,…,Pn）来为每个进程分配其所需的资源，使每个进程都可顺利完成，则称此时系统处于安全状态。若对于每个Pi,Pi申请的资源小于当前可用资源加上所有进程Pj(ji)所占用的资源。进程的序列P1,P2,…,Pn称为安全序列。若不存在安全序列，则称系统处于不安全状态。3.2系统的安全状态36（2）安全状态实例设系统中共有12台磁带机，假设在T0时刻，各进程的需求、占用磁带机的情况如下表所示：若按P2、P1、P3的顺序执行，则三进程都可顺利完成，因此，此时系统处于安全状态。进程最大需求已分配剩余1231049231245051010P2P1P3存在一个正确的顺序推进进程3.2系统的安全状态37（3）由安全状态向不安全状态的转换若P3再申请1个磁带机，需求是否可以分配？进程最大需求已分配剩余1231049325223此时，找不到一个序列可使三进程都顺利的运行结束。即系统进入不安全状态，将导致死锁。因此，在进程提出申请时，即使系统中的资源可以满足，也不一定就可以分配，要考虑分配后是否会进入不安全状态。3.2系统的安全状态38（4）安全状态与不安全状态Basicfacts：如果一个系统在安全状态，就没有死锁.在某一时刻安全状态不唯一如果一个系统处于不安全状态，就有可能进入死锁状态的危险.避免死锁的实质：确保系统不进入不安全状态.如果一个进程申请的资源当前是可用的，但为了避免死锁，该进程也可能必须等待。此时资源利用率会下降。安全状态不安全状态死锁状态3.2系统的安全状态39思考：以下几种状态安全吗？40(1)利用