第10卷第3期 智能系统学报 Vol.10 No.3 2015年6月 CAAI Transactions on Intelligent Systems Jun.2015 D0:10.3969/j.issn.1673-4785.201409021 网络出版地址：http://www.cnki.net/kcms/detail/23.1538.tp.20150514.1432.001.html 一种基于银行家算法的网络爬虫资源配置策略 王庆红，李广凯，周育忠，韦嵘晖 (南方电网科学研究院有限责任公司技术情报所，广东广州510080) 摘要：死锁是多用户操作系统正常运行的一个重要问题，系统资源不足会导致爬虫算法进入不安全状态，进而引 发死锁等问题。引入被广泛用于操作系统的银行家算法，调度多个网络爬虫进程并发运行，并且为每个进程合理分 配系统资源，当进程无法获取系统资源时，则等待其他进程分配完成后释放系统资源，从而完成资源分配，有效降低 死锁率。采用C++编程，设计并实现基于银行家算法的网络爬虫配置策略。通过2h21mim35s工程测试，rlb2 算法死锁率为30%，新算法死锁率仅为2%，测试证明该策略能够有效降低死锁率，能高效完成多个任务进程的资源 分配。 关键词：操作系统：资源配置：死锁：系统安全；银行家算法：网络爬虫 中图分类号：TP361;TM75文献标志码：A文章编号：1673-4785(2015)03-0494-05 中文引用格式：王庆红，李广凯，周育忠，等.一种基于银行家算法的网络爬虫资源配置策略[J】.智能系统学报，2015,10(3)：494498. 英文引用格式：WANG Qinghong,LI Guangkai,ZHOU Yuzhong,tal.A web crawler resource allocation strategy based on the Banker's algorithm[J].CAAI Transactions on Intelligent Systems,2015,10(3):494-498. A web crawler resource allocation strategy based on the Banker's algorithm WANG Qinghong,LI Guangkai,ZHOU Yuzhong,WEI Ronghui (Technology Information Department,Electric Power Research Institute of China Southern Power Grid,Guangzhou 510080.China) Abstract:Deadlock is a major issue for the normal operation of a multi-user operating system.Insufficient sys- tem resource will make the crawler algorithm go into the unsafe state,which will further cause problems such as deadlock.The introduction of the Banker's algorithm,which is widely used in the operating system can schedule multiple web crawler processes running concurrently and allocate system resources rationally for each process.When the process is unable to get the system resources,the other processes need to release resources to complete the allocation of resources,thereby reducing the rate of deadlock effectively.In this paper,a web crawler resource allocation strategy based on Banker's algorithm is designed and implemented using C++pro- gramming.After approximately 2.5 hours of engineering testing the results showed that,the deadlock rate of urllib2 algorithm is 30%and the improved algorithm is only 2%.It is proven that the improved algorithm can reduce deadlock rate effectively and complete resource allocation for multi-process with high efficiency. Keywords:operating system;resource allocation;deadlock;system safety;Banker's algorithm;web crawler 网络爬虫资源分配不足会导致发生死锁，发生 法，通过理论分析证明了理想条件下可以避免死锁。 死锁的爬虫进程无法继续运行，必须通过释放爬虫 Wang)通过实验验证了银行家算法在判断系统安 资源重新抓取网页信息，因此造成爬虫算法效率低 全性中的有效性。本文研究的多用户操作系统属于 下。G.Ricart等研究并实现了计算机网络优化算 共享资源系统，Hao等3-刂研究了共享资源系统的 鲁棒死锁控制方法。Petri网可用于描述多用户操 收稿日期：2014-09-12.网络出版日期：2015-05-14. 作系统模型，Ma等)将银行家算法用于解决Peti 通信作者：王庆红.E-mail:wangghe@csg.cn
第 １０ 卷第 ３ 期 智 能 系 统 学 报 Ｖｏｌ．１０ №．３ ２０１５ 年 ６ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｊｕｎ． ２０１５ ＤＯＩ：１０．３９６９ ／ ｊ．ｉｓｓｎ．１６７３⁃４７８５．２０１４０９０２１ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ｔｐ．２０１５０５１４．１４３２．００１．ｈｔｍｌ 一种基于银行家算法的网络爬虫资源配置策略 王庆红，李广凯，周育忠，韦嵘晖 （南方电网科学研究院有限责任公司 技术情报所，广东 广州 ５１００８０） 摘 要：死锁是多用户操作系统正常运行的一个重要问题，系统资源不足会导致爬虫算法进入不安全状态，进而引 发死锁等问题。 引入被广泛用于操作系统的银行家算法，调度多个网络爬虫进程并发运行，并且为每个进程合理分 配系统资源，当进程无法获取系统资源时，则等待其他进程分配完成后释放系统资源，从而完成资源分配，有效降低 死锁率。 采用 Ｃ＋＋编程，设计并实现基于银行家算法的网络爬虫配置策略。 通过 ２ ｈ ２１ ｍｉｎ ３５ ｓ 工程测试，ｕｒｌｌｉｂ２ 算法死锁率为 ３０％，新算法死锁率仅为 ２％，测试证明该策略能够有效降低死锁率，能高效完成多个任务进程的资源 分配。 关键词：操作系统；资源配置；死锁；系统安全；银行家算法；网络爬虫 中图分类号：ＴＰ３６１； ＴＭ７５ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１５）０３⁃０４９４⁃０５ 中文引用格式：王庆红，李广凯，周育忠，等． 一种基于银行家算法的网络爬虫资源配置策略［Ｊ］． 智能系统学报， ２０１５， １０（３）： ４９４⁃４９８． 英文引用格式：ＷＡＮＧ Ｑｉｎｇｈｏｎｇ， ＬＩ Ｇｕａｎｇｋａｉ， ＺＨＯＵ Ｙｕｚｈｏｎｇ， ｅｔ ａｌ． Ａ ｗｅｂ ｃｒａｗｌｅｒ ｒｅｓｏｕｒｃｅ ａｌｌｏｃａｔｉｏｎ ｓｔｒａｔｅｇｙ ｂａｓｅｄ ｏｎ ｔｈｅ Ｂａｎｋｅｒ＇ｓ ａｌｇｏｒｉｔｈｍ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１５， １０（３）： ４９４⁃４９８． Ａ ｗｅｂ ｃｒａｗｌｅｒ ｒｅｓｏｕｒｃｅ ａｌｌｏｃａｔｉｏｎ ｓｔｒａｔｅｇｙ ｂａｓｅｄ ｏｎ ｔｈｅ Ｂａｎｋｅｒ＇ｓ ａｌｇｏｒｉｔｈｍ ＷＡＮＧ Ｑｉｎｇｈｏｎｇ， ＬＩ Ｇｕａｎｇｋａｉ， ＺＨＯＵ Ｙｕｚｈｏｎｇ， ＷＥＩ Ｒｏｎｇｈｕｉ （Ｔｅｃｈｎｏｌｏｇｙ Ｉｎｆｏｒｍａｔｉｏｎ Ｄｅｐａｒｔｍｅｎｔ， Ｅｌｅｃｔｒｉｃ Ｐｏｗｅｒ Ｒｅｓｅａｒｃｈ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｃｈｉｎａ Ｓｏｕｔｈｅｒｎ Ｐｏｗｅｒ Ｇｒｉｄ， Ｇｕａｎｇｚｈｏｕ ５１００８０， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｄｅａｄｌｏｃｋ ｉｓ ａ ｍａｊｏｒ ｉｓｓｕｅ ｆｏｒ ｔｈｅ ｎｏｒｍａｌ ｏｐｅｒａｔｉｏｎ ｏｆ ａ ｍｕｌｔｉ⁃ｕｓｅｒ ｏｐｅｒａｔｉｎｇ ｓｙｓｔｅｍ． Ｉｎｓｕｆｆｉｃｉｅｎｔ ｓｙｓ⁃ ｔｅｍ ｒｅｓｏｕｒｃｅ ｗｉｌｌ ｍａｋｅ ｔｈｅ ｃｒａｗｌｅｒ ａｌｇｏｒｉｔｈｍ ｇｏ ｉｎｔｏ ｔｈｅ ｕｎｓａｆｅ ｓｔａｔｅ， ｗｈｉｃｈ ｗｉｌｌ ｆｕｒｔｈｅｒ ｃａｕｓｅ ｐｒｏｂｌｅｍｓ ｓｕｃｈ ａｓ ｄｅａｄｌｏｃｋ． Ｔｈｅ ｉｎｔｒｏｄｕｃｔｉｏｎ ｏｆ ｔｈｅ Ｂａｎｋｅｒ＇ｓ ａｌｇｏｒｉｔｈｍ， ｗｈｉｃｈ ｉｓ ｗｉｄｅｌｙ ｕｓｅｄ ｉｎ ｔｈｅ ｏｐｅｒａｔｉｎｇ ｓｙｓｔｅｍ ｃａｎ ｓｃｈｅｄｕｌｅ ｍｕｌｔｉｐｌｅ ｗｅｂ ｃｒａｗｌｅｒ ｐｒｏｃｅｓｓｅｓ ｒｕｎｎｉｎｇ ｃｏｎｃｕｒｒｅｎｔｌｙ ａｎｄ ａｌｌｏｃａｔｅ ｓｙｓｔｅｍ ｒｅｓｏｕｒｃｅｓ ｒａｔｉｏｎａｌｌｙ ｆｏｒ ｅａｃｈ ｐｒｏｃｅｓｓ． Ｗｈｅｎ ｔｈｅ ｐｒｏｃｅｓｓ ｉｓ ｕｎａｂｌｅ ｔｏ ｇｅｔ ｔｈｅ ｓｙｓｔｅｍ ｒｅｓｏｕｒｃｅｓ， ｔｈｅ ｏｔｈｅｒ ｐｒｏｃｅｓｓｅｓ ｎｅｅｄ ｔｏ ｒｅｌｅａｓｅ ｒｅｓｏｕｒｃｅｓ ｔｏ ｃｏｍｐｌｅｔｅ ｔｈｅ ａｌｌｏｃａｔｉｏｎ ｏｆ ｒｅｓｏｕｒｃｅｓ， ｔｈｅｒｅｂｙ ｒｅｄｕｃｉｎｇ ｔｈｅ ｒａｔｅ ｏｆ ｄｅａｄｌｏｃｋ ｅｆｆｅｃｔｉｖｅｌｙ． Ｉｎ ｔｈｉｓ ｐａｐｅｒ， ａ ｗｅｂ ｃｒａｗｌｅｒ ｒｅｓｏｕｒｃｅ ａｌｌｏｃａｔｉｏｎ ｓｔｒａｔｅｇｙ ｂａｓｅｄ ｏｎ Ｂａｎｋｅｒ＇ｓ ａｌｇｏｒｉｔｈｍ ｉｓ ｄｅｓｉｇｎｅｄ ａｎｄ ｉｍｐｌｅｍｅｎｔｅｄ ｕｓｉｎｇ Ｃ＋＋ ｐｒｏ⁃ ｇｒａｍｍｉｎｇ． Ａｆｔｅｒ ａｐｐｒｏｘｉｍａｔｅｌｙ ２． ５ ｈｏｕｒｓ ｏｆ ｅｎｇｉｎｅｅｒｉｎｇ ｔｅｓｔｉｎｇ ｔｈｅ ｒｅｓｕｌｔｓ ｓｈｏｗｅｄ ｔｈａｔ， ｔｈｅ ｄｅａｄｌｏｃｋ ｒａｔｅ ｏｆ ｕｒｌｌｉｂ２ ａｌｇｏｒｉｔｈｍ ｉｓ ３０％ ａｎｄ ｔｈｅ ｉｍｐｒｏｖｅｄ ａｌｇｏｒｉｔｈｍ ｉｓ ｏｎｌｙ ２％． Ｉｔ ｉｓ ｐｒｏｖｅｎ ｔｈａｔ ｔｈｅ ｉｍｐｒｏｖｅｄ ａｌｇｏｒｉｔｈｍ ｃａｎ ｒｅｄｕｃｅ ｄｅａｄｌｏｃｋ ｒａｔｅ ｅｆｆｅｃｔｉｖｅｌｙ ａｎｄ ｃｏｍｐｌｅｔｅ ｒｅｓｏｕｒｃｅ ａｌｌｏｃａｔｉｏｎ ｆｏｒ ｍｕｌｔｉ⁃ｐｒｏｃｅｓｓ ｗｉｔｈ ｈｉｇｈ ｅｆｆｉｃｉｅｎｃｙ． Ｋｅｙｗｏｒｄｓ：ｏｐｅｒａｔｉｎｇ ｓｙｓｔｅｍ； ｒｅｓｏｕｒｃｅ ａｌｌｏｃａｔｉｏｎ； ｄｅａｄｌｏｃｋ； ｓｙｓｔｅｍ ｓａｆｅｔｙ； Ｂａｎｋｅｒ＇ｓ ａｌｇｏｒｉｔｈｍ； ｗｅｂ ｃｒａｗｌｅｒ 收稿日期：２０１４⁃０９⁃１２． 网络出版日期：２０１５⁃０５⁃１４． 通信作者：王庆红． Ｅ⁃ｍａｉｌ： ｗａｎｇｑｈ＠ ｃｓｇ．ｃｎ． 网络爬虫资源分配不足会导致发生死锁，发生 死锁的爬虫进程无法继续运行，必须通过释放爬虫 资源重新抓取网页信息，因此造成爬虫算法效率低 下。 Ｇ． Ｒｉｃａｒｔ 等［１］研究并实现了计算机网络优化算 法，通过理论分析证明了理想条件下可以避免死锁。 Ｗａｎｇ ［２］ 通过实验验证了银行家算法在判断系统安 全性中的有效性。 本文研究的多用户操作系统属于 共享资源系统，Ｈａｏ 等［３－４］ 研究了共享资源系统的 鲁棒死锁控制方法。 Ｐｅｔｒｉ 网可用于描述多用户操 作系统模型，Ｍａ 等［５］ 将银行家算法用于解决 Ｐｅｔｒｉ
第3期 王庆红，等：一种基于银行家算法的网络爬虫资源配置策略 ·495· 网中的死锁问题，有效降低了死锁率，表明银行家算 并发性是导致发生死锁的原因，当系统无法满足进 法可应用于解决多用户操作系统的死锁问题。多处 程的资源请求时，资源申请失败导致发生死锁。 理器片上系统适用于多用户操作系统，Xiao等[6研 1.2死锁 究了多处理器片上系统上的死锁问题，提出了一种 在多用户操作系统，进程是并发执行的，但是存 硬件死锁检测算法。多用户操作系统的死锁问题本 在一种危险一死锁。若无内部鲁棒容错或外部干 质上是多进程访问公共资源导致的死锁问题，Lou 预，系统将长期处于封锁状态。竞争资源及进程推 等)研究了多进程访问公共资源导致的死锁问题， 进顺序非法是导致死锁的主要原因。在当前资源限 提出了一种避免死锁的算法，实验结果表明该算法 制下，寻找一组资源分配的执行顺序，从而避免产生 有效地解决了分布式事务管理系统中的死锁问题。 死锁，是本文研究的主要内容。将银行家算法为避 S.A.Reveliotis等[s劉研究的多车辆系统资源配置算 免死锁获取安全进程序列的递归思想，借鉴到网络 法解决死锁问题。Lang等[)基于银行家算法提出 爬虫算法中。将请求集长度作为一个变量，边界条 了二次时间算法，更好地实现了操作系统资源优化 件为请求集长度及节点状态数组，从而能够确定请 配置。本文研究的网络爬虫配置策略基于Windows 求集节点的合法性。该算法的时间复杂度比rlib2 操作系统进行开发，Windows操作系统是基于事件 算法较小，并且能够获得最优请求集长度。 驱动的程序模型，Tang等[o]提出了一种在事件处理 1.3安全状态 系统中有效避免死锁的方法。Duda等)将Cache 只要保持系统时刻在安全状态，便可避免死锁。 模块增加到爬虫系统中，并采用了热点检测机制，避 假设系统中并发存在n个进程，分别为P,P2,…, 免从服务器端重复地获取相同内容，采用MFC编程 P,如果按照某种序列顺序进行分配资源，使得个 设计并实现了基于银行家算法的网络爬虫资源配置 进程都能顺利完成资源分配，则该序列称为安全序 应用软件，增加Cache模块的设计并引入热点检测 列，此时系统处于安全状态。通过一个实例说明，例 机制，提高了系统的运行效率。Peng等f]将Ajax 如有4个进程共享20个同类资源，进程P,共需15 页面状态的抓取转换为DRPP,在完全状态转换图 个资源，进程P,共需5个资源，进程P,共需8个资 拓扑结构已知的情况下，核心状态转换图增加少量 源，进程P,共需10个资源。假设在T时刻，P,、P2、 取自它的边后成为平衡、强连通图，该欧拉回路即为 P3、P4分别已经获得8、4、4、2个资源，尚有2个空闲 最优搜索路径，从而提高了效率。杨梅等]针对银 资源未分配。经过分析，T时刻是安全的，因为存在 行家算法中的安全分配算法进行了研究，该算法缩 一个安全序列,只要系统按此进程 小了安全检查的范围，提高了系统效率。陈昊成 序列分配资源，每个进程都可以完成资源分配：反 针对预防死锁问题和调度策略问题提出了解决方 之，系统处于不安全状态。如果满足系统安全性条 案，应用于资源管理分配系统。章韵等经过仿真 件，则可以分配：否则暂不分配，以免系统进入不安 实验提出了一种资源分配算法，实验结果证明该算 全状态。 法可以有效避免死锁。 综上所述，本文借用安全性检查算法，将剩余未 以上研究成果表明，银行家算法是一种避免死 分配的空闲资源K作为递归的边界条件，不断地寻 锁的有效算法。本文提出了基于银行家算法的网络 找合法的节点进入请求集，判断下一个节点进入的 爬虫资源分配策略，以降低多任务处理系统的死锁 合法性可以确定当前节点进入的合法性，进而确定 率，提高网络爬虫资源的利用率，避免死锁的发生。 出一组合理的安全序列防止死锁问题的发生。这种 思想在处理多用户操作系统资源配置问题中是一个 1 基本概念 创新点和突破点，值得继续优化和深入研究。 1.1多用户操作系统 根据在同一时间最多允许多少个用户同时操作 2银行家算法 计算机，操作系统可分为单用户操作系统和多用户 银行家算法可以有效避免死锁，该算法最初是 操作系统。同一时间内允许多个用户同时使用计算 用于银行贷款)。如果存在某个状态序列，能满足 机，称为多用户操作系统：反之，同一时间内最多允 所有客户的贷款需求，则该状态是安全的：反之，则 许一个用户操作计算机，则称为单用户操作系统。 可能导致发生死锁。若安全检查结果表明系统处于 常见的多用户操作系统有Windows Server2OO3和 危险状态，则该请求不合法：反之，请求合法。 Windows Server2OO8等。系统资源的有限性及进程
网中的死锁问题，有效降低了死锁率，表明银行家算 法可应用于解决多用户操作系统的死锁问题。 多处 理器片上系统适用于多用户操作系统，Ｘｉａｏ 等［６］ 研 究了多处理器片上系统上的死锁问题，提出了一种 硬件死锁检测算法。 多用户操作系统的死锁问题本 质上是多进程访问公共资源导致的死锁问题，Ｌｏｕ 等［７］研究了多进程访问公共资源导致的死锁问题， 提出了一种避免死锁的算法，实验结果表明该算法 有效地解决了分布式事务管理系统中的死锁问题。 Ｓ． Ａ． Ｒｅｖｅｌｉｏｔｉｓ 等［８］研究的多车辆系统资源配置算 法解决死锁问题。 Ｌａｎｇ 等［９］ 基于银行家算法提出 了二次时间算法，更好地实现了操作系统资源优化 配置。 本文研究的网络爬虫配置策略基于 Ｗｉｎｄｏｗｓ 操作系统进行开发，Ｗｉｎｄｏｗｓ 操作系统是基于事件 驱动的程序模型，Ｔａｎｇ 等［１０］提出了一种在事件处理 系统中有效避免死锁的方法。 Ｄｕｄａ 等［１１］ 将 Ｃａｃｈｅ 模块增加到爬虫系统中，并采用了热点检测机制，避 免从服务器端重复地获取相同内容，采用 ＭＦＣ 编程 设计并实现了基于银行家算法的网络爬虫资源配置 应用软件，增加 Ｃａｃｈｅ 模块的设计并引入热点检测 机制，提高了系统的运行效率。 Ｐｅｎｇ 等［１２］ 将 Ａｊａｘ 页面状态的抓取转换为 ＤＲＰＰ，在完全状态转换图 拓扑结构已知的情况下，核心状态转换图增加少量 取自它的边后成为平衡、强连通图，该欧拉回路即为 最优搜索路径，从而提高了效率。 杨梅等［１３］ 针对银 行家算法中的安全分配算法进行了研究，该算法缩 小了安全检查的范围，提高了系统效率。 陈昊成［１４］ 针对预防死锁问题和调度策略问题提出了解决方 案，应用于资源管理分配系统。 章韵等［１５］ 经过仿真 实验提出了一种资源分配算法，实验结果证明该算 法可以有效避免死锁。 以上研究成果表明，银行家算法是一种避免死 锁的有效算法。 本文提出了基于银行家算法的网络 爬虫资源分配策略，以降低多任务处理系统的死锁 率，提高网络爬虫资源的利用率，避免死锁的发生。 １ 基本概念 １．１ 多用户操作系统 根据在同一时间最多允许多少个用户同时操作 计算机，操作系统可分为单用户操作系统和多用户 操作系统。 同一时间内允许多个用户同时使用计算 机，称为多用户操作系统；反之，同一时间内最多允 许一个用户操作计算机，则称为单用户操作系统。 常见的多用户操作系统有 Ｗｉｎｄｏｗｓ Ｓｅｒｖｅｒ ２００３ 和 Ｗｉｎｄｏｗｓ Ｓｅｒｖｅｒ ２００８ 等。 系统资源的有限性及进程 并发性是导致发生死锁的原因，当系统无法满足进 程的资源请求时，资源申请失败导致发生死锁。 １．２ 死锁 在多用户操作系统，进程是并发执行的，但是存 在一种危险—死锁。 若无内部鲁棒容错或外部干 预，系统将长期处于封锁状态。 竞争资源及进程推 进顺序非法是导致死锁的主要原因。 在当前资源限 制下，寻找一组资源分配的执行顺序，从而避免产生 死锁，是本文研究的主要内容。 将银行家算法为避 免死锁获取安全进程序列的递归思想，借鉴到网络 爬虫算法中。 将请求集长度作为一个变量，边界条 件为请求集长度及节点状态数组，从而能够确定请 求集节点的合法性。 该算法的时间复杂度比 ｕｒｌｌｉｂ２ 算法较小，并且能够获得最优请求集长度。 １．３ 安全状态 只要保持系统时刻在安全状态，便可避免死锁。 假设系统中并发存在 ｎ 个进程，分别为 Ｐ１ ，Ｐ２ ， …， Ｐｎ ，如果按照某种序列顺序进行分配资源，使得 ｎ 个 进程都能顺利完成资源分配，则该序列称为安全序 列，此时系统处于安全状态。 通过一个实例说明，例 如有 ４ 个进程共享 ２０ 个同类资源，进程 Ｐ１共需 １５ 个资源，进程 Ｐ２共需 ５ 个资源，进程 Ｐ３共需 ８ 个资 源，进程 Ｐ４共需 １０ 个资源。 假设在 Ｔｎ时刻，Ｐ１ 、Ｐ２ 、 Ｐ３ 、Ｐ４分别已经获得 ８、４、４、２ 个资源，尚有 ２ 个空闲 资源未分配。 经过分析，Ｔｎ时刻是安全的，因为存在 一个安全序列＜Ｐ １ ，Ｐ２ ，Ｐ３ ，Ｐ４ ＞，只要系统按此进程 序列分配资源，每个进程都可以完成资源分配；反 之，系统处于不安全状态。 如果满足系统安全性条 件，则可以分配；否则暂不分配，以免系统进入不安 全状态。 综上所述，本文借用安全性检查算法，将剩余未 分配的空闲资源 Ｋ 作为递归的边界条件，不断地寻 找合法的节点进入请求集，判断下一个节点进入的 合法性可以确定当前节点进入的合法性，进而确定 出一组合理的安全序列防止死锁问题的发生。 这种 思想在处理多用户操作系统资源配置问题中是一个 创新点和突破点，值得继续优化和深入研究。 ２ 银行家算法 银行家算法可以有效避免死锁，该算法最初是 用于银行贷款［９］ 。 如果存在某个状态序列，能满足 所有客户的贷款需求，则该状态是安全的；反之，则 可能导致发生死锁。 若安全检查结果表明系统处于 危险状态，则该请求不合法；反之，请求合法。 第 ３ 期 王庆红，等：一种基于银行家算法的网络爬虫资源配置策略 ·４９５·
·496· 智能系统学报 第10卷 2.1算法数据结构 求集的过程中，通过初始化请求集向量N的位置节 算法中存在4类数据类型。1)第1类数据类型 点，可以减少初始化节点的差集重复率从而降低请 称为可利用资源向量，该向量随资源分配、回收动态 求集长度。 变化，用含有m个元素的一维数组A,。2)第2类数 2.3算法设计与实现 据类型称为最大需求矩阵，用M矩阵表示。3)第3 采用Visual C++6.0设计Windows界面程序。 类数据类型称为分配矩阵，表示每一类资源已分配 界面分为三部分：参数输入区域、资源分配区域和结 给每个进程的资源数量，用A矩阵表示。4)第4类 果显示区域。用户在参数输入区域输入可利用资源 数据类型称为需求矩阵，用N矩阵表示。 向量A等信息，单击动态添加按键添加进程资源， 2.2银行家算法流程 单击安全检查，可以检查当前所有进程对当前资源 算法包括系统分配资源流程及系统安全性检查 的申请是否安全，是否会使系统因资源不足或其他 流程。 原因进入不安全状态从而不能完成分配。如果进程 1)系统分配资源步骤： 申请资源安全，软件则提示安全，否则提示不安全。 a)当满足R≤N条件时，执行下一步操作，否 软件可以支持最多10类资源进行分配，如图1 则程序返回false; 所示。可利用资源向量为[5,5,5,5,5,5,5,5,5， b)初始化假设F,=false,满足一定条件则置 5],输入进程名称process0(,输入process0最大需求矩 为true; 阵为[1,1,2,1,1,1,1,1,1,1]，process0(分配矩 c)假设系统试分配及安全性检查通过，则可以 阵为[0,0,0,0,0,0,0,0,0,0]，需求矩阵为[1， 进行分配，分配算法为 1,2,1,1,1,1,1,1,1],完成输入之后单击“动态 A.:=A,-R 添加”按键添加进程成功。单击“安全检查”按键，即 A:=A+R 提示系统状态安全，可以执行分配操作。 N:=N:-R 2)系统安全性算法步骤： 指无有中 a)设置2个向量：工作向量与完成向量。W向 量即工作向量，表示系统能够提供给各个进程的资 源数量：F向量即完成向量，表示系统能够顺利地为 m图 每个进程完成分配。初始化假设F,=false,满足一 定条件则置为true。 b)当某个进程满足条件F,=false以及N,<W, 则跳转到步骤c),否则跳转到步骤d)。 c)当进程P,获得资源后，可顺利执行，直至 图1软件安全性检查 完成，并释放该进程分配得到的资源，W=W+ Fig.1 Software security check A可；F:=true,继续执行步骤b)。 d)如果所有进程的F:=rue都完成，则系统处 开始执行分配，在进程名称文本框输入 于安全状态，否则系统将处于一个不够安全的状态， “process0”以及申请资源量。假设输人的申请资源 此时不能完成资源分配工作。 量为[1,1,1,1,1,1,1,1,1,1]，单击“申请资 本文提出的基于银行家算法的网络爬虫资源分 源”，软件弹出“资源分配后安全，可以分配”的消息 配算法一个重要的特点是将银行家算法中核心的递 提示框，表明输入的资源量可以满足申请要求并执 归思想引入到请求集生成过程中。通过测试每个纳 行申请请求。单击确认，进程process(0已经分配资 入请求集数组是否合法来决定是否允许当前节点进 源为[1,1,1,1,1,1,1,1,1,1]，尚需分配资源 入。合法指的是当前节点进入之后可以保障下一个 为[0,0,1,0,0,0,0,0,0,0]，表明process(0申 节点进入请求集。这种递归思想可称为全局递归思 请资源成功。此时系统可用资源数向量由原来的 想或完全递归，消耗时间和系统资源较多。局部递 [5,5,5,5,5,5,5,5,5,5]变为[4,4,4,4,4， 归算法指的是：对经过相应初始化处理的请求集求 4,4,4,4,4],系统为进程process(0分配资源成功， 差集，如果请求集不能覆盖系统所有节点，则只对未 如图2所示。 被表示的节点递归，最后纳入请求集。在初始化请
２．１ 算法数据结构 算法中存在 ４ 类数据类型。 １）第 １ 类数据类型 称为可利用资源向量，该向量随资源分配、回收动态 变化，用含有 ｍ 个元素的一维数组 Ａｖ。 ２）第 ２ 类数 据类型称为最大需求矩阵，用 Ｍ 矩阵表示。 ３）第 ３ 类数据类型称为分配矩阵，表示每一类资源已分配 给每个进程的资源数量，用 Ａｌ矩阵表示。 ４）第 ４ 类 数据类型称为需求矩阵，用 Ｎ 矩阵表示。 ２．２ 银行家算法流程 算法包括系统分配资源流程及系统安全性检查 流程。 １）系统分配资源步骤： ａ）当满足 Ｒｉ≤Ｎｉｊ条件时，执行下一步操作，否 则程序返回 ｆａｌｓｅ； ｂ）初始化假设 Ｆｉ ＝ ｆａｌｓｅ，满足一定条件则置 为 ｔｒｕｅ； ｃ）假设系统试分配及安全性检查通过，则可以 进行分配，分配算法为 Ａｖ： ＝ Ａｖ － Ｒｉ Ａｌ ｉ ： ＝ Ａｌ ｉ ＋ Ｒｉ Ｎｉ： ＝ Ｎｉ － Ｒｉ ２）系统安全性算法步骤： ａ）设置 ２ 个向量：工作向量与完成向量。 Ｗ 向 量即工作向量，表示系统能够提供给各个进程的资 源数量；Ｆ 向量即完成向量，表示系统能够顺利地为 每个进程完成分配。 初始化假设 Ｆｉ ＝ ｆａｌｓｅ，满足一 定条件则置为 ｔｒｕｅ。 ｂ）当某个进程满足条件 Ｆｉ ＝ ｆａｌｓｅ 以及 Ｎｉｊ ＜Ｗｊ， 则跳转到步骤 ｃ），否则跳转到步骤 ｄ）。 ｃ）当进程 Ｐｉ获得资源后，可顺利执行，直至 完成，并释放该进程分配得到的资源， Ｗｊ ＝ Ｗｊ ＋ Ａｌ ｉｊ ；Ｆｉ ＝ ｔｒｕｅ，继续执行步骤 ｂ） 。 ｄ）如果所有进程的 Ｆｉ ＝ ｔｒｕｅ 都完成，则系统处 于安全状态，否则系统将处于一个不够安全的状态， 此时不能完成资源分配工作。 本文提出的基于银行家算法的网络爬虫资源分 配算法一个重要的特点是将银行家算法中核心的递 归思想引入到请求集生成过程中。 通过测试每个纳 入请求集数组是否合法来决定是否允许当前节点进 入。 合法指的是当前节点进入之后可以保障下一个 节点进入请求集。 这种递归思想可称为全局递归思 想或完全递归，消耗时间和系统资源较多。 局部递 归算法指的是：对经过相应初始化处理的请求集求 差集，如果请求集不能覆盖系统所有节点，则只对未 被表示的节点递归，最后纳入请求集。 在初始化请 求集的过程中，通过初始化请求集向量 Ｎ 的位置节 点，可以减少初始化节点的差集重复率从而降低请 求集长度。 ２．３ 算法设计与实现 采用 Ｖｉｓｕａｌ Ｃ＋＋ ６．０ 设计 Ｗｉｎｄｏｗｓ 界面程序。 界面分为三部分：参数输入区域、资源分配区域和结 果显示区域。 用户在参数输入区域输入可利用资源 向量 Ａｖ等信息，单击动态添加按键添加进程资源， 单击安全检查，可以检查当前所有进程对当前资源 的申请是否安全，是否会使系统因资源不足或其他 原因进入不安全状态从而不能完成分配。 如果进程 申请资源安全，软件则提示安全，否则提示不安全。 软件可以支持最多 １０ 类资源进行分配，如图 １ 所示。 可利用资源向量为［５， ５， ５， ５， ５， ５， ５， ５， ５， ５］，输入进程名称 ｐｒｏｃｅｓｓ０，输入 ｐｒｏｃｅｓｓ０ 最大需求矩 阵为［１， １， ２， １， １， １， １， １， １， １］， ｐｒｏｃｅｓｓ０ 分配矩 阵为［０， ０， ０， ０， ０， ０， ０， ０， ０， ０］，需求矩阵为［１， １， ２， １， １， １， １， １， １， １］，完成输入之后单击“动态 添加”按键添加进程成功。 单击“安全检查”按键，即 提示系统状态安全，可以执行分配操作。 图 １ 软件安全性检查 Ｆｉｇ． １ Ｓｏｆｔｗａｒｅ ｓｅｃｕｒｉｔｙ ｃｈｅｃｋ 开 始 执 行 分 配， 在 进 程 名 称 文 本 框 输 入 “ｐｒｏｃｅｓｓ０”以及申请资源量。 假设输入的申请资源 量为［１， １， １， １， １， １， １， １， １， １］，单击“申请资 源”，软件弹出“资源分配后安全，可以分配”的消息 提示框，表明输入的资源量可以满足申请要求并执 行申请请求。 单击确认，进程 ｐｒｏｃｅｓｓ０ 已经分配资 源为［１， １， １， １， １， １， １， １， １， １］，尚需分配资源 为［０， ０， １， ０， ０， ０， ０， ０， ０， ０］，表明 ｐｒｏｃｅｓｓ０ 申 请资源成功。 此时系统可用资源数向量由原来的 ［５， ５， ５， ５， ５， ５， ５， ５， ５， ５］变为［４， ４， ４， ４， ４， ４， ４， ４， ４， ４］，系统为进程 ｐｒｏｃｅｓｓ０ 分配资源成功， 如图 ２ 所示。 ·４９６· 智 能 系 统 学 报 第 １０ 卷
第3期 王庆红，等：一种基于银行家算法的网络爬虫资源配置策略 ·497 表2本文算法抓取日志 Table 2 Banker's algorithm crawl log 任务 死锁 事件 等待时间 中第 开始时间 边界时间 Completed:Requestl 19:47:08 0:00:41 0:02:00 Completed:Request2 19:49:52 0:01:01 0:02:00 Completed:Request3 19:52:13 0:01.05 0:02:00 Locked:Request36 20:42:29 0:02:00 0:02:00 图2进程分配资源成功 Fig.2 Allocation successfulness for processes Locked:Request48 20:58:380:02:00 0:02:00 2.4实验结果 本文算法和ulib2爬虫算法对死锁问题进行 测试实验对比。urllib2是Python中处理HTTP协议 Completed:Request10022:08:430:00:360:02:00 的算法库，可用于监测网络爬虫资源的死锁6)。设 置超时时间为2m,当爬虫资源发生死锁后超时，记 分别采用urllib2爬虫算法和本文算法进行100 录该任务的状态为Locked,完成其他任务后重启该 次请求操作，如果在超时时间之内，爬虫资源完成请 任务：未发生死锁从而完成任务请求，则记录改任务 求操作，则日志中记录该次请求操作为Completed, 的状态为Completed,并记录等待时间。urllib.2爬虫 反之在所设置的超时时间之内未能请求成功，则日 算法抓取日志如表1所示，本文算法抓取日志如表 志中记录该次请求操作为Locked,表示发生死锁。 2所示。 本文算法和uib2爬虫算法死锁边界时间如图3 表1Urib2爬虫算法抓取日志 所示，纵坐标表示任务等待时间，横坐标表示测试实 Table 1 Urllib2 crawler algorithm crawl log 验的时间范围为19：47：08一22：08：43，等待时间等 任务 死锁 于2min表明任务请求发生死锁，小于2min表明任 事 件 等待时间 开始时间 边界时间 务请求完成。 Locked:Requestl 19:47:08 0:02:00 0:02:00 urllib2 0:02:10e 一死锁边界时间一本文算法 Locked:Request2 19:49:52 0:02:00 0:02:00 001：26 Locked:Request3 19:52:130:02:00 0:02:00 0:00:43 Completed:Request4 19.54.38 0:01:21 0:02:00 19:55:59 0:00:00 Completed:Request5 0:02:00 0:02:00 7131925313743495561677379859197103 模拟次数 Completed:Request6 19:58:42 0.01.06 0:02:00 图3死锁边界时间 Locked:Request7 19:59:480:02:00 0:02:00 Fig.3 Deadlock boundary time Completed:Request8 20:02:01 0:00:41 0:02:00 Completed:Request9 20:02:42 0.00.27 0:02:00 Urllib2爬虫算法等待时间合计为2h9min7s, Completed:Request10 20:03:09 0:01:12 0:02:00 死锁次数为30次，死锁率为30%：银行家算法等待时 Completed:Request11 20:04:20 0:01:58 0:02:00 间合计为1h38min28s,死锁次数为2次，死锁率为 Locked:Request12 20:06:18 0:02:00 0:02:00 2%,算法对比实验结果如表3所示。实验结果表明， Completed:Request13 20:09:00 0:00:36 0:02:00 本文算法明显降低了死锁率，提高了系统运行效率。 Completed:Request14 20:09:36 0:00:36 0:02:00 传统资源配置算法死锁率高、效率低下。 Locked:Request15 20:10:120:02:00 0:02:00 表3实验结果对比 Locked:Request16 20:12:260:02:00 0:02:00 Table 3 Comparison of the experimental results Locked:Request17 20:15:170:02:00 0:02:00 算法 等待时间合计死锁次数死锁率/% urib2算法 2:09:07 30 30 Completed:Request100 22:08:43 0:00:36 0:02:00 银行家算法 1:38:28 20
图 ２ 进程分配资源成功 Ｆｉｇ． ２ Ａｌｌｏｃａｔｉｏｎ ｓｕｃｃｅｓｓｆｕｌｎｅｓｓ ｆｏｒ ｐｒｏｃｅｓｓｅｓ ２．４ 实验结果 本文算法和 ｕｒｌｌｉｂ２ 爬虫算法对死锁问题进行 测试实验对比。 ｕｒｌｌｉｂ２ 是 Ｐｙｔｈｏｎ 中处理 ＨＴＴＰ 协议 的算法库，可用于监测网络爬虫资源的死锁［１６］ 。 设 置超时时间为 ２ ｍ，当爬虫资源发生死锁后超时，记 录该任务的状态为 Ｌｏｃｋｅｄ，完成其他任务后重启该 任务；未发生死锁从而完成任务请求，则记录改任务 的状态为 Ｃｏｍｐｌｅｔｅｄ，并记录等待时间。 ｕｒｌｌｉｂ２ 爬虫 算法抓取日志如表 １ 所示，本文算法抓取日志如表 ２ 所示。 表 １ Ｕｒｌｌｉｂ２ 爬虫算法抓取日志 Ｔａｂｌｅ １ Ｕｒｌｌｉｂ２ ｃｒａｗｌｅｒ ａｌｇｏｒｉｔｈｍ ｃｒａｗｌ ｌｏｇ 事 件 任务 开始时间 等待时间 死锁 边界时间 Ｌｏｃｋｅｄ：Ｒｅｑｕｅｓｔ１ １９：４７：０８ ０：０２：００ ０：０２：００ Ｌｏｃｋｅｄ：Ｒｅｑｕｅｓｔ２ １９：４９：５２ ０：０２：００ ０：０２：００ Ｌｏｃｋｅｄ：Ｒｅｑｕｅｓｔ３ １９：５２：１３ ０：０２：００ ０：０２：００ Ｃｏｍｐｌｅｔｅｄ：Ｒｅｑｕｅｓｔ４ １９：５４：３８ ０：０１：２１ ０：０２：００ Ｃｏｍｐｌｅｔｅｄ：Ｒｅｑｕｅｓｔ５ １９：５５：５９ ０：０２：００ ０：０２：００ Ｃｏｍｐｌｅｔｅｄ：Ｒｅｑｕｅｓｔ６ １９：５８：４２ ０：０１：０６ ０：０２：００ Ｌｏｃｋｅｄ：Ｒｅｑｕｅｓｔ７ １９：５９：４８ ０：０２：００ ０：０２：００ Ｃｏｍｐｌｅｔｅｄ：Ｒｅｑｕｅｓｔ８ ２０：０２：０１ ０：００：４１ ０：０２：００ Ｃｏｍｐｌｅｔｅｄ：Ｒｅｑｕｅｓｔ９ ２０：０２：４２ ０：００：２７ ０：０２：００ Ｃｏｍｐｌｅｔｅｄ：Ｒｅｑｕｅｓｔ１０ ２０：０３：０９ ０：０１：１２ ０：０２：００ Ｃｏｍｐｌｅｔｅｄ：Ｒｅｑｕｅｓｔ１１ ２０：０４：２０ ０：０１：５８ ０：０２：００ Ｌｏｃｋｅｄ：Ｒｅｑｕｅｓｔ１２ ２０：０６：１８ ０：０２：００ ０：０２：００ Ｃｏｍｐｌｅｔｅｄ：Ｒｅｑｕｅｓｔ１３ ２０：０９：００ ０：００：３６ ０：０２：００ Ｃｏｍｐｌｅｔｅｄ：Ｒｅｑｕｅｓｔ１４ ２０：０９：３６ ０：００：３６ ０：０２：００ Ｌｏｃｋｅｄ：Ｒｅｑｕｅｓｔ１５ ２０：１０：１２ ０：０２：００ ０：０２：００ Ｌｏｃｋｅｄ：Ｒｅｑｕｅｓｔ１６ ２０：１２：２６ ０：０２：００ ０：０２：００ Ｌｏｃｋｅｄ：Ｒｅｑｕｅｓｔ１７ ２０：１５：１７ ０：０２：００ ０：０２：００ ︙ ︙ ︙ ︙ Ｃｏｍｐｌｅｔｅｄ：Ｒｅｑｕｅｓｔ１００ ２２：０８：４３ ０：００：３６ ０：０２：００ 表 ２ 本文算法抓取日志 Ｔａｂｌｅ ２ Ｂａｎｋｅｒ＇ｓ ａｌｇｏｒｉｔｈｍ ｃｒａｗｌ ｌｏｇ 事 件 任务 开始时间 等待时间 死锁 边界时间 Ｃｏｍｐｌｅｔｅｄ：Ｒｅｑｕｅｓｔ１ １９：４７：０８ ０：００：４１ ０：０２：００ Ｃｏｍｐｌｅｔｅｄ：Ｒｅｑｕｅｓｔ２ １９：４９：５２ ０：０１：０１ ０：０２：００ Ｃｏｍｐｌｅｔｅｄ：Ｒｅｑｕｅｓｔ３ １９：５２：１３ ０：０１：０５ ０：０２：００ ︙ ︙ ︙ ︙ Ｌｏｃｋｅｄ：Ｒｅｑｕｅｓｔ３６ ２０：４２：２９ ０：０２：００ ０：０２：００ ︙ ︙ ︙ ︙ Ｌｏｃｋｅｄ：Ｒｅｑｕｅｓｔ４８ ２０：５８：３８ ０：０２：００ ０：０２：００ ︙ ︙ ︙ ︙ Ｃｏｍｐｌｅｔｅｄ：Ｒｅｑｕｅｓｔ１００ ２２：０８：４３ ０：００：３６ ０：０２：００ 分别采用 ｕｒｌｌｉｂ２ 爬虫算法和本文算法进行 １００ 次请求操作，如果在超时时间之内，爬虫资源完成请 求操作，则日志中记录该次请求操作为 Ｃｏｍｐｌｅｔｅｄ， 反之在所设置的超时时间之内未能请求成功，则日 志中记录该次请求操作为 Ｌｏｃｋｅｄ，表示发生死锁。 本文算法和 ｕｒｌｌｉｂ２ 爬虫算法死锁边界时间如图 ３ 所示，纵坐标表示任务等待时间，横坐标表示测试实 验的时间范围为 １９：４７：０８—２２：０８：４３，等待时间等 于 ２ ｍｉｎ 表明任务请求发生死锁，小于 ２ ｍｉｎ 表明任 务请求完成。 图 ３ 死锁边界时间 Ｆｉｇ． ３ Ｄｅａｄｌｏｃｋ ｂｏｕｎｄａｒｙ ｔｉｍｅ Ｕｒｌｌｉｂ２ 爬虫算法等待时间合计为 ２ ｈ ９ ｍｉｎ ７ ｓ， 死锁次数为 ３０ 次，死锁率为 ３０％；银行家算法等待时 间合计为 １ ｈ ３８ ｍｉｎ ２８ ｓ，死锁次数为 ２ 次，死锁率为 ２％，算法对比实验结果如表 ３ 所示。 实验结果表明， 本文算法明显降低了死锁率，提高了系统运行效率。 传统资源配置算法死锁率高、效率低下。 表 ３ 实验结果对比 Ｔａｂｌｅ ３ Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ 算 法 等待时间合计 死锁次数 死锁率／ ％ ｕｒｌｌｉｂ２ 算法 ２：０９：０７ ３０ ３０ 银行家算法 １：３８：２８ ２０ ２ 第 ３ 期 王庆红，等：一种基于银行家算法的网络爬虫资源配置策略 ·４９７·
·498 智能系统学报 第10卷 3 结束语 making Ajax applications searchable [C]//IEEE 25th In- ternational Conference on Data Engineering.Shanghai, 本文基于银行家算法，在多用户操作系统中，提 China.2009:78-89. 出一种新的网络爬虫资源配置策略。这种基于银行 [12]PENG Zhaomeng,HE Nengqiang,JIANG Chunxiao,et al. 家算法的网络爬虫资源配置策略不但提高了网络爬 Graph-based Ajax crawl:mining data from rich Internet applications[C]//2012 International Conference on Com- 虫资源的利用率，而且能够有效避免死锁的发生。 puter Science and Electronic Engineering.Hangzhou,Chi- 下一步的研究工作可以在目前己有的策略上有针对 na,2012:590-594. 性、方向性地进一步分析和研究降低死锁率的方法。 [13]杨梅，滕少华.基于死锁避免的资源安全分配算法[J] 计算机工程与设计，2011,32(1)：40-43. 参考文献： YANG Mei,TENG Shaohua.Improved safe resource allo- [1]RICART G.AGRAWALA A K.An optimal algorithm for cation algorithm based on deadlock avoidance[J].Comput- mutual exclusion in computer networks[]].Communications er Engineering and Design,2011,32(1):40-43. [14]陈吴成.基于网格计算的资源管理与分配系统的设计 of the ACM,1981,24(1):9-17. [2]WANG Hong.The study of banker's algorithm base on ex- 与实现[D].哈尔滨：哈尔滨工业大学，2010. periment[J].Applied Mechanics and Materials,2013, CHEN Haocheng.Design and implementation of resource 442:303-308. management and allocation system based on grid computing [3 HAO Yue,HU Hesuan.Robust deadlock control using [D].Harbin,China:Harbin Institute of Technology, shared-resources for production systems with unreliable 2010. workstations[C]//2013 IEEE International Conference on [15]章韵，汤楠.服务计算中避免死锁和活锁的资源分配算 Automation Science and Engineering.Madison,USA, 法[J].微电子学与计算机，2010,27(12)：69-73,77. 2013:1095-1100. ZHANG Yun,TANG Nan.Deadlock and livelock free re- [4]YUE Hao,HU Hesuan.A polynomial deadlock avoidance source allocation algorithm in service oriented computing policy for a class of assembly processes based on petri nets []Microelectronics Computer,2010,27(12):69- [C]//2013 IEEE International Conference on Automation 73,77. Science and Engineering.Madison,USA,2013:1151- [16]SHETTY K S,BHAT S,SINGH S.Symbolie verification of 1156. web crawler functionality and its properties[C]//2012 In- [5]MA Xiaohui,YAN Junya.An improved parallel banker's al- ternational Conference on Computer Communication and In- gorithm based on petri net[C]//2011 International Confer- formatics.Coimbatore,India,2012:1-6. ence on Electronic and Mechanical Engineering and Infor- 作者简介： mation Technology.Harbin,China,2011:1538-1541. 王庆红，男，1976年生，高级设计 [6]XIAO Xiang,LEE JJ.A true 0(1)parallel deadlock detec- 师，技术情报所所长，主要研究方向为 tion algorithm for single-unit resource systems and its hard- 电力系统运行、规划与设计以及企业情 ware implementationJ.IEEE Transaction on Parallel and 报系统建设与管理。 Distributed System,2010,21(1):4-19. [7]LOU Lin,TANG Feilong,YOU I,et al.An effective dead- lock prevention mechanism for distributed transaction man- agement[C]//2011 Fifth International Conference on Inno- 李广凯，男，1975年生，副教授，博 vative Mobile and Internet Services in Ubiquitous Compu- 土，主要研究方向为电力系统企业技术 ting.Seoul,Korea,2011:120-127. 情报咨询及直流输电技术。 [8]REVELIOTIS SA,ROSZKOWSKA E.Conflict resolution in free-ranging multivehicle systems:a resource allocation par- adigm[J].IEEE Transactions on Robotics,2011,27(2): 283-296. [9]LANG S D.An extended banker's algorithm for deadlock a- voidance[].IEEE Transactions on Software Engineering, 周育忠，男，1974年生，高级工程 1999,25(3):428-432. 师，主要研究方向为行业情报系统建 [10]TANG Feilong,YOU I,YU Shui,et al.An efficient dead- 设、运维管理和资源整合。 lock prevention approach for service oriented transaction processing[J].Computers Mathematics with Applica- tions,2012,63(2):458-468. [11]DUDA C,PREY G,KOSSMANN D,et al.Ajax crawl:
３ 结束语 本文基于银行家算法，在多用户操作系统中，提 出一种新的网络爬虫资源配置策略。 这种基于银行 家算法的网络爬虫资源配置策略不但提高了网络爬 虫资源的利用率，而且能够有效避免死锁的发生。 下一步的研究工作可以在目前己有的策略上有针对 性、方向性地进一步分析和研究降低死锁率的方法。 参考文献： ［１］ ＲＩＣＡＲＴ Ｇ， ＡＧＲＡＷＡＬＡ Ａ Ｋ． Ａｎ ｏｐｔｉｍａｌ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｍｕｔｕａｌ ｅｘｃｌｕｓｉｏｎ ｉｎ ｃｏｍｐｕｔｅｒ ｎｅｔｗｏｒｋｓ［Ｊ］． Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ｏｆ ｔｈｅ ＡＣＭ， １９８１， ２４（１）： ９⁃１７． ［２］ＷＡＮＧ Ｈｏｎｇ． Ｔｈｅ ｓｔｕｄｙ ｏｆ ｂａｎｋｅｒ＇ｓ ａｌｇｏｒｉｔｈｍ ｂａｓｅ ｏｎ ｅｘ⁃ ｐｅｒｉｍｅｎｔ ［ Ｊ ］． Ａｐｐｌｉｅｄ Ｍｅｃｈａｎｉｃｓ ａｎｄ Ｍａｔｅｒｉａｌｓ， ２０１３， ４４２： ３０３⁃３０８． ［３ ］ ＨＡＯ Ｙｕｅ， ＨＵ Ｈｅｓｕａｎ． Ｒｏｂｕｓｔ ｄｅａｄｌｏｃｋ ｃｏｎｔｒｏｌ ｕｓｉｎｇ ｓｈａｒｅｄ⁃ｒｅｓｏｕｒｃｅｓ ｆｏｒ ｐｒｏｄｕｃｔｉｏｎ ｓｙｓｔｅｍｓ ｗｉｔｈ ｕｎｒｅｌｉａｂｌｅ ｗｏｒｋｓｔａｔｉｏｎｓ［Ｃ］ ／ ／ ２０１３ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ａｕｔｏｍａｔｉｏｎ Ｓｃｉｅｎｃｅ ａｎｄ Ｅｎｇｉｎｅｅｒｉｎｇ． Ｍａｄｉｓｏｎ， ＵＳＡ， ２０１３： １０９５⁃１１００． ［４］ ＹＵＥ Ｈａｏ， ＨＵ Ｈｅｓｕａｎ． Ａ ｐｏｌｙｎｏｍｉａｌ ｄｅａｄｌｏｃｋ ａｖｏｉｄａｎｃｅ ｐｏｌｉｃｙ ｆｏｒ ａ ｃｌａｓｓ ｏｆ ａｓｓｅｍｂｌｙ ｐｒｏｃｅｓｓｅｓ ｂａｓｅｄ ｏｎ ｐｅｔｒｉ ｎｅｔｓ ［Ｃ］ ／ ／ ２０１３ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ａｕｔｏｍａｔｉｏｎ Ｓｃｉｅｎｃｅ ａｎｄ Ｅｎｇｉｎｅｅｒｉｎｇ． Ｍａｄｉｓｏｎ， ＵＳＡ， ２０１３： １１５１⁃ １１５６． ［５］ＭＡ Ｘｉａｏｈｕｉ， ＹＡＮ Ｊｕｎｙａ． Ａｎ ｉｍｐｒｏｖｅｄ ｐａｒａｌｌｅｌ ｂａｎｋｅｒ＇ｓ ａｌ⁃ ｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｐｅｔｒｉ ｎｅｔ［Ｃ］ ／ ／ ２０１１ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒ⁃ ｅｎｃｅ ｏｎ Ｅｌｅｃｔｒｏｎｉｃ ａｎｄ Ｍｅｃｈａｎｉｃａｌ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ｉｎｆｏｒ⁃ ｍａｔｉｏｎ Ｔｅｃｈｎｏｌｏｇｙ． Ｈａｒｂｉｎ， Ｃｈｉｎａ， ２０１１： １５３８⁃１５４１． ［６］ＸＩＡＯ Ｘｉａｎｇ， ＬＥＥ Ｊ Ｊ． Ａ ｔｒｕｅ ０（１） ｐａｒａｌｌｅｌ ｄｅａｄｌｏｃｋ ｄｅｔｅｃ⁃ ｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｓｉｎｇｌｅ⁃ｕｎｉｔ ｒｅｓｏｕｒｃｅ ｓｙｓｔｅｍｓ ａｎｄ ｉｔｓ ｈａｒｄ⁃ ｗａｒｅ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ［Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎ ｏｎ Ｐａｒａｌｌｅｌ ａｎｄ Ｄｉｓｔｒｉｂｕｔｅｄ Ｓｙｓｔｅｍ， ２０１０， ２１（１）： ４⁃１９． ［７］ＬＯＵ Ｌｉｎ， ＴＡＮＧ Ｆｅｉｌｏｎｇ， ＹＯＵ Ｉ， ｅｔ ａｌ． Ａｎ ｅｆｆｅｃｔｉｖｅ ｄｅａｄ⁃ ｌｏｃｋ ｐｒｅｖｅｎｔｉｏｎ ｍｅｃｈａｎｉｓｍ ｆｏｒ ｄｉｓｔｒｉｂｕｔｅｄ ｔｒａｎｓａｃｔｉｏｎ ｍａｎ⁃ ａｇｅｍｅｎｔ［Ｃ］ ／ ／ ２０１１ Ｆｉｆｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｉｎｎｏ⁃ ｖａｔｉｖｅ Ｍｏｂｉｌｅ ａｎｄ Ｉｎｔｅｒｎｅｔ Ｓｅｒｖｉｃｅｓ ｉｎ Ｕｂｉｑｕｉｔｏｕｓ Ｃｏｍｐｕ⁃ ｔｉｎｇ． Ｓｅｏｕｌ， Ｋｏｒｅａ， ２０１１： １２０⁃１２７． ［８］ＲＥＶＥＬＩＯＴＩＳ Ｓ Ａ， ＲＯＳＺＫＯＷＳＫＡ Ｅ． Ｃｏｎｆｌｉｃｔ ｒｅｓｏｌｕｔｉｏｎ ｉｎ ｆｒｅｅ⁃ｒａｎｇｉｎｇ ｍｕｌｔｉｖｅｈｉｃｌｅ ｓｙｓｔｅｍｓ： ａ ｒｅｓｏｕｒｃｅ ａｌｌｏｃａｔｉｏｎ ｐａｒ⁃ ａｄｉｇｍ［Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｒｏｂｏｔｉｃｓ， ２０１１， ２７（２）： ２８３⁃２９６． ［９］ＬＡＮＧ Ｓ Ｄ． Ａｎ ｅｘｔｅｎｄｅｄ ｂａｎｋｅｒ＇ｓ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｄｅａｄｌｏｃｋ ａ⁃ ｖｏｉｄａｎｃｅ［ Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｓｏｆｔｗａｒｅ Ｅｎｇｉｎｅｅｒｉｎｇ， １９９９， ２５（３）： ４２８⁃４３２． ［１０］ＴＡＮＧ Ｆｅｉｌｏｎｇ， ＹＯＵ Ｉ， ＹＵ Ｓｈｕｉ， ｅｔ ａｌ． Ａｎ ｅｆｆｉｃｉｅｎｔ ｄｅａｄ⁃ ｌｏｃｋ ｐｒｅｖｅｎｔｉｏｎ ａｐｐｒｏａｃｈ ｆｏｒ ｓｅｒｖｉｃｅ ｏｒｉｅｎｔｅｄ ｔｒａｎｓａｃｔｉｏｎ ｐｒｏｃｅｓｓｉｎｇ［ Ｊ］． Ｃｏｍｐｕｔｅｒｓ ＆ Ｍａｔｈｅｍａｔｉｃｓ ｗｉｔｈ Ａｐｐｌｉｃａ⁃ ｔｉｏｎｓ， ２０１２， ６３（２）： ４５８⁃４６８． ［１１］ ＤＵＤＡ Ｃ， ＰＲＥＹ Ｇ， ＫＯＳＳＭＡＮＮ Ｄ， ｅｔ ａｌ． Ａｊａｘ ｃｒａｗｌ： ｍａｋｉｎｇ Ａｊａｘ ａｐｐｌｉｃａｔｉｏｎｓ ｓｅａｒｃｈａｂｌｅ［Ｃ］ ／ ／ ＩＥＥＥ ２５ｔｈ Ｉｎ⁃ ｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｄａｔａ Ｅｎｇｉｎｅｅｒｉｎｇ． Ｓｈａｎｇｈａｉ， Ｃｈｉｎａ， ２００９： ７８⁃８９． ［１２］ＰＥＮＧ Ｚｈａｏｍｅｎｇ， ＨＥ Ｎｅｎｇｑｉａｎｇ， ＪＩＡＮＧ Ｃｈｕｎｘｉａｏ， ｅｔ ａｌ． Ｇｒａｐｈ⁃ｂａｓｅｄ Ａｊａｘ ｃｒａｗｌ： ｍｉｎｉｎｇ ｄａｔａ ｆｒｏｍ ｒｉｃｈ Ｉｎｔｅｒｎｅｔ ａｐｐｌｉｃａｔｉｏｎｓ［Ｃ］ ／ ／ ２０１２ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍ⁃ ｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｅｌｅｃｔｒｏｎｉｃ Ｅｎｇｉｎｅｅｒｉｎｇ． Ｈａｎｇｚｈｏｕ， Ｃｈｉ⁃ ｎａ， ２０１２： ５９０⁃５９４． ［１３］杨梅， 滕少华． 基于死锁避免的资源安全分配算法［ Ｊ］． 计算机工程与设计， ２０１１， ３２（１）： ４０⁃４３． ＹＡＮＧ Ｍｅｉ， ＴＥＮＧ Ｓｈａｏｈｕａ． Ｉｍｐｒｏｖｅｄ ｓａｆｅ ｒｅｓｏｕｒｃｅ ａｌｌｏ⁃ ｃａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｄｅａｄｌｏｃｋ ａｖｏｉｄａｎｃｅ［Ｊ］． Ｃｏｍｐｕｔ⁃ ｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ｄｅｓｉｇｎ， ２０１１， ３２（１）： ４０⁃４３． ［１４］陈昊成． 基于网格计算的资源管理与分配系统的设计 与实现［Ｄ］． 哈尔滨： 哈尔滨工业大学， ２０１０． ＣＨＥＮ Ｈａｏｃｈｅｎｇ． Ｄｅｓｉｇｎ ａｎｄ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ ｒｅｓｏｕｒｃｅ ｍａｎａｇｅｍｅｎｔ ａｎｄ ａｌｌｏｃａｔｉｏｎ ｓｙｓｔｅｍ ｂａｓｅｄ ｏｎ ｇｒｉｄ ｃｏｍｐｕｔｉｎｇ ［Ｄ］． Ｈａｒｂｉｎ， Ｃｈｉｎａ： Ｈａｒｂｉｎ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ， ２０１０． ［１５］章韵， 汤楠． 服务计算中避免死锁和活锁的资源分配算 法［Ｊ］． 微电子学与计算机， ２０１０， ２７（１２）： ６９⁃７３， ７７． ＺＨＡＮＧ Ｙｕｎ， ＴＡＮＧ Ｎａｎ． Ｄｅａｄｌｏｃｋ ａｎｄ ｌｉｖｅｌｏｃｋ ｆｒｅｅ ｒｅ⁃ ｓｏｕｒｃｅ ａｌｌｏｃａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｉｎ ｓｅｒｖｉｃｅ ｏｒｉｅｎｔｅｄ ｃｏｍｐｕｔｉｎｇ ［ Ｊ］． Ｍｉｃｒｏｅｌｅｃｔｒｏｎｉｃｓ ＆ Ｃｏｍｐｕｔｅｒ， ２０１０， ２７（ １２）： ６９⁃ ７３， ７７． ［１６］ＳＨＥＴＴＹ Ｋ Ｓ， ＢＨＡＴ Ｓ， ＳＩＮＧＨ Ｓ． Ｓｙｍｂｏｌｉｃ ｖｅｒｉｆｉｃａｔｉｏｎ ｏｆ ｗｅｂ ｃｒａｗｌｅｒ ｆｕｎｃｔｉｏｎａｌｉｔｙ ａｎｄ ｉｔｓ ｐｒｏｐｅｒｔｉｅｓ［Ｃ］ ／ ／ ２０１２ Ｉｎ⁃ ｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｃｏｍｍｕｎｉｃａｔｉｏｎ ａｎｄ Ｉｎ⁃ ｆｏｒｍａｔｉｃｓ． Ｃｏｉｍｂａｔｏｒｅ， Ｉｎｄｉａ， ２０１２： １⁃６． 作者简介： 王庆红，男，１９７６ 年生，高级设计 师，技术情报所所长，主要研究方向为 电力系统运行、规划与设计以及企业情 报系统建设与管理。 李广凯，男，１９７５ 年生，副教授，博 士，主要研究方向为电力系统企业技术 情报咨询及直流输电技术。 周育忠，男，１９７４ 年生，高级工程 师，主要研究方向为行业情报系统建 设、运维管理和资源整合。 ·４９８· 智 能 系 统 学 报 第 １０ 卷