第9章 死锁、系统安全 本章目录9.3.3 具体的安全防护措施9.1 死锁概述 9.1.1 死锁的概念9.1.2 资源分配图9.1.3 产生死锁的必要条件9.2 死锁的预防、避免、检测与恢复9.2.1 死锁预防9.2.2 死锁避免9.2.3 死锁检测与恢复9.3 系统的安全与保护 9.3.1 安全与保护概述 9.3.2 具体的安全威胁进程P1： 进程P2： 申请资源A 申请资源B 申请资源B 申请资源A 释放资源A 释放资源B 释放资源B 释放资源A 9.1 死锁概述 o9.1.1 死锁的概念 死锁举例 1.两个进程P1和P2， 执行过程中要用到需互 斥使用的资源A和B。两 进程的执行框架为下： .P1的进展P2的进展申请B申请A申请A申请B释放B释放B释放A释放A死锁区不可进入的禁区123456不可进入的禁区死锁点如图所示，给出这两个进 程执行时的联合进展情况。 申请资源：若所申请的资源暂时不可用，那么提出申请的进程就只 能等待，一直要等到占用该资源的进程释放了资源为止； 2. 死锁的定义 通常，进程以下面的方式使用资源： . (1)(2) 使用资源； (3) 释放资源。 . 所谓“可抢占资源”，是指可从拥有它的进程手中抢夺过来而不会产生副作用的那些 资源；所谓“不可抢占的资源”，是指不能从当前拥有它的进程手中抢夺，否则就会引起 不必要的麻烦的那些资源。 . 所谓“死锁”，是指若一个进程集合中的所有进程，都在等待只能由该组进程中的其 他进程才能引发的一个事件，那么就说这组进程是死锁的。 “死锁”与“饥饿”是两个不同的概念。在资源分配策略中，一些进程由于它们的优先 级不如其他进程高，因此所提出的资源请求被无限期地忽略。这种现象称为“饥饿”。 . 死锁是两个或更多的进程占有资源而又请求其他资源时引起的一种状态。某个进程 占有着另一个进程请求的资源，同时又请求第二种资源；而另一个进程占有着第二种资 源，同时又请求前面进程所占有的资源。如此这般，使几个进程都不能继续执行。 . 定义中所说的“进程都在等待”，只是可能产生死锁的前提，关键是它们在等待谁来 引发它们所等待的事件。死锁时，等待引发事件的进程就是该组中的其他进程。由于这 组进程中，没有一个进程有能力引发唤醒该进程集合中其他进程的事件，所以它们都只 能无限期地僵持在那里而形成死锁。 返回目录三个进程A、B、C和三个资 源R、S、T（都只一个单元）。现有两种资源申请-释放序列：（1）A申请RB申请 SC申请TA申请SB申请TC申请R；（2）A申请RC申请TA申请SC申请 RA释放RA释放S。用资源分配图描述这两个申请-释放序列，并对它们做出结论。o9.1.2 资源分配图 可以用“资源分配图”来勾勒系统中各个进程的资源分配情况，从中反映 哪个进程已经分配了什么资源，哪个进程由于等候什么资源而处于阻塞。 .资源分配图中，约定圆圈代表进程，方框代表资源，资源结点内的圆点个数表示 这种资源可分配的单元数。从一个进程到资源的有向边，表示该进程申请这种资源，但 还没有得到；从资源到进程的有向边，表示已把该资源的一个单元分配给了这个进程。 如图给出了资源分配图的图例。 请求Ra占有Ra(a)(b)P1P1请求(c)占有Rb请求占有请求Ra (d)占有Rb请求占有P1P2P1P2Ra例9-1 ：.ABCRST(a)ABCRST(b)ABCRST(c)ABCRST(d)ABCRST(e)(f)ABCRST序列（1）的资源分配图如图(a)图(f)所示。此序列实施完后，出现了 进程和资源间的循环等待，即三个进程A、B、C死锁了。 . 序列（2）的资源分配图如图(g)图(l)所示。 整个序列执行完后，在三个进程间没有死锁发生。ABCRST(g)ABCRST(h)ABCRST(i)ABCRST(k)ABCRST(j)ABCRST(l)返回目录“占有并等待”条件：当进程由于申请不到所需资源而等待时，仍占据已分配到的 资源。也就是说，进程不是一次性地得到所需的所有资源，而是在占有一部分资源的情 况下，允许继续申请新的资源。在资源分配中，若一组进程间同时存在下面列出的四个条件，那么就 可能出现死锁。 o9.1.3 产生死锁的必要条件 .(1) 互斥”条件：一旦某个特定资源分配给了一个进程使用，那么该进程 就独占使用这个资源，其他进程不得使用，直到它被释放为止。 (2)(3) “不可抢占”条件：已分配给进程的资源，别的进程不能强行夺取，只能由占用它 的进程自己释放。 (4) “循环等待”条件：系统中存在两个以上的进程，它们组成一个环路，环路中的每 个进程都在等待其他进程占用的资源。 为解决死锁问题，可有下面几种对策。 (1) 忽略死锁：系统中任凭出现死锁，出现死锁时，就重新启动系统。 (2) 预防死锁：上述四个条件是死锁存在的必要条件，通过破坏四个必要条件之一， 就可使系统不具备产生死锁的温床（即条件）。 (3) 避免死锁：小心对待进程提出的每个资源请求，只有在能确保所提出的资源请求 不会招致死锁时，才接受进程提出的资源请求。 (4) 检测死锁并恢复：允许系统出现死锁，能通过一定的办法加以发现和恢复。 返回目录o9.2.1 死锁预防 9.2 死锁的预防、避免、检测与恢复所谓“死锁预防”，就是试图让设计出来的系统里不包含上述四个必要条件中的某 一个。既然排除了发生死锁的可能，系统也就不会出现死锁了。 .1. 破坏“互斥”条件 破坏“互斥”条件，就是在系统里取消互斥。若资源不被一个进程独占使用，那么死 锁是肯定不会发生的。 . . 但一般来说在所列的四个条件中，“互斥”条件是无法破坏的。因此，在死锁预防里 主要是破坏其他几个必要条件，而不去涉及破坏“互斥”条件。 2. 破坏“占有并等待”条件 . 破坏“占有并等待”条件，就是在系统中不允许进程在已获得某种资源的情况下，申 请其他资源。即要想出一个办法，阻止进程在持有资源的同时申请其他资源。 . 方法一：创建进程时，要求它申请所需的全部资源，系统或满足其所有要求，或 么什么也不给它。这是所谓的“一次性分配”方案。. 方法二：要求每个进程提出新的资源申请前，释放它所占有的资源。这样，一个 进程在需要资源S时，须先把它先前占有的资源R释放掉，然后才能提出对S的申请，即 使它可能很快又要用到资源R。 3. 破坏“不可抢占”条件 .破坏“不可抢占”条件，就是允许对资源实行抢夺。4. 破坏“循环等待”条件 . 破坏“循环等待”条件的一种方法，是将系统中的所有资源统一编号， 进程可在任何时刻提出资源申请，但所有申请必须按照资源的编号顺序（升序）提出。 这样做就能保证系统不出现死锁。 1. 输入机 2. 打印机 3. 扫描仪 4. 绘图仪 5. 磁带机 6. CD-ROMABijABij(a)(b)(c).如图（b）所示，假定把不同编号的 资源i和j分配给了进程A和B，那么如果ij， A就不允许再申请资源j，因为这个编号小于A已有资源的编号；如果ij，B就不允许再申 请资源i，因为这个编号小于B已有资源的编号。如图（a）所示，对系统中的5种资 源进行了统一编号，进程可以先申请打印 机，再申请磁带机，但不能先申请磁带机 ，再申请打印机，因为那样做不符合规定 的资源申请原则。 .按这样的规则申请资源，不会形成如图(c)所示的循环等待的环路，破坏了“循环等 待”的条件。.返回目录o9.2.2 死锁避免 1. “拒绝启动进程”法. 所谓“死锁避免”，是允许系统里存在产生死锁的条件，但对于进程的每 次资源申请，都将根据当时资源的分配情况，探测分配结果。只有在探测结 果不会有死锁发生时，才正式接受这次资源请求，把资源分配给进程。 拒绝启动进程法：若一个进程对资源的申请会导致死锁，则不启动该进程。 具体做法是考虑有n个进程、m种不同类型资源的系统。定义如下向量和矩阵： . (1)系统中每种资源的总量（向量）Resource=R=(R1，R2，Rm)； (2) 未分配的每种资源剩余数（向量）Available=V=( V1，V2，Vm)； (3) 每个进程对各种资源的最大需求矩阵： Claim = C =C11 C12 C1m C21 C22 C2m Cn1 Cn2 Cnm每个进程已分配的各种资源数矩阵： (4)Allocation = A =A11 A12 A1m A21 A22 A2m An1 An2 Anm.可以看出有以下关系存在： (1) 所有资源或者可分配，或者已经被分配，即： Rj = Vj +A i j ，对所有的 j i=1n(2) 任何一个进程对任何一种资源的申请，都不能超过系统中这种资源的总量，即： C i j R i ，对所有i，j(3) 分配给任何一个进程的任何一种资源，都不会超过这个进程对该资源的最大需求量 ，即： A i j C i j ，对所有i，j .有了这些准备工作，就可以给出所谓的“拒绝启动进程”的死锁避免方法，即只有在 满足下面的条件：Rj C(n+1) j +C i j ，对所有的 j i=1n时，才允许启动一个新进程Pn+1，否则拒绝启动。 . 即只有在当前所有进程的最大需求量加上新进程的最大需求量后，系统拥有的各 类资源数能够满足它们的要求，那么这才启动一个新的进程。由于这个“拒绝启动进程”法是建立在所有进程都需要最大资源数的基础之上的，保 险系数打得太大，所以不可能是最优的策略。.在接到一个进程对资源的请求时，有权根据当前资源的使用情况暂时加以拒绝 （即阻塞该进程），但保证在有限的时间内让它得到所需要的资源。 2. “拒绝分配资源”法 .所谓系统处于“安全状态”，就是至少存在有一个进程的执行序列，能 够在有限时间内使所有进程最终都能够运行到结束，不导致死锁；否则，就 说系统处于“不安全状态”。 “拒绝分配资源”法即有名的“银行家算法”，它以银行系统所采用的借贷策略为基础 建立资源分配的模型。银行只有有限数目的资金（资源），可用来借贷给不同客户（进 程）。贷款限额是客户对资金的最大需求量。算法对每个资源申请都进行测试，判断接 受申请是否会致使系统进入不安全状态。如果是就拒绝分配；如果接受申请后系统仍然 是安全的，那么就予以分配。 .为实行银行家算法，对进程提出的要求是：(1) 必须预先说明自己对资源的最大需求量； (2)(3)只能一次一个地申请所需要的资源； 如果已获得资源的最大需求量，那应在有限的时间内使用完毕，并归还系统。 .为实行银行家算法，系统的承诺如下： (1) 若一个进程对资源的最大需求量没有超过该资源的总量，那么必须接纳这个进 程，不得拒绝它； (2)在“能执行完”标志为0的进 程中重复以上两步，直到找不到 资源还需数小于系统剩余资源数 的进程时为止。 单种资源的银行家算法 .单种资源银行家算法：将所有进程的 “能执行完”标志清0假定接受该请求, 把资源分配给进程将系统当前所有剩余资源 与”能执行完”标志为0的进 程还需资源数比较,找出一 个能满足其所有需求的进程找