操作系统实验四

1、银行家算法xxx 711103xx 2012年 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 发出资源请求后，系统按下述步骤进行检查： 如果Requesti jWNeed便转向步骤2 ;否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。(2) 如果Requesti jWAvailable j,便转向步骤 ；否则， 表示尚 无足够资源， Pi 须等待。(3) 系统试探着把资源分配给进程 Pi，并修改下面数据结构中的数值：Available j : =Av

3、ailable j -Requesti j ;Allocation i,j： =Allocationi,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<

4、Work j；若找到， 执行步骤，否则，执行步骤 。(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

5、 需要 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、次申请:I E ：；繞程I匚 odebloc 咕谀益四Vs r ker biDebug'.banker.eeSystem Stdte：Auailable:10 5 7A Hoct ion :R 0 00 0 00 0 0a 0 BH 0 0Need ：3 3资源不够情况：Request =Available出错的情况：Requesti v =Need六、实验体会通过本次银行家算法实验， 加深了我对银行家算法的了解， 掌握了如何利用 银行家算法避免死锁。这次实践，我巩固了自己的理论知识。银行家算法是为了使系统保持安全状态。 如果把操作系统看作是银行家， 操 作系统管理相当于银行家管理的资

7、金， 进程向操作系统请求分配资源相当于用户 向银行家贷款。操作系统按照银行家制定的规则为进程分配资源。操作系统的一些原理在生活中都可以找到相应的例子。结合生活中的例子， 可以化抽象为具体，我们会更加清楚地了解到其原理与操作过程 七、源程序并附上注释thread.cpp#include <windows.h>#include <cstdlib>#include <iostream>#include <cmath>#include <ctime>#include <assert.h>using namespace std;ex

8、tern 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 randomRequest(int r,int p) return rand()%(Needpr+1);int randomRelease(int r,int p)retu

9、rn -(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);int RequestrCount;int (*op)(int,int);switch(rand()%10)case 0:case 1:case 2:case 3:ca

10、se 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) Requesti = (*op)(i,pNum);while(handleRequest(Request,pNum) assert( WAIT_OBJECT_0 WaitForSingleObject(Queue,INFINITE); WaitForSingleOb

11、ject(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 namespac

12、e std;const int rCount = 3;const int pCount = 5;int AvailablerCount = 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,

13、sizeof(int)*pCount*rCount); memset(Allocation,0,sizeof(int)*pCount*rCount);/ 初始化信号量Mutex = CreateMutex(NULL,FALSE,NULL);Queue = CreateSemaphore(NULL,0,1,NULL);HANDLE processpCount;for(int i=0;i<pCount;+i) processi=CreateThread(NULL,0,runProcess,new int(i),0,NULL); WaitForMultipleObjects(pCount,pr

14、ocess,TRUE,INFINITE); return 0;bool noGreaterThan(const int *ary1,const int *ary2,int length)for(int i=0;i<length;+i) if(ary1i>ary2i) return false;return true;bool equals(const int *ary1,const int *ary2,int length)for(int i=0;i<length;+i) if(ary1i!=ary2i) return false;return true;bool small

15、erThan(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) ary1i+=ary2i;void substractArrays(int *ary1,const int *ary2,int length)for

16、(int i=0;i<length;+i)ary1i-=ary2i;bool inSafeState()int WorkrCount;memcpy(Work,Available,sizeof(int)*rCount);bool FinishpCount = false;bool EXIST;do EXIST = false;for(int i=0;i<pCount;+i)if(!Finishi)if(noGreaterThan(Needi,Work,rCount) addArrays(Work,Allocationi,rCount); Finishi=true;EXIST = tr

17、ue;i = pCount; while (EXIST);for(int i=0;i<pCount;+i)if(!Finishi)return false;return true;void printResources(int r)for(int i=0;i<rCount;+i)cout << ri << ' 'cout << endl;void printMatrix(int mrCount)for(int i=0;i<pCount;+i)printResources(mi);void printState()cout &

18、lt;< "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

19、<<".*"<<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 zerorCount = 0; if(equals(Request,zero,rCount) retu

20、rn 0;printState();cout << "Process " << pNum+1 << "'s request: " 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"return 1;substractArrays(Available,Request,rC