计算机操作系统原理ch死锁

《计算机操作系统原理ch死锁》由会员分享，可在线阅读，更多相关《计算机操作系统原理ch死锁（69页珍藏版）》请在金锄头文库上搜索。

1、第四章 死锁n死锁的概念n死锁的预防和避免n死锁的检测和解除死锁的概念n死锁举例n产生死锁的原因 n产生死锁的必要条件 n处理死锁的基本方法 死锁举例n例1： 两个小孩在一起玩耍，一个在玩皮球，另一 个玩自动步枪，如果这两个小孩都要对方 手中的玩具，而又不肯先放掉自己拿着的 玩具，这时就发生了僵持局面。n例2： 设系统有一台打印机和一台扫描仪，进程P1 、P2并发执行，在某时刻T，进程P1和P2 分别占用了打印机和扫描仪。在时刻T1（ T1T），P1又要申请扫描仪，但由于扫 描仪被P2占用，P1只有等待。在时刻T2 （T2T），P2又申请打印机，但由于打 印机被P1占用，P2只有等待。如此两进

2、程 均不能执行完成。称这种现象为死锁。n例3： 在生产者-消费者问题中将生产者进程的 两个P操作颠倒时会发生死锁。 将消费者进程的两个P操作颠倒时也会发 生死锁。 死锁的定义一组进程中，两个或多个进程都无 限期地等待永远不会发生的条件， 我们称此系统处于死锁状态。死锁（Deadlock） 饥饿（Starvation）死锁的起因n根本原因：系统能够提供的资源个数比 要求该资源的进程所需的资源个数少。判断1 参与死锁的所有进程都占有资源错误：有可能有的进程在等待其他进程释放资源2 参与死锁的所有进程均正在等待资源错误：有可能一个占有资源3 参与死锁的所有进程中至少有两个进程占 有资源 错误4 参与

3、死锁的进程至少有两个正确参与死锁的进程最少是两个（两个以上进程才会出现死锁）参与死锁的进程至少有两个已经占有资源参与死锁的所有进程都在等待资源参与死锁的进程是当前系统中所有进程的子集注：如果死锁发生，会浪费大量系统资源， 甚至导致系统崩溃关于死锁的一些结论产生死锁的必要条件四个必要条件（重点）n互斥条件：涉及的资源是非共享的。n不剥夺条件：不能强行剥夺进程拥有的资源 。n部分分配条件：进程在等待一新资源时继续 占有已分配的资源。n环路条件：存在一种进程的循环链，链中的 每一个进程已获得的资源同时被链中的下一 个进程所请求。 处理死锁的基本方法1、预防死锁：通过设置某些限制条件，去破坏死锁四个

4、必要条件中的一个或多个，来防止死锁 。较易实现，广泛使用，但由于所施加的限 制往往太严格，可能导致系统资源利用 率和系统吞吐量的降低。2、避免死锁： 不事先采取限制去破坏产生死锁的条件， 而是在资源的动态分配过程中，用某种 方法去防止系统进入不安全状态，从而 避免死锁的发生。实现较难，只需要较弱的限制条件，可获 得较高的资源利用率和系统吞吐量。3、检测死锁：事先并不采取任何限制，也不检查系统是 否进入不安全区，允许死锁发生，但可 通过检测机构及时检测出死锁的发生， 并精确确定与死锁有关的进程和资源， 然后采取适当措施，将系统中已发生的 死锁清除掉4、解除死锁： 与检测死锁相配套，用于将进程从死

5、锁状 态解脱出来。 常用的方法是撤消或挂起一些进程。以回 收一些资源，再将它们分配给处于阻塞 状态的进程，使之转为就绪状态。 实现难度大，但可获得较好的资源利用率 和系统吞吐量。 死锁的预防和避免n死锁的预防 n系统的安全状态 n利用银行家算法避免死锁死锁的预防在系统设计时确定资源分配算法，保证不 发生死锁具体的做法是破坏产生死锁的四个必要 条件之一破坏部分分配条件系统要求所有进程要一次性地申请在整 个运行过程中所需的全部资源。若系统 有足够资源则完全分配。优点：简单、易于实现且安全。 缺点：n一个用户在作业运行之前可能提不出他的作业将要使用的 全部设备。n用户作业必须等待，直到所有资源满足才

6、能运行。实际上 某些资源可能要到运行后期才会用到。n一个作业运行期间，对某些设备的使用时间很短，甚至不 会用到。如：当用户作业出错时才需要打印机输出错误信 息，但采用静态分配法必须把打印机分配给该作业，并长 期占用。采用该方法对系统来说是非常浪费的。 破坏不可剥夺条件一个已拥有资源的进程，若它再提出新资 源要求而不能立即得到满足时，它必须 释放已经拥有的所有资源。以后需要时 再重新申请。实现复杂、要付出很大的代价。 破坏环路条件系统中的所有资源都有一个确定的唯一号码， 所有分配请求必须以序号上升的次序进行。例如：系统中有下列设备：输入机（1），打印 机（2），穿孔机（3），磁带机（4），磁 盘

7、（5）。有一进程要先后使用输入机、磁盘 、打印机，则它申请设备时要按输入机、打 印机、磁盘的顺序申请。优点：同前两法相比，其资源利用率和系 统吞吐量有较明显的改善。缺点：进程实际需要资源的顺序不一定与 资源的编号一致，因此仍会造成资源浪 费。系统的安全状态死锁避免定义在系统运行过程中，对进程发出的 每一个系统能够满足的资源申请进行 动态检查，并根据检查结果决定是否 分配资源，若分配后系统可能发生死 锁，则不予分配，否则予以分配安全状态如果系统能按某种顺序（如P4，P1， ,Pn, 称为安全序列）为每个进程分配 其所需的资源，直至所有进程都能运行 完成，称系统处于安全状态。若不存在 这样一个安全

