2022年操作系统银行家算法 2.pdf

《2022年操作系统银行家算法 2.pdf》由会员分享，可在线阅读，更多相关《2022年操作系统银行家算法 2.pdf（23页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、操作系统课程设计银行家算法名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 23 页 - - - - - - - - - 第一章引言1.1 课程设计目地：操作系统是计算机系统的核心系统软件，它负责控制和管理整个系统的资源并组织用户协调使用这些资源，使计算机高效的工作。课程设计的目的是综合应用学生所学知识，通过实验环节，加深学生对操作系统基本原理和工作过程的理解，提高学生独立分析问题、解决问题的能力，增强学生的动手能力。第二章银行家算法描述2.1 银行家算法简介：银行家算法是

2、一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。要解释银行家算法，必须先解释操作系统安全状态和不安全状态。安全状态：如果存在一个由系统中所有进程构成的安全序列P1， Pn，则系统处于安全状态。安全状态一定是没有死锁发生。不安全状态 : 不存在一个安全序列。不安全状态不一定导致死锁。那么什么是安全序列呢？安全序列：一个进程序列 P1，Pn是安全的， 如果对于每一个进程Pi(1i n） ， 它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j i ) 当前

3、占有资源量之和。2.2 银行家算法描述：我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 23 页 - - - - - - - - - 前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该

4、进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。2.3 银行家算法原理2.3.1 银行家算法的思路先对用户提出的请求进行合法性检查，即检查请求的是不大于需要的，是否不大于可利用的。若请求合法，则进行试分配。最后对试分配后的状态调用安全性检查算法进行安全性检查。若安全，则分配，否则，不分配，恢复原来状态，拒绝申请。2.3.2 银行家算法中用到的主要数据结构可利用资源向量 int Availablej j为资源的种类。最大需求矩阵 i

5、nt Maxij i为进程的数量。分配矩阵 int Allocationij 需求矩阵 int needij= Maxij- Allocationij 申请各类资源数量 int Request ij i进程申请 j 资源的数量工作向量 int Workx int Finishy2.3.3 银行家算法 bank() 进程 i 发出请求申请 k 个 j 资源， Request ij=k (1) 检查申请量是否不大于需求量：Request ij=needi,j,若条件不符重新名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理

6、 - - - - - - - 第 3 页，共 23 页 - - - - - - - - - 输入，不允许申请大于需求量。(2)检 查 申 请 量 是 否 小 于 系 统 中 的 可 利 用 资 源 数 量 ： Request ij=availablei,j，若条件不符就申请失败，阻塞该进程，用goto 语句跳转到重新申请资源。(3) 若以上两个条件都满足，则系统试探着将资源分配给申请的进程，并修改下面数据结构中的数值：Availablei,j= Availablei,j- Request ij；Allocationij= Allocationij+ Request ij；needij= nee

7、dij- Request ij；(4) 试分配后， 执行安全性检查， 调用 safe() 函数检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程；否则本次试探分配作废，恢复原来的资源分配状态，让该进程等待。(5) 用 do while 循环语句实现输入字符y/n 判断是否继续进行资源申请。2.3.4 安全性检查算法（ safe() 函数）(1) 设置两个向量：工作向量 Work，它表示系统可提供给进程继续运行所需的各类资源数目，在执行安全性算法开始时， Work= Available。Finish ，它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做 Finis

8、hi=0；当有足够的资源分配给进程时，再令Finishi=1。(2) 在进程中查找符合以下条件的进程：条件 1：Finishi=0；条件 2：needij=Workj 若找到，则执行步骤 (3) 否则，执行步骤 (4) (3) 当进程获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 23 页 - - - - - - - - - Workj= Workj+ Allocationij；Finishi=1；got

9、o step 2；(4) 如果所有的 Finishi=1都满足，则表示系统处于安全状态，否则，处于不安全状态。第三章银行家算法流程图3.1 系统主要过程流程图名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 23 页 - - - - - - - - - 3.2 银行家算法流程图名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 23 页 - - - - -

10、 - - - - 3.3 、安全性算法流程图名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 23 页 - - - - - - - - - 第四章源程序结构分析4.1 程序结构4.1.1 初始化 chushihua() ：用于程序开始进行初始化输入数据：进程数量、资源种类、各种资源可利用数量、各进程的各种资源已分配数量、各进程对各类资源最大需求数等。4.1.2 当前安全性检查safe() ：用于判断当前状态安全性，根据不同地方的调用提示处理不同。4.1.2 银行家算法 ba

11、nk() ：进行银行家算法模拟实现的模块，调用其他各个模块进行银行家算法模拟过程。4.1.4 显示当前状态 show()：显示当前资源分配详细情况， 包括：各种资源的总数量 (all)、系统目前各种资源可用的数量、各进程已经得到的资源数量、各进程还需要的资源量。4.1.5 主程序 main() 逐个调用初始化、显示状态、安全性检查、银行家算法函数，使程序有序的进行。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 23 页 - - - - - - - - - 4.2 数据结

