精华内容
下载资源
问答
  • 银行家算法之安全性算法

    万次阅读 2016-10-09 01:15:40
    安全序列是指存在一个进程序列{P1,…,Pn}是安全的,不会死锁(至少两个线程占有某资源A,但是都不满足,剩余的资源A分配给谁仍然无法满足),安全状态如果存在一个由系统中所有进程构成的安全序列P1,…,Pn,则系统...

    1. 安全性算法过程描述

    (1) 设置两个向量:① 工作向量Work:它表示系统可提供给进程继续运行所需的各类资源数量的多少,它含有m个元素,在执行安全算法开始时,Work = Available;② Finish:它表示系统是否有足够的资源分配给进程,使之运行完成。开始时先做Finish[i]= false;当有足够资源分配给进程时, 再令Finish[i]= true。

    (2) 从进程集合中找到一个能满足下述条件的进程:
    ① Finish[i]= false; ② Need[i,j]≤ Work[j];
    如果找到,那么,执行步骤(3);否则,执行步骤(4)。

    (3) 当进程Pi获得资源后,可顺利执行,直至完成,并释放出分配给它的资源,故应执行:

     Work[j]= Work[i]+Allocation[i,j]; 
     Finish[i]= true;
     go to step 2; 
    
    

    (4) 如果所有进程的Finish[i]= true都满足, 则表示系统处于安全状态;否则,系统处于不安全状态。

    2. 流程图

    Created with Raphaël 2.2.0开始STEP1:设置工作向量Work和FinishSTEP2:找到一个满足条件进程PiSTEP3:执行进程Pi,释放资源STEP4:all Finish[i]=trueOutput:securable...结束Output:not securableyesnoyesno

    3. 例子

    如果当前资源分配如下表:

    进程 最大需求Max 已分配Allocation 可用Available
    P1 10 5 3
    P2 4 2
    P3 9 2

    安全序列:P2->P1->P3

    4. 代码实现

    /**
     * Copyright ? 2016 Authors. All rights reserved.
     *
     * FileName: bankSecurable.cpp
     * Author: Wu_Being <1040003585@qq.com>
     * Date/Time: 09-10-16 00:39
     * Description: 银行家算法之安全性检查子算法 
     */
    #include <iostream>
    #define N 3			//进程数目 
    #define M 1			//资源类数(为了好理解,这里令资源种类设为1种) 
    
    using namespace std;
    
    int Available[M];		//空闲资源向量Available
    int Max[N][M];			//最大需求矩阵Max
    int Allocation[N][M];	//分配矩阵Allocation
    int Need[N][M];			//需求矩阵Need
    
    bool bankSecurable(int allocation[N][M],int available[M]){
    	
    STEP1:	
    	int finish[N];
    	int work[M];
    	int i=0;			//第i个进程 
    	int j=0;			//第j个资源 
    	
    	for( i=0;i<N;i++){
    		finish[i]=false;
    	}	
    	for( j=0;j<M;j++){
    		work[j]=available[j];
    	}	
    	
    STEP2:
        //for( j=0;j<M;j++)//(资源类数>1)
    	for( i=0;i<N;i++){
    		if(finish[i]==false&&Need[i][0]<=work[0]){//[i][j](资源类数>1)
    			goto STEP3;
    		}else{
    			if(i==N-1){
    			//从进程集合中找不到一个进程能满足条件时
    				goto STEP4;
    			}
    		}
    	}
    	
    STEP3:
    	work[0]=work[0]+allocation[i][0];//[i][j](资源类数>1)
    	//count[i]++(资源类数>1)
    	//if count[i]==M(资源类数>1)
    	finish[i]=true;
    	//securable series[k]=i;
    	goto STEP2;
    	
    STEP4:
    	bool alltrue=true;
    	for( i=0;i<N;i++){
    		if(finish[i]==false){
    			alltrue=false;
    			break;
    		}
    	}
    	
    	return alltrue;
    }
    
    int main(int argc,char* argv[])
    {
    	/* 1、初始化*/
    	Available[0]=3;
    	Max[0][0]=10;Max[0][1]=4;Max[0][2]=9;
    	Allocation[0][0]=5;Allocation[0][1]=2;Allocation[0][2]=2;
    	for(int i=0;i<N;i++){
    		for(int j=0;j<M;j++){
    			Need[i][j]=Max[i][j]-Allocation[i][j];
    		}
    	}		
    	
    	/* 2、安全性检查*/
    	bool secure=bankSecurable(Allocation,Available);
        
    	/* 3、结果输出*/
    	if(secure)cout<<"is securable..."<<endl;
        else cout<<"is not securable!!!"<<endl;
        
    	return 0;
    }
    
    

    5. 运行截图

    这里写图片描述

    Wu_Being博客声明:本人博客欢迎转载,请标明博客原文和原链接!谢谢!
    《银行家算法——安全性检查子算法》:
    http://blog.csdn.net/u014134180/article/details/52762186

    展开全文
  • 用C语言编写银行家算法,其中包括银行家算法安全性检测,资源的请求分配等
  • 一句话+一张图说清楚——银行家算法

    万次阅读 多人点赞 2018-05-08 21:10:44
    当一个进程申请使用资源的时候,银行家算法通过先 试探 分配给该进程资源,然后通过安全性算法判断分配后的系统是否处于安全状态,若不安全则试探分配作废,让该进程继续等待。 那么此时会有一个问题,...

    本文试图用一句话+一张图说清楚操作系统中的银行家算法。我相信用一句话可以讲清楚一个算法的核心思想,一张图可以描述整个算法的操作步骤。但本人能力有限,错误之处望大家指出,多谢。

    一句话:

    当一个进程申请使用资源的时候,银行家算法通过先 试探 分配给该进程资源,然后通过安全性算法判断分配后的系统是否处于安全状态,若不安全则试探分配作废,让该进程继续等待。

    那么此时会有一个问题,如何判断系统是否处于安全状态?算法流程将用下面一张图来表示。

    一张图

    这里写图片描述

    • 首先是银行家算法中的进程
      包含进程Pi的需求资源数量(也是最大需求资源数量,MAX)
      已分配给该进程的资源A(Allocation)
      还需要的资源数量N(Need=M-A)

    • Available为空闲资源数量,即资源池(注意:资源池的剩余资源数量+已分配给所有进程的资源数量=系统中的资源总量)

    假设资源P1申请资源,银行家算法先试探的分配给它(当然先要看看当前资源池中的资源数量够不够),若申请的资源数量小于等于Available,然后接着判断分配给P1后剩余的资源,能不能使进程队列的某个进程执行完毕,若没有进程可执行完毕,则系统处于不安全状态(即此时没有一个进程能够完成并释放资源,随时间推移,系统终将处于死锁状态)。

    若有进程可执行完毕,则假设回收已分配给它的资源(剩余资源数量增加),把这个进程标记为可完成,并继续判断队列中的其它进程,若所有进程都可执行完毕,则系统处于安全状态,并根据可完成进程的分配顺序生成安全序列(如{P0,P3,P2,P1}表示将申请后的剩余资源Work先分配给P0–>回收(Work+已分配给P0的A0=Work)–>分配给P3–>回收(Work+A3=Work)–>分配给P2–>······满足所有进程)。

    如此就可避免系统存在潜在死锁的风险。

    来个例子

    在银行家算法中,若出现下述资源分配情况:
    这里写图片描述

    注:题中共四种资源,P0的Allocation为(0,0,3,2)表示已分配给P0的第一种资源和第二种资源为0个,第三种资源3个,第四种资源2个。

    (1)该状态是否安全? (2)若进程P2提出请求Request(1,2,2,2)后,系统能否将资源分配给它?

    (1)利用安全性算法对上面的状态进行分析(见下表),找到了一个安全序列{P0,P3,P4,P1,P2},故系统是安全的。
    这里写图片描述

    (2)P2发出请求向量Request(1,2,2,2),系统按银行家算法进行检查:

    ①Request2(1,2,2,2)<=Need2(2,3,5,6)
    ②Request2(1,2,2,2)<=Available(1,6,2,2)
    ③系统先假定可为P2分配资源,并修改Available,Allocation2和Need2向量:
    Available=(0,4,0,0)
    Allocation2=(2,5,7,6)
    Need2=(1,1,3,4)
    此时再进行安全性检查,发现 Available=(0,4,0,0) 不能满足任何一个进程,所以判定系统进入不安全状态,即不能分配给P2相应的Request(1,2,2,2)。

    展开全文
  • 1,掌握银行家安全性算法和资源请求算法的原理 2,掌握银行家算法的实现方法 二,基本概念 在银行中,客户申请贷款的数量是有限的,每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量,在满足所有贷款...
  • 在避免死锁的方法中,所施加的限制条件较弱,有可能获得令人满意的系统性能。在该方法中把系统的状态...银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。它是最具有代表的避免死锁的算法。
  • 操作系统之银行家算法—详解流程及案例数据

    万次阅读 多人点赞 2018-12-03 21:46:08
    操作系统之进程调度——优先权法和轮转法...银行家是操作系统比较经典的算法之一,他比较好的防止死锁情况的出现,增加了系统的安全性.在编写银行家算法的过程中,对操作系统的银行家算法有了深入了解和心得。 ...

    操作系统之进程调度——优先权法和轮转法(附上样例讲解)
    操作系统之银行家算法—详解流程及案例数据
    操作系统之多线程编程—读者优先/写者优先详解
    操作系统之存储管理——FIFO算法和LRU算法
    操作系统之磁盘调度——SCAN实例讲解

    要求

    银行家是操作系统比较经典的算法之一,他比较好的防止死锁情况的出现,增加了系统的安全性.在编写银行家算法的过程中,对操作系统的银行家算法有了深入了解和心得。

    一、实验目的
    死锁会引起计算机工作僵死,因此操作系统中必须防止。本实验的目的在于让学生独立的使用高级语言编写和调试一个系统动态分配资源的简单模拟程序,了解死锁产生的条件和原因,并采用银行家算法有效地防止死锁的发生,以加深对课堂上所讲授的知识的理解。
    二、实验要求
    设计有n个进程共享m个系统资源的系统,进程可动态的申请和释放资源,系统按各进程的申请动态的分配资源。
    系统能显示各个进程申请和释放资源,以及系统动态分配资源的过程,便于用户观察和分析;
    三、数据结构
    1.可利用资源向量Available ,它是一个含有m个元素的数组,其中的每一个元素代表一类可利用的资源的数目,其初始值是系统中所配置的该类全部可用资源数目。其数值随该类资源的分配和回收而动态地改变。如果Available(j)=k,标是系统中现有Rj类资源k个。
    2.最大需求矩阵Max,这是一个n×m的矩阵,它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max(i,j)=k,表示进程i需要Rj类资源的最大数目为k。
    3.分配矩阵Allocation,这是一个n×m的矩阵,它定义了系统中的每类资源当前一分配到每一个进程的资源数。如果Allocation(i,j)=k,表示进程i当前已经分到Rj类资源的数目为k。Allocation i表示进程i的分配向量,有矩阵Allocation的第i行构成。
    4.需求矩阵Need,这是一个n×m的矩阵,用以表示每个进程还需要的各类资源的数目。如果Need(i,j)=k,表示进程i还需要Rj类资源k个,才能完成其任务。Need i表示进程i的需求向量,由矩阵Need的第i行构成。
    上述三个矩阵间存在关系:Need(i,j)=Max(i,j)-Allocation(i,j);
    四、安全性算法
    1.设置两个向量。
    Work:它表示系统可提供给进程继续运行的各类资源数目,它包含m个元素,开始执行安全性算法时,Work = Available。
    Finish:它表示系统是否有足够的资源分配给进程,使之运行完成,开始Finish(I)=false;当有足够资源分配给进程Pi时,令Finish(i)=true;
    2.从进程集合中找到一个能满足下述条件的进程。
    Finish(i)= = false;
    Need i ≤work;
    如找到则执行步骤3;否则,执行步骤4;
    3.当进程Pi获得资源后,可顺利执行直到完成,并释放出分配给它的资源,故应执行
    Work = work Allocation i
    Finish(i)=true;转向步骤2;
    4.若所有进程的Finish(i)都为true,则表示系统处于安全状态;否则,系统处于不安全状态。

    流程图:
    在这里插入图片描述
    个人觉得。总的来说,银行家算法就是一个模拟借钱。判断假如借钱是否安全然后考虑借不借的问题。
    先放代码,和数据再说分析:

    代码

    import java.util.ArrayDeque;
    import java.util.Queue;
    import java.util.Scanner;
    public class bank {
    	static Scanner sc=new Scanner(System.in);
    	static int n;
    	static int m;
    	static int available[];
    	static int max[][];//最大需求矩阵
    	static int allocation[][];//当前分配到每一个进程的
    	static int need[][];//需求矩阵
    	static boolean isrelesed[];//资源是否已经释放
    	public static void main(String[] args) {
    		// TODO 自动生成的方法存根		
    		System.out.println("请输入资源种类m:");
    	     m=sc.nextInt();//系统资源
    		initm(m);//初始相关
    		System.out.println("输入进程数量");
    		n=sc.nextInt();//进程数量
    		initn(n);//初始相关矩阵
    		//getstatus();//输出当前状态
    		while(true) {
    		applyresouse();//申请资源
    		}
    	}
    	static void applyresouse()//申请资源
    	{
    		getstatus();//输出状态
    	    int request[]=new int[m];//需求量 为了节省空间写成全部变量
    		System.out.println("输入你想申请资源的编号");
    		int index=sc.nextInt();
    		while(0>index||index>=n) {System.out.println("输入的编号不在编号范围之内,请重新输入");index=sc.nextInt();	}
    		while(isrelesed[index]) 
    		{System.out.println("改编号已经完成资源的释放,无法再请求资源,请重新输入");index=sc.nextInt();
    		while(0>index||index>=n) {System.out.println("输入的编号不在编号范围之内,请重新输入");index=sc.nextInt();	}}
    		System.out.println("请输入"+m+"个资源申请的个数(不申请的资源用0替代)");
            int team=0;
            while(team==0) {
    		for(int i=0;i<m;i++)
    		{
    			request[i]=sc.nextInt();
    			if(request[i]>available[i]) {team=1;}
    			if(request[i]>max[index][i]) {team=2;}
    		}
    		if(team==1) {System.out.println("您的请求量超出 了系统提供量,请重新输入");team=0;}//重新循环
    		else if(team==2) {System.out.println("您的请求量超出 了最大请求量max,请重新输入");team=0;}
    		else team=3;//退出循环用
            }
            //赋值成功后开始
           boolean isfinish= ifallocate(index,request);
           if(isfinish) {System.out.println("所有进程完成资源分配,分配结束");System.exit(0);}
    	}	
    	private static boolean ifallocate(int index,int[] request) {//假设分配
    		/*
    		 * 首先要将真的数组克隆,模拟已经给资源,然后判断这个资源是否安全
    		 */
    		int work[]=available.clone();
    		boolean finish[]=isrelesed.clone();//克隆初始状态
    		int need2[][]=new int[n][m];int allocate2[][]=new int[n][m];
    		for(int i=0;i<n;i++)
    		{
    			need2[i]=need[i].clone();
    			allocate2[i]=allocation[i].clone();
    		}
    		for(int i=0;i<m;i++)
    		{
    			if(need[index][i]<request[i])request[i]=need[index][i];//可以借这么多钱但是我不需要这么多钱an
    			work[i]-=request[i];//假设把钱借出去
    			allocate2[index][i]+=request[i];
    		}
    		//需要把need2重置一下
    		for(int i=0;i<m;i++)
    		{
    			need2[index][i]-=request[i];
    		}
    		boolean isallocate=issafety(work, finish, need2, allocate2);
    		if(!isallocate) {System.out.println("分配造成进程不安全,取消分配"); return false;}
    		else {
    			System.out.println("分配成功");
    			//分配成功就要分配资源
    			for(int i=0;i<m;i++)
    			{
    				available[i]-=request[i];
    				allocation[index][i]+=request[i];
    				need[index][i]-=request[i];
    				//System.out.println(request[i]);
    			}
    			if(!isrelesed[index])//判断改资源是否释放
    			{
    				boolean jud=false;
    				for(int j=0;j<m;j++)
    				{
    					if(need[index][j]!=0)jud=true;
    				}
    				if(!jud)//资源需要释放 
    				{
    					isrelesed[index]=true;
    					for(int j=0;j<m;j++)
    					{
    						available[j]+=allocation[index][j];
    					}
    				}
    			}		
    		}
    		boolean isfinished=true;
    		for(int i=0;i<n;i++)
    		{
    			for(int j=0;j<m;j++) {
    			if(need[i][j]!=0) {isfinished=false;return false;}}
    		}
    		return isfinished;
    	}
    	private static boolean issafety(int work[],boolean finish[],int need2[][],int allocate2[][])//模拟的需求和分配
    	{
    		//int work[]=available.clone();//不能直接等于复制。可以了解下对象克隆或者深浅复制。
    	    Queue<Integer>q1=new ArrayDeque<Integer>();//如果能完成的队列
    	    int time=0;
    	    while(true)
    	    {
    	    	boolean loop=true;
    	    	for(int i=0;i<n;i++)//n个进程模拟
    	    	{
    	    		time++;
    	    		if(!finish[i]) {
    	    		boolean b=false;//完成不了的
    	    		for(int j=0;j<m;j++)
    	    		{
    	    			if(work[j]<need2[i][j])
    	    			{
    	    				b=true;//完成不了的
    	    			}
    	    			if(b) {break;}
    	    		}
    	    		if(!b) {//可以完成的,释放资源
    	    			time=0;//重新计数
    	    			q1.add(i);
    	    			finish[i]=true;//已经完成
    	    			for(int j=0;j<m;j++)
    	    			{
    	    				work[j]+=allocate2[i][j];//
    	    				allocate2[i][j]+=need2[i][j];
    	    				need2[i][j]=0;
    	    			}
    	    			//打印
    	    			System.out.print("进程"+i+" max:");
    	    			for(int j=0;j<m;j++)
    	    			{
    	    			  System.out.print(max[i][j]+" ");
    	    			}
    	    			System.out.print("allocate2: ");
    	    			for(int j=0;j<m;j++)
    	    			{
    	    			  System.out.print(allocate2[i][j]+" ");
    	    			}
    	    			System.out.print("need2: ");
    	    			for(int j=0;j<m;j++)
    	    			{
    	    			  System.out.print(need2[i][j]+" ");
    	    			}
    	    			System.out.print("work: ");
    	    			for(int j=0;j<m;j++)
    	    			{
    	    			  System.out.print(work[j]+" ");
    	    			}
    	    			System.out.println();
    	  	    		}
    	    		}
    	    	}
    	    	boolean isfinish=false;
    	    	for(int i=0;i<n;i++) 
    	    	{
    	    		if(!finish[i]) {isfinish=true;break;}
    	    	}
    	    	if(!isfinish) {return true;}
    	    	if(time>n) {return false;}
    	    }
    		//return false;
    	}
    	static void initm(int m)
    	{
    		System.out.println("请输入"+m+"种资源的最大量");
    		available=new int[m];
    	    isrelesed=new boolean[m];
    		//request=new int[m];
    		for(int i=0;i<m;i++)//初始aviliable
    		{
    			available[i]=sc.nextInt();
    		}
    	}
    	static void initn(int n)
    	{
    		max=new int[n][m];
    		allocation=new int[n][m];
    		need=new int[n][m];
    		//finish=new boolean[n];
    		for(int i=0;i<n;i++)
    		{
    			System.out.println("进程"+i+"的最大需求为:(输入m个数)");
    			boolean jud=false;//判断输出是否有误
    			for(int j=0;j<m;j++)
    			{
    				max[i][j]=sc.nextInt();
    				if(max[i][j]>available[j]) {jud=true;}
    			}
    			if(jud) {System.out.println("最大需求输入有误,请重新赋值(m个数)");i--;}//i自减满足条件
    		}
    		System.out.println("n个线程m种资源最大需求赋值完成\n请输入当前进程已分配资源情况");//初始max
    		for(int i=0;i<n;i++)//初始allocate矩阵
    		{
    			System.out.println("进程"+i+"已分配资源为:(输入m个数)");
    			boolean jud=false;
    			for(int j=0;j<m;j++)
    			{
    				allocation[i][j]=sc.nextInt();
    				if(allocation[i][j]>max[i][j]){jud=true;}
    			}
    			if(jud) {System.out.println("输入有误,请重新输入");i--;}//输入有错误
    		}
    		System.out.println("allocate(当前已分配矩阵已经分配完毕)");
    	}
    	static void getstatus()//输出状态
    	{
    		for(int i=0;i<n;i++)
    		{
    			for(int j=0;j<m;j++)
    			{
    				need[i][j]=max[i][j]-allocation[i][j];
    			}
    		}
    		for(int i=0;i<n;i++)
    		{
    			System.out.print("进程"+i+"的状态为:max: ");
    			for(int j=0;j<m;j++) {System.out.print(" "+max[i][j]+" ");}
    			System.out.print("allocatem: ");
    			for(int j=0;j<m;j++) {System.out.print(" "+allocation[i][j]+" ");}
    			
    			System.out.print("need: ");
    			for(int j=0;j<m;j++) {System.out.print(" "+need[i][j]+" ");}
    			System.out.print("avaliable: ");
    			for(int j=0;j<m;j++) {System.out.print(" "+available[j]+" ");}
    			System.out.println();
    		}
    	}
    }
    
    

    分析

    A还—>借B—>B还—>C—这样可以到最后。但是很多情况下客户是分期借的,这就要考虑安全性问题,比如A借6,6,6还剩4,4,4那么这个银行做多最多只能借2,2,2给其他人,因为一旦借多了A也无法释放,那么就造成死锁。那么这种情况就不能够借钱。所以在借钱的时候需要一个模拟的过程。

    • 还有比较重要的是明白银行加算法各个矩阵的意义和作用非常的重要,我刚开始看银行家算法的时候因为对一些基础概念和数组矩阵的属性不够了解,茫然了很久,也走了很多的坑。那么就先介绍一下吧。
    • 对于全局变量,我的代码中有:
    • 在这里插入图片描述
    • 这些变量是在安全状态下的真实变量其中:
    • (1)n是线程的数量,m是资源的种类。
    • Available[]是当前还可以使用的资源。也就是银行家手中被借出去钱,手中还剩余各种钱的数量。只跟资源有关
    • Max[][]是最大需求矩阵,也可以理解为最终终态矩阵,因为这个max的状态就是客户想达到和满足的状态。也就是线程可以释放的状态。
    • Allocate[][]是已分配矩阵。就是客户已经借到的钱。也就是线程已经占有的资源量
    • Need[][]是还需要资源情况,由max和allcate决定。
    • Isrelese[]这个数组和线程有关和资源无关,它记录的就是线程是否达到终态,完成资源释放的情况,,一旦完成借钱就不需要借钱。
    • 3:最后在具体实现的过程中。由于需要模拟过程,还是会遇到挺多坎的,在理清思路之后。在代码上还是由挺多要注意的。
      第一:对象克隆(深浅拷贝),在模拟的过程中拥有初始化和真实数据一样的数组。但是如果直接赋值那么新对象指向的还是老数组的地址,会造成数据紊乱。那么对象克隆就一定要保证只赋值数据,不复制地址。
      第二:模拟数值的改变,无论在申请资源,还是释放资源的时候,模拟的数值都会改变。但是不过如果模拟成功,真实数组会增加多少。这个需要尤其注意,同时,如果发现数值和预期不符合可以打断点单步调试。

    附上我自己的流程图:
    初始化:
    在这里插入图片描述
    借钱:
    在这里插入图片描述
    ps:本人有点菜,这里面可能有挺多的是错误的。。如果有大佬发现请指正。

    如果对后端、爬虫、数据结构算法等感性趣欢迎关注我的个人公众号交流:bigsai

    展开全文
  • 银行家算法

    2019-11-18 22:12:27
    银行家算法实验 安全性算法 (1)设置两个向量: ① 工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目,它含有m个元素,在执行安全算法开始时,Work∶=Available; ② Finish: 它表示系统是否有足够...

    银行家算法实验

    安全性算法
    (1)设置两个向量:
    ① 工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目,它含有m个元素,在执行安全算法开始时,Work∶=Available;
    ② Finish: 它表示系统是否有足够的资源分配给进程,使之运行完成。开始时先做Finish[i]∶=false; 当有足够资源分配给进程时, 再令Finish[i]∶=true。
    (2)从进程集合中找到一个能满足下述条件的进程:
    ① Finish[i]=false;
    ② Need[i,j]≤Work[j]; 若找到, 执行步骤(3), 否则,执行步骤(4)。
    (3)当进程Pi获得资源后,可顺利执行,直至完成,并释放出分配给它的资源,故应执行:
    Work[j]∶=Work[i]+Allocation[i,j];
    Finish[i]∶=true;
    go to step 2;
    (4)如果所有进程的Finish[i]=true都满足, 则表示系统处于安全状态;否则,系统处于不安全状态。

    安全性算法流程图
    安全性流程图

    #include <iostream>
    #include <string>
    
    #define M 3   //资源的种类数
    #define N 5   //进程的个数
    
    using namespace std;
    
    void output(int iMax[N][M],int iAllocation[N][M],int iNeed[N][M],int iAvailable[M],char cName[N]);
    bool safety(int iAllocation[N][M],int iNeed[N][M],int iAvailable[M],char cName[N]);
    bool banker(int iAllocation[N][M],int iNeed[N][M],int iAvailable[M],char cName[N]);
    
    void main()
    {
    	int i,j;
    
    	//当前可用每类资源的资源数
    	int iAvailable[M]={3,3,2};
    
    	//系统中N个进程中的每一个进程对M类资源的最大需求
    	int iMax[N][M]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}};
    	
    	//iNeed[N][M]每一个进程尚需的各类资源数
    	//iAllocation[N][M]为系统中每一类资源当前已分配给每一进程的资源数
    	int iNeed[N][M],iAllocation[N][M]={{0,1,1},{2,0,0},{3,0,2},{2,1,1},{0,0,2}};
    	
    	//进程名
    	char cName[N]={'a','b','c','d','e'};
    
    	bool bExitFlag=true;   //退出标记
    	char ch;			   //接收选择是否继续提出申请时传进来的值
    	
    	bool bSafe;   //存放安全与否的标志
    	//计算iNeed[N][M]的值
    	for(i=0;i<N;i++)
    		for(j=0;j<M;j++)
    			iNeed[i][j]=iMax[i][j]-iAllocation[i][j];
    		
    	output(iMax,iAllocation,iNeed,iAvailable,cName);
    	bSafe=safety(iAllocation,iNeed,iAvailable,cName);
    	
    	//是否继续
    	while(bExitFlag)
    	{
    		cout<<"\n"<<"继续提出申请?\ny为是;n为否。\n";
    		cin>>ch;
    
    		switch(ch)
    		{  
    		    case 'y':
                    //cout<<"调用银行家算法";
    				bSafe=banker(iAllocation,iNeed,iAvailable,cName);
    				if (bSafe)   //安全,则输出变化后的数据
    					output(iMax,iAllocation,iNeed,iAvailable,cName);
    				break;
    	        case 'n': 
    			    cout<<"退出。\n";
    			    bExitFlag=false; 
    			    break;
    		    default: 
    		        cout<<"输入有误,请重新输入:\n";
    		}
    	}
    }
    

    输出操作

    void output(int iMax[N][M],int iAllocation[N][M],int iNeed[N][M],int iAvailable[M],char cName[N])
    {
    	int i,j;
    
    	cout<<"\n\t   Max  \tAllocation\t  Need  \t Available"<<endl;
    	cout<<"\tA   B   C\tA   B   C\tA   B   C\t A   B   C"<<endl;
    
    	for(i=0;i<N;i++)
    	{	
    		cout<<cName[i]<<"\t";
    		
    		for(j=0;j<M;j++)
    			cout<<iMax[i][j]<<"   ";
    		cout<<"\t";
    		
    		for(j=0;j<M;j++)
    			cout<<iAllocation[i][j]<<"   ";
    		cout<<"\t";
    
    		for(j=0;j<M;j++)
    			cout<<iNeed[i][j]<<"   ";
    		cout<<"\t";
    		cout<<" ";
    		
    		//Available只需要输出一次
    		if (i==0)
    			for(j=0;j<M;j++)
    				cout<<iAvailable[j]<<"   ";
    					
    		cout<<endl;
    	}	
    }
    

    安全性检查算法

    //安全性算法,进行安全性检查
    bool safety(int iAllocation[N][M],int iNeed[N][M],int iAvailable[M],char cName[N])
    {
    	//请同学们自己完成
      	int i,j,k;
    	char cSafeString[N];//存放安全序列中的进程名
    	int loc=0;//存放安全序列数组中的当前下标,即能顺利执行结束的进程个数
    	int iWork[M];
    	bool bFinish[N]={false};//定义并初始化bFinish
    	for(j=0;j<M;j++)//初始化iWork
    		iWork[j]=iAvailable[j];
    //最大需要查找N次即在每一次查找中一次只找到一个满足条件的进程
    		for(k=0;k<N;k++)
    		{
    			for(i=0;i<N;i++)//在一次的查找中,从头向尾查找
    			{//Finish[i]=false满足
    				if(!bFinish[i])
    				{//判断Need[i,j]<Work[j]是否满足
    					for(j=0;j<M;j++)
    					{//不满足Need[i,j]<Work[j]
    						if(iNeed[i][j]>iWork[j]) break;
    					}
    					if(j==M)
    					{//释放已分配资源
    						for(j=0;j<M;j++)
    							iWork[j]=iWork[j]+iAllocation[i][j];
    						bFinish[i]=true;
    						//安全序列
    						cSafeString[loc]=cName[i];
    						//以执行完成的进程个数
    						loc++;
    					}
    				}
    			}
    		}
    		if(loc==N)//安全,则输出安全序列
    		{
    			cout<<"\n当前系统的一个安全序列为:\n";
    			for(i=0;i<N;i++)
    				cout<<" "<<cSafeString[i];
    			cout<<","<<endl;
    			return true;
    		}
    		else//不安全
    			cout<<"\n系统不安全!";
    		return false;
    }
    //定位ch对应的进程名在数组中的位置
    //没找见返回-1,否则返回数组下标
    int locate(char cName[N],char ch)
    		{
    			int i;
    			for(i=0;i<N;i++)
    				if(cName[i]==ch)//找到
    					return i;
    				return -1;
    		}
    //提出申请,返回提出申请的进程名对应的下标
    int request(char cName[N],int iRequest[M])
    		{
    			int i,loc;
    			char ch;
    			bool bFlag=true;
    			//判断输入的进程名是否有误
    			while(bFlag)
    			{//输出进程名
    				for(i=0;i<N;i++)
    					cout<<cName[i]<<"\t";
    			cout<<"\n输入提出资源申请的进程名:\n";
    			cin>>ch;
    			//定位ch对应的进程名在进程名数组中的个位置
    			loc=locate(cName,ch);
    			if(loc==-1)//没找到,重新输入
    				cout<<"\n您输入的进程名有误!请重新输入";
    			else//找到,退出循环
    				bFlag=false;
    			}
    			cout<<"输入申请各类资源的数量:\n";
    				for(i=0;i<M;i++)
    					cin>>iRequest[i];
    				//返回提出申请的进程名对应的下标
    				return loc;
    
    }
    
    bool banker(int iAllocation[N][M],int iNeed[N][M],int iAvailable[M],char cName[N])
    {
    	//请同学们自己完成
    	int i,loc;
    	int iRequest[M];
    	bool bFlag=true;//是否满足条件
    	//提出申请,返回提出申请的进程名对应的下标
    	loc=request(cName,iRequest);
    	//判断是否满足request<=need
    	for(i=0;i<M;i++)
    	{
    		if(iRequest[i]>iNeed[loc][i])
    		{
    			cout<<"需求申请超出最大需求值"<<endl;
    			return false;
    		}
    	}
    	for(i=0;i<M;i++)
    	{
    		if(iRequest[i]>iAvailable[i])
    		{
    			cout<<"系统没有足够资源"<<cName[loc]<<"进程阻塞"<<endl;
    			return false;
    		}
    	}
    	//系统试探着把资源分配给进程,并修改下面数据结构中的数值
    	for(i=0;i<M;i++)
    	{
    		iAvailable[i]=iAvailable[i]-iRequest[i];
    		iNeed[loc][i]=iNeed[loc][i]-iRequest[i];
    		iAllocation[loc][i]=iAllocation[loc][i]+iRequest[i];
    	}
    	//调用安全性算法,判断当前是否安全,安全则真正分配
    	//否则恢复已修改的值
    	bFlag=safety(iAllocation,iNeed,iAvailable,cName);
    	//不安全,恢复已修改的值
    	if(!bFlag)
    	{
    		for(i=0;i<M;i++)
    		{
    		iAvailable[i]=iAvailable[i]-iRequest[i];
    		iNeed[loc][i]=iNeed[loc][i]-iRequest[i];
    		iAllocation[loc][i]=iAllocation[loc][i]+iRequest[i];
    		}
    		cout<<"进程"<<cName[loc]<<"阻塞"<<endl;
    	}
    	return bFlag;
    }
    

    参考资料:

    1、 汤子瀛编.《计算机操作系统》.北京:西安电子科技大出版社。
    2、 张尧学等编著.《计算机操作系统教程》.北京:清华大学出版社。

    大佬勿喷

    展开全文
  • 银行家算法前言一、什么是安全序列?二、怎么避免系统进入不安全状态(银行家算法)总结 前言 本文是OS的理解笔记,旨在理解。前面我们说到处理死锁的静态策略——预防死锁,现在我们考虑动态解决办法。 处理死锁...
  • 银行家算法是最具有代表的避免死锁的算法,原本运用于银行系统,以确保银行在发放现金贷款时,不会发生不能满足用户需求的情况。 为了实现银行家算法,每一个新进程在进入系统时,它必须申明在运行过程中,可能...
  • 进程管理之银行家算法

    千次阅读 2014-06-17 17:28:28
    银行家算法的核心机制: ...编程实现安全性算法函数,编制主函数,动态输入资源的占用情况,进程的资源申请,调用安全性函数,实现银行家算法; 测试:输入可分配和不可分配的请求,测试系统的正确性。
  • 操作系统实验之银行家算法的实验报告,内含设计银行家算法的核心数据结构、安全性检查算法,亲测可执行源码,测试数据截图,银行家算法流程图。
  • 操作系统银行家算法

    2020-02-29 14:44:45
    通过对银行家算法的模拟加深对避免死锁的理解,掌握银行家算法安全性测试算法; 二、实验内容: 系统中有m个同类资源,被n个进程共享,每个进程对资源的最大需求数分别为S1、S2、…、Sn,且Max(Si)<=m(i=1,...
  • 银行家算法的实现。 二、实验目的 银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源,但系统在进行资源分配之前,应先计算此次分配资源的安全性,若分配不会导致系统进入不安全...
  • 银行家算法主要用于判断内存分配是否安全合理。 1、是否合理 主要是看进程的请求是否小于所需值,以及是否小于现有资源量。这个部分比较简单,根据available,need这两个二维矩阵就可以直接判断。 2、是否安全 主要...
  • OS 避免死锁(银行家算法)

    千次阅读 2017-05-16 14:26:38
    虽然代码看起来有点长,实际上都是输入输出,核心代码就是银行家算法(bankerAlgorithm()),以及安全性算法(SecurityAlgorithm()) 懂得人都明白原理不难,只是按照我们老师要求的界面输入输出排版难受。
  • 银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源,但系 [银行家算法] 银行家算法 统在进行资源分配之前,应先计算此次分配资源的安全性,若分配不会导致系统进入不安全状态,...
  • 银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源,但系 统在进行资源分配之前,应先计算此次分配资源的安全性,若分配不会导致系统进入不安全状态,则分配,否则等待。为实现...
  • 用C#编写的银行家算法,可以通过安全性算法判断当前序列是否安全,如果安全,会给出一个安全序列。还可以进行资源的分配,若分配后处于安全状态,则予以分配,相应各进程参数发生变化并显示,否则不予分配。
  • 银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源,但系 银行家算法 统在进行资源分配之前,应先计算此次分配资源的安全性,若分配不会导致系统进入不安全状态,则分配,否则...
  • Banker's Algorithm 银行家算法 js 描述 进程运行前需要申明需要使用的最大资源数目,每次申请资源时操作系统将根据所有进程的申明搜索可能的执行路径(安全的进程执行顺序),若...编版 P113 "银行家算法之例" 节例
  • 银行家算法=-- - 1. 安全状态: 在某时刻系统中所有进程可以排列一个安全序列:{P1,P2,`````Pn},刚称此时,系统是安全的. 所谓安全序列{P1,P2,`````Pn}是指对于P2,都有它所需要剩余资源数量不大于系统掌握的剩余的...
  • 5.7.3 安全性算法 1) 设置两个向量:工作向量Work和Finish。算法开始时Work=Available;Finish表示系统是否有足够的资源分配给进程,使运行完成,开始时,令Finish[i]=False;如果有足够的资源分配给进程,则令...
  • Java实现银行家算法 文章目录Java实现银行家算法前言银行计算法概述主要思路1....银行家算法是避免死锁的一种重要方法,防止死锁的机构只能确保上述四个条件一不出现,则系统就不会发生死锁。通过这个算法可
  • 银行家算法是一种资源分配和避免死锁算法,它通过模拟所有资源的预定最大可能数量的分配来测试安全性,然后进行 “ s-state ” 检查来测试可能的活动,然后决定是否允许继续分配。 为什么要叫银行家算法捏? 银行...
  • 银行家算法——软考探究(四)

    千次阅读 热门讨论 2014-11-01 21:40:11
    著名的银行家算法,最早是由Dijkstra提出来的。它是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源,但系资源分配之前,应先计算此次分配资源的安全性,若分配不会导致系统进入不安全状态...

空空如也

空空如也

1 2 3 4
收藏数 70
精华内容 28
关键字:

银行家算法之安全性算法