用C++實(shí)現(xiàn)進(jìn)程安全序列搜索算法

張帆

摘要：該文通過(guò)分析銀行家算法的核心思想，提出了一種在系統(tǒng)某一時(shí)刻進(jìn)程安全序列的搜索算法，并利用面向?qū)ο缶幊陶Z(yǔ)言C#實(shí)現(xiàn)了該算法。

關(guān)鍵詞：銀行家算法；C#語(yǔ)言；安全序列；搜索算法

中圖分類(lèi)號(hào)：TP312文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：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)中，可通過(guò)多個(gè)進(jìn)程的并發(fā)執(zhí)行來(lái)改善系統(tǒng)的資源利用率,提高系統(tǒng)的處理能力。為了避免與時(shí)間有關(guān)的錯(cuò)誤，人們建立了各種同步機(jī)構(gòu)。但是有這樣一種種與時(shí)間有關(guān)的錯(cuò)誤需要進(jìn)一步研究和探討，這就是死鎖問(wèn)題。所謂死鎖是指兩個(gè)或兩個(gè)以上進(jìn)程處于無(wú)休止地等待永遠(yuǎn)不成立的條件的狀態(tài)。

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

1算法的設(shè)計(jì)與流程

1.1算法流程圖

如圖1所示。

1.2算法的數(shù)據(jù)結(jié)構(gòu)

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

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

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

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

5）上述三個(gè)矩陣間存在關(guān)系：Need（i，j）=Max（i，j）-Allocation（i，j）；

1.3安全性檢測(cè)

1）如果Requesti≤Need，則轉(zhuǎn)向步驟2；否則，認(rèn)為出錯(cuò)，因?yàn)樗?qǐng)求的資源數(shù)已超過(guò)它當(dāng)前的最大需求量。

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

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

Available = Available - Requesti

Allocationi = Allocationi + Requesti

Needi = Needi - Requesti

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

2算法的實(shí)現(xiàn)

用C++語(yǔ)言編寫(xiě)主體程序如下：

#include

#include

#include

#define False 0

#define True 1

using namespace std;

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

char name[100]={0};//資源的名稱(chēng)

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

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

int Request[100]={0};//請(qǐng)求資源向量

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

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

int M=100;//進(jìn)程的最大數(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()//利用銀行家算法對(duì)申請(qǐng)資源對(duì)進(jìn)行判定

{ char ch;

int i=0,j=0;

ch=y;

cout<<"請(qǐng)輸入要求分配的資源進(jìn)程號(hào)(0-"<>i;//輸入須申請(qǐng)的資源號(hào)

cout<<"請(qǐng)輸入進(jìn)程"<

for(j=0;j

{ cout<

cin>>Request[j];//輸入需要申請(qǐng)的資源}

for (j=0;j

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

{ cout<<"進(jìn)程"<

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

ch=n;

break; }

else {

if(Request[j]>Avaliable[j])//判斷申請(qǐng)是否大于當(dāng)前資源，若大于則出錯(cuò)

{ cout<<"進(jìn)程"<

cout<<"分配出錯(cuò)，不予分配!"<

ch=n;

break; } } }

if(ch==y)

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

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

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

3結(jié)束語(yǔ)

該文通過(guò)分析銀行家算法的核心思想，提出了一種在系統(tǒng)某一時(shí)刻進(jìn)程安全序列的搜索算法，并提供了算法的流程圖，結(jié)合面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言的特點(diǎn)，利用C++語(yǔ)言實(shí)現(xiàn)了該算法。通過(guò)分析安全序列，可以對(duì)系統(tǒng)資源的合理分配與進(jìn)程調(diào)度的優(yōu)化提供支持。

參考文獻(xiàn)：

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

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

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

[4]譚浩強(qiáng)C++程序設(shè)計(jì)[M]. 2版.北京:清華大學(xué)出版社,2011.