死锁避免之模拟银行家算法的编程实现

刘畅，文家俊，贾海鹏，徐艳

（四川大学锦城学院计算机与软件学院，四川成都，611731）

1 研究背景与意义

在进程运行中，经常出现多方进程都需要同一资源时，各方都希望其它进程能释放出所需要的资源，从而所有进程都无法获得所需要的资源而没有继续运行，也导致都无法释放出其占有的资源，且会一直在该状态，最后形成死锁。而形成它的四个条件有互斥，不可抢占，占有和等待，环路等待等条件[1]。Dijkstra的银行家算法原本是为了银行的系统设计的，是为了保证银行能顺利的发放贷款，在操作系统中也可以解决系统资源问题，使多进程进入安全状态，能够有效的避免死锁和合理的分配资源给多个进程[2]，从而避免了死锁。

2 死锁的产生与避免思路

2.1 死锁的定义

死锁，其实便是一组多个进程在运行过程中因争夺临界资源而导致的一种僵局。因此可以给死锁做出如下的定义：如果一组进程中的每一个进程都在等待仅由该组进程中的其它进程才能引发的事件，那么该组进程是死锁的（Deadlock）。[3]

2.2 处理死锁的方法

（1）预防死锁，事先采取某种限制措施，破坏产生死锁的四个必要条件中的一个或多个来预防死锁。（2）避免死锁，在资源动态分配过程中，防止系统进入不安全状态，来避免发生死锁。（3）检测死锁，允许进程在运行时产生死锁，但在产生死锁后可及时通过检测机构检测出死锁，并采用适当措施，从而解决死锁。4.解除死锁，当检测到进程中已经有死锁后，采用相应措施，解除进程的死锁。

2.3 银行家算法

避免死锁有鸵鸟算法，有序资源分配法，银行家算法。其中最著名的便是Dijkstra的银行家算法。是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。

3 问题分析与编程实现

3.1 安全性算法流程

（1）先对内容进行初始化，然后输入进程号和资源数。

（2）request请求矩阵与Avaliable资源，Need需求矩阵判断，如果请求矩阵小于它们则进行，否则Error报错。

（3）判断需求矩阵是否为0，当为0时，使q[n]=1,a=a-1,Avalab+=max.否则直接进入search查询，得出是否为安全状态，若是不安全状态则略过重复步骤1。

3.2 算法程序的实现

银行家算法目前的已知条件是：系统的总资源，已分配的资源，最大的需求资源，仍需要的资源。以下是用C语言为主体编写的程序。

Work用于存储当前可用资源。按顺序判断每个没有结束的进程是否能完成，count用来统计可以完成的进程数，a代表进程数，如果count和a相等，说明系统是安全的。只循环一次是不够的，最多需要循环a次，所以当循环要结束时令i=-1重新开始循环直到循环a次还有未完成的进程说明系统是不安全的。

输入每种资源的需求数量，判断输入是否合理并分配资源。如果分配不合理，则退回资源。z1=1时表示输入的数据不合规范分配出错，z1=0则分配正常。如果需求资源=0，说明进程执行结束，退回资源。

用Security函数判断是否安全，安全则输出结果，不安全则输出并退回资源。

3.3 运行结果

对演视样例编译，其中输入的第一个参数为该资源中的第几个进程，第二个参数，第三个参数等为目前的资源数量，由图1得需求矩阵，同时得到当前可利用资源数量{2，3，3}。输入选择当前小于可利用资源数的序列，在输入{1，3，4，7}，{2，1，3，4}，{3，0，0，6}，{4，2，2，1}，{5，1，1，0}中有P5即{5，1，1，0}，然后释放P5，运行P1即{1，3，4，7}以此类推，验证求得如下运行结果如下，序列P5->P1->P2->P3->P4符合要求：

4 应用分析

4.1 于银行贷款中的应用

贷款是银行或其他金融机构按一定利率和必须归还等条件出借货币资金的一种信用活动形式。由于一定数量的货币需要在多个客户之间借贷周转，银行家算法可以有效防止银行资金无法周转从而倒闭，对每一笔贷款都要考察是否能按期归还。在银行贷款中，银行的流动货币是有限的，客户想申请贷款时，第一次必须要声明自己所需的货币量，客户也需要按时还款。在银行贷款中，这个规则就是操作系统，银行的流动货币就是系统中的资源，而客户就是需要资源申请资源的进程。

4.2 于网络爬虫中的应用

网络爬虫资源分配不足会导致发生死锁，发生死锁的爬虫进程无法继续运行，必须通过释放爬虫资源重新抓取网页信息，因此造成爬虫算法效率低下。

死锁是多用户操作系统正常运行的一个重要问题，系统资源不足会导致爬虫算法进入不安全状态，进而引发死锁等问题。引入被广泛用于操作系统的银行家算法，调度多个网络爬虫进程并发运行，并且为每个进程合理分配系统资源，当进程无法获取系统资源时，则等待其他进程分配完成后释放系统资源，从而完成资源分配，有效降低死锁率。而死锁率的降低就等于提高了爬虫算法的效率，合理分配了资源。

4.3 于旅游业中的应用

游客分流管理作为游客管理中的一方面，对景区游客分配、景点科学设置都有着重要作用。由于景区对游客和各类资源分配不合理，所以景区也同样存在拥堵的问题。本质上看，两者都是因为管理者没有采用合理方法对目标对象进行合理配置造成的[4]。这个问题的本质就是资源的分配和管理。在这个问题中，游客可以看作进程申请资源，景区各个景点可以看作系统资源，银行家算法就应用到了问题中，通过固定的算法对景区进行管理，就会解决景区中的“死锁”问题。