计算机操作系统银行家算法实验报告材料
- 格式:doc
- 大小:123.50 KB
- 文档页数:8
操作系统实验报告----银行家算法班级:______计算机03(7)班______________ 姓名:_________李君益__________________ 学号:______________(61号)___提交日期:____06.7.11___________________ 指导老师: ______林穗____________________一、设计题目加深了解有关资源申请、避免死锁等概念,并体会和了解死锁和避免死锁的具体实施方法。
要求编写和调试一个系统动态分配资源的简单模拟程序,观察死锁产生的条件,并采用银行家算法,有效的防止和避免死锁的发生。
二、设计要求内容:编制银行家算法通用程序,并检测思考题中所给状态的安全性。
要求:(1)下列状态是否安全?(三个进程共享12个同类资源)进程已分配资源数最大需求数1 1 4 (状态a)2 4 43 5 81 1 42 4 6 (状态b)3 6 8(2)考虑下列系统状态分配矩阵最大需求矩阵可用资源矩阵0 0 1 2 0 0 1 2 1 5 2 01 0 0 0 1 7 5 01 3 5 423 5 60 6 3 2 0 6 5 20 0 1 4 0 6 5 6问系统是否安全?若安全就给出所有的安全序列。
若进程2请求(0420),可否立即分配?三、设计分析一.关于操作系统的死锁1.死锁的产生计算机系统中有许多独占资源,他们在任一时刻只能被一个进程使用,如磁带机,绘图仪等独占型外围设备,或进程表,临界区等软件资源。
两个进程同时向一台打印机输出将导致一片混乱,两个进程同时进入临界区将导致数据库错误乃至程序崩溃。
正因为这些原因,所有操作系统都具有授权一个进程独立访问某一辞源的能力。
一个进程需要使用独占型资源必须通过以下的次序:●申请资源●使用资源●归还资源若申请施资源不可用,则申请进程进入等待状态。
对于不同的独占资源,进程等待的方式是有差别的,如申请打印机资源、临界区资源时,申请失败将一位这阻塞申请进程;而申请打开文件文件资源时,申请失败将返回一个错误码,由申请进程等待一段时间之后重试。
《计算机操作系统》课程设计题目银行家算法分析学院计算机与软件学院专业计算机科学与技术班级学号姓名指导教师起止时间一、算法综述银行家算法:在进程向系统提出资源分配请求时,算法会先对进程提出的请求进行合法性检查,即检查请求的是不大于需要的,是否不大于可利用的。
若请求合法,则进行试分配。
最后对试分配后的状态调用安全性检查算法进行安全性检查。
若安全,则分配,否则,不分配,恢复原来状态,拒绝申请。
二.算法分析2.1 银行家算法中的数据结构为资源的种类i进程的数量j可利用资源向量int Available[j]最大需求矩阵int Max[i][j]分配矩阵int Allocation[i][j]需求矩阵int need[i][j]= Max[i][j]- Allocation[i][j]申请各类资源数量int Request i[j] i进程申请j资源的数量工作向量int Work[x] int Finish[y]2.2银行家算法设Request i是进程P i的请求向量,如果Request i[j]=K,表示进程P i需要k个Rj类型的资源,当P i发出资源请求后,系统按照下述步骤进行检查:(1)如果Request i[j]≤Need[j],便转向步骤(2);否则认为出错,因为它所需要的资源数已经超过它所宣布的最大值。
(2)如果Request i[j]≤Available[j],便转向步骤(3);否则,表示尚无足够资源,P i须等待。
(3)系统试探着将资源分配给进程P i,并修改下面数据结构中的数值:Available[j]:=Available[j]-Request i[j];Allocation[i,j]:=Allocation[i,j]+Request i[j];Need[i,j]:=Need[i,j]-Request i[j];(4)系统执行安全性算法,检查此次资源分配后系统是否处于安全状态。
若安全,才正式将资源分配给进程P i,以完成本次分配;否则本次的试探分配作废,恢复原来的资源分配状态,让进程P i等待。
实验五银行家算法一、实验目的和要求①理解死锁概念,银行家算法及安全检测算法。
②在Linux操作系统下用C++进行编程。
③利用C++设计实现银行家算法的基本过程。
④验证银行家算法对于避免死锁的作用。
二、实验方法内容①算法设计思路1.设计进程对各类资源最大申请表示及初值确定。
2.设定系统提供资源初始状况。
3.设定每次某个进程对各类资源的申请表示。
4.编制程序,依据银行家算法,决定其申请是否得到满足。
②算法流程图如下:③算法中用到的数据结构说明1. 可利用资源向量Available ,它是一个含有m个元素的数组,其中的每一个元素代表一类可利用的资源的数目,其初始值是系统中所配置的该类全部可用资源数目。
其数值随该类资源的分配和回收而动态地改变。
如果Available[j]=k,标是系统中现有Rj类资源k个。
2. 最大需求矩阵P,这是一个n×m的矩阵,它定义了系统中n个进程中的每一个进程对m类资源的最大需求。
如果P(i,j)=k,表示进程Pi需要Rj类资源的最大数目为k。
3. 分配矩阵Allocation,这是一个n×m的矩阵,它定义了系统中的每类资源当前一分配到每一个进程的资源数。
如果Allocation(i,j)=k,表示进程Pi 当前已经分到Rj类资源的数目为k。
Allocation i表示进程Pi的分配向量,有矩阵Allocation的第i行构成。
4. 需求矩阵Need,这是一个n×m的矩阵,用以表示每个进程还需要的各类资源的数目。
如果Need(i,j)=k,表示进程Pi还需要Rj类资源k个,才能完成其任务。
Need i表示进程i的需求向量,由矩阵Need的第i行构成。
上述三个矩阵间存在关系:Need(i,j)=P(i,j)-Allocation(i,j);5. Request i是进程Pi 的请求向量。
Request i(j)=k表示进程Pi请求分配Rj类资源k个。
淮海工学院计算机工程学院实验报告书课程名:《操作系统原理》题目:银行家算法班级:学号:姓名:一、实验目的银行家算法是操作系统中避免死锁的典型算法,本实验可以加深对银行家算法的步骤和相关数据结构用法的更好理解。
实验环境Turbo C 2.0/3.0或VC++6.0实验学时4学时,必做实验。
二、实验内容用C语言编写一个简单的银行家算法模拟程序,用银行家算法实现资源分配。
程序能模拟多个进程共享多种资源的情形。
进程可动态地申请资源,系统按各进程的申请动态地分配资源。
要求程序具有显示和打印各进程的某一时刻的资源分配表和安全序列;显示和打印各进程依次要求申请的资源数量以及为某进程分配资源后的有关资源数据的情况。
三、实验说明实验中进程的数量、资源的种类以及每种资源的总量Total[j]最好允许动态指定。
初始时每个进程运行过程中的最大资源需求量Max[i,j]和系统已分配给该进程的资源量Allocation[i,j]均为已知(这些数值可以在程序运行时动态输入),而算法中其他数据结构的值(包括Need[i,j]、Available[j])则需要由程序根据已知量的值计算产生。
四、实验步骤1、理解本实验中关于两种调度算法的说明。
2、根据调度算法的说明,画出相应的程序流程图。
3、按照程序流程图,用C语言编程并实现。
五、分析与思考1.要找出某一状态下所有可能的安全序列,程序该如何实现?答:要找出这个状态下的所有可能的安全序列,前提是要是使这个系统先处于安全状态,而系统的状态可通过以下来描述:进程剩余申请数=最大申请数-占有数;可分配资源数=总数-占有数之和;通过这个描述来算出系统是否安全,从而找出所有的安全序列。
2.银行家算法的局限性有哪些?答:银行家算法是一种最有代表性的避免死锁的算法。
银行家算法即把操作系统看作是银行家,操作系统管理的资源相当于银行家管理的资金,进程向操作系统请求分配资源相当于用户向银行家贷款。
操作系统按照银行家制定的规则为进程分配资源,当进程首次申请资源时,要测试该进程对资源的最大需求量,如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源,否则就推迟分配。
银⾏家算法_实验报告课程设计报告课程设计名称共享资源分配与银⾏家算法系(部)专业班级姓名学号指导教师年⽉⽇⽬录⼀、课程设计⽬的和意义 (3)⼆、⽅案设计及开发过程 (3)1.课题设计背景 (3)2.算法描述 (3)3.数据结构 (4)4.主要函数说明 (4)5.算法流程图 (5)三、调试记录与分析四、运⾏结果及说明 (6)1.执⾏结果 (6)2.结果分析 (7)五、课程设计总结 (8)⼀、程设计⽬的和意义计算机科学与技术专业学⽣学习完《计算机操作系统》课程后,进⾏的⼀次全⾯的综合训练,其⽬的在于加深催操作系统基础理论和基本知识的理解,加强学⽣的动⼿能⼒.银⾏家算法是避免死锁的⼀种重要⽅法。
通过编写⼀个模拟动态资源分配的银⾏家算法程序,进⼀步深⼊理解死锁、产⽣死锁的必要条件、安全状态等重要概念,并掌握避免死锁的具体实施⽅法⼆、⽅案设计及开发过程1.课题设计背景银⾏家算法⼜称“资源分配拒绝”法,其基本思想是,系统中的所有进程放⼊进程集合,在安全状态下系统受到进程的请求后试探性的把资源分配给他,现在系统将剩下的资源和进程集合中其他进程还需要的资源数做⽐较,找出剩余资源能满⾜最⼤需求量的进程,从⽽保证进程运⾏完成后还回全部资源。
这时系统将该进程从进程集合中将其清除。
此时系统中的资源就更多了。
反复执⾏上⾯的步骤,最后检查进程的集合为空时就表明本次申请可⾏,系统处于安全状态,可以实施本次分配,否则,只要进程集合⾮空,系统便处于不安全状态,本次不能分配给他。
请进程等待2.算法描述1)如果Request[i] 是进程Pi的请求向量,如果Request[i,j]=K,表⽰进程Pi 需要K个Rj类型的资源。
当Pi发出资源请求后,系统按下述步骤进⾏检查:如果Requesti[j]<= Need[i,j],便转向步骤2;否则认为出错,因为它所需要的资源数已超过它所宣布的最⼤值。
2)如果Requesti[j]<=Available[j],便转向步骤3,否则,表⽰尚⽆⾜够资源,进程Pi须等待。
1. 题目分析1.1 设计目的●理解死锁产生的原因和必要条件●了解避免死锁的几种基本方法●掌握银行家算法及安全性算法1.2 设计内容设计内容包括银行家算法和安全性算法,以及用VC界面实现输出1.3 相关知识概述银行家算法是一种最有代表性的避免死锁的算法。
要解释银行家算法,必须先解释操作系统安全状态和不安全状态。
安全状态:如果存在一个由系统中所有进程构成的安全序列P1,…,Pn,则系统处于安全状态。
安全状态一定是没有死锁发生。
不安全状态:不存在一个安全序列。
不安全状态一定导致死锁。
安全序列:一个进程序列{P1,…,Pn}是安全的,如果对于每一个进程Pi(1≤i≤n),它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和。
2. 概要设计2.1主要数据结构描述static int MAX[5][3]; //最大需求矩阵static int AVAILABLE[3]; //可利用资源矩阵static int ALLOCATION[5][3]; //分配矩阵static int NEED[5][3]; //需求矩阵因为数组成员MAX,AVAILABLE, ALLOCATION, NEED的值每次调用一次银行家算法,如果分配成功,都会改变,所以将他们设定为静态成员变量。
int Request[3]; //请求向量int Work[3]; //工作向量bool FINISH[5];//标记系统是否有足够的资源分配给进程2.2 流程图(1)银行家算法流程图单击“执行银行家算法”按钮时会调用OnButton1()函数,相当于银行家算法注:只要不按“退出”按钮退出程序,数组MAX,A V AILABLE, ALLOCATION, NEED中会保留上一次执行完后变化的值,不停的单击“进行银行家算法”按钮,程序会在上一次执行完后的基础上反复的执行银行家算法。
(2)安全性算法流程图3. 详细设计3.1 主要算法描述当进程pi提出资源申请时,系统执行下列步骤:(1)若Request≤Need,转(2);否则错误返回(2)若Request≤Available,转(3);否则进程等待(3)假设系统分配了资源,则有:Available:=Available-Request;Allocation:=Allocation+Request;Need:=Need-Request若系统新状态是安全的,则分配完成若系统新状态是不安全的,则恢复原状态,进程等待安全性检查的步骤:(1) Work:=Available;Finish:=false;(2) 寻找满足条件的i:Finish=false;Need≤Work;如果不存在,则转(4)(3) Work:=Work+Allocation;Finish:=true;转(2)(4) 若对所有i,Finish=true,则系统处于安全状态,否则处于不安全状态3.2 程序界面设计4. 编码实现4.1 开发工具简介Visual C++集成开发环境下下实现的4.2 部分程序源码int CSisuoDlg::MAX[5][3]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}};int CSisuoDlg::AVAILABLE[3]={3,3,2};int CSisuoDlg::ALLOCATION[5][3]={{0,1,0},{2,0,0},{3,0,2},{2,1,1},{0,0,2}}; int CSisuoDlg::NEED[5][3]={{7,4,3},{1,2,2},{6,0,0},{0,1,1},{4,3,1}};int CSisuoDlg::safe(){int i,j,k,l=0;int Work[3];bool FINISH[5];int p[5];for(i=0;i<3;i++)Work[i]=AVAILABLE[i];for(i=0;i<5;i++){ FINISH[i]=false;}for(i=0;i<5;i++){if(FINISH[i]==true){ continue;}else{for(j=0;j<3;j++){if(NEED[i][j]>Work[j]){break;}}if(j==3)//找到满足要求的进程{FINISH[i]=true;for(k=0;k<3;k++){Work[k]+=ALLOCATION[i][k];}p[l++]=i;//记录安全序列i=-1;//每次都是从头开始找}else{continue;}}if(l==5){show+="经安全性检查,系统安全,本次分配成功。
操作系统实验报告一、实验内容简要描述1.实验目标:加深了解有关资源申请、避免死锁等概念,并体会和了解死锁和避免死锁的具体实施方法。
要求编写和调试一个系统动态分配资源的简单模拟程序,观察死锁产生的条件,并采用银行家算法,有效的防止和避免死锁的发生。
2.实验要求:银行家算法是避免死锁的一种重要方法,本实验要求用高级语言编写和调试一个简单的银行家算法程序。
用银行家算法实现资源分配。
设计五个进程{p0,p1,p2,p3,p4}共享三类资源{A,B,C}的系统,{A,B,C}的资源数量分别为10,5,7。
进程可动态地申请资源和释放资源,系统按进程的申请动态地分配资源,要求程序具有显示和打印各进程的某一个时刻的资源分配表和安全序列;显示和打印各进程依次要求申请的资源号以及为某进程分配资源后的有关资源数据。
二、报告主要内容1.设计思路A、设计进程对各在资源最大申请表示及初值确定。
B、设定系统提供资源初始状态。
C、设定每次某个进程对各类资源的申请表示。
D、编制程序,依据银行家算法,决定其申请是否得到满足。
2.主要数据结构假设有M个进程N类资源,则有如下数据结构:MAX[M*N] M个进程对N类资源的最大需求量AVAILABLE[N] 系统可用资源数ALLOCATION[M*N] M个进程已经得到N类资源的资源量NEED[M*N] M个进程还需要N类资源的资源量3.主要代码结构void main()void showdata()void changdata(int)void rstordata(int)int chkerr(int)4.主要代码段分析#include "string.h"#include "iostream.h"#define M 5 //总进程数#define N 3 //总资源数#define FALSE 0#define TRUE 1//M个进程对N类资源最大资源需求量int MAX[M][N]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}};//系统可用资源数int AVAILABLE[N]={10,5,7};//M个进程已经得到N类资源的资源量intALLOCATION[M][N]={{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0}};//M个进程还需要N类资源的资源量int NEED[M][N]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}};int Request[N]={0,0,0};void main(){int i=0,j=0;char flag='Y';void showdata();void changdata(int);void rstordata(int);int chkerr(int);showdata();while(flag=='Y'||flag=='y'){i=-1;while(i<0||i>=M){cout<<" 请输入需申请资源的进程号(从0到"<<M-1<<",否则重输入!):";cin>>i;if(i<0||i>=M) cout<<"输入的进程号不存在,重新输入!"<<endl;}cout<<" 请输入进程"<<i<<"申请的资源数"<<endl;for (j=0;j<N;j++){cout<<" 资源"<<j<<":";cin>>Request[j];if(Request[j]>NEED[i][j]){cout<<" 进程"<<i<<"申请的资源数大于进程"<<i<<"还需要"<<j<<"类资源的资源量!";cout<<"申请不合理,出错!请重新选择!"<<endl<<endl;flag='N';break;}else{if(Request[j]>AVAILABLE[j]){cout<<" 进程"<<i<<"申请的资源数大于系统可用"<<j<<"类资源的资源量!";cout<<"申请不合理,出错!请重新选择!"<<endl<<endl;flag='N';break;}}}if(flag=='Y'||flag=='y'){changdata(i);if(chkerr(i)){rstordata(i);showdata();}elseshowdata();}elseshowdata();cout<<endl;cout<<" 是否继续银行家算法演示,按'Y'或'y'键继续,按'N'或'n'键退出演示:";cin>>flag;}}void showdata(){int i,j;cout<<" 系统可用的资源数为:"<<endl<<endl;cout<<" ";for(j=0;j<N;j++) cout<<" 资源"<<j<<": "<<AVAILABLE[j];cout<<endl;cout<<endl;cout<<" 各进程还需要的资源量:"<<endl<<endl;for(i=0;i<M;i++){cout<<"进程"<<i<<":";for(j=0;j<N;j++) cout<<" 资源"<<j<<", "<<NEED[i][j];cout<<endl;}cout<<endl;cout<<" 各进程已经得到的资源量:"<<endl<<endl;for(i=0;i<M;i++){cout<<"进程"<<i<<":";for(j=0;j<N;j++) cout<<" 资源"<<j<<": "<<ALLOCATION[i][j]; cout<<endl;}cout<<endl;};void changdata(int k){int j;for(j=0;j<N;j++){AVAILABLE[j]=AVAILABLE[j]-Request[j];ALLOCATION[k][j]=ALLOCATION[k][j]+Request[j];NEED[k][j]=NEED[k][j]-Request[j];}};void rstordata(int k){int j;for(j=0;j<N;j++){AVAILABLE[j]=AVAILABLE[j]+Request[j];ALLOCATION[k][j]=ALLOCATION[k][j]-Request[j];NEED[k][j]=NEED[k][j]+Request[j];}};int chkerr(int s){int WORK,FINISH[M],temp[M];int i,j,k=0;for(i=0;i<M;i++) FINISH[i]=FALSE;for(j=0;j<N;j++){WORK=AVAILABLE[j];i=s;while(i<M){if(FINISH[i]==FALSE&&NEED[i][j]<=WORK){WORK=WORK+ALLOCATION[i][j];FINISH[i]=TRUE;temp[k]=i;k++;i=0;}else{i++;}}for(i=0;i<M;i++)if(FINISH[i]==FALSE){cout<<endl;cout<<" 系统不安全!!!本次资源申请不成功!!!"<<endl; cout<<endl;return 1;}}cout<<endl;cout<<" 经安全性检查,系统安全,本次分配成功。
一、实验背景在计算机系统中,资源分配和死锁问题是操作系统领域的重要研究课题。
在多进程环境下,进程之间会共享系统资源,如CPU、内存、磁盘等。
然而,当多个进程同时申请资源时,可能会出现死锁现象,导致系统瘫痪。
为了避免死锁,研究者提出了多种资源分配算法,其中最具代表性的就是银行家算法。
银行家算法最初由Edsger Dijkstra于1965年提出,旨在解决银行在贷款业务中可能出现的死锁问题。
该算法通过模拟银行家在贷款业务中的决策过程,对资源分配进行动态规划,以确保系统处于安全状态,从而避免死锁的发生。
二、实验目的本次实验旨在通过实现银行家算法,加深对资源分配、死锁和安全性概念的理解,并掌握以下内容:1. 了解资源分配的基本原理和死锁的概念。
2. 掌握银行家算法的原理和实现方法。
3. 能够运用银行家算法对系统资源进行动态分配,并确保系统处于安全状态。
4. 分析实验结果,验证银行家算法的有效性。
三、实验原理1. 资源分配资源分配是指操作系统将资源分配给进程的过程。
在多进程环境下,资源分配策略需要考虑以下因素:(1)资源的类型和数量。
(2)进程对资源的最大需求。
(3)进程当前已分配的资源。
(4)系统可利用的资源。
2. 死锁死锁是指多个进程在执行过程中,因争夺资源而相互等待,导致系统无法继续执行的现象。
产生死锁的必要条件包括:(1)互斥条件:资源不能被多个进程同时占用。
(2)请求和保持条件:进程在等待资源时,仍保持已占有的资源。
(3)不剥夺条件:进程不能被强制剥夺已占有的资源。
(4)循环等待条件:存在一个进程序列,其中每个进程都在等待前一个进程所持有的资源。
3. 安全状态安全状态是指系统可以按照某种顺序为每个进程分配资源,使得所有进程都可以顺利完成的状态。
判断系统是否处于安全状态的方法如下:(1)计算每个进程的最大需求。
(2)计算系统可利用的资源。
(3)从最大需求中减去已分配的资源,得到剩余需求。
(4)判断剩余需求是否小于等于系统可利用的资源。
操作系统原理课程设计——银行家算法指导老师:周敏唐洪英杨宏雨杨承玉傅由甲黄贤英院系:计算机学院计算机科学与技术系班级:0237-6学号:2002370608姓名:朱应瑜同组者:陈源时间:2005/12/22---2005/12/28目录一、设计目的 (3)二、设计内容 (3)三、银行家算法的基本思想 (3)(一)死锁 (3)(二)系统安全状态 (4)(三)银行家算法避免死锁 (4)1、银行家算法中的数据结构 (4)2、银行家算法 (4)3、安全性算法 (5)四、系统模块间关系图 (6)五、系统子模块结构图 (7)六、输入、输出数据 (9)七、源程序及系统文件使用说明 (12)(一)源程序 (12)(二)系统文件使用说明 (25)八、心得体会 (26)九、参考文献 (26)银行家算法一、设计目的本课程设计是学习完《计算机操作系统》课程后,进行的一次全面的综合训练。
通过这次课程设计,让我们更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和重要算法的理解,加强动手能力。
二、设计内容编制银行家算法通用程序,并检测所给状态的系统安全性。
三、银行家算法的基本思想(一)死锁在多道程序系统中,虽可借助于多个进程的并发执行,来改善系统的资源利用率,提高系统的吞吐量,但可能发生一种危险——死锁。
所谓死锁,是指多个进程在运行过程中因争夺资源而造成的一种僵局,当进程处于这种僵持状态时,若无外力作用,它们都将无法再向前推进。
产生死锁的原因可归结为如下两点:(1)竞争资源。
(2)进程间推进顺序非法。
死锁的发生必须具备下列四个必要条件:(1)互斥条件。
(2)请求和保持条件。
(3)不剥夺条件。
(4)环路等待条件。
(二)系统安全状态避免死锁的实质在于:系统在进行资源分配时,如何使系统不进入不安全状态。
所谓安全状态,是指系统能按某种进程顺序(P1,P2,……,Pn)(称<P1,P2,……,Pn>序列为安全序列),来为每个进程P i分配其所需资源,直至满足每个进程对资源的最大需求,使每个进程都可顺利的完成。
实验四银行家算法实习内容通过编程理解银行家算法,掌握进程安全性检查的方法及资源分配的方法,加深了解有关资源申请、避免死锁等概念,体会和了解死锁和避免死锁的具体实施方法。
实习目的银行家算法是避免死锁的代表性算法。
本实习旨在加深了解有关资源申请、避免死锁、状态安全性等概念,并体会和运用避免死锁的具体实施方法。
然后依照本实习,自行设计模拟程序。
实习原理算法思想:银行家算法操作系统按照银行家制定的规则为进程分配资源,当进程首次申请资源时,要测试该进程对资源的最大需求量,如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源,否则就推迟分配。
当进程在执行中继续申请资源时,先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。
若超过则拒绝分配资源,若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量,若能满足则按当前的申请量分配资源,否则也要推迟分配。
安全状态:如果存在一个由系统中所有进程构成的安全序列P1,…,Pn,则系统处于安全状态。
安全状态一定是没有死锁发生。
不安全状态:不存在一个安全序列。
不安全状态一定导致死锁。
实习编程思路和流程在避免死锁的方法中,如果施加的限制条件较弱,有可能获得令人满意的系统性能。
在该方法中把系统的状态分为安全状态和不安全状态,只要能使系统始终都处于安全状态,便可以避免发生死锁。
基本思想为:在分配资源之前,判断系统是否是安全的;若安全,才分配。
它是最具代表性的死锁算法,具体算法如下表示:假设进程P提出请求Request[i],则银行家算法按如下步骤进行判断:1)如果Request[i] <=Need[i],则转向2);否则出错。
2)如果Request[i] <=Available[i],则转向3);否则出错。
3)系统试探分配相关资源,修改相关数据:Available[i]=Available[i]-Request[i];Allocation[i]=Allocation[i]+Request[i];Need[i]=Need[i]-Request[i];4)系统执行安全性检查,如安全,则分配成立;否则试探性分配资源作废,系统恢复原状,进程进入等待状态。
实用标准文案
文档大全
计算机操作系统实验报告
一、 实验名称:银行家算法
二、 实验目的:银行家算法是避免死锁的一种重要方法,通过编写
一个简单的银行家算法程序,加深了解有关资源申请、避免死
锁等概念,并体会和了解死锁和避免死锁的具体实施方法。
三、 问题分析与设计:
1、算法思路:先对用户提出的请求进行合法性检查,即检查请
求是否大于需要的,是否大于可利用的。若请求合法,则进行
预分配,对分配后的状态调用安全性算法进行检查。若安全,
则分配;若不安全,则拒绝申请,恢复到原来的状态,拒绝申
请。
2、银行家算法步骤:(1)如果Requesti<or =Need,则转向步
骤(2);否则,认为出错,因为它所需要的资源数已超过它所宣
布的最大值。
(2)如果Request<or=Available,则转向步骤(3);否则,表示
系统中尚无足够的资源,进程必须等待。
(3)系统试探把要求的资源分配给进程Pi,并修改下面数据结构
中的数值:
Available=Available-Request[i];
Allocation=Allocation+Request;
实用标准文案
文档大全
Need=Need-Request;
(4)系统执行安全性算法,检查此次资源分配后,系统是否处于安
全状态。
3、安全性算法步骤:
(1)设置两个向量
①工作向量Work。它表示系统可提供进程继续运行所需要的各类资
源数目,执行安全算法开始时,Work=Allocation;
②布尔向量Finish。它表示系统是否有足够的资源分配给进程,使之
运行完成,开始时先做Finish[i]=false,当有足够资源分配给进程时,
令Finish[i]=true。
(2)从进程集合中找到一个能满足下述条件的进程:
①Finish[i]=false
②Need
(3)当进程P获得资源后,可顺利执行,直至完成,并释放出分配
给它的资源,故应执行:
Work=Work+Allocation;
Finish[i]=true;
转向步骤(2)。
实用标准文案
文档大全
(4)如果所有进程的Finish[i]=true,则表示系统处于安全状态;否则,
系统处于不安全状态。
四.程序源代码:
#include
#define W 5//最大进程数W=5
#define R 3//最大资源总数=3
int Available[3];//可利用资源向量
int Max[5][3];//最大需求矩阵
int Allocation[5][3]; //分配矩阵
int Need[5][3];//需求矩阵
int Request[3];//进程请求向量
void dispose()
{
printf("请输入可利用资源向量Available(格式:a,b,c)\n");
scanf("%d,%d,%d",&Available[0],&Available[1],&Available[2])
;
printf("请输入最大需求数Max(格式:a,b,c)\n");
for(int j=0;j<5;j++)
{
printf("进程%d:\n",j);
scanf("%d,%d,%d",&Max[j][0],&Max[j][1],&Max[j][2]);
}
printf("请输入分配数Allocation(格式:a,b,c)\n");
实用标准文案
文档大全
for(j=0;j<5;j++)
{
printf("进程%d\n",j);
scanf("%d,%d,%d",&Allocation[j][0],&Allocation[j][1],&Al
location[j][2]);
}//输入Max[5][3],Available[5][3],Allocation[5][3]
for(j=0;j<5;j++)
for(int i=0;i<3;i++)
Need[j][i]=Max[j][i]-Allocation[j][i];//求出Need[5][3]
}
main()
{
printf(" 银行家算法 \n");
dispose();
printf("安全性检查\n");
int Work[3];//系统可提供进程继续运行所需的各类资源数
char Finish[5];//表示系统是否有足够的资源分配
for(int i=0;i<5;i++)
Finish[i]='f';
for(int k=0;k<3;k++)
Work[k]=Available[k];
int q[5];
for(int x=0;x<50;x++)
{
printf("请输入一个序列:\n");
实用标准文案
文档大全
scanf("%d,%d,%d,%d,%d",&q[0],&q[1],&q[2],&q[3],&q[4]);
for(i=0;i<5;i++)
{
if((Need[q[i]][0]<=Work[0])&&(Need[q[i]][1]<=Work[1])&&(Nee
d[q[i]][2]<=Work[2]))//比较Need[i][j]与Work[j]
{
for(k=0;k<3;k++)
Work[k]=Work[k]+Allocation[q[i]][k];
Finish[i]='t';
}
}
if((Finish[0]=='t')&&(Finish[1]=='t')&&(Finish[2]=='t')&
&(Finish[3]=='t')&&(Finish[4]=='t'))//通过Finish[i]判断系统
是否安全
break;
else
printf("此序列不是安全序列,请重新输入一个序列!\n");
if(x==49)
return 0;
}
printf("这个系统安全!\n");
实用标准文案
文档大全
int a;
printf("请输入Request进程:\n");
scanf("%d",&a);
printf("该进程Request(a,b,c)\n");
scanf("%d,%d,%d",&Request[0],&Request[1],&Request[2]);//输
入请求量Request[3]
if((Request[0]<=Need[a][0])&&(Request[1]<=Need[a][1])&&(Req
uest[2]<=Need[a][2]))//判断Request[i]<=Need[a][i]
{
if((Request[0]<=Need[a][0])&&(Request[0]<=Need[a][1])&&(
Request[0]<=Need[a][2]))//判断Request[i]<=Available[a][i]
{
for(int k=0;k<3;k++)
{
Available[k]=Available[k]-Request[k];
Allocation[a][k]=Allocation[a][k]+Request[k];
Need[a][k]=Need[a][k]-Request[k];
//如果上述判断成功,则修改相应的
Available[k],Allocation[a][k],Need[a][k]
}
printf("资源分配成功!\n");
}
else
{
printf("资源分配失败!\n");
return 0;
实用标准文案
文档大全
}
}
else
{
printf("资源分配失败!\n");
return 0;
}
}
程序截图:
实用标准文案
文档大全
五.实验总结
多个进程同时运行时,系统根据各类系统资源的最大需求和各
类系统的剩余资源为进程安排安全序列,使得系统能快速且安
全地运行进程,不至发生死锁。银行家算法是避免死锁的主要
方法,其思路在很多方面都非常值得我们来学习借鉴
。