8、序列称系统处于不安全状 态。安全状态举例有三个进程p1,p2,p3，有12台磁带机 。P1共要求10台，P2共要求4台，P3共 要求9台。在T0时刻，p1,p2,p3分别获 得5、2、2台，尚有3台空闲。进程最大需求已分配还需可用p110553p2422p3927经分析，在T0时刻，系统是安全的。 因为存在一个安全序列p2、p1、p3。见下图。由安全状态向不安全状态的转换如果不按安全序列分配资源，则系统 可能会由安全状态进入不安全状态。如 在T0以后，P3要求1台磁带机，若系统 分给它一台，则系统进入不安全状态。 因为其余2台分给P2，P2完成后，只能 释放4台，这既不能满足P1（5台）， 也

9、不能满足P3（6台）。将导致死锁。 可见当P3申请资源时，尽管系统中有资 源也不能分给它。 系统进入不安全状态进程最大需求已分配还需可用p110552p2422p3936利用银行家算法避免死锁最有代表性的避免死锁算法，由Dijkstra提出 。 1、银行家算法中的数据结构n可利用资源向量Available。它是一个含有 m个元素的数组，其中每个元素代表一类 可利用资源的数目。n如： ABC 523n最大需求矩阵Max。n*m矩阵，表示n 个进程的每一个对m类资源的最大需求 。ABCP1562P2331P3425P4332n分配矩阵Allocation 。n*m矩阵，表示 每个进程分配的资源数。

10、ABCP1212P2121P3222P4132n需求矩阵Need 。n*m矩阵，表示每个 进程还需要各类资源数。ABCP1352P2211P3223P4232例 设系统有五个进程和三类资源，每类资源分别有10 、5、7。在T0时刻资源分配情况如图银行家算法描述当进程pi提出资源申请时，系统执行下 列步骤： （1）若RequestiNeedi,转（2） ；否则错误返回 （2）若RequestiAvailable,转（3）；否则进程等待(3）假设系统分配了资源，则有： Available:=Available-Requesti; Allocationi:=Allocationi+Requesti;

11、 Needi:=Needi-Requesti （4）执行安全性算法，若系统新状态是 安全的，则分配完成，若系统新状态是 不安全的，则恢复原状态，进程等待安全性算法为进行安全性检查，定义数据结构： Work:ARRAY0.m-1 of integer; Finish:ARRAY0.n-1 of Boolean;m代表资源的数量，n代表进程的数量安全性算法步骤(1) Work:=Available;Finish:=false; (2) 寻找满足下列条件的i：a). Finishi=false;b). NeediWork; 如果不存在，则转(4)(3) Work:=Work+Allocationi;

12、Finishi:=true;转(2) (4) 若对所有i,Finishi=true,则 系统处于安全状态，否则处于不安 全状态T0时刻的安全性检查nT0时刻可以找到一个安全序列p1,p3,p4,p2,p0. 系统是安全的。例1：T0时刻P1请求资源nP1发出请求Request(1,0,2)，执行银行家算法执行安全性算法n可以找到一个安全序列p1,p3,p4,p0,p2. 系统是安全的，可以将P1的 请求分配给它。例2：P4请求资源nP4发出请求Request(3,3,0), 执行银行 家算法nAvailable=2 3 0n不能通过算法第2步（ RequestiAvailable ），所以P4

13、等 待。例3：P0请求资源nRequest（0，2，0），执行银行家算法进行安全性检查nAvailable2,1,0已不能满足任何进程需 要，所以系统进入不安全状态，P0的请 求不能分配n练习：有三类资源A(17)、B(5)、C(20)。有5个进 程P1P5。T0时刻系统状态如下：问(1)、T0时刻是否为安全状态，给出安全序列。 (2)、T0时刻，P2: Request(0,3,4)，能否分配，为什么？ (3)、在(2)的基础上P4：Request(2,0,1)，能否分配，为什么？ (4)、 在(3)的基础上P1：Request(0,2,0)，能否分配，为什么？ 最大需求已分配 P15 5 9

14、2 1 2 P25 3 64 0 2 P34 0 114 0 5 P44 2 52 0 4 P54 2 43 1 4解：(1) T0时刻得出安全系列最大需求已分配Need P15 5 92 1 23 4 7 P25 3 64 0 21 3 4 P34 0 114 0 50 0 6 P44 2 52 0 42 2 1 P54 2 43 1 41 1 0A(17)、B(5)、C(20) Work=available=2 3 3先求出Need和WorkWorkAllocationNeedW+AFinish P52 3 33 1 41 1 05 4 7T P45 4 72 0 42 2 17 4 11

15、TP37 4 114 0 50 0 611 4 16T P211 4 164 0 21 3 415 4 18T P115 4 182 1 23 4 717 5 20TWork=2 3 3(2) P2: Request(0,3,4)n因（ Available =2 3 3） Request(0,3,4) 所以 不能分配(3) P4：Request(2,0,1)Available =2 3 3AllocationNeedAvailable P12 1 23 4 70 3 2 P24 0 21 3 4P34 0 50 0 6 P44 0 50 2 0 P53 1 41 1 0WorkAllocationNeedW+AFinishP40 3 24 0 50 2 04 3 7TP54 3 73 1 41 1 07 4 11TP37 4 114 0 50 0 611 4 16TP211 4 164 0 21 3 415 4 18TP115 4 182 1 23 4 717 5 20T有安全序列P4 P5 P3 P2 P1 可以分配(4) P1：Request(0,2,0)AllocationNeedAvailable P12 3 23