第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时刻是安全的，因为存在 行家算法中的安全分配算法进行了研究，该算法缩 一个安全序列<P1,P2,P,P4>,只要系统按此进程 小了安全检查的范围，提高了系统效率。陈昊成 序列分配资源，每个进程都可以完成资源分配：反 针对预防死锁问题和调度策略问题提出了解决方 之，系统处于不安全状态。如果满足系统安全性条 案，应用于资源管理分配系统。章韵等经过仿真 件，则可以分配：否则暂不分配，以免系统进入不安 实验提出了一种资源分配算法，实验结果证明该算 全状态。 法可以有效避免死锁。 综上所述，本文借用安全性检查算法，将剩余未 以上研究成果表明，银行家算法是一种避免死 分配的空闲资源K作为递归的边界条件，不断地寻 锁的有效算法。本文提出了基于银行家算法的网络 找合法的节点进入请求集，判断下一个节点进入的 爬虫资源分配策略，以降低多任务处理系统的死锁 合法性可以确定当前节点进入的合法性，进而确定 率，提高网络爬虫资源的利用率，避免死锁的发生。 出一组合理的安全序列防止死锁问题的发生。这种 思想在处理多用户操作系统资源配置问题中是一个 1 基本概念 创新点和突破点，值得继续优化和深入研究。 1.1多用户操作系统 根据在同一时间最多允许多少个用户同时操作 2银行家算法 计算机，操作系统可分为单用户操作系统和多用户 银行家算法可以有效避免死锁，该算法最初是 操作系统。同一时间内允许多个用户同时使用计算 用于银行贷款)。如果存在某个状态序列，能满足 机，称为多用户操作系统：反之，同一时间内最多允 所有客户的贷款需求，则该状态是安全的：反之，则 许一个用户操作计算机，则称为单用户操作系统。 可能导致发生死锁。若安全检查结果表明系统处于 常见的多用户操作系统有Windows Server2OO3和 危险状态，则该请求不合法：反之，请求合法。 Windows Server2OO8等。系统资源的有限性及进程网中的死锁问题，有效降低了死锁率，表明银行家算 法可应用于解决多用户操作系统的死锁问题。 多处 理器片上系统适用于多用户操作系统，Ｘｉａｏ 等［６］ 研 究了多处理器片上系统上的死锁问题，提出了一种 硬件死锁检测算法。 多用户操作系统的死锁问题本 质上是多进程访问公共资源导致的死锁问题，Ｌｏｕ 等［７］研究了多进程访问公共资源导致的死锁问题， 提出了一种避免死锁的算法，实验结果表明该算法 有效地解决了分布式事务管理系统中的死锁问题。 Ｓ． Ａ． Ｒｅｖｅｌｉｏｔｉｓ 等［８］研究的多车辆系统资源配置算 法解决死锁问题。 Ｌａｎｇ 等［９］ 基于银行家算法提出 了二次时间算法，更好地实现了操作系统资源优化 配置。 本文研究的网络爬虫配置策略基于 Ｗｉｎｄｏｗｓ 操作系统进行开发，Ｗｉｎｄｏｗｓ 操作系统是基于事件 驱动的程序模型，Ｔａｎｇ 等［１０］提出了一种在事件处理 系统中有效避免死锁的方法。 Ｄｕｄａ 等［１１］ 将 Ｃａｃｈｅ 模块增加到爬虫系统中，并采用了热点检测机制，避 免从服务器端重复地获取相同内容，采用 ＭＦＣ 编程 设计并实现了基于银行家算法的网络爬虫资源配置 应用软件，增加 Ｃａｃｈｅ 模块的设计并引入热点检测 机制，提高了系统的运行效率。 Ｐｅｎｇ 等［１２］ 将 Ａｊａｘ 页面状态的抓取转换为 ＤＲＰＰ，在完全状态转换图 拓扑结构已知的情况下，核心状态转换图增加少量 取自它的边后成为平衡、强连通图，该欧拉回路即为 最优搜索路径，从而提高了效率。 杨梅等［１３］ 针对银 行家算法中的安全分配算法进行了研究，该算法缩 小了安全检查的范围，提高了系统效率。 陈昊成［１４］ 针对预防死锁问题和调度策略问题提出了解决方 案，应用于资源管理分配系统。 章韵等［１５］ 经过仿真 实验提出了一种资源分配算法，实验结果证明该算 法可以有效避免死锁。 以上研究成果表明，银行家算法是一种避免死 锁的有效算法。 本文提出了基于银行家算法的网络 爬虫资源分配策略，以降低多任务处理系统的死锁 率，提高网络爬虫资源的利用率，避免死锁的发生。 １ 基本概念 １．１ 多用户操作系统 根据在同一时间最多允许多少个用户同时操作 计算机，操作系统可分为单用户操作系统和多用户 操作系统。 同一时间内允许多个用户同时使用计算 机，称为多用户操作系统；反之，同一时间内最多允 许一个用户操作计算机，则称为单用户操作系统。 常见的多用户操作系统有 Ｗｉｎｄｏｗｓ Ｓｅｒｖｅｒ ２００３ 和 Ｗｉｎｄｏｗｓ Ｓｅｒｖｅｒ ２００８ 等。 系统资源的有限性及进程 并发性是导致发生死锁的原因，当系统无法满足进 程的资源请求时，资源申请失败导致发生死锁。 １．２ 死锁 在多用户操作系统，进程是并发执行的，但是存 在一种危险—死锁。 若无内部鲁棒容错或外部干 预，系统将长期处于封锁状态。 竞争资源及进程推 进顺序非法是导致死锁的主要原因。 在当前资源限 制下，寻找一组资源分配的执行顺序，从而避免产生 死锁，是本文研究的主要内容。 将银行家算法为避 免死锁获取安全进程序列的递归思想，借鉴到网络 爬虫算法中。 将请求集长度作为一个变量，边界条 件为请求集长度及节点状态数组，从而能够确定请 求集节点的合法性。 该算法的时间复杂度比 ｕｒｌｌｉｂ２ 算法较小，并且能够获得最优请求集长度。 １．３ 安全状态 只要保持系统时刻在安全状态，便可避免死锁。 假设系统中并发存在 ｎ 个进程，分别为 Ｐ１ ，Ｐ２ ， …， Ｐｎ ，如果按照某种序列顺序进行分配资源，使得 ｎ 个 进程都能顺利完成资源分配，则该序列称为安全序 列，此时系统处于安全状态。 通过一个实例说明，例 如有 ４ 个进程共享 ２０ 个同类资源，进程 Ｐ１共需 １５ 个资源，进程 Ｐ２共需 ５ 个资源，进程 Ｐ３共需 ８ 个资 源，进程 Ｐ４共需 １０ 个资源。 假设在 Ｔｎ时刻，Ｐ１ 、Ｐ２ 、 Ｐ３ 、Ｐ４分别已经获得 ８、４、４、２ 个资源，尚有 ２ 个空闲 资源未分配。 经过分析，Ｔｎ时刻是安全的，因为存在 一个安全序列＜Ｐ １ ，Ｐ２ ，Ｐ３ ，Ｐ４ ＞，只要系统按此进程 序列分配资源，每个进程都可以完成资源分配；反 之，系统处于不安全状态。 如果满足系统安全性条 件，则可以分配；否则暂不分配，以免系统进入不安 全状态。 综上所述，本文借用安全性检查算法，将剩余未 分配的空闲资源 Ｋ 作为递归的边界条件，不断地寻 找合法的节点进入请求集，判断下一个节点进入的 合法性可以确定当前节点进入的合法性，进而确定 出一组合理的安全序列防止死锁问题的发生。 这种 思想在处理多用户操作系统资源配置问题中是一个 创新点和突破点，值得继续优化和深入研究。 ２ 银行家算法 银行家算法可以有效避免死锁，该算法最初是 用于银行贷款［９］ 。 如果存在某个状态序列，能满足 所有客户的贷款需求，则该状态是安全的；反之，则 可能导致发生死锁。 若安全检查结果表明系统处于 危险状态，则该请求不合法；反之，请求合法。 第 ３ 期 王庆红，等：一种基于银行家算法的网络爬虫资源配置策略 ·４９５·