拓冰网站定制 
王道操作系统笔记视频链接2.4.3 死锁的处理策略—避免死锁知识总览死锁的处理不允许死锁发生静态策略预防死锁动态策略避免死锁本节内容什么是安全序列什么是系统的不安全状态与死锁有何联系如何避免系统进入不安全状态——银行家算法允许死锁发生死锁的检测和解除什么是安全序列你是一位成功的银行家手里掌握着100个亿的资金有三个企业想找你贷款分别是企业B、企业A、企业T为描述方便简称BAT。B表示“大哥我最多会跟你借70亿…”A表示“大哥我最多会跟你借40亿…”T表示“大哥我最多会跟你借50亿…”然而江湖中有个不成文的规矩如果你借给企业的钱总数达不到企业提出的最大要求那么不管我之前给企业借了多少钱那些钱都拿不回来了。刚开始BAT三个企业分别从你这儿借了20、10、30亿。表企业最大需求已借走最多还会借B702050A401030T503020假设手里还有40亿此时B还想借30亿应该借吗如果答应了B那么手里只剩下10亿此时如果BAT都提出再借20亿的请求那么任何一个企业的需求都得不到满足。也就是都没有回款所以不该借。此时A还想借20亿应该借吗如果答应了A那么手里还有20亿可以先把20亿全借给T等T把钱全部还回来了手里就会有50亿再把这些钱全借给BB还钱后会有70亿最后再借给A这样就会全部回款PS当然也可以有其他顺序T→ \to→B→ \to→A或者A→ \to→T→ \to→B都可以所谓安全序列就是指如果系统按照这种序列分配资源则每个进程都能顺利完成。只要能找出一个安全序列系统就是安全状态。当然安全序列可能有多个。如果分配了资源之后系统中找不出任何一个安全序列系统就进入了不安全状态。这就意味着之后可能所有进程都无法顺利的执行下去。当然如果有进程提前归还了一些资源那系统也有可能重新回到安全状态比如A先归还了10亿不过我们在分配资源之前总是要考虑到最坏的情况。如果系统处于安全状态就一定不会发生死锁。如果系统进入不安全状态就可能发生死锁。处于不安全状态未必就是发生了死锁但发生死锁时一定是在不安全状态。因此可以在资源分配之前预先判断这次分配是否会导致系统进入不安全状态以此决定是否答应资源分配请求这也是“银行家算法”的核心思想。银行家算法银行家算法是荷兰学者 Dijkstra 为银行系统设计的以确保银行在发放现金贷款时不会发生不能满足所有客户需要的情况。后来该算法被用在操作系统中用于避免死锁。核心思想在进程提出资源申请时先预判此次分配是否会导致系统进入不安全状态。如果会进入不安全状态就暂时不答应这次请求让该进程先阻塞等待。思考BAT 的例子中只有一种类型的资源——钱但是在计算机系统中会有多种多样的资源应该怎么把算法拓展为多种资源的情况呢解决方法可以把单维的数字拓展为多维的向量。例子系统中有5个进程 P0到P43种资源 R0到R2初始数量为 (10, 5, 7)假设某一时刻的情况可表示如下进程最大需求已分配最多还需要P0(7, 5, 3)(0, 1, 0)(7, 4, 3)P1(3, 2, 2)(2, 0, 0)(1, 2, 2)P2(9, 0, 2)(3, 0, 2)(6, 0, 0)P3(2, 2, 2)(2, 1, 1)(0, 1, 1)P4(4, 3, 3)(0, 0, 2)(4, 3, 1)根据以上表格已知资源总数 (10, 5, 7)剩余可用资源 (3, 3, 2)问题此时系统是否处于安全状态思路尝试找出一个安全序列。依次检查剩余可用资源 (3, 3, 2) 是否能满足各进程的需求P0分配不行P1可以分配说明可以优先把资源分配给P1然后等P1结束会得到更多资源此时资源数为(2, 0, 0) (3, 3, 2) (5, 3, 2)可满足P1需求将 P1 加入安全序列并更新剩余可用资源值为 (5, 3, 2)依次检查剩余可用资源 (5, 3, 2) 是否能满足剩余进程的需求这里以及后续类似步骤都不包括已加入安全序列的进程可满足P3需求将 P3 加入安全序列并更新剩余可用资源值为 (7, 4, 3)依次检查剩余可用资源 (7, 4, 3) 是否能满足剩余进程的需求……以此类推共五次循环检查即可将5个进程都加入安全序列中最终可得一个安全序列。该算法称为安全性算法。可以很方便地用代码实现以上流程每一轮检查都从编号较小的进程开始检查。实际做题(手算)时可以更快速的得到安全序列就是一次性对比多项比如第一次(3, 3, 2) 的资源可以满足P1和P3就把P1和P3都加入安全序列然后继续计算说明此时系统处于安全状态暂不可能发生死锁进程最大需求已分配最多还需要P0(8, 5, 3)(0, 1, 0)(8, 4, 3)P1(3, 2, 2)(2, 0, 0)(1, 2, 2)P2(9, 5, 2)(3, 0, 2)(6, 5, 0)P3(2, 2, 2)(2, 1, 1)(0, 1, 1)P4(4, 3, 6)(0, 0, 2)(4, 3, 4)上面的表格是一个找不到安全序列的例子已知资源总数 (10, 5, 7)剩余可用资源 (3, 3, 2)经对比发现(3, 3, 2) 可满足 P1、P3说明无论如何这两个进程的资源需求一定是可以依次被满足的因此P1、P3一定可以顺利的执行完并归还资源。可把 P1、P3 先加入安全序列。返还后剩余可用资源总数为(2, 0, 0) (2, 1, 1) (3, 3, 2) (7, 4, 3)剩下的 P0 需要 (8, 4, 3)P2 需要 (6, 5, 0)P4 需要 (4, 3, 4)任何一个进程都不能被完全满足于是无法找到任何一个安全序列说明此时系统处于不安全状态有可能发生死锁。代码实现方法假设系统中有 n 个进程m 种资源每个进程在运行前先声明对各种资源的最大需求数则可用一个 n*m 的矩阵 (可用二维数组实现) 表示所有进程对各种资源的最大需求数。不妨称为最大需求矩阵 MaxMax[i, j]K 表示进程P i P_iPi最多需要 K 个资源R j R_jRj。同理系统可以用一个 n*m 的分配矩阵 Allocation表示对所有进程的资源分配情况。Max - Allocation Need 矩阵表示各进程最多还需要多少各类资源。另外还要用一个长度为 m 的一维数组 Available表示当前系统中还有多少可用资源。某进程P i P_iPi向系统申请资源可用一个长度为 m 的一维数组R e q u e s t i Request_iRequesti表示本次申请的各种资源量。进程最大需求已分配最多还需要P0(7, 5, 3)(2, 2, 1)(5, 3, 2)P1(3, 2, 2)(2, 0, 0)(1, 2, 2)P2(9, 0, 2)(3, 0, 2)(6, 0, 0)P3(2, 2, 2)(2, 1, 1)(0, 1, 1)P4(4, 3, 3)(0, 0, 2)(4, 3, 1)如上表格所示可用银行家算法预判本次分配是否会导致系统进入不安全状态①如果R e q u e s t [ i , j ] ≤ N e e d [ i , j ] Request[i,j] \leq Need[i,j]Request[i,j]≤Need[i,j](0≤j≤m) 便转向②否则认为出错。也就是算出来发现进程所需的资源数已经超过它所宣布的最大值②如果R e q u e s t [ i , j ] ≤ A v a i l a b l e [ i , j ] Request[i,j] \leq Available[i,j]Request[i,j]≤Available[i,j](0≤j≤m)便转向③否则表示尚无足够资源P i P_iPi必须等待。③系统试探着把资源分配给进程P i P_iPi并修改相应的数据并非真的分配修改数值只是为了做预判A v a i l a b l e A v a i l a b l e − R e q u e s t ; Available Available - Request;AvailableAvailable−Request;A l l o c a t i o n [ i , j ] A l l o c a t i o n [ i , j ] R e q u e s t [ i , j ] ; Allocation[i, j] Allocation[i, j] Request[i,j];Allocation[i,j]Allocation[i,j]Request[i,j];N e e d [ i , j ] N e e d [ i , j ] − R e q u e s t [ i , j ] Need[i, j] Need[i,j] - Request[i,j]Need[i,j]Need[i,j]−Request[i,j]④操作系统执行安全性算法检查此次资源分配后系统是否处于安全状态。若安全才正式分配否则恢复相应数据让进程阻塞等待。知识回顾与重要考点数据结构长度为m mm的一维数组A v a i l a b l e AvailableAvailable表示还有多少可用资源n ∗ m n*mn∗m矩阵M a x MaxMax表示各进程对资源的最大需求数n ∗ m n*mn∗m矩阵A l l o c a t i o n AllocationAllocation表示已经给各进程分配了多少资源M a x − A l l o c a t i o n N e e d Max - Allocation NeedMax−AllocationNeed矩阵表示各进程最多还需要多少资源用长度为m mm的一位数组R e q u e s t RequestRequest表示进程此次申请的各种资源数银行家算法步骤①检查此次申请是否超过了之前声明的最大需求数②检查此时系统剩余的可用资源是否还能满足这次请求③试探着分配更改各数据结构④用安全性算法检查此次分配是否会导致系统进入不安全状态安全性算法步骤检查当前的剩余可用资源是否能满足某个进程的最大需求如果可以就把该进程加入安全序列并把该进程持有的资源全部回收。不断重复上述过程看最终是否能让所有进程都加入安全序列。PS安全性算法是银行家算法中的核心子步骤当然安全性算法也可以单独用。考察银行家算法时一般会告诉此时系统当中还有多少可用资源A v a i l a b l e AvailableAvailable并且告诉M a x MaxMax和A l l o c a t i o n AllocationAllocation矩阵可以根据这两个矩阵计算N e e d NeedNeed之后就可以根据前面的流程判断系统安全性如何注意事项先理解算法逻辑再钻研代码逻辑死锁和不安全状态的关系经常在选择题中考察系统处于不安全状态未必死锁但死锁时一定处于不安全状态。系统处于安全状态一定不会死锁。 操作系统笔记-2.4.3 死锁的处理策略—避免死锁
王道操作系统笔记视频链接2.4.3 死锁的处理策略—避免死锁知识总览死锁的处理不允许死锁发生静态策略预防死锁动态策略避免死锁本节内容什么是安全序列什么是系统的不安全状态与死锁有何联系如何避免系统进入不安全状态——银行家算法允许死锁发生死锁的检测和解除什么是安全序列你是一位成功的银行家手里掌握着100个亿的资金有三个企业想找你贷款分别是企业B、企业A、企业T为描述方便简称BAT。B表示“大哥我最多会跟你借70亿…”A表示“大哥我最多会跟你借40亿…”T表示“大哥我最多会跟你借50亿…”然而江湖中有个不成文的规矩如果你借给企业的钱总数达不到企业提出的最大要求那么不管我之前给企业借了多少钱那些钱都拿不回来了。刚开始BAT三个企业分别从你这儿借了20、10、30亿。表企业最大需求已借走最多还会借B702050A401030T503020假设手里还有40亿此时B还想借30亿应该借吗如果答应了B那么手里只剩下10亿此时如果BAT都提出再借20亿的请求那么任何一个企业的需求都得不到满足。也就是都没有回款所以不该借。此时A还想借20亿应该借吗如果答应了A那么手里还有20亿可以先把20亿全借给T等T把钱全部还回来了手里就会有50亿再把这些钱全借给BB还钱后会有70亿最后再借给A这样就会全部回款PS当然也可以有其他顺序T→ \to→B→ \to→A或者A→ \to→T→ \to→B都可以所谓安全序列就是指如果系统按照这种序列分配资源则每个进程都能顺利完成。只要能找出一个安全序列系统就是安全状态。当然安全序列可能有多个。如果分配了资源之后系统中找不出任何一个安全序列系统就进入了不安全状态。这就意味着之后可能所有进程都无法顺利的执行下去。当然如果有进程提前归还了一些资源那系统也有可能重新回到安全状态比如A先归还了10亿不过我们在分配资源之前总是要考虑到最坏的情况。如果系统处于安全状态就一定不会发生死锁。如果系统进入不安全状态就可能发生死锁。处于不安全状态未必就是发生了死锁但发生死锁时一定是在不安全状态。因此可以在资源分配之前预先判断这次分配是否会导致系统进入不安全状态以此决定是否答应资源分配请求这也是“银行家算法”的核心思想。银行家算法银行家算法是荷兰学者 Dijkstra 为银行系统设计的以确保银行在发放现金贷款时不会发生不能满足所有客户需要的情况。后来该算法被用在操作系统中用于避免死锁。核心思想在进程提出资源申请时先预判此次分配是否会导致系统进入不安全状态。如果会进入不安全状态就暂时不答应这次请求让该进程先阻塞等待。思考BAT 的例子中只有一种类型的资源——钱但是在计算机系统中会有多种多样的资源应该怎么把算法拓展为多种资源的情况呢解决方法可以把单维的数字拓展为多维的向量。例子系统中有5个进程 P0到P43种资源 R0到R2初始数量为 (10, 5, 7)假设某一时刻的情况可表示如下进程最大需求已分配最多还需要P0(7, 5, 3)(0, 1, 0)(7, 4, 3)P1(3, 2, 2)(2, 0, 0)(1, 2, 2)P2(9, 0, 2)(3, 0, 2)(6, 0, 0)P3(2, 2, 2)(2, 1, 1)(0, 1, 1)P4(4, 3, 3)(0, 0, 2)(4, 3, 1)根据以上表格已知资源总数 (10, 5, 7)剩余可用资源 (3, 3, 2)问题此时系统是否处于安全状态思路尝试找出一个安全序列。依次检查剩余可用资源 (3, 3, 2) 是否能满足各进程的需求P0分配不行P1可以分配说明可以优先把资源分配给P1然后等P1结束会得到更多资源此时资源数为(2, 0, 0) (3, 3, 2) (5, 3, 2)可满足P1需求将 P1 加入安全序列并更新剩余可用资源值为 (5, 3, 2)依次检查剩余可用资源 (5, 3, 2) 是否能满足剩余进程的需求这里以及后续类似步骤都不包括已加入安全序列的进程可满足P3需求将 P3 加入安全序列并更新剩余可用资源值为 (7, 4, 3)依次检查剩余可用资源 (7, 4, 3) 是否能满足剩余进程的需求……以此类推共五次循环检查即可将5个进程都加入安全序列中最终可得一个安全序列。该算法称为安全性算法。可以很方便地用代码实现以上流程每一轮检查都从编号较小的进程开始检查。实际做题(手算)时可以更快速的得到安全序列就是一次性对比多项比如第一次(3, 3, 2) 的资源可以满足P1和P3就把P1和P3都加入安全序列然后继续计算说明此时系统处于安全状态暂不可能发生死锁进程最大需求已分配最多还需要P0(8, 5, 3)(0, 1, 0)(8, 4, 3)P1(3, 2, 2)(2, 0, 0)(1, 2, 2)P2(9, 5, 2)(3, 0, 2)(6, 5, 0)P3(2, 2, 2)(2, 1, 1)(0, 1, 1)P4(4, 3, 6)(0, 0, 2)(4, 3, 4)上面的表格是一个找不到安全序列的例子已知资源总数 (10, 5, 7)剩余可用资源 (3, 3, 2)经对比发现(3, 3, 2) 可满足 P1、P3说明无论如何这两个进程的资源需求一定是可以依次被满足的因此P1、P3一定可以顺利的执行完并归还资源。可把 P1、P3 先加入安全序列。返还后剩余可用资源总数为(2, 0, 0) (2, 1, 1) (3, 3, 2) (7, 4, 3)剩下的 P0 需要 (8, 4, 3)P2 需要 (6, 5, 0)P4 需要 (4, 3, 4)任何一个进程都不能被完全满足于是无法找到任何一个安全序列说明此时系统处于不安全状态有可能发生死锁。代码实现方法假设系统中有 n 个进程m 种资源每个进程在运行前先声明对各种资源的最大需求数则可用一个 n*m 的矩阵 (可用二维数组实现) 表示所有进程对各种资源的最大需求数。不妨称为最大需求矩阵 MaxMax[i, j]K 表示进程P i P_iPi最多需要 K 个资源R j R_jRj。同理系统可以用一个 n*m 的分配矩阵 Allocation表示对所有进程的资源分配情况。Max - Allocation Need 矩阵表示各进程最多还需要多少各类资源。另外还要用一个长度为 m 的一维数组 Available表示当前系统中还有多少可用资源。某进程P i P_iPi向系统申请资源可用一个长度为 m 的一维数组R e q u e s t i Request_iRequesti表示本次申请的各种资源量。进程最大需求已分配最多还需要P0(7, 5, 3)(2, 2, 1)(5, 3, 2)P1(3, 2, 2)(2, 0, 0)(1, 2, 2)P2(9, 0, 2)(3, 0, 2)(6, 0, 0)P3(2, 2, 2)(2, 1, 1)(0, 1, 1)P4(4, 3, 3)(0, 0, 2)(4, 3, 1)如上表格所示可用银行家算法预判本次分配是否会导致系统进入不安全状态①如果R e q u e s t [ i , j ] ≤ N e e d [ i , j ] Request[i,j] \leq Need[i,j]Request[i,j]≤Need[i,j](0≤j≤m) 便转向②否则认为出错。也就是算出来发现进程所需的资源数已经超过它所宣布的最大值②如果R e q u e s t [ i , j ] ≤ A v a i l a b l e [ i , j ] Request[i,j] \leq Available[i,j]Request[i,j]≤Available[i,j](0≤j≤m)便转向③否则表示尚无足够资源P i P_iPi必须等待。③系统试探着把资源分配给进程P i P_iPi并修改相应的数据并非真的分配修改数值只是为了做预判A v a i l a b l e A v a i l a b l e − R e q u e s t ; Available Available - Request;AvailableAvailable−Request;A l l o c a t i o n [ i , j ] A l l o c a t i o n [ i , j ] R e q u e s t [ i , j ] ; Allocation[i, j] Allocation[i, j] Request[i,j];Allocation[i,j]Allocation[i,j]Request[i,j];N e e d [ i , j ] N e e d [ i , j ] − R e q u e s t [ i , j ] Need[i, j] Need[i,j] - Request[i,j]Need[i,j]Need[i,j]−Request[i,j]④操作系统执行安全性算法检查此次资源分配后系统是否处于安全状态。若安全才正式分配否则恢复相应数据让进程阻塞等待。知识回顾与重要考点数据结构长度为m mm的一维数组A v a i l a b l e AvailableAvailable表示还有多少可用资源n ∗ m n*mn∗m矩阵M a x MaxMax表示各进程对资源的最大需求数n ∗ m n*mn∗m矩阵A l l o c a t i o n AllocationAllocation表示已经给各进程分配了多少资源M a x − A l l o c a t i o n N e e d Max - Allocation NeedMax−AllocationNeed矩阵表示各进程最多还需要多少资源用长度为m mm的一位数组R e q u e s t RequestRequest表示进程此次申请的各种资源数银行家算法步骤①检查此次申请是否超过了之前声明的最大需求数②检查此时系统剩余的可用资源是否还能满足这次请求③试探着分配更改各数据结构④用安全性算法检查此次分配是否会导致系统进入不安全状态安全性算法步骤检查当前的剩余可用资源是否能满足某个进程的最大需求如果可以就把该进程加入安全序列并把该进程持有的资源全部回收。不断重复上述过程看最终是否能让所有进程都加入安全序列。PS安全性算法是银行家算法中的核心子步骤当然安全性算法也可以单独用。考察银行家算法时一般会告诉此时系统当中还有多少可用资源A v a i l a b l e AvailableAvailable并且告诉M a x MaxMax和A l l o c a t i o n AllocationAllocation矩阵可以根据这两个矩阵计算N e e d NeedNeed之后就可以根据前面的流程判断系统安全性如何注意事项先理解算法逻辑再钻研代码逻辑死锁和不安全状态的关系经常在选择题中考察系统处于不安全状态未必死锁但死锁时一定处于不安全状态。系统处于安全状态一定不会死锁。