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

趙富星，張 帆，黃繼海

(鄭州工程技術(shù)學(xué)院 a.機(jī)電與車輛工程學(xué)院 b.信息工程學(xué)院, 鄭州 450044)

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

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

(鄭州工程技術(shù)學(xué)院 a.機(jī)電與車輛工程學(xué)院 b.信息工程學(xué)院, 鄭州 450044)

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

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

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

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

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

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

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

1 銀行家算法分析

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

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

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

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

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

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

表1 安全序列資源分配

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

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

2 算法描述

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

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

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

2)最大需求矩陣Max

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

3)已分配矩陣Allocation

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

4)尚需矩陣Need

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

上述三個(gè)矩陣間存在的關(guān)系：

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

2.1 銀行家算法

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

1)若Request[i]≤Need[i]，則轉(zhuǎn)至(2)。否則，報(bào)錯(cuò)，因?yàn)樾碌馁Y源請(qǐng)求超過其還能獲得的資源量。

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

3)試分配。滿足進(jìn)程Pi的新資源請(qǐng)求，并修改對(duì)應(yīng)的數(shù)據(jù)：

Available-=Request[i];

Allocation+=Request[i];

Need[i]-=Request[i];

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

2.2 安全性檢驗(yàn)算法

安全性檢驗(yàn)算法如圖1所示。

圖1 安全性檢驗(yàn)算法

1)設(shè)置兩個(gè)向量Work和Finish

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

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

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

a.Finish[i]=false;

b.Need[i]≤Work;

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

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

Work+=Allocation；

Finish[i]=true；

轉(zhuǎn)至(2)。

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

3 基于回退技術(shù)的檢索方法

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

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

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

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

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

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

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; //若所有進(jìn)程都處理完，則找到一個(gè)安全序列，并輸出；否則遞歸處理下一進(jìn)程

if(numFinished==nProcess){

Output(SafeSequence,nProcess);

NumSafeSeq++;}

else

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

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

D[i]=0;

——numFinished;}}

returnNumSafeSeq;}。

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

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

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

[4]仲兆滿，管燕.銀行家算法的改進(jìn)及其在操作系統(tǒng)上的推廣[J].連云港師范高等?？茖W(xué)校學(xué)報(bào),2002(2):46-48.

[5]李斌.銀行家算法的研究及其計(jì)算機(jī)仿真[J].揚(yáng)州教育學(xué)院學(xué)報(bào),2003,21(3):32-34.

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

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

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

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

(責(zé)任編輯 姚虹)

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

河南省基礎(chǔ)與前沿技術(shù)研究計(jì)劃項(xiàng)目(152300410006)

趙富星(1982—)，男，河南宜陽人，鄭州工程技術(shù)學(xué)院機(jī)電與車輛工程學(xué)院教師，主要研究方向?yàn)橛?jì)算機(jī)應(yīng)用技術(shù)。

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

TP301.6

A

1008-3715(2017)04-0117-04