实验三 银行家调度算法

1．实验目的

（1）使学生加深对死锁的理解，理解预防死锁的思想和方法，使学生明确系统安全状态的概念。

（2）使学生能利用银行家调度算法实现避免死锁。 2．实验预备内容

阅读死锁的基本概念，产生死锁的原因、产生死锁的必要条件以及处理死锁的基本方法，重点阅读关于死锁避免的章节。 3．实验环境

（1）一台运行Windows 2000 professional操作系统的计算机。

（2）选用turbo c、visual c++、delphi、c++ builder或visual basic等任何一种语言，建议用c++。 4．实验时间：

4个机时。

5．实验内容

(1)设置银行家算法中的数据结构 (a)可利用资源向量Available

它是一个含有m个元素的数组，其中的每一个元素代表一类可利用资源的数目，其初始值是系统中所配置该类全部可用资源数目。其数值随该类资源的分配和回收而动态地改变。

如果Available[j]=k表示系统中现有

类资源k个。

(b)最大需求矩阵Max 这是一个的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。

如果Max(i,j)=k，表示进程i需要

类资源的最大数目为k。

(c)分配矩阵Allocation 这是一个的矩阵，它定义了系统中每一类资源当前已分配该每一进程的资源数。

如果Allocation(i,j)=k,表示进程i当前已分得

类资源的数目为k。

(d)分配矩阵Need 这是一个的矩阵，用以表示每一个进程尚需的各类资源数。 如果Need(i,j)=k表示进程i还需要

类资源k个，方能完成其任务。

上述三个矩阵存在如下关系：

Need(i,j)=Max(i,j)-Allocation(i,j)

(2)银行家算法 设类的资源。当

① 如果

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

② 如果必须等待。

③系统试探把要求的资源分配给进程

Available

，并修改下面数据结构中的数值： Available-

； ； ；

④系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程状态，让进程

，以完成本次分配；否则，将试探分配作废，恢复原来的资源分配

，则转向步骤③；否则，表示系统中尚无足够的的资源，

是进程

的请求向量。如果

[j]=k，表示进程

需要k个

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

,则转向步骤②；否则，认为出错，因为它所需要的资源数

等待。

(3)安全性算法

系统所执行的安全性算法描述如下： ①设置两个向量

(a)工作向量Work。它表示系统可提供给进程继续运行所需要的各类资源数目，它含有m个元素，执行安全算法开始时，Work:=Available。

(b)Finish。它表示系统是否有足够的资源分配给进程，使之运行完成，开始时先做Finish[i] :=false；当有足够资源分配给进程时，令 Finish[i] :=true。

②从进程集合中找到一个能满足下列条件的进程： (a) Finish[i]:=false

(b)

如找到，执行步骤③；否则执行步骤④。 ③当进程

获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执

行：

Work:=Work+Allocationi; Finish[i]:=true; go to step (2)

④如果所有进程的Finish[i]:=true，则表示系统处于安全状态；否则，系统处于不安全

状态。 6．参考算法

#include #include #include #include \"windows.h\"

#define MAX_PROCESS 32 //最大进程数 #define MAX_COURCE //最大资源类别 int MAX_FACT_PROCESS; //实际总进程数 int MAX_FACT_COURCE; //实际资源类别数 int Available[MAX_COURCE]; //可利用资源向量 int Max[MAX_PROCESS][MAX_COURCE]; //最大需求矩阵 int Allocation[MAX_PROCESS][MAX_COURCE]; //分配矩阵 int Need[MAX_PROCESS][MAX_COURCE]; //需求矩阵 int Request_PROCESS; //发出请求的进程 int Request_COURCE; //被请求资源类别 int Request_COURCE_NEMBER; //请求资源数 struct COMP{ int value; int num; int next; }; int flag=0;

