银行家算法(28页PPT).pptx

计算机操作系统计算机操作系统2死锁的死锁的“3W”3W”WhatWhyHow什么是死锁？什么是死锁？为什么会发生死锁？为什么会发生死锁？怎么解决死锁？怎么解决死锁？3死锁的处理方法死锁的处理方法 （1 1）预防死锁）预防死锁）预防死锁）预防死锁：通过某些限制条件的设置，去破坏产生通过某些限制条件的设置，去破坏产生通过某些限制条件的设置，去破坏产生通过某些限制条件的设置，去破坏产生死锁的四个必要条件；死锁的四个必要条件；死锁的四个必要条件；死锁的四个必要条件； （2 2）避免死锁）避免死锁）避免死锁）避免死锁：在资源的动态分配过程中，用某种方法去在资源的动态分配过程中，用某种方法去在资源的动态分配过程中，用某种方法去在资源的动态分配过程中，用某种方法去防止系统进入不安全状态；防止系统进入不安全状态；防止系统进入不安全状态；防止系统进入不安全状态； （3 3）检测死锁）检测死锁）检测死锁）检测死锁：及时检测死锁的发生，并确定与之相关及时检测死锁的发生，并确定与之相关及时检测死锁的发生，并确定与之相关及时检测死锁的发生，并确定与之相关的进程、资源，从而采取措施清除死锁；的进程、资源，从而采取措施清除死锁；的进程、资源，从而采取措施清除死锁；的进程、资源，从而采取措施清除死锁； （4 4）解除死锁）解除死锁）解除死锁）解除死锁：撤消或挂起某些进程以回收一些资源，用于撤消或挂起某些进程以回收一些资源，用于撤消或挂起某些进程以回收一些资源，用于撤消或挂起某些进程以回收一些资源，用于解脱另一些处于死锁的进程。

解脱另一些处于死锁的进程解脱另一些处于死锁的进程解脱另一些处于死锁的进程4避免死锁避免死锁银行家算法银行家算法设银行家有10万周转资金，P, Q, R分别需要8,3,9万元搞项目，如果P已申请到了4万，Q要申请2万，R要申请4万.Q1：客户要求分期贷款，一旦得到每期贷款，就能够归还贷款Q2：银行家应谨慎的贷款，防止出现坏帐什么是银行家问题？什么是银行家问题？什么是银行家问题？什么是银行家问题？银行家-操作系统 周转资金-系统资源 贷款客户-进程当某进程请求分配资源时，系统假定先分配给它，之后若能找到一个进程完成序列（安全序列），说明系统是安全的，可进行实际分配；否则，让申请者等待银行家算法的实现思想银行家算法的实现思想银行家算法的实现思想银行家算法的实现思想5表表表表 示示示示 形形形形 式式式式含含含含 义义义义AvailableAvailable（可用资源数组）可用资源数组）可用资源数组）可用资源数组）Available j Available j k k现有资源现有资源现有资源现有资源 j j 的数目为的数目为的数目为的数目为 k k Max（最大需求矩阵）最大需求矩阵）最大需求矩阵）最大需求矩阵）Max i, j Max i, j k k进程进程进程进程 i i 对资源对资源对资源对资源 j j 的最大需的最大需的最大需的最大需求数目为求数目为求数目为求数目为 k k Allocation（分配矩阵）分配矩阵）分配矩阵）分配矩阵）Allocation i, j Allocation i, j k k进程进程进程进程 i i 当前已分得的资源当前已分得的资源当前已分得的资源当前已分得的资源 j j 的数目为的数目为的数目为的数目为 k kNeed（需求矩阵）需求矩阵）需求矩阵）需求矩阵）Need i, j Need i, j k k进程进程进程进程 i i 尚需分配的资源尚需分配的资源尚需分配的资源尚需分配的资源 j j 的数目为的数目为的数目为的数目为 k k银行家算法中的数据结构银行家算法中的数据结构6银行家算法当Pi发出资源请求，分配一个Request向量然后系统按下述流程进行执行：Requesti：是进程Pi的请求向量如果Requestij=K，表示进程i需要K个Rj类型的资源。

