一種基于回退技術的安全序列檢索方法

趙富星，張 帆，黃繼海

(鄭州工程技術學院 a.機電與車輛工程學院 b.信息工程學院, 鄭州 450044)

一種基于回退技術的安全序列檢索方法

趙富星a，張 帆b，黃繼海b

(鄭州工程技術學院 a.機電與車輛工程學院 b.信息工程學院, 鄭州 450044)

在操作系統的設計與實現中，可以借助多進程并發執行，來提高系統的資源利用率，進一步提高系統的吞吐量，但與此同時就有可能伴隨死鎖一類的運行錯誤。死鎖是指由多進程并發執行中因競爭資源而造成的一種僵局，若無外力作用，這些進程都將無法繼續向前推進。而銀行家算法則是一種極具代表性的、典型的避免死鎖的算法。本文通過對銀行家算法的分析，著重討論了其安全序列和安全狀態，給出其結構化模型，提出銀行家算法的關鍵在于安全序列;描述了安全性檢驗的抽象算法，并在此基礎上，利用回退技術給出了一種檢索全部安全序列的方法。

銀行家算法;死鎖;安全序列

在操作系統引入多道程序設計后，可通過多進程宏觀上并行、微觀上交替執行來提高系統對資源的利用率和處理能力。為了規避與時間有關的錯誤的發生，人們提出了各種解決方案。但有這樣一種特殊的與時間有關的錯誤，需要我們進一步研究和探討，那就是死鎖。[1]所謂死鎖，就是指若干并發進程因競爭資源而陷入的一種僵局，若無外力作用這些進程將永遠無法向前推進。死鎖的產生會嚴重影響系統的可靠性。

通過對死鎖產生的原因進行分析，可以歸結為兩點：

1)資源不足。當系統中所擁有的資源量不足以滿足多進程并發執行時，就會因為對資源的競爭而產生死鎖。

2)進程推進次序不當。多進程在執行過程中，其請求與釋放資源的次序不當，也可能導致死鎖的發生。

銀行家算法是最早由Dijkstra提出的一種避免死鎖的策略。該算法的核心就是判斷資源擬分配后系統是否安全，即是否能找到一個安全序列，以確保系統處于安全狀態。[2]所謂安全狀態，就是指若干并發進程能夠按照某種序列P1→P2→…→Pn分配所需資源，進而滿足每個進程資源的最大需求，使每個進程均能順利執行完畢。此時系統處于完全狀態，序列P1→P2→…→Pn為安全序列。如果找不到任意一個安全序列，那么系統就處于不安全狀態。根據銀行家算法的描述，進程安全序列會有多個，如何找出所有的安全序列，以及在不同領域進行應用和改進，就成為了一個值得探討的問題。本文通過對安全狀態的分析，給出一種基于回退技術的檢索全部安全序列的方法。在具體實現的過程中，借助棧結構模擬遞歸，并借助面向對象C++語言，描述某一時刻檢索所有安全序列的算法，最后采用該語言實現了這種算法。

1 銀行家算法分析

在銀行家算法里，把操作系統看作是銀行家，操作系統管理的軟硬件資源看作是銀行家管理的資金，并發進程向操作系統請求分配資源看作是客戶向銀行家借貸。銀行家算法就是對每個并發進程提出的資源分配請求進行安全性檢驗，判斷滿足該分配請求后，是否會使系統進入不安全狀態。如果會，就暫停分配，拒絕該進程對資源的請求；如果不會，就分配下去，滿足該進程對資源的需求。

1.1 安全狀態和安全序列

安全狀態，就是指操作系統能按某種進程的執行次序P1→P2→…→Pn，為每個進程分配尚需資源，從而達到其最大需求，讓每個并發進程都能順利執行完畢。一般稱進程的執行序列P1→P2→…→Pn為安全序列，若找不到安全序列，那么系統就處于不安全狀態。

如果一個操作系統處于不安全狀態，就有可能會出現死鎖。反之，如果處于安全狀態，就一定不會出現死鎖。

1.2 安全狀態分析

若操作系統中有三個并發進程P1、P2和P3，共有12個待分配資源。進程P1共需資源10個，P2和P3分別需求4個和9個。[3]設T0時刻，進程P1、P2和P3已分別獲得資源5個、2個和2個，剩余3個資源可用，如表1所示。

表1 安全序列資源分配