void Read_Initiate(void){ //读入初始化文档 ifstream infile(\"Initiate.txt\"); if(!infile){

cout<<\"不能打开输入文件:\"<<\"Initiate.txt\"<<'\\n'; exit(1); }

cout<<\"开始读入初始化文档\"<<'\\n'; int ch;

int Array[MAX_PROCESS*MAX_COURCE*2]; int num=0; while(infile>>ch) Array[num++]=ch; num=0;

MAX_FACT_COURCE=Array[num++]; for(int j=0;jMAX_FACT_PROCESS=Array[num++];

for(int i=0;iinfile.close(); }

void Write_Initiate(void){ //写入初始化文档(分配资源 ofstream outfile(\"Initiate.txt\"); if(!outfile){

cout<<\"不能打开初始化文档：\"<<'\\n'; exit(1); }

int Array[MAX_PROCESS*MAX_COURCE*2]; int num=0;

Array[num++]=MAX_FACT_COURCE; for(int i=0;iArray[num++]=MAX_FACT_PROCESS; for(i=0;ioutfile<DWORD m_delay=3000; Sleep(m_delay); outfile.close();

cout<<\"修改初始化文档成功!\"<void Allocated_list(void){ //读入已分配资源列表 ifstream infile(\"Allocated_list.txt\"); if(!infile){

cout<<\"不能打开输入文件:\"<<\"Allocated_list.txt\"<<'\\n'; exit(1); }

cout<<\"开始读入已分配资源列表\"<<'\\n'; int ch,num=0;

int Array[MAX_PROCESS*MAX_COURCE]; while(infile>>ch) Array[num++]=ch; num=0;

for(int i=0;ivoid Set_Need(void){ //设置需求矩阵 cout<<\"设置需求矩阵\"<<'\\n';

for(int i=0;ivoid Read_Request(void){ //读入请求向量 ifstream infile(\"Request_list.txt\"); if(!infile){

cout<<\"不能打开输入文件:\"<<\"Request_list.txt\"<<'\\n'; exit(1); }

cout<<\"开始读入请求向量\"<<'\\n'; int Array[3]; int num=0,ch; while(infile>>ch) Array[num++]=ch;

Request_PROCESS=Array[0]; Request_COURCE=Array[1];

Request_COURCE_NEMBER=Array[2]; infile.close(); }

void Write_Allocation(void){ //修改资源分配列表(资源分配) ofstream outfile(\"Allocated_list.txt\"); if(!outfile){

cout<<\"不能打开资源分配列表：\"<<'\\n'; exit(1); }

for(int i=0;ioutfile<DWORD m_delay=3000; Sleep(m_delay);

cout<<\"修改资源分配列表成功!\"<void Allocate_Source(void){ //开始分配(已通过扫描和安全性检测) cout<<'\\n'<<\"开始给第\"<cout<<'\\n'<<\"祝贺您，资源分配已成功!\"<void Test_Safty(){ //安全性检测 cout<<'\\n'<<\"进入安全性检测!\"<for(int i=0;ibool Finish[MAX_PROCESS][MAX_COURCE]; for(i=0;ifor(i=0;iArray[i].value=Need[i][Request_COURCE-1]; Array[i].num=i; }

for(i=0;i=Array[j].value){ int t;

t=Array[j].value;

Array[j].value=Array[i].value; Array[i].value=t; t=Array[j].num;

Array[j].num=Array[i].num; Array[i].num=t; }

else continue; }

DWORD m_delay=3000; Sleep(m_delay);

/*for(i=0;iif(Finish[Request_PROCESS-1][Request_COURCE-1]==false&&Need[Request_PROCESS-1][Request_COURCE-1]<=Work[Request_COURCE-1]) {

Work[Request_COURCE-1]=Work[Request_COURCE-1]+Allocation[Request_PROCESS-1][Request_COURCE-1];

Finish[Request_PROCESS-1][Request_COURCE-1]=true; } else {

cout<<\"未通过安全性测试，不与以分配\"<for(i=0;iif(Array[i].num!=Request_PROCESS-1&&Finish[Array[i].num][Request_COURCE-1]==false&&Need[Array[i].num][Request_COURCE-1]<=Work[Request_COURCE-1]){

Work[Request_COURCE-1]=Work[Request_COURCE-1]+Allocation[Array[i].num][Request_COURCE-1]; Finish[Array[i].num][Request_COURCE-1]=true; } }

for(i=0;iif(Finish[i][Request_COURCE-1]==true) continue; else {

cout<<\"未通过安全性测试，不与以分配\"<cout<<'\\n'<<\"找到一个安全序列:\"<<\"P\"<\"; for(i=0;icontinue; else

cout<<\"P\"<\"; }

cout<<'\\n'<<\"已通过安全性测试!\"<void RUN(void){ //执行银行家算法

cout<<\"*************************************************\"<<'\\n'<<\"点击1执行!\" <<'\\n'<<\"点击2退出!\"

<<'\\n'<<\"*************************************************\"<>flag; if(flag==2) exit(0); if(flag==1) {

cout<<\"开始扫描请求信息!\"<if(Request_COURCE_NEMBER>Need[Request_PROCESS-1][Request_COURCE-1]) {

cout<<'\\n'<<\"第\"<cout<<\"可是已超出该进程尚需的该类资源的最大数量,所以不予以分配!!\"<if(Request_COURCE_NEMBER>Available[Request_COURCE-1]) {

cout<<'\\n'<<\"第\"<cout<<\"可是系统中尚无足够的资源,所以进入等待队列!!\"<Available[Request_COURCE-1]=Available[Request_COURCE-1]-Request_COURCE_NEMBER;

Allocation[Request_PROCESS-1][Request_COURCE-1]=Allocation[Request_PROCESS-1][Request_COURCE-1]+Request_COURCE_NEMBER;

Need[Request_PROCESS-1][Request_COURCE-1]=Need[Request_PROCESS-1][Request_COURCE-1]-Request_COURCE_NEMBER; cout<<\"扫描通过\"<} else {

cout<<\"输入错误,请重新输入!\"<<'\\n'; RUN(); } }

void main(void){ Read_Initiate();

cout<cout<DWORD m_delay=3000; Sleep(m_delay); cout<<\"读入成功\"<<'\\n'; Allocated_list();

for(i=0;iSleep(m_delay); cout<<\"读入成功\"<<'\\n'; Set_Need();

for(i=0;iSleep(m_delay); cout<<\"设置成功\"<<'\\n'; Read_Request();

cout<<'\\n'<<\"第\"<\"<注:数组Array[I]表示第I+1个实际意义量需要创建三个txt文本。 1.Initiate.txt文本

3 3 3 2 //共有3类资源,Available[0]=3; Available[1]=3; Available[2]=2 5 //当前系统中有个进程 7 5 3 // Max[0][0]=7 3 2 2 //Max[1][1]=3 9 0 2 2 2 2 4 3 3

2.Allocated_list.txt文本 0 1 0 //Allocation[0][1]=1 2 0 0 3 0 2 2 1 1 0 0 2

3.Request_list.txt文本

2 1 1 //第2个进程请求第1类资源1个Request[1][0]=1 本程序假设当前时刻只有一个进程请求某一类资源n个.

若要满足某个进程当前时刻同时请求不止一类资源,则需要为最大需求矩阵Max,分配矩阵Allocation和需求矩阵Need增加维数,当然代码量也将大大增加,但是算法逻辑本身并无变化.