网络爬虫资源分配不足会导致发生死锁，发生死锁的爬虫进程无法继续运行，必须通过释放爬虫资源重新抓取网页信息，因此造成爬虫算法效率低下。G. Ricart等^[1]研究并实现了计算机网络优化算法，通过理论分析证明了理想条件下可以避免死锁。Wang^[2]通过实验验证了银行家算法在判断系统安全性中的有效性。本文研究的多用户操作系统属于共享资源系统，Hao等^[3,4]研究了共享资源系统的鲁棒死锁控制方法。Petri网可用于描述多用户操作系统模型，Ma等^[5]将银行家算法用于解决Petri网中的死锁问题，有效降低了死锁率，表明银行家算法可应用于解决多用户操作系统的死锁问题。多处理器片上系统适用于多用户操作系统，Xiao等^[6]研究了多处理器片上系统上的死锁问题，提出了一种硬件死锁检测算法。多用户操作系统的死锁问题本质上是多进程访问公共资源导致的死锁问题，Lou等^[7]研究了多进程访问公共资源导致的死锁问题，提出了一种避免死锁的算法，实验结果表明该算法有效地解决了分布式事务管理系统中的死锁问题。S. A. Reveliotis等^[8]研究的多车辆系统资源配置算法解决死锁问题。Lang等^[9]基于银行家算法提出了二次时间算法，更好地实现了操作系统资源优化配置。本文研究的网络爬虫配置策略基于Windows操作系统进行开发，Windows操作系统是基于事件驱动的程序模型，Tang等^[10]提出了一种在事件处理系统中有效避免死锁的方法。Duda等^[11]将Cache模块增加到爬虫系统中，并采用了热点检测机制，避免从服务器端重复地获取相同内容，采用MFC编程设计并实现了基于银行家算法的网络爬虫资源配置应用软件，增加Cache模块的设计并引入热点检测机制，提高了系统的运行效率。Peng等^[12]将Ajax页面状态的抓取转换为DRPP，在完全状态转换图拓扑结构已知的情况下，核心状态转换图增加少量取自它的边后成为平衡、强连通图，该欧拉回路即为最优搜索路径，从而提高了效率。杨梅等^[13]针对银行家算法中的安全分配算法进行了研究，该算法缩小了安全检查的范围，提高了系统效率。陈昊成^[14]针对预防死锁问题和调度策略问题提出了解决方案，应用于资源管理分配系统。章韵等^[15]经过仿真实验提出了一种资源分配算法，实验结果证明该算法可以有效避免死锁。

以上研究成果表明，银行家算法是一种避免死锁的有效算法。本文提出了基于银行家算法的网络爬虫资源分配策略，以降低多任务处理系统的死锁率，提高网络爬虫资源的利用率，避免死锁的发生。

根据在同一时间最多允许多少个用户同时操作计算机，操作系统可分为单用户操作系统和多用户操作系统。同一时间内允许多个用户同时使用计算机，称为多用户操作系统；反之，同一时间内最多允许一个用户操作计算机，则称为单用户操作系统。常见的多用户操作系统有Windows Server 2003 和Windows Server 2008等。系统资源的有限性及进程并发性是导致发生死锁的原因，当系统无法满足进程的资源请求时，资源申请失败导致发生死锁。

在多用户操作系统，进程是并发执行的，但是存在一种危险—死锁。若无内部鲁棒容错或外部干预，系统将长期处于封锁状态。竞争资源及进程推进顺序非法是导致死锁的主要原因。在当前资源限制下，寻找一组资源分配的执行顺序，从而避免产生死锁，是本文研究的主要内容。将银行家算法为避免死锁获取安全进程序列的递归思想，借鉴到网络爬虫算法中。将请求集长度作为一个变量，边界条件为请求集长度及节点状态数组，从而能够确定请求集节点的合法性。该算法的时间复杂度比urllib2算法较小，并且能够获得最优请求集长度。

只要保持系统时刻在安全状态，便可避免死锁。假设系统中并发存在n个进程，分别为P₁，P₂,…,P_n，如果按照某种序列顺序进行分配资源，使得n个进程都能顺利完成资源分配，则该序列称为安全序列，此时系统处于安全状态。通过一个实例说明，例如有4个进程共享20个同类资源，进程P₁共需15个资源，进程P₂共需5个资源，进程P₃共需8个资源，进程P₄共需10个资源。假设在T_n时刻，P₁、P₂、P₃、P₄分别已经获得8、4、4、2个资源，尚有2个空闲资源未分配。经过分析，T_n时刻是安全的，因为存在一个安全序列< P₁，P₂，P₃，P₄>，只要系统按此进程序列分配资源，每个进程都可以完成资源分配；反之，系统处于不安全状态。如果满足系统安全性条件，则可以分配；否则暂不分配，以免系统进入不安全状态。

综上所述，本文借用安全性检查算法，将剩余未分配的空闲资源K作为递归的边界条件，不断地寻找合法的节点进入请求集，判断下一个节点进入的合法性可以确定当前节点进入的合法性，进而确定出一组合理的安全序列防止死锁问题的发生。这种思想在处理多用户操作系统资源配置问题中是一个创新点和突破点，值得继续优化和深入研究。

银行家算法可以有效避免死锁，该算法最初是用于银行贷款^[9]。如果存在某个状态序列，能满足所有客户的贷款需求，则该状态是安全的；反之，则可能导致发生死锁。若安全检查结果表明系统处于危险状态，则该请求不合法；反之，请求合法。

算法中存在4类数据类型。1)第1类数据类型称为可利用资源向量，该向量随资源分配、回收动态变化，用含有m个元素的一维数组A_v。2)第2类数据类型称为最大需求矩阵，用M矩阵表示。3)第3类数据类型称为分配矩阵，表示每一类资源已分配给每个进程的资源数量，用A_l矩阵表示。4)第4类数据类型称为需求矩阵，用N矩阵表示。

