银行家算法MATLAB实现附代码

课程设计

题目银行家算法

学生姓名张雪明学号2009112209 专业计算机科学与技术班级1122 指导教师张莉莉

完成日期

2012 年 1月4日

银行家算法

摘要：本文解决的是操作系统进程管理当中有关死锁的避免问题，对如何用银行家算法来

处理操作系统给进程分配资源做了详细的说明，包括前言、系统总体框架设计、算法描述、函数模块、程序测试案例及其源程序代码清单。并通过MATLAB软件实现了由Dijkstra给出的银行家算法。

关键词：银行家算法死锁安全性算法安全序列

1. 前言

具有代表性的死锁避免算法是由Dijkstra给出的银行家算法。在避免死锁的方法中，允许进程动态地申请资源，系统在进行资源分配之前，先计算资源分配的安全性。若此次分配不会导致系统进入不安全状态，便将资源分配给进程，否则进程等待。

如果在某一时刻，系统能按某种顺序如?P1,P2,...,Pn?来为每个进程分配其所需的资源，直至最大需求，使每个进程都可以顺利运行完成，则称此时的系统状态为安全状态，称序列若某一时刻系统中不存在一个安全序列，则称此时的系统状态?P1,P2,...,Pn?为安全序列。为不安全状态。

银行家算法就是对每一个请求进行检查，检查它是否会导致系统进入不安全状态，若是，则不予资源分配；否则给予资源分配。

2.系统总体框架设计

进入系统 数据初始化 输出系统在T0时刻的资源分配情况

重新输入 choose(1/2) Y N choose = 1 choose = 2 T0时刻系统安全性检查 进程发出资源请求 CONTINUE1 1 0 YN(1/0) Exit 1 0 CONTINUE2 输入进程编号num 0 Exit 示此时的资源分配情况输出一个安全序列并显输入资源请求向量 1 安全性检查 安全 不安全 该进程必须等待资源分配失败， 3. 算法描述

3.1银行家算法中使用的数据结构

①可利用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类资源的空闲资源个数，其初始值是系统中所配置的该类资源的个数，其数值随该类资源的分配和回收而动态地改变。如果Available(j)?k, 表示系统中现有空闲的Rj类资源k个。

②最大需求矩阵Max。这是一个n?m的矩阵，它定义了系统中每一个进程对各类资源的最大需求个数。如果Max(i,j)?k，表示进程Pi需要Rj类资源的最大个数为k。 ③分配矩阵Allocation。这是一个n?m的矩阵，它定义了系统中当前已分配给每一个进程的各类资源个数。如果Allocation(i,j)?k，表示进程Pi当前已分到Rj类资源的个数为k。

④需求矩阵Need。这是一个n?m的矩阵，它定义了系统中每一个进程还需要的各类资源个数。如果Need(i,j)?k，表示进程Pi还需要Rj类资源k个，才能完成其任务。

上述三个矩阵间存在关系：

Need(i,j)?Max(i,j)?Allocation(i,j)

3.2 银行家算法的实现思想如下：

设Requesti是进程Pi的请求向量，Requesti(j)?k表示进程Pi请求分配Rj类资源k个。当Pi发出资源请求后，系统按下述步骤进行检查：

Step1:如果Requesti?Needi, 则转向Step2；否则出错，因为进程所需要的资源个

数已超过它所宣布的最大值。

Step2:如果Requesti?Available，则转向Step3；否则，表示系统中尚无足够的资

源满足进程Pi的申请，Pi必须等待。

Step3:系统试着把申请的资源分配给进程Pi，并修改下面数据结构中的数值：

Available?Available?Requesti Allocationi?Allocationi?Requesti

Needi?Needi?Requesti

Step4:系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，

才正式将资源分配给进程Pi，以完成本次分配；否则，将试分配作废，恢复原来的资源分配状态，让进程Pi等待。

3.3 安全性算法

Step1:设置如下两个向量。

