《操作系统》 9死锁、系统安全课件

第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死锁概述9.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申请R→B申请S→C申请T→A申请S→B申请T→C申请R；（2）A申请R→C申请T→A申请S→C申请R→A释放R→A释放S。用资源分配图描述这两个申请-释放序列，并对它们做出结论。9.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)返回目录“占有并等待”条件：当进程由于申请不到所需资源而等待时，仍占据已分配到的资源。也就是说，进程不是一次性地得到所需的所有资源，而是在占有一部分资源的情况下，允许继续申请新的资源。在资源分配中，若一组进程间同时存在下面列出的四个条件，那么就可能出现死锁。9.1.3产生死锁的必要条件..(1)互斥”条件：一旦某个特定资源分配给了一个进程使用，那么该进程就独占使用这个资源，其他进程不得使用，直到它被释放为止。(2)(3)“不可抢占”条件：已分配给进程的资源，别的进程不能强行夺取，只能由占用它的进程自己释放。(4)“循环等待”条件：系统中存在两个以上的进程，它们组成一个环路，环路中的每个进程都在等待其他进程占用的资源。为解决死锁问题，可有下面几种对策。(1)忽略死锁：系统中任凭出现死锁，出现死锁时，就重新启动系统。(2)预防死锁：上述四个条件是死锁存在的必要条件，通过破坏四个必要条件之一，就可使系统不具备产生死锁的温床（即条件）。(3)避免死锁：小心对待进程提出的每个资源请求，只有在能确保所提出的资源请求不会招致死锁时，才接受进程提出的资源请求。(4)检测死锁并恢复：允许系统出现死锁，能通过一定的办法加以发现和恢复。返回目录9.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)所示的循环等待的环路，破坏了“循环等待”的条件。.返回目录9.2.2死锁避免1.“拒绝启动进程”法..所谓“死锁避免”，是允许系统里存在产生死锁的条件，但对于进程的每次资源申请，都将根据当时资源的分配情况，探测分配结果。只有在探测结果不会有死锁发生时，才正式接受这次资源请求，把资源分配给进程。拒绝启动进程法：若一个进程对资源的申请会导致死锁，则不启动该进程。具体做法是考虑有n个进程、m种不同类型资源的系统。定义如下向量和矩阵：.(1)系统中每种资源的总量（向量）Resource=R=(R1，R2，…Rm)；(2)未分配的每种资源剩余数（向量）Available=V=(V1，V2，…Vm)；(3)每个进程对各种资源的最大需求矩阵：Claim=C=C11C12…C1mC21C22…C2m…………Cn1Cn2…Cnm每个进程已分配的各种资源数矩阵：(4)Allocation=A=A11A12…A1mA21A22…A2m…………An1An2…Anm.可以看出有以下关系存在：(1)所有资源或者可分配，或者已经被分配，即：Rj=Vj+∑Aij，对所有的ji=1n(2)任何一个进程对任何一种资源的申请，都不能超过系统中这种资源的总量，即：Cij≤Ri，对所有i，j(3)分配给任何一个进程的任何一种资源，都不会超过这个进程对该资源的最大需求量，即：Aij≤Cij，对所有i，j.有了这些准备工作，就可以给出所谓的“拒绝启动进程”的死锁避免方法，即只有在满足下面的条件：Rj≥C(n+1)j+∑Cij，对所有的ji=1n时，才允许启动一个新进程Pn+1，否则拒绝启动。.即只有在当前所有进程的最大需求量加上新进程的最大需求量后，系统拥有的各类资源数能够满足它们的要求，那么这才启动一个新的进程。由于这个“拒绝启动进程”法是建立在所有进程都需要最大资源数的基础之上的，保险系数打得太大，所以不可能是最优的策略。.在接到一个进程对资源的请求时，有权根据当前资源的使用情况暂时加以拒绝（即阻塞该进程），但保证在有限的时间内让它得到所需要的资源。2.“拒绝分配资源”法..所谓系统处于“安全状态”，就是至少存在有一个进程的执行序列，能够在有限时间内使所有进程最终都能够运行到结束，不导致死锁；否则，就说系统处于“不安全状态”。“拒绝分配资源”法即有名的“银行家算法”，它以银行系统所采用的借贷策略为基础建立资源分配的模型。银行只有有限数目的资金（资源），可用来借贷给不同客户（进程）。贷款限额是客户对资金的最大需求量。算法对每个资源申请都进行测试，判断接受申请是否会致使系统进入不安全状态。如果是就拒绝分配；如果接受申请后系统仍然是安全的，那么就予以分配。.为实行银行家算法，对进程提出的要求是：(1)必须预先说明自己对资源的最大需求量；(2)(3)只能一次一个地申请所需要的资源；如果已获得资源的最大需求量，那应在有限的时间内使用完毕，并归还系统。.为实行银行家算法，系统的承诺如下：(1)若一个进程对资源的最大需求量没有超过该资源的总量，那么必须接纳这个进程，不得拒绝它；(2)在“能执行完”标志为0的进程中重复以上两步，直到找不到资源还需数小于系统剩余资源数的进程时为止。单种资源的银行家算法.单种资源银行家算法：将所有进程的“能执行完”标志清0假定接受该请求,把资源分配给进程将系统当前所有剩余资源与”能执行完”标志为0的进程还需资源数比较,找出一个能满足其所有需求的进程找到了吗？将该进程的”能执行完”标志置为1,系统收回它所要求的全部资源数YN检查所有进程的“能执行完”标志还有”能执行完”标志为0的进程吗？这一请求不安全,暂时不予接受YN这一请求是安全的,可以分配在安全状态下，系统接到进程的资源请求后，先假定接受这一请求，把需要的资源分配给这个进程。(1)(2)在该假设下，检查每个进程对资源的还需要数。看能否找到一个进程，其还需数目小于系统剩余资源数。如果找不到，那么系统就有可能死锁，因为任何进程都无法运行结束。(3)若找到了，假设它获得了最大资源数，并运行结束。于是把它的“能执行完”标志置为1。这样就能假定收回它使用的所有资源，使系统剩余资源数增加。(4)(5)若所有进程的“能执行完”均为1，表示接受这次请求是安全的；否则暂时不能接受进程的这次资源请求。资源总量为10。三个进程A、B、C的最大资源需求量分别是9、4、7，如图（a）所示。若干次请求后，资源使用情况如图（b）所示。现在进程B提出一个资源请求，系统可接受该请求吗？请用银行家算法进行测试，做出判断。例9-2：ABC进程最大需求947已有量000系统剩余数：10(a)ABC进程最大需求947已有量322系统剩余数：3(b)ABC进程最大需求947已有量332系统剩余数：2(c)ABC进程最大需求947已有量342系统剩余数：1(d)ABC进程最大需求9--7已有量302系统剩余数：5(e)ABC进程最大需求9--7已有量307系统剩余数：0(f)ABC进程最大需求9----已有量300系统剩余数