算法包括系统分配资源流程及系统安全性检查流程。

1)系统分配资源步骤：

a)当满足R_i≤N_ij条件时，执行下一步操作，否则程序返回false；

b)初始化假设F_i=false，满足一定条件则置为true；

c)假设系统试分配及安全性检查通过，则可以进行分配，分配算法为

2)系统安全性算法步骤：

a)设置2个向量：工作向量与完成向量。W向量即工作向量，表示系统能够提供给各个进程的资源数量；F向量即完成向量，表示系统能够顺利地为每个进程完成分配。初始化假设F_i=false，满足一定条件则置为true。

b)当某个进程满足条件F_i=false以及N_ij＜W_j，则跳转到步骤c)，否则跳转到步骤d)。

c)当进程P_i获得资源后，可顺利执行，直至完成，并释放该进程分配得到的资源，W_j=W_j+A_l^ij；F_i= true，继续执行步骤b)。

d)如果所有进程的F_i=true都完成，则系统处于安全状态，否则系统将处于一个不够安全的状态，此时不能完成资源分配工作。 本文提出的基于银行家算法的网络爬虫资源分配算法一个重要的特点是将银行家算法中核心的递归思想引入到请求集生成过程中。通过测试每个纳入请求集数组是否合法来决定是否允许当前节点进入。合法指的是当前节点进入之后可以保障下一个节点进入请求集。这种递归思想可称为全局递归思想或完全递归，消耗时间和系统资源较多。局部递归算法指的是：对经过相应初始化处理的请求集求差集，如果请求集不能覆盖系统所有节点，则只对未被表示的节点递归，最后纳入请求集。在初始化请求集的过程中，通过初始化请求集向量N的位置节点，可以减少初始化节点的差集重复率从而降低请求集长度。

采用Visual C++ 6.0设计Windows界面程序。界面分为三部分：参数输入区域、资源分配区域和结果显示区域。用户在参数输入区域输入可利用资源向量A_v等信息，单击动态添加按键添加进程资源，单击安全检查，可以检查当前所有进程对当前资源的申请是否安全，是否会使系统因资源不足或其他原因进入不安全状态从而不能完成分配。如果进程申请资源安全，软件则提示安全，否则提示不安全。

软件可以支持最多10类资源进行分配，如图 1所示。可利用资源向量为[5, 5, 5, 5, 5, 5, 5, 5, 5, 5],输入进程名称process0，输入process0最大需求矩阵为[1, 1, 2, 1, 1, 1, 1, 1, 1, 1],process0分配矩阵为[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]，需求矩阵为[1, 1, 2, 1, 1, 1, 1, 1, 1, 1]，完成输入之后单击“动态添加”按键添加进程成功。单击“安全检查”按键，即提示系统状态安全，可以执行分配操作。

图 1 软件安全性检查 Fig. 1 Software security check

图选项

开始执行分配，在进程名称文本框输入“process0”以及申请资源量。假设输入的申请资源量为[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]，单击“申请资源”，软件弹出“资源分配后安全，可以分配”的消息提示框，表明输入的资源量可以满足申请要求并执行申请请求。单击确认，进程process0已经分配资源为[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],尚需分配资源为[0, 0, 1, 0, 0, 0, 0, 0, 0, 0]，表明process0申请资源成功。此时系统可用资源数向量由原来的[5, 5, 5, 5, 5, 5, 5, 5, 5, 5]变为[4, 4, 4, 4, 4, 4, 4, 4, 4, 4]，系统为进程process0分配资源成功，如图 2所示。

图 2 进程分配资源成功 Fig. 2 Allocation successfulness for processes

图选项

2.4 实验结果

本文算法和urllib2爬虫算法对死锁问题进行测试实验对比。urllib2是Python中处理HTTP协议的算法库，可用于监测网络爬虫资源的死锁^[16]。设置超时时间为2 m，当爬虫资源发生死锁后超时，记录该任务的状态为Locked，完成其他任务后重启该任务；未发生死锁从而完成任务请求，则记录改任务的状态为Completed，并记录等待时间。urllib2爬虫算法抓取日志如表 1所示，本文算法抓取日志如表 2所示。

分别采用urllib2爬虫算法和本文算法进行100次请求操作，如果在超时时间之内，爬虫资源完成请求操作，则日志中记录该次请求操作为Completed，反之在所设置的超时时间之内未能请求成功，则日志中记录该次请求操作为Locked，表示发生死锁。本文算法和urllib2爬虫算法死锁边界时间如图 3所示，纵坐标表示任务等待时间，横坐标表示测试实验的时间范围为19:47:08—22:08:43，等待时间等于2 min表明任务请求发生死锁，小于2 min表明任务请求完成。

图 3 死锁边界时间 Fig. 3 Deadlock boundary time

图选项

Urllib2爬虫算法等待时间合计为2 h 9 min 7 s，死锁次数为30次，死锁率为30%；银行家算法等待时间合计为1 h 38 min 28 s，死锁次数为2次，死锁率为2%，算法对比实验结果如表 3所示。实验结果表明，本文算法明显降低了死锁率，提高了系统运行效率。传统资源配置算法死锁率高、效率低下。

本文基于银行家算法，在多用户操作系统中，提出一种新的网络爬虫资源配置策略。这种基于银行家算法的网络爬虫资源配置策略不但提高了网络爬虫资源的利用率，而且能够有效避免死锁的发生。下一步的研究工作可以在目前己有的策略上有针对性、方向性地进一步分析和研究降低死锁率的方法。