?Work：表示系统可提供给进程继续运行的各类资源的空闲资源个数，它含有m个元素，执行安全性算法开始时，

Work?Available

?Finish：表示系统是否有足够的资源分配给进程，使之运行完成。开始时，

Finish(i)?false；当有足够资源分配给进程Pi时，令Finish(i)?true。

Step2:从进程集合中找到一个能满足下述条件的进程：

Finish(i)??false

Needi?Work

如找到则执行Step3；否则执行Step4。

Step3:当进程Pi获得资源后，可顺利执行直到完成，并释放出分配给它的资源，故应

执行：

Work?Work?Allocation

Finish(i)?true

然后转向Step2。

Step4:若所有进程的Finish(i)都为true，则表示系统处于安全状态；否则，系统处于

不安全状态。

4. 函数模块

4.1 主程序

BankerAlgorithm

4.2 银行家算法

function BankerAlgMain(RAvailable,RAllocation,RNeed,n,m)

4.3 安全性算法

function [IsSafety,Available,Allocation,Need]=SafetyCheck(Available,Allocation,Need,n)

4.4 银行家算法检查

function [IsPass,Need,Available,Allocation]=BankerAlgorithmFun(Request,num,Need,Available,Allocation,n,m)

4.5 资源请求

function [IsRQ,Request,num]=ResourceRequest(n,m)

5. 程序测试案例

5.1 案例1

将定系统中有4个进程P1、P2、P3、P4，三种类型的资源R1、R2、R3，数量分别为9、3、6，在T0时刻的资源分配情况如下表所示。试问： ⑴T0时刻是否安全？

