计算机操作系统章 ——处理机调度与死锁.ppt

2、死锁定理 我们可以利用资源分配图加以简化的方法，来检测系统处于某状态时是否为死锁状态。简化方法如下： 3.7.1 死锁的检测 可以证明：S状态为死锁状态的充分条件是当且仅当S状态的资源分配图是不可完全简化的。死锁定理 r1 r2 P2 P1 1. 在资源分配图中找出一个既不阻塞又非独立的进程结点Pi，在顺利的情况下运行完毕，释放其占有的全部资源。 2. 由于释放了资源，这样能使其它被阻塞的进程获得资源继续运行。 3. 在经过一系列简化后若能消去图中的所有的边，使所有进程结点都孤立，则称该图是可完全简化的，反之是不可完全简化的。 3.7.2 死锁的解除 当发现进程死锁时，便应立即把它们从死锁状态中解脱出来。常采用的方法是： 1、剥夺资源：从其他进程剥夺足够数量的资源给死锁进程以解除死锁状态。 2、撤销进程：最简单的是让全部进程都死掉；温和一点的是按照某种顺序逐个撤销进程，直至有足够的资源可用，使死锁状态消除为止。 作业 竞争临时性资源引起死锁 打印机之类的资源属于可顺序重复使用型资源，称为永久性资源。与之相对的是临时性资源，是指由一个进程产生，被另一进程使用一短暂时间后便无用的资源，也称为消耗性资源，它也可能引起死锁。 s3 s1 s2 p3 p2 p1 P1: ...Request(s3);release(s1)… P2: ...Request(s1);release(s2)… P3: ...Request(s2);release(s3)… 2、进程推进顺序不当引起死锁 由于进程在运行中具有异步性特征，这就可能使上述P1和P2两个进程按下述两种顺序向前推进。 进程推进顺序合法 进程推进顺序非法 3.5.1 产生死锁的原因 3.5 产生死锁的原因和必要条件 3.5.1 产生死锁的原因 3.5.2 产生死锁的必要条件 3.5.3 处理死锁的基本方法 3.5.2 产生死锁的必要条件 虽然进程在运行过程中可能发生死锁，但死锁的发生也必须具备一定的条件。可以看出，必须具备以下四个必要条件: 1、互斥条件：进程访问的是临界资源，即在一段时间内某资源只由一个进程占用。如果此时还有其他进程请求该资源，则请求者只能等待，直至占有该资源的进程用完释放。 2、请求和保持条件：一进程在请求新的资源的同时，保持对已分配资源的占有。 3、不剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。 4、环路等待条件：指在发生死锁时，必然存在一个进程--资源的环形链。即进程集合{P0,P1,P2,…,Pn}中的P0正在等待一个P1占用的资源；P1正在等待一个P2占用的资源，……，Pn正在等待一个已被P0占用的资源。 3.5.2 产生死锁的必要条件 P1 P2 R1 R2 3.5.3 处理死锁的基本方法 在系统中已经出现死锁后，则应及时检测到死锁的发生，并采取适当措施来解除死锁。目前处理死锁的方法可归结为以下四种： 1、预防死锁 2、避免死锁 3、检测死锁 4、解除死锁 1、预防死锁 这是一种较简单和直观的事先预防方法。该方法是通过设置某些限制条件，去破坏产生死锁的四个必要条件的一个或几个，来预防发生死锁。预防死锁是一种较易实现的方法，已被广泛使用。但由于所施加的限制条件往往太严格,可能会导致系统资源利用率和系统吞吐量降低。 3.5.3 处理死锁的基本方法 2、避免死锁 该方法同样是属于事先预防的策略，这种方法不是预先加上各种限制条件以预防产生死锁的可能性，而是用某种方法去防止系统进入不安全状态，使死锁不致于最终发生。 这种方法只须事先加以较弱的限制条件，便可获得较高的资源利用率及系统吞吐量，但在实现上有一定的难度。目前在较完善的系统中，常用此方法来避免发生死锁。 3.5.3 处理死锁的基本方法 3、检测死锁 这种方法并不须事先采取任何限制性措施，也不必检查系统是否已经进入不安全区。此方法允许系统在运行过程中发生死锁，但可通过系统所设置的检测机构，及时的检测出死锁的发生，并精确的确定与死锁有关的进程和资源；然后采取适当的措施，从系统中将已发生的死锁清除掉。 3.5.3 处理死锁的基本方法 3.5.3 处理死锁的基本方法 4、解除死锁 这是与死锁检测相配套的一种措施。当检测到系统中已发生死锁时，须将进程从死锁状态中解脱出来。常用的实施方法是撤销或挂起一些进程，以便回收一些资源，再将这些资源分配给已处于阻塞状态的进程，使之转为就绪状态，以继续运行。死锁的检测与解除措施，有可能使系统获得较好的资源利用率和吞吐量，但在实现上难度也最大。 第三章 处理机调度与死锁 3.1 处理机调度的基本概念 3.2 调度算法