对于改进避免死锁安全算法的策略研究

戴家刚

摘 要：随着社会的不断进步以及科技的发展，避免死锁的安全算法也成为了目前最为关注的问题，因此为了能够有效地节省检测开销，将对避免死锁的算法进行相应改进，笔者也将针对改进避免死锁安全算法的策略进行深入的探讨和研究，为以后锁的应用发展奠定了坚实基础。本文将首先分析产生死锁的必要因素，概述处理死锁的具体方法，详细阐述如何改进避免死锁安全算法的相关策略，希望可以为相关工作人员提供有用的参考。

关键词：改进策略 死锁安全算法 研究 必要因素

中图分类号：TP273 文献标识码：A 文章编号：1672-3791（2018）10（b）-0008-02

1 产生死锁的必要因素

在计算机的系统中，如果出现了死锁的情况，那么必然是由如下因素造成的。

（1）互斥性。在规定的时间里，一个进程只能被一个资源独占应用，一旦有别的进程也想寻求此资源，那么必然需要进行相应的等待和释放。

（2）等待以及保持。使进程允许在不释放已得资源的情况下，进行等待新资源的分配。

（3）非剥夺性。一旦进程获得了一定资源，那么如果没有使用完，是不能被其他的进程掠夺的，必须由自身进行一定的释放。

（4）循环性等待。有一个等待的集合存在着，如{p1，p2，…，pn}，p1所等待的资源是被p2占用的，然而p2的是被p3占用的，……，一直到pn等待下一个可占用的资源。

2 处理死锁的方法

处理死锁的主要方法如下：（1）可以设定一定的规则使相应的系统不受到损害，处于死锁状态；（2）在设定死锁状态后还要设定相应的复活模式，但是如果想要能够使系统及时的进行复活，那么必然面临着一定的困难同时还会付出昂贵的代价。然而在一般情况下将处理死锁方法分为避免死锁和阻止死锁两种方法。

2.1 阻止死锁的方法

一旦发生死锁的状况，那么肯定是具备了上述四个必然因素，只要有其中一条不成立，那么就可能有效阻止死锁的发生，但是阻止死锁的办法多种多样，就不一一介绍了。

2.2 避免死锁的方法

由dijkstra和habermann两种共同结合而成称之为银行家算法，在所有的算法中具有典型的作用，并且它可以适用于任何一個资源系统中。像是对于有很多种资源以及进程的系统，都需要很多次的运算，因此也就致使了有很大的开销。

其实每一个不同的资源类型中几乎只含有一个独立个体，同时也只有一个最为有效的运算方式，但是这个方式也是受限于分配图的[2]。判定系统的安全状态不但需要对系统图中的闭合环路形成进行寻找，而且还要进行一定的n2运算。笔者将针对此种方法进行一定的改进，将运算级次降到n。

2.3 改进的安全算法

当进程pi要请求资源分配的时候，只需要对r资源进行相应的检查和标志，同时和进程pi所有请求边以及宣告边相连的资源顶点标志为{F，r，j1，F，r，j2，…，F，r，jk}是否等同。如果F.rj=F.r.j，并且其中至少存在着一个资源顶点标志与其它的相同，那么就说明了此系统属于安全不佳的状态；相反是处于一个安全的状态[3]。

例如：在图1中显示，系统是不具有一定的分配资源的。假如说进程p1对r1资源发出请求，系统所处的状态是安全的，因此有效把资源r1分配给p1，这时候的资源分配图就会变成图1这种模式。

如果此时的进程p3对资源r3进行归还，那么这时候的资源分配图为如图2所示。

3 改进避免死锁安全算法的相关策略

3.1 E-策略

有国外的相关研究人员提出了一种死锁预防措施叫做E-策略，这种方法也是避免死锁的一种有效措施。E-策略的实施就是将网中的全部严格极小信标，之后再对全部的严格极小信标添加一个控制库，而控制库所的输出弧均指向原始网模型的源变迁，从而能够有效保证扩展网系统不会出现新的严格极小信标，并且扩展网系统也是一个良好的活性控制器。这种方法在使用的过程中虽然有着一定优点，然而随着使用时间的增加，也暴露出了很多的问题。首先，E-策略的结构比较复杂，这就导致其许可行为限制过大，还提升了计算复杂度。产生许可行为限制过大的问题是因为输出弧均指向原始网模型的源变迁所造成的；而计算复杂度过大的问题是因为要计算全部极小信标本身就十分复杂；造成结构复杂问题出现的主要原因则是：E-策略需要对原始网模型全部的严格极小信标增加控制库所导致的。所以要想更好地使用E-策略，就需要根据实际情况进行控制和调整，从而提升E-策略的使用效果。

3.2 H1-策略

H1-策略的在控制系统的过程也就是一个迭代过程，这是一种基于混合整数规划技术避免出现死锁的有效策略，这种策略可以找到在网络中存在的最大可被清空信标，这样就可以有效将最大可被清空信标中的对应严格极小信标导出，从而有效的避免出现死锁问题。而这种策略的使用同样分为两个步骤。第一步就是如E-策略相同的添加控制库所，然后可以被清空信标检测出来，在对其添加控制库所，然后如此一直迭代进行，一直到没有能够被清空的信标为止。完成这一步之后，就进入第二步，然后还是使用如是B策略中的方法，也就是控制库所的输出弧均指向原始网模型的源变迁，在完成了这两个步骤之后，控制库所中就不会出现新的严格极小信标，就能够有效的避免出现死锁的问题。

3.3 H2-策略

H2-策略是一种基于H1-策略的有效改进措施，这一策略的核心概念就是基本信标的概念。这种策略主要是改进H1-策略的第一个步骤，第二个步骤则与H1-策略相同。H2-策略的第一步是要将系统中的全部基本信标找到，然后对每一个基本信标添加控制库所。这种方法的优点是相比H1-策略所添加的控制库所要更少。

4 结语

总而言之，需要重点强调的是只要系统处于安全状态，那么必然不会出现死锁的状况；但是只要系统是不安全状态，那么会致使死锁状况的发生，但是也有可能不会发生死锁状况，因此导致必要的等待出现。但是这种方法与其他的检测方法相比造成的等待还是较少的。现如今我们可以将方法进行重新的命名，像是“触网式”安全检测。并且这种方法与直接检测环路相比更具有一定的优势，能够将运算级次进行有效降低，在一定程度上节约了成本和检测开销。除此以外，这种触网式检测在等待图中的充分应用取得了明显的效果。

参考文献

[1] 朱淑芹，李俊青，王文宏.对改进的基于DNA编码和混沌的图像加密算法的安全性分析[J].计算机应用研究，2017，34（10）：3090-3093.

[2] 侯欣蕾，于莲芝.基于改进蚁群算法的移动机器人路径规划[J].软件导刊，2017（12）：162-164.

[3] 高思宇，余敬，马林茂.稀土安全评价：集成算法改进与实证[J].数学的实践与认识，2017，47（3）：90-101.