模擬銀行家演算法

課程設計任務書

模擬銀行家演算法

設計題目:程式設計序模擬銀行家演算法

設計目的

1、銀行家演算法是避免死鎖的一種重要方法,本實驗要求用高階語言編寫和除錯一個簡單的銀行家演算法程式。加深瞭解有關資源申請、避免死鎖等概念,並體會和了解死鎖和避免死鎖的具體實施方法。

2、提高學生的程式設計能力、 提高演算法設計質量與程式設計素質 ;

設計任務 (在規定的時間內完成下列任務)

思想:將一定數量的資金供多個使用者週轉使用,當用戶對資金的最大申請量不超過現存資金時可接納一個新客戶,客戶可以分期借款,但借款總數不能超過最大的申請量。銀行家對客戶的借款可以推遲支付,但是能夠使客戶在有限的時間內得到借款,客戶得到所有的借款後能在有限的時間內歸還。

用銀行家演算法分配資源時,測試程序對資源的最大需求量,若現存資源能滿足最大需求就滿足當前程序的申請,否則推遲分配,這樣能夠保證至少有一個程序可以得到所需的全部資源而執行到結束,然後歸還資源,若OS能保證所有程序在有限的時間內得到所需資源則稱系統處於安全狀態。

1. 需求分析

1.1 課程設計題目

程式設計序模擬銀行家演算法

1.2 課程設計目的

1、銀行家演算法是避免死鎖的一種重要方法,本實驗要求用高階語言編寫和除錯一個簡單的銀行家演算法程式。加深瞭解有關資源申請、避免死鎖等概念,並體會和了解死鎖和避免死鎖的具體實施方法。

2、提高自己的.程式設計能力、 提高演算法設計質量與程式設計素質;

1.3 課程設計任務及要求

思想:將一定數量的資金供多個使用者週轉使用,當用戶對資金的最大申請量不超過現存資金時可接納一個新客戶,客戶可以分期借款,但借款總數不能超過最大的申請量。銀行家對客戶的借款可以推遲支付,但是能夠使客戶在有限的時間內得到借款,客戶得到所有的借款後能在有限的時間內歸還。

銀行家演算法在系統在分配資源時自始自終地做出正確的選擇,這樣可以避免死鎖的發生。

用銀行家演算法分配資源時,測試程序對資源的最大需求量,若現存資源能滿足最大需求就滿足當前程序的申請,否則推遲分配,這樣能夠保證至少有一個程序可以得到所需的全部資源而執行到結束,然後歸還資源,若OS能保證所有程序在有限的時間內得到所需資源則稱系統處於安全狀態。

1.4 軟硬體執行環境及開發工具

1.4.1硬體環境

PC機一臺,支援WINDOWS XP,和LINUX。

1.4.2軟體環境

在LINUX下執行,在WINDOWS下用WIN-TC 執行或在Turbo C for Windows下執行。

2. 概要設計

2.1 程式流程圖

2.2 設計原理及方法

銀行家演算法的設計思想是:當用戶申請一組資源時,系統必須做出判斷;如果把這些資源分出去,系統是否還處於安全裝他。若是,就可以分出這些資源;否則,該申請暫不能滿足。

實現銀行家演算法要有若干資料結構,它們用來表示資源分配系統的狀態。令n表示系統中程序的數目,m表示資源的分類數。還需要以下資料結構:

1. Available是一個長度為m的向量,它表示每類資源可用的數量。Available [j]=k,表示rj類資源可用的數量為k。

是一個n×m矩陣,它表示每個程序對資源的最大需求。Max [i,j]=k,表示程序pi至多可以申請k個rj類資源單位。

3. Allocation是一個n×m矩陣,它表示當前分給每個程序的資源數目。Allocation [i,j]=k,表示程序pi當前分到k個rj類資源。

4. Need是一個n×m矩陣,它表示每個程序還缺少多少資源。Need[i,j]=k,表示程序pi尚需k個rj類資源才能完成其任務。顯然Need[i,j]= Max [i,j]- Allocation [i,j]。

這些資料結構的大小和數值隨時間推移而改變。

系統所執行的安全性演算法描述如下:

1.設定2個向量:工作向量Work:它表示系統可提供給程序繼續執行所需的各類資源數目,它含有m個元素,在執行安全演算法開始時,Work = Available。

Finish[i] :它表示系統是否有足夠的資源分配給程序,使之完成執行。開始時先做Finish[i]=true。

2.從程序集合中找到一個滿足下述條件的程序:Finish[i]=flase;Need[i,j]≤Work[j];若找到,則執行步驟3,否則,執行步驟4。

3.當程序pi獲得資源後,可順利執行,直至完成,並釋放分配給它的資源。

4.如果所有程序的Finish[i]=true都滿足。則表示系統處於安全狀態;否則,系統處於不安全狀態。

3. 詳細設計

3.1 程式原始碼

#include "string.h"

#include

#include

#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類資源最大資源需求量*/

int ALLOCATION[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}};

/*M個程序還需要N類資源的資源量*/

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)

{

printf("請輸入需申請資源的程序號(從0到");

printf("%d",M-1);

printf(",否則重輸入!):");

scanf("%d",&i);

if(i<0||i>=M)printf("輸入的程序號不存在,重新輸入!");

}

printf("請輸入程序");

printf("%d",i);

printf("申請的資源數");

for (j=0;j

{

printf("資源");

printf("%d",j);

printf(":");

scanf("%d",&Request[j]);

if(Request[j]>NEED[i][j])

{

printf("程序");

printf("%d",i);

printf("申請的資源數大於程序");

printf("%d",i);

printf("還需要");

printf("%d",j);

printf("類資源的資源量!申請不合理,出錯!請重新選擇!");

flag=N;

break;

}

else

{

if(Request[j]>AVAILABLE[j])

{

printf("程序");

printf("%d",i);

printf("申請的資源數大於系統可用");

printf("%d",j);

printf("類資源的資源量!申請不合理,出錯!請重新選擇!");

flag=N;

break;

}

}

}

if(flag==Y||flag==y)

{

changdata(i);

if(chkerr(i))

{

rstordata(i);

showdata();

}

else

showdata();

}

else

showdata();

printf("");

printf("是否繼續銀行家演算法演示,按Y或y鍵繼續,按N或n鍵退出演示: ");

scanf("%c",&flag);

}

}

void showdata()

{

int i,j;

printf("系統可用的資源數為:");

printf(" ");

for (j=0;j

printf(" 資源");

printf("%d",j);

printf(":");

printf("%d",AVAILABLE[j]);

printf("");

printf("各程序還需要的資源量:");

for (i=0;i

{

printf(" 程序");

printf("%d",i);

printf(":");

for (j=0;j

printf("資源");

printf("%d",j);

printf(":");

printf("%d",NEED[i][j]);

/*printf("");*/

}

printf("");

}

printf("各程序已經得到的資源量:");

for (i=0;i

{

printf(" 程序");

printf("%d",i);

for (j=0;j

printf("資源");

printf("%d",j);

printf(":");

printf("%d",ALLOCATION[i][j]);

}

printf("");

}

}

void changdata(int k)

{

int j;

for (j=0;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

{

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;