銀行家演算法程序
Ⅰ 銀行家演算法
什麼是銀行家演算法：
銀行家演算法是一種最有代表性的避免死鎖的演算法。在避免死鎖方法中允許進程動態地申請資源，但系統在進行資源分配之前，應先計算此次分配資源的安全性，若分配不會導致系統進入不安全狀態，則分配，否則等待。為實現銀行家演算法，系統必須設置若干數據結構。
要解釋銀行家演算法，必須先解釋操作系統安全狀態和不安全狀態。
安全序列是指一個進程序列{P1，…，Pn}是安全的，如果對於每一個進程Pi(1≤i≤n），它以後尚需要的資源量不超過系統當前剩餘資源量與所有進程Pj (j < i )當前佔有資源量之和。
安全狀態
如果存在一個由系統中所有進程構成的安全序列P1，…，Pn，則系統處於安全狀態。安全狀態一定是沒有死鎖發生。
不安全狀態
不存在一個安全序列。不安全狀態不一定導致死鎖。
原理：
我們可以把操作系統看作是銀行家，操作系統管理的資源相當於銀行家管理的資金，進程向操作系統請求分配資源相當於用戶向銀行家貸款。
為保證資金的安全,銀行家規定:
(1) 當一個顧客對資金的最大需求量不超過銀行家現有的資金時就可接納該顧客;
(2) 顧客可以分歧貸款,但貸款的總數不能超過最大需求量;
(3) 當銀行家現有的資金不能滿足顧客尚需的貸款數額時,對顧客的貸款可推遲支付,但總能使顧客在有限的時間里得到貸款;
(4) 當顧客得到所需的全部資金後,一定能在有限的時間里歸還所有的資金.
操作系統按照銀行家制定的規則為進程分配資源，當進程首次申請資源時，要測試該進程對資源的最大需求量，如果系統現存的資源可以滿足它的最大需求量則按當前的申請量分配資源，否則就推遲分配。當進程在執行中繼續申請資源時，先測試該進程已佔用的資源數與本次申請的資源數之和是否超過了該進程對資源的最大需求量。若超過則拒絕分配資源，若沒有超過則再測試系統現存的資源能否滿足該進程尚需的最大資源量，若能滿足則按當前的申請量分配資源，否則也要推遲分配。
程序舉例：
已知進程{P0,P1,P2,P3,P4}，有三類系統資源A、B、C的數量分別為10、5、7，在T0時刻的資源
（1）若進程P1請求資源，發出請求向量Request1（1，0，2），編寫程序用銀行家演算法判斷系統能否將資源分配給它；
（2）若進程P2提出請求Request(0，1，0)，用銀行家演算法程序驗證系統能否將資源分配給它。
程序代碼：
P1進程提出的請求，可以分配。
P2進程不能分配，因為請求的B類資源超過了它的最大值。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXSIZE 50
void main()
{
unsigned int Available[MAXSIZE]; //可利用資源向量
unsigned int Max[MAXSIZE][MAXSIZE]; //最大需求矩陣
unsigned int Allocation[MAXSIZE][MAXSIZE]; //已分配矩陣
unsigned int Need[MAXSIZE][MAXSIZE]; //需求矩陣
unsigned int Request[MAXSIZE]; //請求向量
unsigned int Work[MAXSIZE]; //工作向量
bool Finish[MAXSIZE]; //是否有足夠資源分配給進程,使之運行完成
unsigned int SafeSequence[MAXSIZE]; //安全序列
int i,j;
int p; //請求資源的進程的下標
int temp = 0; //安全序列下標
int total = 0;
int N;
int M;
printf("請輸入進程數N=");
scanf("%d",&N);
printf("請輸入資源種類數M=");
scanf("%d",&M);
//用戶輸入數據,初始化Available數組
printf("初始化可用資源數組:\n");
for(i=0; i<M; i++)
{
printf("\t%c類資源:",65+i);
scanf("%d",&Available[i]);
}
//用戶輸入數據,初始化Max數組
printf("初始化最大需求數組:\n");
for(i=0; i<N; i++)
{
printf("\tP%d進程最大需要\n",i);
for(j=0; j<M; j++)
{
printf("\t\t%c類資源:",65+j);
scanf("%d",&Max[i][j]);
}
}
//用戶輸入數據,初始化Allocation數組
printf("初始化已分配資源數組:\n");
for(i=0; i<N; i++)
{
printf("\tP%d進程已分配\n",i);
for(j=0; j<M; j++)
{
printf("\t\t%c類資源:",65+j);
scanf("%d",&Allocation[i][j]);
}
}
//初始化Need數組
for(i=0; i<N; i++)
for(j=0; j<M; j++)
{
Need[i][j] = Max[i][j] - Allocation[i][j];
}
//進程發出資源請求後檢查
do
{
printf("資源請求:\n");
printf("\t輸入請求資源的進程下標:");
scanf("%d",&p);
printf("\t進程P%d請求\n",p);
//初始化請求向量
for(i=0; i<M; i++)
{
printf("\t\t%c類資源:",65+i);
scanf("%d",&Request[i]);
}
for(i=0; i<M; i++) //檢查Request <= Need ?
if(Request[i] > Need[p][i])
{
printf("\t請求的%c類資源數超過它所宣布的最大值!\n",65+i);
break;
}
if(i == M) //通過上層檢查,繼續檢查Request <= Available ?
{
for(i=0; i<M; i++)
if(Request[i] > Available[i])
{
printf("\t尚無足夠%c類資源,P%d須等待!\n",65+i,p);
break;
}
}
if(i == M) //嘗試分配
{
for(i=0; i<M; i++)
{
Available[i] -= Request[i];
Allocation[p][i] += Request[i];
Need[p][i] -= Request[i];
}
}
}while(i<M);
//初始化Work,Finish向量
for(i=0; i<M; i++)
{
Work[i] = Available[i];
}
for(i=0; i<N; i++)
{
Finish[i] = false;
}
//安全性演算法
do
{
total = temp;
for(i=0; i<N; i++)
{
if(Finish[i] == false)
{
for(j=0; j<M; j++)
if(Need[i][j] > Work[j])
{
break;
}
if(j == M) //各類資源都滿足Need <= Work
{
for(j=0; j<M; j++)
{
Work[j] += Allocation[i][j]; //釋放資源
}
Finish[i] = true;
SafeSequence[temp++] = i; //加入安全序列
}
}
}
}while(total != temp); //所有進程檢查一遍之後，如果安全序列有變化，則進行下一輪
//否則說明所有的Finish都為true,或者因沒有安全序列退出循環
if(temp == N)
{
printf("安全序列:");
for(temp=0; temp<N; temp++)
{
printf("P%d ",SafeSequence[temp]);
}
}
else
{
printf("系統處於不安全狀態!不能分配!\n");
}
getchar();
getchar();
}
這個程序還行，輸入有點麻煩，我自己編寫的是用文件輸入系統描述信息的，但是缺少說明，怕你搞不明白。希望對你有所幫助！
Ⅱ 鈥滈摱琛屽剁畻娉曠▼搴忥紝鍏堟潵鍏堟湇鍔¤皟搴︾畻娉曪紝瀛樺偍綆＄悊鐨勬ā鎷熷疄鐜扳
-
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<iomanip>
#include<conio.h>
using namespace std;
const int MAX_P=20;
const int MAXA=10; //瀹氫箟A綾昏祫婧愮殑鏁伴噺
const int MAXB=5;
const int MAXC=7;
typedef struct node{
int a;
int b;
int c;
int remain_a;
int remain_b;
int remain_c;
}bank;
typedef struct node1{
char name[20];
int a;
int b;
int c;
int need_a;
int need_b;
int need_c;
}process;
bank banker;
process processes[MAX_P];
int quantity;
//鍒濆嬪寲鍑芥暟
void initial()
{
int i;
banker.a=MAXA;
banker.b=MAXB;
banker.c=MAXC;
banker.remain_a=MAXA;
banker.remain_b=MAXB;
banker.remain_c=MAXC;
for(i=0;i<MAX_P;i++){
strcpy(processes[i].name,"");
processes[i].a=0;
processes[i].b=0;
processes[i].c=0;
processes[i].need_a=0;
processes[i].need_b=0;
processes[i].need_c=0;
}
}
//鏂板姞浣滀笟
void add()
{
char name[20];
int flag=0;
int t;
int need_a,need_b,need_c;
int i;
cout<<endl;
cout<<"鏂板姞浣滀笟"<<endl;
cout<<"鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣"<<endl;
cout<<"璇瘋緭鍏ユ柊鍔犱綔涓氬悕:";
cin>>name;
for(i=0;i<quantity;i++){
if(!strcmp(processes[i].name,name)){
flag=1;
break;
}
}
if(flag){
cout<<"閿欒,浣滀笟宸插瓨鍦"<<endl;
}
else{
cout<<"鏈浣滀笟鎵闇A綾昏祫婧:";
cin>>need_a;
cout<<"鏈浣滀笟鎵闇B綾昏祫婧:";
cin>>need_b;
cout<<"鏈浣滀笟鎵闇C綾昏祫婧:";
cin>>need_c;
t=1;
cout<<need_a<<banker.remain_a;
if(need_a>banker.remain_a){
cout<<"閿欒,鎵闇A綾昏祫婧愬ぇ浜庨摱琛屽舵墍鍓〢綾昏祫婧"<<endl;
t=0;
}
if(need_b>banker.remain_b){
cout<<"閿欒,鎵闇B綾昏祫婧愬ぇ浜庨摱琛屽舵墍鍓〣綾昏祫婧"<<endl;
t=0;
}
if(need_c>banker.remain_c){
cout<<"閿欒,鎵闇C綾昏祫婧愬ぇ浜庨摱琛屽舵墍鍓〤綾昏祫婧"<<endl;
t=0;
}
if(t){
strcpy(processes[quantity].name,name);
processes[quantity].need_a=need_a;
processes[quantity].need_b=need_b;
processes[quantity].need_c=need_c;
quantity++;
cout<<"鏂板姞浣滀笟鎴愬姛"<<endl;
}
else{
cout<<"鏂板姞浣滀笟澶辮觸"<<endl;
}
}
}
//涓轟綔涓氱敵璇瘋祫婧
void bid()
{
char name[20];
int i,p;
int a,b,c;
int flag;
cout<<endl<<"涓轟綔涓氱敵璇瘋祫婧"<<endl;
cout<<"鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣"<<endl;
cout<<"瑕佺敵璇瘋祫婧愮殑浣滀笟鍚:";
cin>>name;
p=-1;
for(i=0;i<quantity;i++){
if(!strcmp(processes[i].name,name)){
p=i;
break;
}
}
if(p!=-1){
cout<<"璇ヤ綔涓氳佺敵璇稟綾昏祫婧愭暟閲:";
cin>>a;
cout<<"璇ヤ綔涓氳佺敵璇稡綾昏祫婧愭暟閲:";
cin>>b;
cout<<"璇ヤ綔涓氳佺敵璇稢綾昏祫婧愭暟閲:";
cin>>c;
flag=1;
if((a>banker.remain_a)||(a>processes[p].need_a-processes[p].a)){
cout<<"閿欒,鎵鐢寵稟綾昏祫婧愬ぇ浜庨摱琛屽舵墍鍓〢綾昏祫婧愭垨璇ヨ繘紼嬭繕闇鏁伴噺"<<endl;
flag=0;
}
if((b>banker.remain_b)||(b>processes[p].need_b-processes[p].b)){
cout<<"閿欒,鎵鐢寵稡綾昏祫婧愬ぇ浜庨摱琛屽舵墍鍓〣綾昏祫婧愭垨璇ヨ繘紼嬭繕闇鏁伴噺"<<endl;
flag=0;
}
if((c>banker.remain_c)||(c>processes[p].need_c-processes[p].c)){
cout<<"閿欒,鎵鐢寵稢綾昏祫婧愬ぇ浜庨摱琛屽舵墍鍓〤綾昏祫婧愭垨璇ヨ繘紼嬭繕闇鏁伴噺"<<endl;
flag=0;
}
if(flag){
banker.remain_a-=a;
banker.remain_b-=b;
banker.remain_c-=c;
processes[p].a+=a;
processes[p].b+=b;
processes[p].c+=c;
cout<<"涓轟綔涓氱敵璇瘋祫婧愭垚鍔"<<endl;
}
else{
cout<<"涓轟綔涓氱敵璇瘋祫婧愬け璐"<<endl;
}
}
else{
cout<<"璇ヤ綔涓氫笉瀛樺湪"<<endl;
}
}
//鎾ゆ秷浣滀笟
void finished()
{
char name[20];
int i,p;
cout<<endl<<"鎾ゆ秷浣滀笟"<<endl;
cout<<"鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣"<<endl;
cout<<"瑕佹挙娑堜綔涓氬悕:";
cin>>name;
p=-1;
for(i=0;i<quantity;i++){
if(!strcmp(processes[i].name,name)){
p=i;
break;
}
}
if(p!=-1){
banker.remain_a+=processes[p].a;
banker.remain_b+=processes[p].b;
banker.remain_c+=processes[p].c;
for(i=p;i<quantity-1;i++){
processes[i]=processes[i+1];
}
strcpy(processes[quantity-1].name,"");
processes[quantity-1].a=0;
processes[quantity-1].b=0;
processes[quantity-1].c=0;
processes[quantity-1].need_a=0;
processes[quantity-1].need_b=0;
processes[quantity-1].need_c=0;
quantity--;
cout<<"鎾ゆ秷浣滀笟鎴愬姛"<<endl;
}
else{
cout<<"鎾ゆ秷浣滀笟澶辮觸"<<endl;
}
}
//鏌ョ湅璧勬簮鎯呭喌
void view()
{
int i;
cout<<endl<<"鏌ョ湅璧勬簮鎯呭喌"<<endl;
cout<<"鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣"<<endl;
cout<<"閾惰屽舵墍鍓╄祫婧(鍓╀綑璧勬簮/鎬誨叡璧勬簮)"<<endl;
cout<<"A綾:"<<banker.remain_a<<"/"<<banker.a;
cout<<" B綾:"<<banker.remain_b<<"/"<<banker.b;
cout<<" C綾:"<<banker.remain_c<<"/"<<banker.c;
cout<<endl<<endl<<"浣滀笟鍗犵敤鎯呭喌(宸插崰鐢ㄨ祫婧/鎵闇璧勬簮)"<<endl<<endl;
if(quantity>0){
for(i=0;i<quantity;i++){
cout<<"浣滀笟鍚:"<<processes[i].name<<endl;
cout<<"A綾:"<<processes[i].a<<"/"<<processes[i].need_a;
cout<<" B綾:"<<processes[i].b<<"/"<<processes[i].need_b;
cout<<" C綾:"<<processes[i].c<<"/"<<processes[i].need_c;
cout<<endl;
}
}
else{
cout<<"褰撳墠娌℃湁浣滀笟"<<endl;
}
}
//鏄劇ず鐗堟潈淇℃伅鍑芥暟
void version()
{
cout<<endl<<endl;
cout<<" 鈹忊攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹"<<endl;
cout<<" 鈹 閾 琛 瀹 綆 娉 鈹"<<endl;
cout<<" 鈹犫斺斺斺斺斺斺斺斺斺斺斺斺斺斺斺斺斺斺斺斺斺斺斺敤"<<endl;
cout<<" 鈹 (c)All Right Reserved Neo 鈹"<<endl;
cout<<" 鈹 [email protected] 鈹"<<endl;
cout<<" 鈹 version 2004 build 1122 鈹"<<endl;
cout<<" 鈹椻攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹"<<endl;
cout<<endl<<endl;
}
int main(void)
{
int chioce;
int flag=1;
initial();
version();
while(flag){
cout<<"鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣鈹佲攣"<<endl;
cout<<"1.鏂板姞浣滀笟 2.涓轟綔涓氱敵璇瘋祫婧 3.鎾ゆ秷浣滀笟"<<endl;
cout<<"4.鏌ョ湅璧勬簮鎯呭喌 0.閫鍑虹郴緇"<<endl;
cout<<"璇烽夋嫨:";
cin>>chioce;
switch(chioce){
case 1:
add();
break;
case 2:
bid();
break;
case 3:
finished();
break;
case 4:
view();
break;
case 0:
flag=0;
break;
default:
cout<<"閫夋嫨閿欒"<<endl<<endl;
}
}
return 0;
}
Ⅲ 銀行家演算法是如何實現的
銀行家演算法是從當前狀態出發，逐個按安全序列檢查各客戶中誰能完成其工作，然後假定其完成工作且歸還全部貸款，再進而檢查下一個能完成工作的客戶。如果所有客戶都能完成工作，則找到一個安全序列，銀行家才是安全的。
�7�4 與預防死鎖的幾種方法相比較，限制條件少，資源利用程度提高了。
�7�4 缺點：該演算法要求客戶數保持固定不變，這在多道程序系統中是難以做到的；該演算法保證所有客戶在有限的時間內得到滿足，但實時客戶要求快速響應，所以要考慮這個因素；由於要尋找一個安全序列，實際上增加了系統的開銷.
Banker algorithm 最重要的一點是：保證操作系統的安全狀態！這也是操作系統判斷是否分配給一個進程資源的標准！那什麼是安全狀態？舉個小例子，進程 P 需要申請 8 個資源（假設都是一樣的），已經申請了 5 個資源，還差 3 個資源。若這個時候操作系統還剩下 2 個資源。很顯然，這個時候操作系統無論如何都不能再分配資源給進程 P 了，因為即使全部給了他也不夠，還很可能會造成死鎖。若這個時候操作系統還有 3 個資源，無論 P 這一次申請幾個資源，操作系統都可以滿足他，因為操作系統可以保證 P 不死鎖，只要他不把剩餘的資源分配給別人，進程 P 就一定能順利完成任務。 為什麼銀行家演算法是可行的呢？這里需要嚴格的證明一下。不管任何時候，操作系統分配資源的時候都可以保證當前接受資源的進程不會陷入死鎖，因為操作系統總是可以滿足該進程需要的資源的。假設有 n 個進程 {p1, p2, p3, … pn} ，最後一個分配到資源的是 pi ， pi 還需要 mi 個資源，假設此時操作系統還有 m 個資源剩餘。那麼很顯然 m>=mi ！而且如果之後操作系統又把資源分配給其他進程了，假設是 pj ， pj 還需要 mj 個資源，同理可知 m>=mj ！也就是說在所有的進程中，還需要的資源數總是有小於 m 的！這樣就可以保證資源數永遠不會為 0 ，即使可能暫時性為 0 。另外，還需要保證資源數不會減少！而且，所有已經分配到資源的進程總有一天會歸還它所擁有的資源！根據操作系統再分配的時候的狀態即可判定。
Ⅳ 求：用java語言編寫的銀行家演算法的源代碼
import java.util.*;
class ThreadTest {
static int type = 4, num = 10; //定義資源數目和線程數目
static int[] resource = new int[type]; //系統資源總數
//static int[] Resource = new int[type]; //副本
static Random rand = new Random();
static Bank[] bank = new Bank[num]; //線程組
Bank temp = new Bank();
public void init() {
//初始化組中每個線程，隨機填充系統資源總數
for(int i = 0; i < type; i++)
resource[i] = rand.nextInt(10) + 80;
System.out.print("Resource:");
for(int i = 0; i < type; i++)
System.out.print(" " + resource[i]);
System.out.println("");
for(int i = 0; i < bank.length; i++)
bank[i] = new Bank("#" + i);
}
public ThreadTest4() {
init();
}
class Bank extends Thread {
//銀行家演算法避免死鎖
public int[]
max = new int[type], //總共需求量
need = new int[type], //尚需資源量
allocation = new int[type]; //已分配量
private int[]
request = new int[type], //申請資源量
Resource = new int[type]; //資源副本
private boolean isFinish = false; //線程是否完成
int[][] table = new int[bank.length][type*4]; //二維資源分配表
private void init() {
// 隨機填充總共、尚需、已分配量
synchronized(resource) {
for(int i = 0; i < type; i++) {
max[i] = rand.nextInt(5) + 10;
need[i] = rand.nextInt(10);
allocation[i] = max[i] - need[i];
resource[i] -= allocation[i]; //從系統資源中減去已分配的
}
printer();
for(int i = 0; i < type; i++) {
if(resource[i] < 0) {
//若出現已分配量超出系統資源總數的錯誤則退出
System.out.println("The summation of Threads' allocations is out of range!");
System.exit(1);
}
}
}
}
public Bank(String s) {
setName(s);
init();
start();
}
public Bank() {
//none
}
public void run() {
try {
sleep(rand.nextInt(2000));
}
catch(InterruptedException e) {
throw new RuntimeException(e);
}
while(true) {
//程序沒有完成時一直不斷申請資源
if(askFor() == false) {
try {
sleep(1000);
}
catch(InterruptedException e) {
throw new RuntimeException(e);
}
}
else
tryRequest();
if(noNeed() == true)
break;
}
//休眠一段時間模擬程序運行
try {
sleep(1000);
}
catch(InterruptedException e) {
throw new RuntimeException(e);
}
System.out.println(getName() + " finish!");
synchronized(resource) {
//運行結束釋放佔有資源
for(int i = 0; i < type; i++) {
resource[i] += allocation[i];
need[i] = allocation[i] = max[i] = 0;
}
}
}
private void printer() {
//列印當前資源信息
System.out.print(getName() + " Max:");
for(int i = 0; i < type; i++)
System.out.print(" " + max[i]);
System.out.print(" Allocation:");
for(int i = 0; i < type; i++)
System.out.print(" " + allocation[i]);
System.out.print(" Need:");
for(int i = 0; i < type; i++)
System.out.print(" " + need[i]);
System.out.print(" Available:");
for(int i = 0; i < type; i++)
System.out.print(" " + resource[i]);
System.out.println("");
}
private boolean askFor() {
//隨機產生申請資源量並檢測是否超標
boolean canAsk = false;
for(int i = 0; i < type; i++) {
request[i] = rand.nextInt(20);
//防止申請量超過所需量
if(request[i] > need[i])
request[i] = need[i];
}
for(int i = 0; i < type; i++) //防止隨機申請資源全為0
if(request[i] > 0)
canAsk = true;
synchronized(resource) {
//鎖住可供資源檢查是否超標
for(int i = 0; i < type; i++) {
if(request[i] > resource[i])
//如果申請資源超過可供資源則等待一段時間後重新申請
return false;
}
}
return canAsk;
}
private void tryRequest() {
//創建副本嘗試分配請求
synchronized(resource) {
for(int i = 0; i < type; i++)
//依然要防止請求量超出范圍
if(request[i] > resource[i])
return;
for(int i = 0; i < type; i++) {
//復制資源量並減去需求量到一個副本上
Resource[i] = resource[i];
Resource[i] -= request[i];
}
System.out.print(getName() + " ask for:");
for(int i = 0; i < type; i++)
System.out.print(" " + request[i]);
System.out.println("");
if(checkSafe() == true) {
//如果檢查安全則將副本值賦給資源量並修改佔有量和需求量
for(int i = 0; i < type; i++) {
resource[i] = Resource[i];
allocation[i] += request[i];
need[i] -= request[i];
}
System.out.println(getName() + " request succeed!");
}
else
System.out.println(getName() + " request fail!");
}
}
private boolean checkSafe() {
//銀行家演算法檢查安全性
synchronized(bank) {
//將線程資源信息放入二維資源分配表檢查安全性，0~type可用資源／type~type*2所需資源／type*2~type*3佔有資源／type*3~-1可用+佔用資源
for(int i = 0; i < bank.length; i++) {
for(int j = type; j < type*2; j++) {
table[i][j] = bank[i].need[j%type];
}
for(int j = type*2; j < type*3; j++) {
table[i][j] = bank[i].allocation[j%type];
}
}
//冒泡排序按需求資源從小到大排
for(int i = 0; i < bank.length; i++) {
for(int j = i; j < bank.length-1; j++) {
sort(j, 4);
}
}
//進行此時刻的安全性檢查
for(int i = 0; i < type; i++) {
table[0][i] = Resource[i];
table[0][i+type*3] = table[0][i] + table[0][i+type*2];
if(table[0][i+type*3] < table[1][i+type])
return false;
}
for(int j = 1; j < bank.length-1; j++) {
for(int k = 0; k < type; k++) {
table[j][k] = table[j-1][k+type*3];
table[j][k+type*3] = table[j][k] + table[j][k+type*2];
if(table[j][k+type*3] < table[j+1][k+type])
return false;
}
}
}
return true;
}
private void sort(int j, int k) {
//遞歸冒泡排序
int tempNum;
if(table[j][k] > table[j+1][k]) {
for(int i = type; i < type*2; i++) {
tempNum = table[j][i];
table[j][i] = table[j+1][i];
table[j+1][i] = tempNum;
}
/*temp = bank[j];
bank[j] = bank[j+1];
bank[j+1] = temp;*/
}
else if(table[j][k] == table[j+1][k] && k < type*2) //此資源量相同時遞歸下一個資源量排序並且防止超出范圍
sort(j, k+1);
}
private boolean noNeed() {
//是否還需要資源
boolean finish = true;
for(int i = 0; i < type; i++) {
if(need[i] != 0) {
finish = false;
break;
}
}
return finish;
}
}
public static void main(String[] args) {
ThreadTest t = new ThreadTest();
//後台線程，設定程序運行多長時間後自動結束
new Timeout(30000, "---Stop!!!---");
}
}
Ⅳ 銀行家演算法C++描述
#include <iostream>
#include <string>
#define M 3 //資源的種類數
#define N 5 //進程的個數
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]);
int 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;
}
}
//安全性演算法，進行安全性檢查；安全返回true，並且輸出安全序列，不安全返回false，並輸出不安全的提示；
bool safety(int iAllocation[N][M],int iNeed[N][M],int iAvailable[M],char cName[N])
{
}
//定位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])
{
}
這個是c++的 我的報告