⑵T0时刻以后，若进程P2发出资源请求Request2(1,0,1)，系统能否将资源分配给它？ ⑶在进程P若P,0,1)，系统能否将资源分配给它？ 2申请资源后，1发出资源请求Request1(1⑷在进程P若P系统能否将资源分配给它？ 1申请资源后，3发出资源请求Request3(0,0,1)，

T0时刻的资源分配表

进 程 Max Allocation Need Available R1 3 6 3 4 R2 2 1 1 2 R3 2 3 4 2 R1 1 5 2 0 R2 0 1 1 0 R3 0 1 1 2 R1 2 1 1 4 R2 2 0 0 2 R3 2 2 3 0 R1 1 R2 1 R3 2 P1 P2 P3 P4

5.2 案例2

A资源的数量为设系统中有3种类型的资源(A,B,C)和5个进程P1、P2、P3、P4、P5，

17，B资源的数量为5，C资源的数量为20。在T0时刻系统状态如下表所示。系统采用银行家算法实施死锁避免策略。

T0时刻系统状态

进程 最大资源需求量 已分配资源数量 A B 5 3 0 2 2 C 9 6 11 5 4 A 2 4 4 2 3 B 1 0 0 0 1 C 2 2 5 4 4 P1 P2 P3 P4 P5 剩余资 源数

5 5 4 4 4 A 2 B 3 C 3 ⑴T0时刻是否为安全状态？，若是，请给出安全序列。

⑵若在T0时刻进程P2请求资源(0,3,4)，是否能实施资源分配？为什么？ ⑶在⑵的基础上，若进程P4请求资源(2,0,1)，是否能实施资源分配？为什么？ ⑷在⑶的基础上，若进程P1请求资源(0,2,0)，是否能实施资源分配？为什么？

5.3 案例测试(MATLAB)

7. 附录程序代码清单

程序代码：

% 操作系统课程设计

% Designed By: ZhangXuemingStudentNumber: 2009112209 % Time: From 2011-12-18 To 2011-12-21 %% 银行家算法 Banker Algorithm

% 具有代表性的死锁避免算法是Dijkstra给出的银行家算法。为实现银行家算法，系统中必须设置若干数据结构。假定系统中有

% n 个进程(P1, P2, ... , Pn), m 类资源(R1, R2, ... ,Rm), 银行家算法中使用的数据结构如下： % * 可利用资源向量 Available。这是一个含有 m 个元素的数组，其中的每一个元素代表一类资源的空闲资源个数，其初始

% 值是系统中所配置的该类资源的个数，其数值随该类资源的分配和回收而动态地改变。如果 Available(j) = k, 表示系统

% 中现有空闲的Rj类资源 k 个。

% * 最大需求矩阵 Max。这是一个 n * m 的矩阵，它定义了系统中每一个进程对各类资源的最大需求个数。如果 Max(i, j) =

% k，表示进程 Pi 需要Rj类资源的最大个数为 k。

% * 分配矩阵 Allocation。这是一个 n * m 的矩阵，它定义了系统中当前已分配给每一个进程的各类资源个数。如果

% Allocation(i, j) = k，表示进程 Pi 当前已分到Rj类资源的个数为 k。

% * 需求矩阵 Need。这是一个 n * m 的矩阵，它定义了系统中每一个进程还需要的各类资源个数。如果 Need(i, j) = k，表

% 示进程 Pi 还需要Rj类资源 k 个，才能完成其任务。 % Need(i, j) = Max(i, j) - Allocation(i, j)

%------------------------------------------------------------------------------------------------------------ % 银行家算法的实现思想如下：

% 设 Request(i) 是进程 Pi 的请求向量，Request(i, j) = k 表示进程 Pi 请求分配Rj类资源 k 个。当

% Pi 发出资源请求后，系统按下述步骤进行检查：

% Step1：如果 Request(i) <= Need(i), 则转向 Step2；否则出错，因为进程所需要的资源个数已超过它所宣布的最大值。

% Step2：如果 Request(i) <= Available，则转向 Step3；否则，表示系统中尚无足够的资源满足进程 Pi 的申请，

% Pi 必须等待。

% Step3：系统试着把申请的资源分配给进程 Pi，并修改下面数据结构中的数值： % Available = Available - Request(i);

% Allocation(i) = Allocation(i) + Request(i); % Need(i) = Need(i) - Request(i);

% Step4：系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程 Pi，以完成本次

% 分配；否则，将试分配作废，恢复原来的资源分配状态，让进程 Pi 等待。 %------------------------------------------------------------------------------------------------------------

% 系统所执行的安全性算法描述如下： % Step1：设置如下两个向量。 % * Work：表示系统可提供给进程继续运行的各类资源的空闲资源个数，它含有 m 个元素，执行安全性算法开始时，

% Work = Available。

% * Finish：表示系统是否有足够的资源分配给进程，使之运行完成。开始时，Finish(i) = false；当有足够资源分配

% 给进程 Pi 时，令 Finish(i) = true。 % Step2：从进程集合中找到一个能满足下述条件的进程： % Finish(i) == false; % Need(i) <= Work;

% 如找到则执行 Step3；否则执行 Step4.

% Step3：当进程 Pi 获得资源后，可顺利执行直到完成，并释放出分配给它的资源，故应执行：

% Work = Work + Allocation; % Finish(i) = true; % 然后转向 Step2。

% Step4：若所有进程的 Finish(i) 都为 true，则表示系统处于安全状态；否则，系统处于不安全状态。

%% 注：程序中用 1 代表 true(算法当中出现的)，0 代表 false(算法当中出现的) clear clc

true = 1; % 这里的 true 是用于循环控制的 while( true ) clear

fprintf('\\n\\t\\t\\t操\\t\\t作\\t\\t系\\t\\t统\\t\\t课\\t\\t程\\t\\t设\\t\\t计\\n'); fprintf('\\n\\t\\t\\t\\t\\t\\t银\\t\\t行\\t\\t家\\t\\t算\\t\\t法\\n\\n'); % 系统中进程个数 n true1 = 1; while( true1 )

n = input('请输入系统中进程个数 n(1 <= n <= 10), n = '); if( n < 1 || n > 10 ) fprintf('input error!\\n'); true1 = 1; else

if( n ~= fix(n) )

fprintf('input error! (n should be an integer!)\\n'); true1 = 1; else

true1 = 0; end end

end

% 资源类型数 m true2 = 1; while( true2 )

m = input('请输入资源类型数 m(1 <= m <= 10), m = '); if( m < 1 || m > 10 ) fprintf('input error!\\n'); true2 = 1; else

if( m ~= fix(m) )

fprintf('input error! (m should be an integer!)\\n'); true2 = 1; else

true2 = 0; end end end

% 预分配内存

RMax = zeros(n, m); % 最大需求矩阵 RAllocation = zeros(n, m); % 分配矩阵 RNeed = zeros(n, m); % 需求矩阵

RAvailable = zeros(1, m); % 可利用资源向量

% 初始化RMax true3 = 1; while( true3 )

fprintf('请输入在 T0 时刻的最大需求矩阵RMax(%d * %d 矩阵)\\n', n, m); RMax = input('RMax = ');

if ( ismatrix( RMax ) && ~iscell( RMax) ) [rRM, cRM] = size(RMax); if(rRM == n &&cRM == m ) true3 = 0; else

fprintf('input error!(RMax should be a %d * %d matrix)\\n', n, m); true3 = 1; end else

fprintf('input error!(RMax should be a %d * %d matrix)\\n', n, m); true3 = 1; end end

% 初始化RAllocation true4 = 1; while( true4 )

fprintf('请输入在 T0 时刻的分配矩阵RAllocation(%d * %d 矩阵)\\n', n, m); RAllocation = input('RAllocation = ');

if ( ismatrix( RAllocation ) && ~iscell( RAllocation) ) [rA, cA] = size(RAllocation); if(rA == n &&cA == m ) true4 = 0; else

fprintf('input error!(RAllocation should be a %d * %d matrix)\\n', n, m); true4 = 1; end else

fprintf('input error!(RAllocation should be a %d * %d matrix)\\n', n, m); true4 = 1; end end

% 计算在 T0 时刻的需求矩阵RNeed fori = 1 : n for j = 1 : m

RNeed(i, j) = RMax(i, j) - RAllocation(i, j); end end

% 初始化在 T0 时刻的可利用资源向量RAvailable true5 = 1; while( true5 )

fprintf('请输入在 T0 时刻的可利用资源向量RAvailable(1 * %d)\\n', m); RAvailable = input('RAvailable = ');

if(isvector(RAvailable) && ~iscell( RAvailable ) ) [rRA, cRA] = size(RAvailable); if(rRA == 1 &&cRA == m ) true5 = 0; else

disp('input error!');

true5 = 1; end else

disp('RAvailable should be a vector');

true5 = 1; end end

% 输出在 T0 时刻的RMax, RAllocation, RNeed, RAvailable

fprintf('\\n\\t\\t\\t系\\t统\\t在\\tT0\\t时\\t刻\\t的\\t资\\t源\\t分\\t配\\t情\\t况\\n\\n'); fori = 1 : n

fprintf('进程P%d :\\n', i); fprintf('\\t\\t RMax%d :', i); for j = 1 : m

fprintf(' %d\\t', RMax(i, j)); end

fprintf('\\n RAllocation%d :', i); for j = 1 : m

fprintf(' %d\\t', RAllocation(i, j)); end

fprintf('\\n\\t\\tRNeed%d :', i); for j = 1 : m

fprintf(' %d\\t', RNeed(i, j)); end

fprintf('\\n\\n'); end

fprintf('\\n RAvailable :'); fori = 1 : m

fprintf(' %d\\t', RAvailable(i)); end

fprintf('\\n');

BankerAlgMain(RAvailable, RAllocation, RNeed, n, m );

fprintf('\\n\\t\\t\\t1 stands for continue while 0 stands for exit\\n'); trueEnd = 1; while(trueEnd )

choice = input('Would You Like To Use This System Again ?(1/0), chioce = '); if choice == 1

true = 1; trueEnd = 0; elseif choice == 0

fprintf('\\n\\t\\t\\tinputBankerAlgorithm to run it again!\\n'); true = 0; trueEnd = 0; else

fprintf('\\ninput error!\\n');

trueEnd = 1; end end end

%--------------------------------------------------------------------------------------------------------- %M文件2 % 银行家算法

functionBankerAlgMain( RAvailable, RAllocation, RNeed, n, m )

RUN = 1; while( RUN )

fprintf('\\t\\t1: T0时刻系统安全性检查\\t\\t 2: 进程发出资源请求\\n'); trueBA1 = 1; while( trueBA1 )

ch = input('Please choose,(ch = 1 or ch = 2), ch = '); if(ch == 1 || ch == 2 )

trueBA1 = 0; else

disp('input error!');

trueBA1 = 1; end end

switchch case 1

SafetyCheck(RAvailable, RAllocation, RNeed, n ); run3 = 1; while( run3 )

CONTINUE1 = input('Continue ? (1/0), CONTINUE1 = '); if( CONTINUE1 == 1 )

run3 = 0; RUN = 1; elseif( CONTINUE1 == 0 )

run3 = 0; RUN = 0; else

disp('input error!');

run3 = 1; end end case 2 run = 1; while( run )

[IsRQ, Request, num] = ResourceRequest( n, m ); if( IsRQ ) % 有进程请求资源

[IsPass, Need, Available, Allocation] = BankerAlgorithmFun( Request, num, RNeed, RAvailable, RAllocation, n, m ); run1 = 1; while( run1 )

con = input('Continue ? (1/0), con = '); if( con == 1 )

run1 = 0; run = 1;

% 更新数据 RNeed = Need;

RAvailable = Available; RAllocation = Allocation; elseif( con == 0 )

run1 = 0; run = 0; else

disp('input error!');

run1 = 1; end end else run = 0; end end

run4 = 1; while( run4 )

CONTINUE2 = input('Continue ? (1/0), CONTINUE2 = '); if( CONTINUE2 == 1 )

run4 = 0; RUN = 1; elseif( CONTINUE2 == 0 )

run4 = 0; RUN = 0; else

disp('input error!');

run4 = 1; end end

otherwise disp('error!'); return

end end end

%% 安全性算法

function [IsSafety, Available, Allocation, Need] = SafetyCheck( Available, Allocation, Need, n ) % SafetyCheck安全性算法

% Work: 表示系统可提供给进程继续运行的各类资源的空闲资源个数 Work = Available; % 执行安全性算法开始时，Work = Available % Finish 表示系统是否有足够的资源分配给进程，使之运行完成。 Finish = zeros(n, 1); % 开始时，Finish(i) = 0 safeSequence = []; % 初始化安全序列 Try = 1; while( Try ) fori = 1 : n

if( Finish(i) == 0 && all( Need(i, :) <= Work ) ) fprintf('进程P%d获得资源\\n', i);

Work = Work + Allocation(i, :); Finish(i) = 1;

safeSequence = [safeSequence, i]; break; end

Try = Try + 1; end

if( all(Finish) || Try > ceil(n*n/2 + n) ) Try = 0; end end

if( all(Finish) ) % 若所有进程的 Finish(i) 都为 true fprintf('系统处于安全状态, 存在一个安全系列为 :\\n'); fori = 1 : n

fprintf('\\tP%d\\t', safeSequence(i)); end

fprintf('\\n');

IsSafety = 1; else

disp('系统处于不安全状态'); IsSafety = 0; end

end % the end of SafetyCheck function

%% 银行家算法检查

function [IsPass, Need, Available, Allocation] = BankerAlgorithmFun( Request, num, Need, Available, Allocation, n, m )

% Request : Request(i) 是进程 Pi 的请求向量 % num : 请求资源分配进程的编号 RNeed = Need;

RAvailable = Available; RAllocation = Allocation;

if( all(Request <= Need(num, :)) ) if( all(Request <= Available) )

fprintf('系统试着把申请的资源分配给进程P%d\\n', num); % 修改下面数据结构中的数值 Available = Available - Request;

Allocation(num, :) = Allocation(num, :) + Request; Need(num, :) = Need(num, :) - Request;

% 系统执行安全性算法

[IsSafety, Available, Allocation, Need] = SafetyCheck( Available, Allocation, Need, n ); if(IsSafety )

disp('资源分配成功!');

fprintf('\\n\\t\\t\\t系\\t统\\t此\\t时\\t的\\t资\\t源\\t分\\t配\\t情\\t况\\n\\n'); Max = Allocation + Need; fori = 1 : n

fprintf('进程P%d :\\n', i); fprintf('\\t\\t Max%d :', i); for j = 1 : m

fprintf(' %d\\t', Max(i, j)); end

fprintf('\\n Allocation%d :', i); for j = 1 : m

fprintf(' %d\\t', Allocation(i, j)); end

fprintf('\\n\\t\\tNeed%d :', i); for j = 1 : m

fprintf(' %d\\t', Need(i, j)); end

fprintf('\\n\\n');

end

fprintf('\\n Available :'); fori = 1 : m

fprintf(' %d\\t', Available(i)); end

fprintf('\\n');

IsPass = 1; else

disp('资源分配失败!');

% 取消资源分配 Need = RNeed;

Available = RAvailable; Allocation = RAllocation; IsPass = 0; end else

fprintf('\\t\\tAllocation Failed!\\n系统中尚无足够的资源满足进程P%d的申请，P%d必须等待。\\n', num, num); IsPass = 0; end else

fprintf('\\t\\tAllocation Failed!\\n进程所需要的资源个数已超过它所宣布的最大值。\\n'); IsPass = 0; end

end % the end of BankerAlgorithmFun function %% 资源请求

function [IsRQ, Request, num] = ResourceRequest( n, m )

trueYN = 1; while(trueYN )

YN = input('Any Resource Request? (YN = 1 or 0), YN = '); if( YN == 1 )

trueBA2 = 1;

while( trueBA2 ) % 发出资源请求的进程的编号num

fprintf('请输入发出资源请求的进程的编号num(1 <= num<= %d)\\n', n); num = input('num = '); if(num< 1 || num> n ) disp('input error!');

trueBA2 = 1; else

if(num ~= fix( num ) )

disp('input error! (num should be an integer!)'); trueBA2 = 1; else

trueBA2 = 0; end end end

trueBA3 = 1;

while( trueBA3 ) % 资源请求向量 Request fprintf('请输入资源请求向量 Request(1 * %d)\\n', m); Request = input('Request = ');

if(isvector(Request) && ~iscell( Request ) ) [rRq, cRq] = size(Request); if(rRq == 1 &&cRq == m )

trueBA3 = 0; else

disp('input error!');

trueBA3 = 1; end else

disp('Request should be a vector'); trueBA3 = 1; end end

trueYN = 0;

IsRQ = 1; % 有资源请求进程

elseif( YN == 0 ) trueYN = 0;

IsRQ = 0; % 没有资源请求进程 else

disp('input error!'); trueYN = 1; end end

end % the end of ResourceRequest function

disp('input error! (num should be an integer!)'); trueBA2 = 1; else

trueBA2 = 0; end end end

trueBA3 = 1;

while( trueBA3 ) % 资源请求向量 Request fprintf('请输入资源请求向量 Request(1 * %d)\\n', m); Request = input('Request = ');

if(isvector(Request) && ~iscell( Request ) ) [rRq, cRq] = size(Request); if(rRq == 1 &&cRq == m )

trueBA3 = 0; else

disp('input error!');

trueBA3 = 1; end else

disp('Request should be a vector'); trueBA3 = 1; end end

trueYN = 0;

IsRQ = 1; % 有资源请求进程

elseif( YN == 0 ) trueYN = 0;

IsRQ = 0; % 没有资源请求进程 else

disp('input error!'); trueYN = 1; end end

end % the end of ResourceRequest function

本文来源：https://www.bwwdw.com/article/wf4t.html