2022年操作系统实验--银行家算法 .pdf
共享资源分配与银行家算法一、问题描述本题主要内容是模拟实现资源分配。银行家算法是避免死锁的一种重要方法，本实验要求用高级语言编写和调试一个简单的银行家算法程序。加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。二、基本要求具体用银行家算法实现资源分配。要求如下：(1)设计一个P（例如 P=3）个并发进程共享J（例如 J=4）类不同资源的系统，进程可动态地申请资源和释放资源，系统按各进程的申请动态地分配资源。(2)设计用银行家算法，实现资源分配，应具有显示或打印各进程依次要求申请的资源数以及依次分配资源的情况。(3)确定一组各进程依次申请资源数的序列，输出运行结果。三、方案设计及开发过程1、银行家分配算法银行家分配算法，顾名思义是来源于银行的借贷业务，一定数量的本金要应多个客户的借贷周转，为了防止银行加资金无法周转而倒闭，对每一笔贷款，必须考察其是否能限期归还。在操作系统中研究资源分配策略时也有类似问题，系统中有限的资源要供多个进程使用，必须保证得到的资源的进程能在有限的时间内归还资源，以供其他进程使用资源。如果资源分配不得到就会发生进程循环等待资源，每个进程都无法继续执行下去的死锁现象。把每个进程需要和已占有资源的情况记录在进程控制中，假定进程控制块PCB 其中“状态”有就绪态、等待态和完成态。当进程在处于等待态时，表示系统不能满足该进程当前的资源申请。“资源需求总量”表示进程在整个执行过程中总共要申请的资源量。显然，每个进程的资源需求总量不能超过系统拥有的资源总数，银行算法进行资源分配可以避免死锁。2、算法描述银行家算法:设进程 I 提出请求RequestN，则银行家算法按如下规则进行判断。(1)如果 RequestN=Need I,N，则转(2)；否则，出错。(2)如果 RequestN=Available，则转(3)；否则，出错。(3)系统试探分配资源，修改相关数据：Available=Available-Request Allocation=Allocation+Request Need=Need-Request(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。3、安全性检查(1)设置两个工作向量Work=Available；FinishM=False(2)从进程集合中找到一个满足下述条件的进程Finishi=False Need=Work 如找到，执行(3)；否则，执行(4)(3)设进程获得资源，可顺利执行，直至完成，从而释放资源Work=Work+Allocation 名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 5 页 -Finish=True Go To 2(4)如所有的进程FinishM=true，则表示安全；否则系统不安全4、数据结构假设有 M 个进程 N 类资源，则有如下数据结构:#define W 10#define R 20 int M;/总进程数int N;/资源种类int All_ResourceW;/各种资源的数目总和int MaxWR;/M 个进程对 N 类资源最大资源需求量int A Available R;/系统可用资源数int Allocation WR;/M 个进程已经得到N 类资源的资源量int Need WR;/M 个进程还需要N 类资源的资源量int RequestR;/请求资源个数四、实验要求完成实验内容并写出实验报告，报告应具有以下内容：1、实验目的。2、实验内容。3、程序及运行情况。4、实验过程中出现的问题及解决方法。/Bank.cpp:Defines the entry point for the console application./#include stdafx.h#include stdio.h#define W 5#define R 3 int M;/总进程数int N;/资源种类int All_ResourceW;/各种资源的数目总和int MaxWR=7,5,3,3,2,2,9,0,2,2,2,2,4,3,3;/M 个进程对 N 类资源最大资源需求量int AvailableR=3,3,2;/系统可用资源数int AllocationWR=0,1,0,2,0,0,3,0,2,2,1,1,0,0,2;/M 个进程已经得到 N 类资源的资源量int Need WR=7,4,3,1,2,2,6,0,0,0,1,1,4,3,1;/M 个进程还需要N 类资源的资源量int RequestR;/请求资源个数int safeW+1=-1,-1,-1,-1,-1,-1;名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 5 页 -bool judge(int apply,int now)/判断是否可以申请 int i=0,j=0;for(i=0;i=applyi&(Allocationnowi+applyi)=Maxnowi)continue;else return false;return true;bool check()/检测是否有安全序列 int i=0,j=0,finish=0,flag=0,pass=0,s=0;int Available_backR,Allocation_backWR,fW=0,0,0,0,0;for(i=0;iR;i+)/备份资源列表 Available_backi=Availablei;for(j=0;jW;j+)Allocation_backji=Allocationji;while(finishW)flag=0;for(i=0;iW;i+)printf(%dn,i);if(fi=1)continue;pass=0;for(j=0;j=Needij)/需求可以满足pass+;continue;else if(pass=R)/此进程完成 flag=1;名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 5 页 -safes=i;fi=1;s+;finish+;/写入安全序列for(j=0;jR;j+)Available_backj+=Allocation_backij;Allocation_backij=0;/printf(%d t%d%d%d,fi,Available_back0,Available_back1,Available_back2);getchar();if(flag=0&finish!=W)return false;safes=-1;return true;void main()int i=0,j=0,applyR=0,0,0,now=1;/now的值为 0-4 for(i=0;iW;i+)for(j=0;jR;j+)Needij=Maxij-Allocationij;/printf(%d,Needij);/printf(n);if(judge(apply,now)for(i=0;iR;i+)Availablei-=applyi;Allocationnowi+=applyi;if(check()printf(安全序列为：);for(i=0;safei!=-1;i+)printf(P%d。,safei);名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 5 页 -else for(i=0;iR;i+)Availablei+=applyi;Allocationnowi-=applyi;printf(现在这个请求为不安全的n);else printf(这个请求大于最大需求！);名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 5 页 -
