天天看點
傳回

銀行家算法_作業系統

銀行家算法_作業系統

    • 一、實驗内容
    • 二、實驗準備
    • 三、實驗截圖
    • 三、程式源代碼 - -Java- -

一、實驗内容

編制模拟銀行間算法的程式，并以下面給出的例子驗證所編寫的程式的正确性。

例3-1 某系統有A、 B、 C、 D4類資源共5個程序(P0、 P1、 P2、 P3、 P4)共享, 1各程序對資源的需求和配置設定情況如表3 - 1所示。

銀行家算法_作業系統

現在系統中A、 B、 C、 D4類資源分别還剩1、5、2、 0個,請按銀行家算法回答下列問題:

① 現在系統是否處于安全狀态?

②如果現在程序P1提出需要(o、4、2、 0)個資源的請求,系統能否滿足它的

在該實驗中涉及銀行家算法和安全檢査性算法;- 下事:分 别對兩種算法作具體的介紹 。

二、實驗準備

1.銀行家算法

在避免死鎖的方法中, 如果所施加的限制條件較弱, 有可能獲得令人滿意的系統性能。在該方法中把系統的狀态分為安全狀态和不安全狀态,隻要能使系統始終都處于安全狀系度可以避免發生死鎖。

.

基本思想是配置設定資源之前,判斷系統是否是安全的;若安全,才配置設定。它是最具有代.生的避免死鎖的算法,具體算法如下表示:

假設程序 P提出請求 Request[i],則銀行家算法按如下步驟進行判斷。

Step1:如果Request[i]<=Need[i],則轉向 Step2;否則,出錯

Step2:如果Request[i]<=Available[i],則轉向 Step3;否則, 出錯。

Step3:系統試探配置設定相關資源,修改相關資料:

Available[i]=Available[i]-Request[i] , …

Available[i]=Available[i]+ Request[i] ,

Need[i]=Need[i]- Request[i] ,

SteP4:系統執行安全性檢査,如安全,則配置設定成立;否則試探性配置設定資源廢棄,系名次複原狀 程序進人等待态。

:’

根據以上的銀行家算法步驟, 可得出如圖所示3-1的銀行家算法程式流程圖 。

如圖3 -1銀行家算法程式流程圖  。
銀行家算法_作業系統

2.安全性檢查算法

安全性檢查算法主要是根據銀行家算法進行資源配置設定後,檢查資源配置設定後的系統狀态是否處于安全狀态之中。具體算法如下所示:

step1: 設定兩個工作向量 Work=Available, Finish=false;

step2 : 從程序集合中找到一個滿足下述條件的程序;

Finish=false,

Need<=Work,

如果能夠找到該程序, 則執行 Step3, 否則, 執行 Step4;

Step3:假設上述找到的程序獲得資源,可順利執行,直至完成,進而釋放資源。

Work=Work十A:L1ocation,

Finish=true,

Goto Step2;

Step4:如果所有程序的 Finish=true,則表示該系統安全;否則系統不安全。

根據以上安全性檢査算法的步驟, 可得出如圖3 - 2所示的安全性檢査算法程式流程圖 。

如圖3 - 2安全性檢査算法程式流程圖 。
銀行家算法_作業系統

三、實驗截圖

銀行家算法_作業系統

三、程式源代碼 - -Java- - 

package jincheng;

class Pid{
	static char[]resource;//資源類别
	static int[]available;//現在剩餘資源
	int[]request;//申請資源數量
	{
		request=new int [Pid.resource.length];
	}
	
	
	boolean finish;
	{
		finish=false;
	}
	int[]allocation;//已經占用資源
	int[]maxneed;//程序所需要最大資源
	int[]need;//程序現在需要資源
	{
		allocation=new int [Pid.resource.length];
		maxneed=new int [Pid.resource.length];
		need=new int [Pid.resource.length];
	}
	//初始化
	public Pid(int[] allocation, int[] maxneed) {
		this.allocation = allocation;
		this.maxneed = maxneed;
	}
	
	public int[] getRequest() {
		return request;
	}

	public void setRequest(int[] request) {
		this.request = request;
	}

	public int[] getAllocation() {
		return allocation;
	}
	
	public int[] getMaxneed() {
		return maxneed;
	}
	
	
	
	public void show() {
		for(int a:this.getAllocation()) {
			System.out.print(a +" ");
		}
	}

}