T0時刻，操作系統處于安全狀態，因為此刻存在一個安全序列P2→P1→P3，操作系統只要按此序列為每個進程分配尚需資源，就能達到其最大需求，進程都能順利執行完。操作系統先從剩余資源中取出2個分配給P2，滿足其尚需資源量，此時系統剩余資源減少為1個；待P2執行完，便會釋放其先后申請到的4個資源，使剩余資源增至5個，然后再將全部資源分配給P1；待P1執行完，會釋放10個資源，此時，P3就有足夠多的資源可以申請，進而使P1、P2、P3都能順利完成。

若不按此安全序列分配資源，則操作系統就可能會進入不安全狀態。[4-5]在T0時刻后，P3又請求1個資源，如果系統將剩余資源3個中的1個分配給P3，那么系統就會進入不安全狀態。因為此時再把系統剩余的2個資源分配給P2，在P2滿足尚需資源、執行完并釋放資源后，系統剩余資源為4個，既不能滿足P1的尚需資源，也不能滿足P3的尚需資源。這樣都無法順利執行完畢，彼此都在等待對方釋放資源，結果將會出現死鎖。通過以上分析可以看出，自從操作系統為P3再分配1個資源開始，系統便進入了不安全狀態。由此可見，在P3提出了新的資源請求時，盡管系統剩余資源量能夠滿足，但也不會分配，必須讓P3一直等待到P1和P2執行完畢，釋放資源后，再將資源分配給P3，這樣才能順利執行。

2 算法描述

銀行家算法所需數據結構：

1)系統剩余資源向量Available

一個包含m個元素的一維數組，數組中的每一個元素代表了一類可用資源。數組中元素的初值分別代表了系統中各類資源數量，數組元素的值會隨著資源的分配和回收而動態變化。如Available[j]= k，則表示系統中有Rj類資源k個。

2)最大需求矩陣Max

一個n*m的矩陣，分別定義了系統中n個并發進程對m類資源的最大需求。如Max[i,j]= k，則表示進程i對Rj類資源的最大需求是k個。

3)已分配矩陣Allocation

一個n*m的矩陣，分別定義了系統已分配給n個進程的各類資源數量。如Allocation[i,j]= k，則表示進程i已分配Rj類資源k個。

4)尚需矩陣Need

一個n*m的矩陣，分別定義了n個進程尚需各類資源的數量，如Need[i,j]= k，則表示進程i尚需Rj類資源k個，才能達到自身最大需求，順利執行完畢。

上述三個矩陣間存在的關系：

Max[i,j]=Allocation[i,j]+Need[i,j][6-7]

2.1 銀行家算法

設進程Pi的新資源請求向量為Request[i]。如Request[i]= k，則還需為進程Pi分配Rj類資源k個。當Pi發出資源請求后，操作系統按下述步驟進行檢驗：[8]

1)若Request[i]≤Need[i]，則轉至(2)。否則，報錯，因為新的資源請求超過其還能獲得的資源量。

2)若Request[i]≤Available，則轉至(3)。否則，報錯，新的資源請求超過了系統剩余資源量，資源不足，無法分配，進程必須等待。

3)試分配。滿足進程Pi的新資源請求，并修改對應的數據：

Available-=Request[i];

Allocation+=Request[i];

Need[i]-=Request[i];

4)進行系統安全性檢驗。若找到安全序列，則系統安全，正式為進程Pi分配資源。否則，判定試分配無效，恢復原有系統資源狀態，讓進程Pi等待。

2.2 安全性檢驗算法

安全性檢驗算法如圖1所示。

圖1 安全性檢驗算法

1)設置兩個向量Work和Finish

a.Work是具有m個元素的一維數組，表示系統可提供給進程繼續執行的各類資源數量。初始狀態下，Work=Allocation。

b.Finish是具有n個元素的一維數組，表示系統能否提供給進程足夠的資源使其順利執行完畢。初始狀態下，Finish[i]=false；當有足夠資源分配給進程時，Finish[i]=true。

2)在并發進程中找到能滿足下述條件的進程：

a.Finish[i]=false;

b.Need[i]≤Work;

如果找到，則轉至(3)；否則，轉至(4)。

3)進程Pi獲得資源后，滿足尚需資源量，可順利執行完畢，并釋放分配給它的所有資源，因此：

Work+=Allocation；

Finish[i]=true；

轉至(2)。

