趙富星，張 帆，黃繼海

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

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

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

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

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

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

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

通過對死鎖產(chǎn)生的原因進行分析，可以歸結(jié)為兩點：

1)資源不足。當系統(tǒng)中所擁有的資源量不足以滿足多進程并發(fā)執(zhí)行時，就會因為對資源的競爭而產(chǎn)生死鎖。

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

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

1 銀行家算法分析

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

1.1 安全狀態(tài)和安全序列

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

如果一個操作系統(tǒng)處于不安全狀態(tài)，就有可能會出現(xiàn)死鎖。反之，如果處于安全狀態(tài)，就一定不會出現(xiàn)死鎖。

1.2 安全狀態(tài)分析

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

表1 安全序列資源分配

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

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

2 算法描述

銀行家算法所需數(shù)據(jù)結(jié)構：

1)系統(tǒng)剩余資源向量Available

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

2)最大需求矩陣Max

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

3)已分配矩陣Allocation

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

4)尚需矩陣Need

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

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

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

2.1 銀行家算法

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

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

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

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

Available-=Request[i];

Allocation+=Request[i];

Need[i]-=Request[i];

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

2.2 安全性檢驗算法

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

圖1 安全性檢驗算法

1)設置兩個向量Work和Finish

a.Work是具有m個元素的一維數(shù)組，表示系統(tǒng)可提供給進程繼續(xù)執(zhí)行的各類資源數(shù)量。初始狀態(tài)下，Work=Allocation。

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

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

a.Finish[i]=false;

b.Need[i]≤Work;

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

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

Work+=Allocation；

Finish[i]=true；

轉(zhuǎn)至(2)。

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

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

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

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

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); //取消此次標記，恢復處理前的環(huán)境，以便開始新的回退

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

D[i]=0;

——numFinished;}}

returnNumSafeSeq;}。

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

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

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

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

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

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

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

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

[9]張帆.用C++實現(xiàn)進程安全序列搜索算法[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