银行家算法实现过程银行家算法实现过程78安全性算法实现过程安全性算法实现过程安全性算法两个向量：Work和FinishWork表示系统可提供给进程继续运行所需的各类资源数目（即在分配过程中，系统的可用资源数）初始值 Work=Available;Finish表示系统是否有足够的资源分配给进程i，使之运行完成初始值 Finishi:=false当有足够资源分配给进程时 Finishi:=true910 假假假假定定定定系系系系统统统统中中中中有有有有五五五五个个个个进进进进程程程程P P0 0, , P P1 1, , P P2 2, , P P3 3, , P P4 4和和和和三三三三类类类类资资资资源源源源A, A, B, B, C C，各各各各种种种种资资资资源源源源的的的的数数数数量量量量分分分分别别别别为为为为1010、5 5、7 7，在在在在T T0 0时时时时刻刻刻刻的的的的资资资资源源源源分分分分配配配配情情情情况如下图所示况如下图所示况如下图所示况如下图所示 P P4 4P P3 3P P2 2P P1 1P P0 0AvailableAvailableA, B, CA, B, CNeedNeedA, B, CA, B, CAllocationAllocationA, B, CA, B, CMaxMaxA, B, CA, B, C进进进进 程程程程资源资源资源资源 情况情况情况情况7, 5, 37, 5, 33, 2, 23, 2, 29, 0, 29, 0, 22, 2, 22, 2, 24, 3, 34, 3, 30, 1, 00, 1, 02, 0, 02, 0, 03, 0, 23, 0, 22, 1, 12, 1, 10, 0, 20, 0, 27, 4, 37, 4, 31, 2, 21, 2, 26, 0, 06, 0, 00, 1, 10, 1, 14, 3, 14, 3, 13, 3, 23, 3, 2银行家算法实例银行家算法实例11（1 1）T T0 0时刻系统是否安全？时刻系统是否安全？时刻系统是否安全？时刻系统是否安全？执行安全性算法进行检查：执行安全性算法进行检查：执行安全性算法进行检查：执行安全性算法进行检查： 向量初值向量初值向量初值向量初值 Work :Work :AvailableAvailable(3, 3, 2)(3, 3, 2)； Finish i : Finish i :falsefalse；（；（；（；（i i0, 1, , 40, 1, , 4） 在进程集合中找到在进程集合中找到在进程集合中找到在进程集合中找到 NeedNeed1 1(1, 2, 2)(1, 2, 2) WorkWork 且且且且 Finish 1 Finish 1 falsefalse； 则设则设则设则设 P P1 1 顺利执行完成，从而有：顺利执行完成，从而有：顺利执行完成，从而有：顺利执行完成，从而有： WorkWork : :WorkWorkAllocationAllocation1 1 (3, 3, 2)(3, 3, 2)(2, 0, 0)(2, 0, 0)(5, 3, 2)(5, 3, 2) Finish 1 :Finish 1 :truetrue银行家算法实例银行家算法实例12Chapter 3 Chapter 3 处理机调度与死锁处理机调度与死锁处理机调度与死锁处理机调度与死锁FinishFinishWork+AllocationWork+AllocationAllocationAllocationNeedNeedWorkWorktrue5 3 22 0 01 2 23 3 2P1AllocationAllocationNeedNeedP00 1 07 4 3P12 0 01 2 2P23 0 26 0 0P32 1 10 1 1P40 0 24 3 113Chapter 3 Chapter 3 处理机调度与死锁处理机调度与死锁处理机调度与死锁处理机调度与死锁FinishFinishWork+AllocationWork+AllocationAllocationAllocationNeedNeedWorkWorktrue7 4 35 3 22 1 10 1 1P3true5 3 22 0 01 2 23 3 2P1AllocationAllocationNeedNeedP00 1 07 4 3P12 0 01 2 2P23 0 26 0 0P32 1 10 1 1P40 0 24 3 114Chapter 3 Chapter 3 处理机调度与死锁处理机调度与死锁处理机调度与死锁处理机调度与死锁FinishFinishWork+AllocationWork+AllocationAllocationAllocationNeedNeedWorkWorktrue7 5 37 4 30 1 07 4 3true7 4 32 1 10 1 15 3 2true5 3 22 0 01 2 23 3 2P0P3P1AllocationAllocationNeedNeedP00 1 07 4 3P12 0 01 2 2P23 0 26 0 0P32 1 10 1 1P40 0 24 3 115Chapter 3 Chapter 3 处理机调度与死锁处理机调度与死锁处理机调度与死锁处理机调度与死锁FinishFinishWork+AllocationWork+AllocationAllocationAllocationNeedNeedWorkWorktrue10 5 57 5 3true7 5 30 1 07 4 37 4 33 0 26 0 0true7 4 32 1 10 1 15 3 2true5 3 22 0 01 2 23 3 2P0P2P3P1AllocationAllocationNeedNeedP00 1 07 4 3P12 0 01 2 2P23 0 26 0 0P32 1 10 1 1P40 0 24 3 116Chapter 3 Chapter 3 处理机调度与死锁处理机调度与死锁处理机调度与死锁处理机调度与死锁AllocationAllocationNeedNeedP00 1 07 4 3P12 0 01 2 2P23 0 26 0 0P32 1 10 1 1P40 0 24 3 1true10 5 70 0 24 3 110 5 5P4FinishFinishWork+AllocationWork+AllocationAllocationAllocationNeedNeedWorkWorktrue10 5 57 5 3true7 5 30 1 07 4 37 4 33 0 26 0 0true7 4 32 1 10 1 15 3 2true5 3 22 0 01 2 23 3 2P0P2P3P117 发现：目前可执行的所有资源分配工作完成之后，各个进程对发现：目前可执行的所有资源分配工作完成之后，各个进程对发现：目前可执行的所有资源分配工作完成之后，各个进程对发现：目前可执行的所有资源分配工作完成之后，各个进程对应的状态向量应的状态向量应的状态向量应的状态向量 Finish i Finish i truetrue；且对应于该向量置为且对应于该向量置为且对应于该向量置为且对应于该向量置为 “ “true” true” 的进的进的进的进程编号依次为：程编号依次为：程编号依次为：程编号依次为：1 1 33 00 2 2 4 4，故：，故：，故：，故： 系统存在安全序列系统存在安全序列系统存在安全序列系统存在安全序列 P P1 1，P P3 3，P P0 0，P P2 2，P P4 4 所以，所以，所以，所以，T T0 0 时刻系统处于安全状态！时刻系统处于安全状态！时刻系统处于安全状态！时刻系统处于安全状态！银行家算法实例银行家算法实例18Chapter 3 Chapter 3 处理机调度与死锁处理机调度与死锁处理机调度与死锁处理机调度与死锁 由分析知：执行完由分析知。