一种基于回退技术的安全序列检索方法

赵富星，张 帆，黄继海

(郑州工程技术学院 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