public class BankDemo426 {
	static int []x=new int[5];
	public static void main(String[] args) {
		//靜态 資源類别資源剩餘數量初始化
		char []res= {'A','B','C','D'};Pid.resource=res;
		int len=Pid.resource.length;
		int []ava= {1,5,2,0};Pid.available=ava;
		//占用資源allocation最大資源maxneed初始化
		int []a0= {0,0,1,2};int[]b0= {0,0,1,2};Pid p0=new Pid(a0,b0);
		int []a1= {1,0,0,0};int[]b1= {1,7,5,0};Pid p1=new Pid(a1,b1);
		int []a2= {1,3,5,4};int[]b2= {2,3,5,6};Pid p2=new Pid(a2,b2);
		int []a3= {0,6,3,2};int[]b3= {0,6,5,2};Pid p3=new Pid(a3,b3);
		int []a4= {0,0,1,4};int[]b4= {0,6,5,6};Pid p4=new Pid(a4,b4);
		//申請資源request初始化
		int []c1= {0,4,2,0};p1.setRequest(c1);
		Pid []p=new Pid[5];
		//程序加載p
		p[0]=p0;p[1]=p1;p[2]=p2;p[3]=p3;p[4]=p4;
		//need ins
		for (Pid pi:p) {
			for(int j=0;j<len;j++)
				pi.need[j]=pi.maxneed[j]-pi.allocation[j];
		}
		if(bankFun(p,1)) {
			System.out.println("--配置設定成立");
			System.out.print("安全順序:");
			for(int px:x) {
				System.out.print("p"+px+" ");
			}
		}			
		else
			System.out.println("--配置設定失敗");		
	}
	//銀行家算法
	public static boolean bankFun(Pid []p,int n) {
		int len=Pid.resource.length;
		//step1 Request[i]<=Need[i]
		for (int i = 0; i < len; i++) {
			if(p[n].request[i]>p[n].need[i]) {
				System.out.println("--Request[i]<=Need[i] error");
				return false;
			}
		}
		System.out.println("1.Request[i]<=Need[i]");
		//step2 Request[i]<=Available[i]
		for (int i = 0; i < len; i++) {
			if(p[n].request[i]>Pid.available[i]) {
				System.out.println("--Request[i]<=Available[i] error");
				return false;
			}
		}
		System.out.println("2.Request[i]<=Available[i]");
		//step3 系統試探配置設定相關資源
		int []memava=Pid.available;
		int []memall=p[n].allocation;
		int []memnee=p[n].need;
		for(int i=0;i<len;i++) {
			Pid.available[i]-=p[n].request[i];
			p[n].allocation[i]+=p[n].request[i];
			p[n].need[i]-=p[n].request[i];
		}
		System.out.println("3.系統試探配置設定相關資源");
		//setp4 系統執行安全性檢査
		System.out.println("4.系統執行安全性檢査");
		if(safeFun(p)) {
			return true;
		}
		else {
			System.out.println("--失敗 已恢複");
			Pid.available=memava;
			p[n].allocation=memall;
			p[n].need=memnee;
			return false;
		}
	}
	public static boolean safeFun(Pid []p) {
		int len=Pid.resource.length;
		/*資料  檢測
		for(Pid pi:p) {
			for (int i = 0; i < pi.need.length; i++) {
				System.out.print(pi.need[i]);
			}	
			System.out.println();
		}		
		for(Pid pi:p) {
			for (int i = 0; i < pi.allocation.length; i++) {
				System.out.print(pi.allocation[i]);
			}	
			System.out.println();
		}	
		*/
		//setp1 Work=Available, Finish=false;
		int []work=Pid.available;	
		
		System.out.println("a.Work=Available, Finish=false;");
		//setp2 Finish=false;Need<=Work;
		for(int i=0,k=0;i<p.length;i++) {
			if(!p[i].finish&&cheekNK(p[i],work)) {
				System.out.println("b.可以執行p"+i);
				//step3 順利執行,直至完成,進而釋放資源
				for(int j=0;j<len;j++) {
					work[j]+=p[i].allocation[j];
				}
				p[i].finish=true;
				System.out.println("c.p"+i+"順利執行,釋放資源");
				x[k]=i;k++;
				i=0;
			}
		}
		//step4  所有程序的 Finish=true
		System.out.println("d.程序安全檢測");
		for(Pid pi:p) {
			if(!pi.finish) {
				System.out.println("--有程序不能執行");
				System.out.println("--不安全");
				return false;
			}	
		}
		System.out.println("--所有程序的 Finish=true");
		System.out.println("--安全");
		return true;
	}
	public static boolean cheekNK(Pid pi,int []work) {
		for(int i=0;i<pi.need.length;i++) {
			if(pi.need[i]>work[i]) {				
				return false;
			}				
		}
		return true;
	}
}
銀行家算法 作業系統 java 算法
上一篇: java 銀行家算法_作業系統——銀行家算法（java實作）
下一篇: 作業系統（七）：銀行家算法

繼續閱讀