4)如果所有進程Finish[i]==true，則表示系統處于安全狀態，通過了系統安全性檢驗；否則，系統就處于不安全狀態。

3 基于回退技術的檢索方法

引入向量F和D分別表示暫時性V向量和檢索中是否被滿足，并使之運行完成。初始狀態，對所有未滿足的進程Pi記作D[i]=false；當有足夠資源分配給進程時，記作D[i]=true，并釋放其擁有的所有資源。[9]

擬分配的結果如果可以達到D[1…n]=true，則表示系統處于安全狀態，資源擬分配有效；否則，系統處于不安全狀態，暫停資源分配。

voidreleaseResource(intA[],intF[],intmResource); //進程Pi完成，釋放已分配資源

voidcancelRelease(intA[],intF[],intmResource); //回退，取消資源釋放

intisEnough(intN[],intF[],intmResource); //剩余資源能否滿足進程Pi尚需資源請求

voidoutPut(intSafeSequence[],intnProcess); //輸出一個安全序列

intBankAlgo(intnProcess,intmResource,intF[],intA[][],intN[][],intD[],intnumFinished,intSafeSequence[],intNumSafeSeq) { //基于回退的銀行家算法

for(inti= 0;i

if(!D[i]&&isEnough(N[i],F,mResource)){

releaseResource(A[i],F,mResource);

D[i]=1;

SafeSequence[++numFinished]=i; //若所有進程都處理完，則找到一個安全序列，并輸出；否則遞歸處理下一進程

if(numFinished==nProcess){

Output(SafeSequence,nProcess);

NumSafeSeq++;}

else

NumSafeSeq=BankAlgo(nProcess,mResource,F,A,N,D,numFinished,SafeSequence,NumSafeSeq); //取消此次標記，恢復處理前的環境，以便開始新的回退

CancelRelease(A[i],F,mResource);

D[i]=0;

——numFinished;}}

returnNumSafeSeq;}。

[1]左萬利，王拉柱.銀行家算法的改進[J].吉林大學學報:理學版, 2007(1):35-38.

[2]帖軍，蔣天發.銀行家算法中的安全序列分析[J].武漢理工大學學報, 2007, 29(6):114-117.

[3]王繼奎，王會勇.基于銀行家算法的進程安全序列全搜索算法[J].甘肅科學學報, 2009,21(2):152-154.

[4]仲兆滿，管燕.銀行家算法的改進及其在操作系統上的推廣[J].連云港師范高等專科學校學報,2002(2):46-48.

[5]李斌.銀行家算法的研究及其計算機仿真[J].揚州教育學院學報,2003,21(3):32-34.

[6]左萬歷,周長林.計算機操作系統教程[M].北京：高等教育出版社, 2004.

[7]湯子瀛.計算機操作系統[M].西安：西安電子科技大學出版社, 1996.

[8]張帆，張文.用C#實現和改進銀行家算法[J].電腦知識與技術, 2011,7(8):1829-1831.

[9]張帆.用C++實現進程安全序列搜索算法[J].電腦知識與技術, 2012,8(21):5104-5106.

(責任編輯 姚虹)

A Search Method of Safe Sequence Based on the Backtracking

ZHAO Fu-xinga, ZHANG Fanb, HUANG Ji-haib

(a. College of Mechanical-electronic and Vehicle Engineering, Zhengzhou Institute of Technology, Zhengzhou 450044, China;b. College of Information Engineering, Zhengzhou Institute of Technology, Zhengzhou 450044, China)

In the process of design and realization of the operating system, the concurrent implementation of a number of processes can improve the utilization rate of system resources. However, an error may occur: deadlock. Deadlock is a kind of stalemate caused by competing resources in the implementation of multiple processes. If there is no external force, processes will be not running. Banker algorithm is a very representative and typical method to avoid deadlock. This essay discusses secured sequence and the security state of banker’s algorithm, and points out the importance of safe sequence. Meanwhile, it describes bankers’ model. Finally, it provides the detailed realization of safe sequence searching algorithm based on the backtracking.

banker’s algorithm; deadlock; safe sequence

2017-06-09

河南省基礎與前沿技術研究計劃項目(152300410006)

趙富星(1982—)，男，河南宜陽人，鄭州工程技術學院機電與車輛工程學院教師，主要研究方向為計算機應用技術。

10.13783/j.cnki.cn41-1275/g4.2017.04.025

TP301.6

A

1008-3715(2017)04-0117-04