12、构程序使用的全局变量：const int x=10，y=10； /定义常量int Availablex; /各种资源可利用的数量int Allocationyy; /各进程当前已分配的资源数量int Maxyy; /各进程对各类资源的最大需求数int Needyy; /还需求矩阵int Requestx; /申请各类资源的数量int Workx; /工作向量，表系统可提供给进程运行所需各类资源数量int Finishy; /表系统是否有足够的资源分配给进程，0 为否， 1 为是int py; /存储安全序列int i,j; /全局变量，主要用于循环语句中int n,m; /n为进程的数量 ,m

13、为资源种类数int l=0,counter=0; 4.3 函数声明void chushihua(); / 系统初始化函数void safe(); / 安全性算法函数void bank(); /银行家算法函数void show (); / 输出当前资源分配情况4.4 主函数 main() int main() cout / 显示程序开始提示信息 chushihua(); /初始化函数调用coutendlendl; showdata(); /输出初始化后的状态 /=判断当前状态的安全性 = 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - -

14、 - 名师精心整理 - - - - - - - 第 9 页，共 23 页 - - - - - - - - - safe(); /安全性算法函数调用 if (ln) coutn当前状态不安全， 无法申请 , 程序退出 !endl; coutendl; system(pause); sign(); /调用签名函数 return 0; / break; else int i; /局部变量 l=0; coutn安全的状态 !endl; cout安全序列为 : ; coutendl进程(p0); /输出安全序列，考虑显示格式，先输出第一个 for (i=1; in; i+) cout进程(pi); fo

15、r (i=0; in; i+) Finishi=0; /所有进程置为未分配状态 coutendlendl; bank(); /银行家算法函数调用return 0; 第五章银行家算法代码实现5.1源程序代码：#include #include 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 23 页 - - - - - - - - - #include using namespace std; #define TRUE 1 /定义 TRUE =1 #define FALS

16、E 0 /定义 FLASE=0 void bank(vector,vectorvector ,vectorvector ,int ,int ); / 声明 bank（应行家算法）int safe(vector Available,vectorvector Need,vectorvector Allocation,int n,int m);/声明 safe （）安全性算法void init(); /*主函数main()*/ void main() init(); int safe(vector Available,vectorvector Need,vectorvector Allocation

17、,int n,int m); /*初始化函数init()*/ / 下面的是在 dos 命令下使用的程序void init() int m; /m资源类数int n; /进程数cout 输入资源类数 m; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 23 页 - - - - - - - - - vector Available(m); /动态申请数组 Available可用资源向量cout 输入各类资源总数 :endl; for (int i=0;im;i+) cou

