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

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

1、银行家算法xxx711103xx2012年 5月 21日一、实验目的通过实验，加深对多实例资源分配系统中死锁避免方法银行家算法的 理解，掌握 Windows 环境下银行家算法的实现方法，同时巩固利用 Windows API 进行共享数据互斥访问和多线程编程的方法。二、实验内容1. 在 Windows 操作系统上，利用 Win32 API 编写多线程应用程序实现银 行家算法。2. 创建 n 个线程来申请或释放资源，只有保证系统安全，才会批准资源申 请。3. 通过 Win32 API 提供的信号量机制，实现共享数据的并发访问。三、实验步骤（设计思路和流程图） 最主要的用以实现系统功能的应该有两个部

2、分， 一是用银行家算法来判断， 二是用安全性算法来检测系统的安全性。1、银行家算法设 Requesti 是进程 Pi 的请求向量，如果 Requesti j=K ，表示进程 Pi 需要 K个 Rj 类型的资源。当 Pi 发出资源请求后，系统按下述步骤进行检查：(1) 如果 Requesti jNeed i,j，便转向步骤 2 ；否则认为出错，因 为它所需要的资源数已超过它所宣布的最大值。(2) 如果 Requesti jAvailable j ，便转向步骤 (3) ；否则， 表示尚 无足够资源， Pi 须等待。(3) 系统试探着把资源分配给进程 Pi，并修改下面数据结构中的数值：Availab

3、le 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,jWo

4、rk 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 ，则表示进

5、程 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 AvailablerCount = 10,5,7;const int MaxpCountrCount = 7,5,3 , 3,2,2 , 9,0,2 , 2,2,2 , 4,3,3 ；第

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

7、ad.cpp#include #include #include #include #include #include using namespace std;extern const int rCount = 3;extern const int pCount = 5;extern const int NeedpCountrCount; extern const int AllocationpCountrCount;extern HANDLE Mutex; extern HANDLE Queue;int handleRequest(int Request,int pNum);int rand

8、omRequest(int r,int p) return rand()%(Needpr+1);int randomRelease(int r,int p)return -(rand()%(Allocationpr+1);int completeRelease(int r,int p)return -Allocationpr;DWORD WINAPI runProcess(void *param) int pNum = *(int*)param; srand(unsigned)time(NULL);bool RUNNING = true; while(RUNNING)Sleep(500);in

9、t RequestrCount;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;irCount;+i) Requesti = (*op)(i,pNum);while(handleRequest(Request,pN

10、um) assert( WAIT_OBJECT_0 WaitForSingleObject(Queue,INFINITE); WaitForSingleObject(Mutex,INFINITE);cout Process pNum+1 terminated.n; ReleaseMutex(Mutex);return 0;#include #include #include #include #include #include using namespace std;const int rCount = 3;const int pCount = 5;int AvailablerCount =

11、10,5,7;const int MaxpCountrCount = 7,5,3 , 3,2,2 , 9,0,2 , 2,2,2 , 4,3,3 ;int AllocationpCountrCount;int NeedpCountrCount;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*rCo

12、unt);/ 初始化信号量Mutex = CreateMutex(NULL,FALSE,NULL);Queue = CreateSemaphore(NULL,0,1,NULL);HANDLE processpCount;for(int i=0;ipCount;+i) processi=CreateThread(NULL,0,runProcess,new int(i),0,NULL); WaitForMultipleObjects(pCount,process,TRUE,INFINITE); return 0;bool noGreaterThan(const int *ary1,const in

13、t *ary2,int length)for(int i=0;iary2i) return false;return true;bool equals(const int *ary1,const int *ary2,int length)for(int i=0;ilength;+i) if(ary1i!=ary2i) return false;return true;bool smallerThan(const int *ary1,const int *ary2,int length) if(noGreaterThan(ary1,ary2,length)&!equals(ary1,ary2,l

14、ength) return true;return false;void addArrays(int *ary1,const int *ary2,int length)for(int i=0;ilength;+i) ary1i+=ary2i;void substractArrays(int *ary1,const int *ary2,int length)for(int i=0;ilength;+i)ary1i-=ary2i;bool inSafeState()int WorkrCount;memcpy(Work,Available,sizeof(int)*rCount);bool Finis

15、hpCount = false;bool EXIST;do EXIST = false;for(int i=0;ipCount;+i)if(!Finishi)if(noGreaterThan(Needi,Work,rCount) addArrays(Work,Allocationi,rCount); Finishi=true;EXIST = true;i = pCount; while (EXIST);for(int i=0;ipCount;+i)if(!Finishi)return false;return true;void printResources(int r)for(int i=0

16、;irCount;+i)cout ri ;cout endl;void printMatrix(int mrCount)for(int i=0;ipCount;+i)printResources(mi);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;coutendlendl;in

17、t 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 zerorCount = 0; if(equals(Request,zero,rCount) return 0;printState();cout Process pNum+1 s request:

18、printResources(Request);/system(pause);if(!noGreaterThan(Request,NeedpNum,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, returncout Not enough resources.n;ret

19、urn 1;substractArrays(Available,Request,rCount);addArrays(AllocationpNum,Request,rCount);substractArrays(NeedpNum,Request,rCount);if(smallerThan(AllocationpNum,zero,rCount)cout Process error in releasing resources.n;return -2;if(smallerThan(Request,zero,rCount)cout Release detected.n;for(int i=0;ipC

20、ount-1;+i)ReleaseSemaphore(Queue,1,NULL); else if(!inSafeState()/ 否则，检查安全性/undoaddArrays(Available,Request,rCount); substractArrays(AllocationpNum,Request,rCount); addArrays(NeedpNum,Request,rCount);/allocation not allowed, returncout Allocation denied due to safety risk.n; system(pause);return 2;cout Allocation permitted.n;return 0;