操作系统实验四 银行家算法.doc

银行家算法
xxx
711103xx
2012年5月21日
一、实验目的
通过实验，加深对多实例资源分配系统中死锁避免方法——银行家算法的理解，掌握Windows环境下银行家算法的实现方法，同时巩固利用Windows API进行共享数据互斥访问和多线程编程的方法。

二、实验内容
1. 在Windows操作系统上，利用Win32 API编写多线程应用程序实现银行家算法。
2. 创建n个线程来申请或释放资源，只有保证系统安全，才会批准资源申请。
3. 通过Win32 API提供的信号量机制，实现共享数据的并发访问。

三、实验步骤（设计思路和流程图）
最主要的用以实现系统功能的应该有两个部分，一是用银行家算法来判断，二是用安全性算法来检测系统的安全性。
1、银行家算法
设Requesti是进程Pi的请求向量，如果Requesti［j］=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：
(1) 如果Requesti［j］≤Need［i,j］，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。
(2) 如果Requesti［j］≤Available［j］，便转向步骤(3)；否则， 表示尚无足够资源，Pi须等待。
(3) 系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：
Available［j］∶=Available［j］-Requesti［j］;
Allocation［i,j］∶=Allocation［i,j］+Requesti［j］;
Need［i,j］∶=Need［i,j］-Requesti［j］;
(4) 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则， 将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。
2、 安全性算法
(1) 设置两个向量：① Work∶=Available; ② Finish
(2) 从进程集合中找到一个能满足下述条件的进程：① Finish［i］=false; ② Need［i,j］≤Work［j］； 若找到， 执行步骤(3)， 否则，执行步骤(4)。
(3) 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：Work［j］∶=Work［i］+Allocation［i,j］;
Finish［i］∶=true;
go to step 2;
(4) 如果所有进程的Finish［i］=true都满足， 则表示系统处于安全状态；否则，系统处于不安全状态。

四、主要数据结构及其说明
(1) 可利用资源向量Available。如果Available［j］=K，则表示系统中现有Rj类资源K个。
(2) 最大需求矩阵Max。如果Max［i,j］=K，则表示进程i需要Rj类资源的最大数目为K。
(3) 分配矩阵Allocation。如果Allocation［i,j］=K，则表示进程i当前已分得Rj类资源的数目为K。
(4) 需求矩阵Need。如果Need［i,j］=K，则表示进程i还需要Rj类资源K个，方能完成其任务。Need［i,j］=Max［i,j］-Allocation［i,j］

五、程序运行时的初值和运行结果
int Available[rCount] = {10,5,7};
const int Max[pCount][rCount] = { { 7,5,3 },
{ 3,2,2 },
{ 9,0,2 },
{ 2,2,2 },
{ 4,3,3 } }；

第一次申请：

资源不够情况：Request＜=Available

出错的情况：Requesti＜=Need

六、实验体会
通过本次银行家算法实验，加深了我对银行家算法的了解，掌握了如何利用银行家算法避免死锁。这次实践，我巩固了自己的理论知识。
银行家算法是为了使系统保持安全状态。如果把操作系统看作是银行家，操作系统管理相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源。
操作系统的一些原理在生活中都可以找到相应的例子。结合生活中的例子，可以化抽象为具体，我们会更加清楚地了解到其原理与操作过程。

七、源程序并附上注释
thread.cpp
#include <windows.h>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <ctime>
#include <assert.h>
using namespace std;

extern const int rCount = 3;
extern const int pCount = 5;
extern const int Need[pCount][rCount];
extern const int Allocation[pCount][rCount];

extern HANDLE Mutex;
extern HANDLE Queue;

int handleRequest(int Request[],int pNum);

int randomRequest(int r,int p){
return rand()%(Need[p][r]+1);
}
int randomRelease(int r,int p){
return -(rand()%(Allocation[p][r]+1));
}
int completeRelease(int r,int p){
return -Allocation[p][r];
}

DWORD WINAPI runProcess(void *param){
int pNum = *(int*)param;
srand((unsigned)time(NULL));
bool RUNNING = true;
while(RUNNING){
Sleep(500);
int Request[rCount];
int (*op)(int,int);

switch(rand()%10){
case 0:case 1:
case 2:case 3:
case 4:case 5:
case 6:
op = randomRequest;
break;
case 7:case 8:
op = randomRelease;
break;
case 9:
op = completeRelease;
RUNNING = false;
break;
}

for(int i=0;i<rCount;++i)
Request[i] = (*op)(i,pNum);
while(handleRequest(Request,pNum)){
assert( WAIT_OBJECT_0 == WaitForSingleObject(Queue,INFINITE));
}
}
WaitForSingleObject(Mutex,INFINITE);
cout << "Process " << pNum+1 << " terminated.\n";
ReleaseMutex(Mutex);

return 0;
}