18、t 输入 RiAvailablei; coutn输入进程数 n; vectorvector Max(n, vector(m); cout 输入进程 i 的最大需求向量 ; for (int j=0;jm;j+) cout 输入需要 RjMaxij; while (MaxijAvailablej) coutjMaxij; cout 输入已分配的 Allocationendl; vectorvector Allocation(n, vector(m); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - -

19、 - - 第 12 页，共 23 页 - - - - - - - - - vectorvector Need(n, vector(m); for ( i=0;in;i+) cout 输入为进程 i 的分配向量 ; for (int j=0;jm;j+) cout 输入分配 RjAllocationij; while(AllocationijMaxij) coutj+1Allocationij; Needij=Maxij-Allocationij; Availablej =Availablej-Allocationij; int safe(vector Available,vectorvecto

20、r Need,vectorvector Allocation,int n,int m); cout 此状态安全 !endl; bank(Available,Need,Allocation,n,m);/调用银行家算法 bank() 函数/ 下面的是在文件中导入我们所需的信息/*/void init() int m; /m资源类数名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 23 页 - - - - - - - - - int n; /进程数cout 输入资源类数 m;

21、vector Available(m); /动态申请数组 Available可用资源向量cout 输入各类资源总数 :endl; FILE *fp; fp=fopen(Available.txt,r+); cout 从 Available.txt文件中读入数据，并输出 endl; for(int i=0;im;i+) fscanf(fp,%d,&Availablei); coutAvailableit; fclose(fp); coutn输入进程数 n; vectorvector Max(n, vector(m); fp=fopen(Max.txt,r+); cout 从 Max.txt文件中

22、读入数据，并输出endl; for(i=0;in;i+) for (int j=0;jm;j+) fscanf(fp,%d,&Maxij); coutMaxij ; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 23 页 - - - - - - - - - coutendl; fclose(fp); cout 输入已分配的 Allocationendl; vectorvector Allocation(n, vector(m); vectorvector Need(n

23、, vector(m); fp=fopen(Allocation.txt,r+); coutAllocation.txt从文件中读入数据，并输出endl; for(i=0;in;i+) for (int j=0;jm;j+) fscanf(fp,%d,&Allocationij); Needij=Maxij-Allocationij; /在初始化 Max时，同时初始化 Need数组Availablej =Availablej-Allocationij; /在初始化 Max时，同时修改 Available数组coutAllocationij ; coutendl; fclose(fp); int

24、 safe(vector Available,vectorvector Need,vectorvector Allocation,int n,int m); cout 此状态安全 !endl; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 23 页 - - - - - - - - - bank(Available,Need,Allocation,n,m);/调用银行家算法 bank() 函数 /*/ /*银行家算法 bank() 函数*/ void bank(vect

25、or Available,vectorvector Need,vectorvector Allocation,int n,int m) vector Request(m); int all=0; / 定义变量 all ，如果 all=0 ，表示进程已经运行完，如果all=1 ，表示还有进程没有运行完for (int i=0;in;i+) for(int j=0;jm;j+) all +=Needij; if (0=all) cout 所有进程已经运行完，结束=1 ，表示还有进程没有运行完/ 循环直至 all0,即找到一个未运行完的进程cout 任选一个进程作为当前进程0-n-1jc; for

26、(int j=0;jm;j+) all += Needjcj; if (0=all) cout 此进程已经运行，重新输入endl; cout 输入该进程的请求向量 endl; for (i=0;iRequesti; while(RequestiNeedjci|RequestiAvailablei) cout 请求向量无法满足 endl; break; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 23 页 - - - - - - - - - / / 系统试探着把资源分

27、配给该进程/ for (i=0;im;i+) Availablei=Availablei-Requesti; Allocationjci=Allocationjci+Requesti; Needjci=Needjci-Requesti; int bb=0; bb=safe(Available,Need,Allocation,n,m);/调用安全性算法，判断此次资源分配后，系统是否处安全状态if (1=bb) cout 系统成功分配资源 endl; else cout 系统未能成分配资源 , 收回预分配资源 endl; for (i=0;im;i+) Availablei=Availablei+

28、Requesti; Allocationjci=Allocationjci-Requesti; Needjci=Needjci+Requesti; cout 您还想再次请求分配吗 ?是请按 y/Y, 否请按其它键 again; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 23 页 - - - - - - - - - if(again=y|again=Y) all=0; continue; break; /*安全性算法 safe() 函数*/ int safe(vec

29、tor Available,vectorvector Need,vectorvector Allocation,int n,int m) vector Work(m),Finish(n);/申请工作向量 work，finish Work=Available; vector count(n); /记录安全序列int len=-1; /记录安全序列的进程个数，如果len=n，即表示所有的finish【i 】=true ，处于安全状态for(int i=0;im;i+)Finishi=FALSE; for (i=0;in;i+) int needed=1; for (int j=0;jm;j+) i

30、f(Needij=Workj) needed=needed*TRUE; else needed=needed*FALSE; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 23 页 - - - - - - - - - if (Finishi=FALSE)&needed=1) for (j=0;jm;j+) Workj=Workj+Allocationij; Finishi=TRUE; len=len+1; countlen=i; i=-1; if (len=n-1) c

31、out 系统是安全的 endl; cout 安全序列 endl; for (i=0;i=len;i+) coutcounti; if (i!=len) cout; coutendl; return TRUE; else 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 23 页 - - - - - - - - - cout 系统是不安全的 endl; return FALSE; 第六章运行结果6.1 初始化结果6.1.1通过文本初始化：测试使用的是文本导入信息6.1.2

32、安全检验名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 21 页，共 23 页 - - - - - - - - - 6.1.3 dos命令下的手动输入，我们就不做了第七章课程设计总结操作系统的基本特征是并发与共享。系统允许多个进程并发执行，并且共享系统的软、硬件资源。为了最大限度的利用计算机系统的资源，操作系统应采用动态分配的策略，但是这样就容易因资源不足，分配不当而引起“死锁”。这次课程设计就是利用银行家算法来避免“死锁”。银行家算法就是一个分配资源的过程，使分配的序列不会产生死锁

33、。本课程设计的存在着以下不足：一、不能实现并发操作，即当总资源同时满足几个进程所需要的资源数时，这些进程不能同时进行，只能一一按进程顺名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 22 页，共 23 页 - - - - - - - - - 序执行。二、扫描进程顺序单一，只能按进程到来的顺序（即编号）来扫描，从而产生的安全顺序只能是在这个顺序的基础上产生的，而其实安全顺序是有多个的。三、对进程数和资源数进行的数量进行了限制，都只能最多有十个。四、运行程序后，界面较差，进程数，所需要资源数，已分配资源数，能用资源数，不能一目了然。本次课程设计让我学到了很多的实用性知识。除了对这个算法有了更加深刻的认识， 而且对 C+ 语言进行了复习， 而且其过程中弄明白了许多以前没有弄明白的知识点，只有动手去做才能够极大的提高我们的水平，光靠看是没有用的。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 23 页，共 23 页 - - - - - - - - -