操作系统实验报告三-银行家算法

银行家算法操作系统实验三银行家算法姓名：杨益林 学号：报告日期：2017.06.07一、实验目的通过实验， 加深对多实例资源分配系统中死锁避免方法银行家算法的理解，掌握 Windows 环境下银行家算法的实现方法，同时巩固利用 Windows API进行共享数据互斥访问和多线程编程的方法。二、实验内容1.在 Windows 操作系统上，利用 Win32API 编写多线程应用程序实现银行家算法。2.创建 n 个线程来申请或释放资源，只有保证系统安全，才会批准资源申请。3.通过 Win32 API 提供的信号量机制，实现共享数据的并发访问。三、实验步骤（一）设计思路：银行家算法可分为个主要的功能模块，其描述如下：1.初始化由用户输入数据，分别对运行的进程数、总的资源种类数、总资源数、各进程所需要的最大资源数量（Max），已分配的资源数量赋值。2.安全性检查算法(1)设置两个工作向量Work=AVAILABLE;FINISH=false;(2)从进程集合中找到一个满足下述条件的进程，FINISH=false;NEED=Work;如找到，执行(3)；否则，执行(4)(3)设进程获得资源，可顺利执行，直至完成，从而释放资源。Work+=ALLOCATION;Finish=true;(4).如所有的进程Finish= true，则表示安全；否则系统不安全。 3. 银行家算法在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。它是最具有代表性的避免死锁的算法。设进程j提出请求REQUEST i，则银行家算法按如下规则进行判断。(1).如果REQUEST j i= NEEDji，则转(2)；否则，出错。(2).如果REQUEST j i= AVAILABLEji，则转(3)；否则，出错。(3).系统试探分配资源，修改相关数据： AVAILABLEi-=REQUESTji; ALLOCATIONji+=REQUESTji;NEEDji-=REQUESTji;用到的数据结构：实现银行家算法要有若干数据结构，它们用来表示资源分配系统的状态。令n表示系统中进程的数目，m表示资源的分类数。还需要以下数据结构：1).Available是一个长度为m的向量，它表示每类资源可用的数量。Available j=k，表示j类资源可用的数量为k。2).Max是一个nm矩阵，它表示每个进程对资源的最大需求。Max i，j=k，表示进程pi至多可以申请k个j类资源单位。3).Allocation是一个nm矩阵，它表示当前分给每个进程的资源数目。Allocation i，j=k，表示进程i当前分到k个j类资源。4).Need是一个nm矩阵，它表示每个进程还缺少多少资源。Needi，j=k，表示进程pi尚需k个j类资源才能完成其任务。显然Needi，j= Max i，j- Allocation i，j。（二）流程图四、运行结果示例这里以书上的例子为例，初值如下表：AllocationMaxAvailableA B CA B CA B CP00 1 07 5 33 3 2P12 0 03 2 2P23 0 19 0 0P32 1 12 2 2P40 0 24 3 3现在让进程P1再申请A:1 B:0 C:2个资源，首先调用安全算法测试如果分配后系统是否安全，然后给出了分配序列，如下图：如果再让P4申请A:0 B:2 C:0个资源，首先调用安全算法测试如果分配后系统是否安全，发现分配后系统不安全，于是报分配错误，不予分配，结果如下图：七、实验体会银行家算法的具体实现，我学到了很多课本上没有的知识。想要完成模拟银行家算法的C+程序，首先就是要彻底熟悉算法，了解算法的基本原理，才能开始着手程序设计在程序设计设计过程中，遇到了一些困难，通过向同学询问，翻阅资料等，问题被一一解决了。首先就是在知识层面上了解了银行家算法这种进程调度和避免死锁的算法，并用C+程序真正模拟出安全性检查和银行家算法过程，复习了之前所学C+和数据结构的知识；在编程过程中虽然遇到很多困难，解决问题的过程中，同时也锻炼了我不怕困难，勇于迎接挑战的精神，为以后的工作打下了坚实的基础。八、源程序并附上注释#include#include#include#include#define False 0#define True 1using namespace std;int Max100100 = 0 ;/各进程所需各类资源的最大需求int ReMax100100 = 0 ;int Avaliable100 = 0 ;/系统可用资源int ReAvaliable100 = 0 ;char name100 = 0 ;/资源的名称int Allocation100100 = 0 ;/系统已分配资源int ReAllocation100100 = 0 ;int Need100100 = 0 ;/还需要资源int ReNeed100100 = 0 ;int Request100 = 0 ;/请求资源向量int temp100 = 0 ;/存放安全序列int Work100 = 0 ;/存放系统可提供资源int M = 100;/进程的最大数量为100int N = 100;/资源的最大数量为100void showdata()/显示资源矩阵int i, j;cout endl;cout Max Allocation Need Avaliable endl;cout ;for (j = 0; j4; j+)for (i = 0; iN; i+)cout namei ;cout ;cout endl;for (i = 0; iM; i+)cout i ;for (j = 0; jN; j+)cout Maxij ;cout ;for (j = 0; jN; j+)cout Allocationij ;cout ;for (j = 0; jN; j+)cout Needij ;if (i = 0)cout ;for (j = 0; jN; j+)cout Avaliablej ;cout endl;void save()int i, j;for (i = 0; i N; i+)ReAvaliablei = Avaliablei;for (i = 0; i M; i+)for (j = 0; j N; j+)ReMaxij = Maxij;ReAllocationij = Allocationij;ReNeedij = Needij;void restore()int i, j;for (i = 0; i N; i+)Avaliablei=ReAvaliablei ;for (i = 0; i M; i+)for (j = 0; j N; j+)Maxij = ReMaxij;Allocationij = ReAllocationij;Needij = ReNeedij;int changdata(int i)/进行资源分配int j;for (j = 0; jM; j+) Avaliablej = Avaliablej - Requestj;Allocationij = Allocationij + Requestj;Needij = Needij - Requestj;return 1;int safe()/安全性算法int i, k = 0, m, apply, Finish100 = 0 ;int j;int flag = 0;for (int num = 0; num N; num+)Worknum = Avaliablenum;for (i = 0; iM; i+)apply = 0;for (j = 0; jN; j+)if (Finishi = False&Needij = Workj)apply+;if (apply = N)for (m = 0; mN; m+)Workm = Workm + Allocationim;/变分配数Finishi = True;tempk = i;i = -1;k+;flag+;for (i = 0; iM; i+)if (Finishi = False)cout 系统不安全,所有状态不改变！ endl;/不成功系统不安全return 1;cout 系统是安全的! endl;/如果安全，输出成功save();/进行保存cout 安全序列:;for (i = 0; iM; i+)/输出运行进程数组cout tempi;if (iM - 1) cout ;cout endlendl;return 0;void share()/利用银行家算法对申请资源对进行判定bool ch=true;int i = 0, j = 0;/ch = y;cout 请输入请求分配资源的进程号(0- M - 1 i;/输入须申请的资源号cout 请输入进程 i 申请的资源数量: endl;for (j = 0; jN; j+)cout namej Requestj;/输入需要申请的资源for (j = 0; jNeedij)/判断申请是否大于需求，若大于则出错cout 进程 i 申请的资源大于它需要的资源;cout 分配不合理，不予分配！ Avaliablej)/判断申请是否大于当前资源，若大于则 /出错cout 进程 i 申请的资源大于系统现在可利用的资源;cout 分配出错，不予分配! endl;ch = false;break;if (ch) changdata(i);/根据进程需求量变换资源if (safe()restore();/根据进程需求量进行银行家算法判断showdata();/根据进程需求量显示变换后的资源void changeresources()/修改资源函数cout 当前的 Avaliable: endl;for (int i = 0; iN; i+)cout namei : Avaliablei ;cout endl 输入修改值: endl;for (int i = 0; i N; i+)cout namei Avaliablei;cout 修改后的 Avaliable: endl;for (int k = 0; kN; k+)cout namek : Avaliablek endl;showdata();safe();int main()/主函数int i, j, number, m, n, flag;int choice = 1;char ming;cout n;N = n;cout 请依次输入系统资源的名称与数量：endl;for (i = 0; in; i+)/cout 资源 i + 1 mingnumber;namei = ming;/cout 资源 i + 1 number;Avaliablei = number;cout endl;cout m;M = m;cout 请输入各进程的最大需求量( m * n 矩阵) Max: endl;for (i = 0; im; i+)for (j = 0; j Maxij;doflag = 0;cout 请输入各进程已经申请的资源量( m * n 矩阵) Allocation: endl;for (i = 0; im; i+)for (j = 0; j Allocationij;if (AllocationijMaxij)flag = 1;Needij = Maxij - Allocationij;Avaliablej = Avaliablej - Allocationij;if (flag)cout 申请的资源大于最大需求量，请重新输入!n; while (flag);showdata();/显示各种资源safe();/用银行家算法判定系统是否安全while (choice)cout *银行家算法演示* endl;cout 1:修改现有资源实例数量 endl;cout 2:进程请求