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

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

《操作系统实验四银行家算法.docx》由会员分享，可在线阅读，更多相关《操作系统实验四银行家算法.docx（14页珍藏版）》请在冰点文库上搜索。

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

银行家算法

xxx

711103xx

2012年5月21日

一、实验目的

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

二、实验内容

1.在Windows操作系统上，利用Win32API编写多线程应用程序实现银行家算法。

2.创建n个线程来申请或释放资源，只有保证系统安全，才会批准资源申请。

3.通过Win32API提供的信号量机制，实现共享数据的并发访问。

三、实验步骤（设计思路和流程图）

最主要的用以实现系统功能的应该有两个部分，一是用银行家算法来判断，二是用安全性算法来检测系统的安全性。

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;

gotostep2;

（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］

五、程序运行时的初值和运行结果

intAvailable[rCount]={10,5,7};

constintMax[pCount][rCount]={{7,5,3},

{3,2,2},

{9,0,2},

{2,2,2},

{4,3,3}}；

第一次申请：

资源不够情况：

Request＜=Available

出错的情况：

Requesti＜=Need

六、实验体会

通过本次银行家算法实验，加深了我对银行家算法的了解，掌握了如何利用银行家算法避免死锁。

这次实践，我巩固了自己的理论知识。

银行家算法是为了使系统保持安全状态。

如果把操作系统看作是银行家，操作系统管理相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。

操作系统按照银行家制定的规则为进程分配资源。

操作系统的一些原理在生活中都可以找到相应的例子。

结合生活中的例子，可以化抽象为具体，我们会更加清楚地了解到其原理与操作过程。

七、源程序并附上注释

thread.cpp

#include

#include

#include

#include

#include

#include

usingnamespacestd;

externconstintrCount=3;

externconstintpCount=5;

externconstintNeed[pCount][rCount];

externconstintAllocation[pCount][rCount];

externHANDLEMutex;

externHANDLEQueue;

inthandleRequest（intRequest[],intpNum）;

intrandomRequest（intr,intp）{

returnrand（）%（Need[p][r]+1）;

}

intrandomRelease（intr,intp）{

return-（rand（）%（Allocation[p][r]+1））;

}

intcompleteRelease（intr,intp）{

return-Allocation[p][r];

}

DWORDWINAPIrunProcess（void*param）{

intpNum=*（int*）param;

srand（（unsigned）time（NULL））;

boolRUNNING=true;

while（RUNNING）{

Sleep（500）;

intRequest[rCount];

int（*op）（int,int）;

switch（rand（）%10）{

case0:

case1:

case2:

case3:

case4:

case5:

case6:

op=randomRequest;

break;

case7:

case8:

op=randomRelease;

break;

case9:

op=completeRelease;

RUNNING=false;

break;

}

for（inti=0;i

Request[i]=（*op）（i,pNum）;

while（handleRequest（Request,pNum））{

assert（WAIT_OBJECT_0==WaitForSingleObject（Queue,INFINITE））;

}

}

WaitForSingleObject（Mutex,INFINITE）;

cout<<"Process"<

ReleaseMutex（Mutex）;

return0;

}

#include

#include

#include

#include

#include

#include

usingnamespacestd;

constintrCount=3;

constintpCount=5;

intAvailable[rCount]={10,5,7};

constintMax[pCount][rCount]={

{7,5,3},

{3,2,2},

{9,0,2},

{2,2,2},

{4,3,3}

};

intAllocation[pCount][rCount];

intNeed[pCount][rCount];

DWORDWINAPIrunProcess（void*param）;

HANDLEMutex;

HANDLEQueue;

voidprintState（）;

intmain（）{

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）;

HANDLEprocess[pCount];

for（inti=0;i

process[i]=CreateThread（NULL,0,runProcess,newint（i）,0,NULL）;

}

WaitForMultipleObjects（pCount,process,TRUE,INFINITE）;

return0;

}

boolnoGreaterThan（constint*ary1,constint*ary2,intlength）{

for（inti=0;i

if（ary1[i]>ary2[i]）

returnfalse;

returntrue;

}

boolequals（constint*ary1,constint*ary2,intlength）{

for（inti=0;i

if（ary1[i]!

=ary2[i]）

returnfalse;

returntrue;

}

boolsmallerThan（constint*ary1,constint*ary2,intlength）{

if（noGreaterThan（ary1,ary2,length）&&!

equals（ary1,ary2,length））

returntrue;

returnfalse;

}

voidaddArrays（int*ary1,constint*ary2,intlength）{

for（inti=0;i

ary1[i]+=ary2[i];

}

voidsubstractArrays（int*ary1,constint*ary2,intlength）{

for（inti=0;i

ary1[i]-=ary2[i];

}

boolinSafeState（）{

intWork[rCount];

memcpy（Work,Available,sizeof（int）*rCount）;

boolFinish[pCount]={false};

boolEXIST;

do{

EXIST=false;

for（inti=0;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（inti=0;i

if（!

Finish[i]）

returnfalse;

returntrue;

}

voidprintResources（intr[]）{

for（inti=0;i

cout<

cout<

}

voidprintMatrix（intm[][rCount]）{

for（inti=0;i

printResources（m[i]）;

}

voidprintState（）{

cout<<"SystemState:

"<

cout<<"Available:

\n";

printResources（Available）;

cout<<'\n';

cout<<"Allocation:

\n";

printMatrix（Allocation）;

cout<<'\n';

cout<<"Need:

\n";

printMatrix（Need）;

cout<

cout<<"****************************************"<

}

inthandle（intRequest[],intpNum）;

inthandleRequest（intRequest[],intpNum）{

WaitForSingleObject（Mutex,INFINITE）;

intr=handle（Request,pNum）;

ReleaseMutex（Mutex）;

returnr;

}

inthandle（intRequest[],intpNum）{

intzero[rCount]={0};

if（equals（Request,zero,rCount））return0;

printState（）;

cout<<"Process"<

";

printResources（Request）;

//system（"pause"）;

if（!

noGreaterThan（Request,Need[pNum],rCount））{

//raiseanerrorcondition（processexceededitsmaximumclaim）

cout<<"Processerrorinrequestingresources.\n";

return-1;

}

if（!

noGreaterThan（Request,Available,rCount））{

//notenoughresources,return

cout<<"Notenoughresources.\n";

return1;

}

substractArrays（Available,Request,rCount）;

addArrays（Allocation[pNum],Request,rCount）;

substractArrays（Need[pNum],Request,rCount）;

if（smallerThan（Allocation[pNum],zero,rCount））{

cout<<"Processerrorinreleasingresources.\n";

return-2;

}

if（smallerThan（Request,zero,rCount））{

cout<<"Releasedetected.\n";

for（inti=0;i

ReleaseSemaphore（Queue,1,NULL）;

}elseif（!

inSafeState（））{//否则，检查安全性

//undo

addArrays（Available,Request,rCount）;

substractArrays（Allocation[pNum],Request,rCount）;

addArrays（Need[pNum],Request,rCount）;

//allocationnotallowed,return

cout<<"Allocationdeniedduetosafetyrisk.\n";

system（"pause"）;

return2;

}

cout<<"Allocationpermitted.\n";

return0;

}