银行家算法课件

计算机操作系统银行家算法1可编辑死锁的“3W”WhatWhyHow什么是死锁？为什么会发生死锁？怎么解决死锁？2可编辑死锁的处理方法

（1）预防死锁：通过某些限制条件的设置，去破坏产生死锁的四个必要条件；

（2）避免死锁：在资源的动态分配过程中，用某种方法去防止系统进入不安全状态；

（3）检测死锁：及时检测死锁的发生，并确定与之相关的进程、资源，从而采取措施清除死锁；

（4）解除死锁：撤消或挂起某些进程以回收一些资源，用于解脱另一些处于死锁的进程。3可编辑避免死锁—银行家算法设银行家有10万周转资金，P,Q,R分别需要8,3,9万元搞项目，如果P已申请到了4万，Q要申请2万，R要申请4万.Q1：客户要求分期贷款，一旦得到每期贷款，就能够归还贷款Q2：银行家应谨慎的贷款，防止出现坏帐什么是银行家问题？银行家->操作系统周转资金->系统资源贷款客户->进程当某进程请求分配资源时，系统假定先分配给它，之后若能找到一个进程完成序列（安全序列），说明系统是安全的，可进行实际分配；否则，让申请者等待。银行家算法的实现思想4可编辑表示形式含义Available（可用资源数组）Available[j]＝k现有资源j的数目为kMax（最大需求矩阵）Max[i,j]＝k进程i对资源j的最大需求数目为k

Allocation（分配矩阵）Allocation[i,j]＝k进程i当前已分得的资源j的数目为kNeed（需求矩阵）Need[i,j]＝k进程i尚需分配的资源j的数目为k银行家算法中的数据结构5可编辑银行家算法当Pi发出资源请求，分配一个Request向量然后系统按下述流程进行执行：Requesti：是进程Pi的请求向量如果Requesti[j]=K，表示进程i需要K个Rj类型的资源。银行家算法实现过程6可编辑7可编辑安全性算法实现过程安全性算法两个向量：Work和Finish

Work表示系统可提供给进程继续运行所需的各类资源数目（即在分配过程中，系统的可用资源数）。初始值Work∶=Available;

Finish表示系统是否有足够的资源分配给进程i，使之运行完成。初始值

Finish[i]:=false当有足够资源分配给进程时Finish[i]:=true8可编辑9可编辑

假定系统中有五个进程｛P0,P1,P2,P3,P4｝和三类资源｛A,B,C｝，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如下图所示。

P4P3P2P1P0AvailableA,B,CNeedA,B,CAllocationA,B,CMaxA,B,C进程资源情况7,5,33,2,29,0,22,2,24,3,30,1,02,0,03,0,22,1,10,0,27,4,31,2,26,0,00,1,14,3,13,3,2银行家算法实例10可编辑（1）T0时刻系统是否安全？执行安全性算法进行检查：

①

向量初值

Work:＝Available＝(3,3,2)；Finish[i]:＝false；（i＝0,1,…,4）

②

在进程集合中找到Need1＝(1,2,2)

≤Work

且Finish[1]＝false；③

则设P1顺利执行完成，从而有：

Work:＝Work＋Allocation1＝(3,3,2)＋(2,0,0)＝(5,3,2)

Finish[1]:＝true银行家算法实例11可编辑Chapter3处理机调度与死锁FinishWork+AllocationAllocationNeedWorktrue532200122332P1AllocationNeedP0010743P1200122P2302600P3211011P400243112可编辑Chapter3处理机调度与死锁FinishWork+AllocationAllocationNeedWorktrue743532211011P3true532200122332P1AllocationNeedP0010743P1200122P2302600P3211011P400243113可编辑Chapter3处理机调度与死锁FinishWork+AllocationAllocationNeedWorktrue753743010743true743211011532true532200122332P0P3P1AllocationNeedP0010743P1200122P2302600P3211011P4002431142024/12/2015可编辑Chapter3处理机调度与死锁FinishWork+AllocationAllocationNeedWorktrue1055753true753010743743302600true743211011532true532200122332P0P2P3P1AllocationNeedP0010743P1200122P2302600P3211011P400243116可编辑Chapter3处理机调度与死锁AllocationNeedP0010743P1200122P2302600P3211011P4002431true10570024311055P4FinishWork+AllocationAllocationNeedWorktrue1055753true753010743743302600true743211011532true532200122332P0P2P3P117可编辑

④发现：目前可执行的所有资源分配工作完成之后，各个进程对应的状态向量Finish[i]＝true；且对应于该向量置为“true”的进程编号依次为：1

→3

→

0→

2

→

4，故：系统存在安全序列{P1，P3，P0，P2，P4}

所以，T0

时刻系统处于安全状态！银行家算法实例18可编辑Chapter3处理机调度与死锁由分析知：执行完P1、P3

的资源分配请求之后，系统可用的资源数量可以满足其它3个进程的资源请求，则此时的资源分配顺序已无关紧要。所以：安全序列可以不唯一！true10570024311055P4FinishWork+AllocationAllocationNeedWorktrue1055753true753010743743302600true743211011532true532200122332P0P2P3P119可编辑（2）P1发出请求Request(1,0,2)，系统能分配资源吗？

执行银行家算法：

①

Request1(1,0,2)≤Need1(1,2,2)；

②Request1(1,0,2)≤Available(3,3,2)；

③系统为P1进行预分配，并修改Available，Allocation1和Need1向量：银行家算法实例Request1(1,0,2)，Need1，Available20可编辑

Available:＝Available－Request1＝(3,3,2)－(1,0,2)＝(2,3,0)

Allocation1:＝Allocation1＋Request1＝(2,0,0)＋(1,0,2)＝(3,0,2)

Need1:＝Need1－Request1＝(1,2,2)－(1,0,2)＝(0,2,0)银行家算法实例21可编辑

④

执行安全性算法：a.Work:＝Available＝(2,3,0)；Finish[i]:＝false；在进程集合中找到Need1＝(0,2,0)

≤Work；b’.在进程集合中找到Need3＝(0,1,1)

≤Work（5，3，2）

且Finish[3]＝false；c.则设P1可顺利执行完成，从而有：

Work:＝Work＋Allocation1＝(2,3,0)＋(3,0,2)＝(5,3,2)

Finish[1]:＝true银行家算法实例22可编辑c’.则设P3顺利执行完成，从而有：

Work:＝Work＋Allocation3＝(5,3,2)＋(2,1,1)＝(7,4,3)

Finish[3]:＝true………执行安全性算法检查时，仍能够得到安全序列{P1，P3，P0，P2，P4}，故请求向量Request1(1,0,2)发出时系统安全！银行家算法实例23可编辑（3）P4发出请求Request(3,2,1)，系统能分配资源吗？

执行银行家算法进行检查：①

Request4(3,2,0)≤Need4(4,3,1)；②Request4(3,2,1)

Available(2,3,0)

故：P4资源请求失败，让其等待！＞银行家算法实例24可编辑（4）P0发出请求Request(0,2,0)，系统能分配资源吗？

执行银行家算法进行检查：

①

Request0(0,2,0)≤Need0(7,4,3)；

②Request0(0,2,0)≤Available(2,3,0)；

③

系统为P0作预分配，并修改有关数据：银行家算法实例25可编辑

Available:＝Available－Request0＝(2,3,0)－(0,2,0)＝(2,1,0)

Allocation0:＝Allocation0＋Request0＝(0,1,0)＋(0,2,0)＝(0,3,0)

Need0

:＝Need0－Request0