張帆

摘要：該文通過分析銀行家算法的核心思想，提出了一種在系統(tǒng)某一時刻進程安全序列的搜索算法，并利用面向對象編程語言C#實現(xiàn)了該算法。

關鍵詞：銀行家算法；C#語言；安全序列；搜索算法

中圖分類號：TP312文獻標識碼：A文章編號：1009-3044(2012)21-5104-03

Implementation of Search Algorithm for Secured Sequence by C++ Language

ZHANG Fan

(School of Informational Engineering, Zhongzhou University, Zhengzhou 450000, China)

Abstract: Based on the core idea of the bankers algotithm,an algorithm which searchs all processes for a Secured Sequence at a given time is implemented by C++ language.

Key words: bankers algorithm; C++ language;secured sequence; search algorithm

在多道程序系統(tǒng)中，可通過多個進程的并發(fā)執(zhí)行來改善系統(tǒng)的資源利用率,提高系統(tǒng)的處理能力。為了避免與時間有關的錯誤，人們建立了各種同步機構。但是有這樣一種種與時間有關的錯誤需要進一步研究和探討，這就是死鎖問題。所謂死鎖是指兩個或兩個以上進程處于無休止地等待永遠不成立的條件的狀態(tài)。

Dijkstra的銀行家算法是最有代表性的避免死鎖算法。允許進程動態(tài)地申請資源，系統(tǒng)在進行資源分配之前，先計算資源分配的安全性。若此次分配不會導致系統(tǒng)進入不安全狀態(tài)，便將資源分配給進程；否則，進程進入等待狀態(tài)。所謂安全狀態(tài)，是指系統(tǒng)能按某種順序（P1，P2，…，Pn）來為每個進程分配其所需資源，直至最大需求，使每個進程都可順序完成。我們稱（P1，P2，…，Pn）序列為安全序列。若系統(tǒng)不存在這樣一個安全序列，則稱系統(tǒng)處于不安全狀態(tài)。

1算法的設計與流程

1.1算法流程圖

如圖1所示。

1.2算法的數(shù)據(jù)結構

1）可利用資源向量Available，它是一個最多含有100個元素的數(shù)組，其中的每一個元素代表一類可利用的資源的數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源數(shù)目。其數(shù)值隨該類資源的分配和回收而動態(tài)地改變。如果Available（j）=k，標是系統(tǒng)中現(xiàn)有j類資源k個。

2）最大需求矩陣Max，這是一個n×m的矩陣，它定義了系統(tǒng)中n個進程中的每一個進程對m類資源的最大需求。如果Max（i，j）=k，表示進程i需要j類資源的最大數(shù)目為k。

3）分配矩陣Allocation，這也是一個n×m的矩陣，它定義了系統(tǒng)中的每類資源當前一分配到每一個進程的資源數(shù)。如果Alloca tion（i，j）=k，表示進程i當前已經(jīng)分到j類資源的數(shù)目為k。Allocation i表示進程i的分配向量，有矩陣Allocation的第i行構成。

4）需求矩陣Need，這還是一個n×m的矩陣，用以表示每個進程還需要的各類資源的數(shù)目。如果Need（i，j）=k，表示進程i還需要j類資源k個，才能完成其任務。Need i表示進程i的需求向量，由矩陣Need的第i行構成。

5）上述三個矩陣間存在關系：Need（i，j）=Max（i，j）-Allocation（i，j）；

1.3安全性檢測

1）如果Requesti≤Need，則轉向步驟2；否則，認為出錯，因為它所請求的資源數(shù)已超過它當前的最大需求量。

2）如果Requesti≤Available，則轉向步驟3；否則，表示系統(tǒng)中尚無足夠的資源滿足i的申請，i必須等待。

3）系統(tǒng)試探性地把資源分配給進程i，并修改下面數(shù)據(jù)結構中的數(shù)值：

Available = Available - Requesti

Allocationi = Allocationi + Requesti

Needi = Needi - Requesti

4）系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。如果安全才正式將資源分配給進程i，以完成本次分配；否則，將試探分配作廢，恢復原來的資源分配狀態(tài)，讓進程i等待。

2算法的實現(xiàn)

用C++語言編寫主體程序如下：

#include

#include

#include

#define False 0

#define True 1

using namespace std;

int Max[100][100]={0};//各進程所需各類資源的最大需求int Avaliable[100]={0};//系統(tǒng)可用資源

char name[100]={0};//資源的名稱

int Allocation[100][100]={0};//系統(tǒng)已分配資源

int Need[100][100]={0};//還需要資源

int Request[100]={0};//請求資源向量

int temp[100]={0};//存放安全序列

int Work[100]={0};//存放系統(tǒng)可提供資源

int M=100;//進程的最大數(shù)為

int N=100;//資源的最大數(shù)為

int safe()//安全性算法

{ int i,k=0,m,apply,Finish[100]={0};

int j;

int flag=0;

Work[0]=Avaliable[0];

Work[1]=Avaliable[1];

Work[2]=Avaliable[2];

for(i=0;i

apply=0;

for(j=0;j

if (Finish[i]==False&&Need[i][j]<=Work[j]){

apply++;

if(apply==N){

for(m=0;m

Work[m]=Work[m]+Allocation[i][m];//變分配數(shù)

Finish[i]=True;

temp[k]=i;

i=-1;

k++;

flag++; } } } }

for(i=0;i

if(Finish[i]==False){

cout<<"系統(tǒng)不安全"<

return -1; } }

cout<<"系統(tǒng)是安全的!"<

cout<<"分配的序列:";

for(i=0;i

if(i

void share()//利用銀行家算法對申請資源對進行判定

{ char ch;

int i=0,j=0;

ch=y;

cout<<"請輸入要求分配的資源進程號(0-"<>i;//輸入須申請的資源號

cout<<"請輸入進程"<

for(j=0;j

{ cout<

cin>>Request[j];//輸入需要申請的資源}

for (j=0;j

if(Request[j]>Need[i][j])//判斷申請是否大于需求，若大于則出錯

{ cout<<"進程"<

cout<<"分配不合理，不予分配！"<

ch=n;

break; }

else {

if(Request[j]>Avaliable[j])//判斷申請是否大于當前資源，若大于則出錯

{ cout<<"進程"<

cout<<"分配出錯，不予分配!"<

ch=n;

break; } } }

if(ch==y)

{ changdata(i);//根據(jù)進程需求量變換資源

showdata();//根據(jù)進程需求量顯示變換后的資源

safe();//根據(jù)進程需求量進行銀行家算法判斷} }

3結束語

該文通過分析銀行家算法的核心思想，提出了一種在系統(tǒng)某一時刻進程安全序列的搜索算法，并提供了算法的流程圖，結合面向對象程序設計語言的特點，利用C++語言實現(xiàn)了該算法。通過分析安全序列，可以對系統(tǒng)資源的合理分配與進程調度的優(yōu)化提供支持。

參考文獻：

[1]左萬歷.計算機操作系統(tǒng)教程[M]. 3版.北京:高等教育出版社,2010.

[2]湯子瀛.計算機操作系統(tǒng)[M].西安:西安電子科技大學出版社,1996.

[3] Silberschatz A,Galvin P B,Gagne G.操作系統(tǒng)概念[M].鄭扣根,譯. 6版.北京:高等教育出版社,2004.

[4]譚浩強C++程序設計[M]. 2版.北京:清華大學出版社,2011.