#include <windows.h>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <ctime>
#include <assert.h>
using namespace std;

const int rCount = 3;
const int pCount = 5;
int Available[rCount] = {10,5,7};
const int Max[pCount][rCount] = {
{ 7,5,3 },
{ 3,2,2 },
{ 9,0,2 },
{ 2,2,2 },
{ 4,3,3 }
};
int Allocation[pCount][rCount];
int Need[pCount][rCount];

DWORD WINAPI runProcess(void *param);

HANDLE Mutex;
HANDLE Queue;
void printState();
int main(){
memcpy(Need,Max,sizeof(int)*pCount*rCount);
memset(Allocation,0,sizeof(int)*pCount*rCount);
//初始化信号量
Mutex = CreateMutex(NULL,FALSE,NULL);
Queue = CreateSemaphore(NULL,0,1,NULL);
HANDLE process[pCount];
for(int i=0;i<pCount;++i){
process[i]=CreateThread(NULL,0,runProcess,new int(i),0,NULL);
}
WaitForMultipleObjects(pCount,process,TRUE,INFINITE);
return 0;
}

bool noGreaterThan(const int *ary1,const int *ary2,int length){
for(int i=0;i<length;++i)
if(ary1[i]>ary2[i])
return false;
return true;
}
bool equals(const int *ary1,const int *ary2,int length){
for(int i=0;i<length;++i)
if(ary1[i]!=ary2[i])
return false;
return true;
}
bool smallerThan(const int *ary1,const int *ary2,int length){
if(noGreaterThan(ary1,ary2,length)&&!equals(ary1,ary2,length))
return true;
return false;
}
void addArrays(int *ary1,const int *ary2,int length){
for(int i=0;i<length;++i)
ary1[i]+=ary2[i];
}
void substractArrays(int *ary1,const int *ary2,int length){
for(int i=0;i<length;++i)
ary1[i]-=ary2[i];
}

bool inSafeState(){
int Work[rCount];
memcpy(Work,Available,sizeof(int)*rCount);
bool Finish[pCount] = {false};
bool EXIST;
do {
EXIST = false;
for(int i=0;i<pCount;++i)
if(!Finish[i])
if(noGreaterThan(Need[i],Work,rCount)){
addArrays(Work,Allocation[i],rCount);
Finish[i]=true;
EXIST = true;
i = pCount;
}
} while (EXIST);
for(int i=0;i<pCount;++i)
if(!Finish[i])
return false;
return true;
}
void printResources(int r[]){
for(int i=0;i<rCount;++i)
cout << r[i] << ' ';
cout << endl;
}
void printMatrix(int m[][rCount]){
for(int i=0;i<pCount;++i)
printResources(m[i]);
}
void printState(){
cout << "System State: " << endl;
cout << "Available: \n";
printResources(Available);
cout << '\n';
cout << "Allocation: \n";
printMatrix(Allocation);
cout << '\n';
cout << "Need: \n";
printMatrix(Need);
cout << endl;
cout<<"****************************************"<<endl<<endl;
}
int handle(int Request[],int pNum);
int handleRequest(int Request[],int pNum){

WaitForSingleObject(Mutex,INFINITE);
int r = handle(Request,pNum);
ReleaseMutex(Mutex);
return r;
}
int handle(int Request[],int pNum){
int zero[rCount] = {0};
if(equals(Request,zero,rCount)) return 0;

printState();
cout << "Process " << pNum+1 << "'s request: ";
printResources(Request);
//system("pause");

if(!noGreaterThan(Request,Need[pNum],rCount)){
//raise an error condition(process exceeded its maximum claim)
cout << "Process error in requesting resources.\n";
return -1;
}
if(!noGreaterThan(Request,Available,rCount)){
//not enough resources, return
cout << "Not enough resources.\n";
return 1;
}

substractArrays(Available,Request,rCount);
addArrays(Allocation[pNum],Request,rCount);
substractArrays(Need[pNum],Request,rCount);

if(smallerThan(Allocation[pNum],zero,rCount)){
cout << "Process error in releasing resources.\n";
return -2;
}
if(smallerThan(Request,zero,rCount)){
cout << "Release detected.\n";
for(int i=0;i<pCount-1;++i)
ReleaseSemaphore(Queue,1,NULL);
} else if(!inSafeState()){//否则，检查安全性
//undo
addArrays(Available,Request,rCount);
substractArrays(Allocation[pNum],Request,rCount);
addArrays(Need[pNum],Request,rCount);
//allocation not allowed, return
cout << "Allocation denied due to safety risk.\n";
system("pause");
return 2;
}
cout << "Allocation permitted.\n";
return 0;
}