一種基于銀行家算法的網(wǎng)絡(luò)爬蟲資源配置策略

網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/23.1538.tp.20150514.1432.001.html

一種基于銀行家算法的網(wǎng)絡(luò)爬蟲資源配置策略

王慶紅，李廣凱，周育忠，韋嶸暉

(南方電網(wǎng)科學(xué)研究院有限責(zé)任公司 技術(shù)情報所，廣東 廣州 510080)

摘要：死鎖是多用戶操作系統(tǒng)正常運行的一個重要問題，系統(tǒng)資源不足會導(dǎo)致爬蟲算法進入不安全狀態(tài)，進而引發(fā)死鎖等問題。引入被廣泛用于操作系統(tǒng)的銀行家算法，調(diào)度多個網(wǎng)絡(luò)爬蟲進程并發(fā)運行，并且為每個進程合理分配系統(tǒng)資源，當(dāng)進程無法獲取系統(tǒng)資源時，則等待其他進程分配完成后釋放系統(tǒng)資源，從而完成資源分配，有效降低死鎖率。采用C++編程，設(shè)計并實現(xiàn)基于銀行家算法的網(wǎng)絡(luò)爬蟲配置策略。通過2 h 21 min 35 s工程測試，urllib2算法死鎖率為30%，新算法死鎖率僅為2%，測試證明該策略能夠有效降低死鎖率，能高效完成多個任務(wù)進程的資源分配。

關(guān)鍵詞：操作系統(tǒng)；資源配置；死鎖；系統(tǒng)安全；銀行家算法；網(wǎng)絡(luò)爬蟲

DOI:10.3969/j.issn.1673-4785.201409021

中圖分類號：TP361; TM75 文獻標(biāo)志碼：A

收稿日期：2014-09-12. 網(wǎng)絡(luò)出版日期：2015-05-14.

作者簡介：

中文引用格式：王慶紅，李廣凱，周育忠，等. 一種基于銀行家算法的網(wǎng)絡(luò)爬蟲資源配置策略[J]. 智能系統(tǒng)學(xué)報, 2015, 10(3): 494-498.

英文引用格式：WANG Qinghong, LI Guangkai, ZHOU Yuzhong, et al. 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 system 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++ programming. 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

通信作者：王慶紅. E-mail: wangqh@csg.cn.

網(wǎng)絡(luò)爬蟲資源分配不足會導(dǎo)致發(fā)生死鎖，發(fā)生死鎖的爬蟲進程無法繼續(xù)運行，必須通過釋放爬蟲資源重新抓取網(wǎng)頁信息，因此造成爬蟲算法效率低下。G. Ricart等[1]研究并實現(xiàn)了計算機網(wǎng)絡(luò)優(yōu)化算法，通過理論分析證明了理想條件下可以避免死鎖。Wang[2]通過實驗驗證了銀行家算法在判斷系統(tǒng)安全性中的有效性。本文研究的多用戶操作系統(tǒng)屬于共享資源系統(tǒng)，Hao等[3-4]研究了共享資源系統(tǒng)的魯棒死鎖控制方法。Petri網(wǎng)可用于描述多用戶操作系統(tǒng)模型，Ma等[5]將銀行家算法用于解決Petri網(wǎng)中的死鎖問題，有效降低了死鎖率，表明銀行家算法可應(yīng)用于解決多用戶操作系統(tǒng)的死鎖問題。多處理器片上系統(tǒng)適用于多用戶操作系統(tǒng)，Xiao等[6]研究了多處理器片上系統(tǒng)上的死鎖問題，提出了一種硬件死鎖檢測算法。多用戶操作系統(tǒng)的死鎖問題本質(zhì)上是多進程訪問公共資源導(dǎo)致的死鎖問題，Lou等[7]研究了多進程訪問公共資源導(dǎo)致的死鎖問題，提出了一種避免死鎖的算法，實驗結(jié)果表明該算法有效地解決了分布式事務(wù)管理系統(tǒng)中的死鎖問題。S. A. Reveliotis等[8]研究的多車輛系統(tǒng)資源配置算法解決死鎖問題。Lang等[9]基于銀行家算法提出了二次時間算法，更好地實現(xiàn)了操作系統(tǒng)資源優(yōu)化配置。本文研究的網(wǎng)絡(luò)爬蟲配置策略基于Windows操作系統(tǒng)進行開發(fā)，Windows操作系統(tǒng)是基于事件驅(qū)動的程序模型，Tang等[10]提出了一種在事件處理系統(tǒng)中有效避免死鎖的方法。Duda等[11]將Cache模塊增加到爬蟲系統(tǒng)中，并采用了熱點檢測機制，避免從服務(wù)器端重復(fù)地獲取相同內(nèi)容，采用MFC編程設(shè)計并實現(xiàn)了基于銀行家算法的網(wǎng)絡(luò)爬蟲資源配置應(yīng)用軟件，增加Cache模塊的設(shè)計并引入熱點檢測機制，提高了系統(tǒng)的運行效率。Peng等[12]將Ajax頁面狀態(tài)的抓取轉(zhuǎn)換為DRPP，在完全狀態(tài)轉(zhuǎn)換圖拓撲結(jié)構(gòu)已知的情況下，核心狀態(tài)轉(zhuǎn)換圖增加少量取自它的邊后成為平衡、強連通圖，該歐拉回路即為最優(yōu)搜索路徑，從而提高了效率。楊梅等[13]針對銀行家算法中的安全分配算法進行了研究，該算法縮小了安全檢查的范圍，提高了系統(tǒng)效率。陳昊成[14]針對預(yù)防死鎖問題和調(diào)度策略問題提出了解決方案，應(yīng)用于資源管理分配系統(tǒng)。章韻等[15]經(jīng)過仿真實驗提出了一種資源分配算法，實驗結(jié)果證明該算法可以有效避免死鎖。

以上研究成果表明，銀行家算法是一種避免死鎖的有效算法。本文提出了基于銀行家算法的網(wǎng)絡(luò)爬蟲資源分配策略，以降低多任務(wù)處理系統(tǒng)的死鎖率，提高網(wǎng)絡(luò)爬蟲資源的利用率，避免死鎖的發(fā)生。

1基本概念

1.1多用戶操作系統(tǒng)

根據(jù)在同一時間最多允許多少個用戶同時操作計算機，操作系統(tǒng)可分為單用戶操作系統(tǒng)和多用戶操作系統(tǒng)。同一時間內(nèi)允許多個用戶同時使用計算機，稱為多用戶操作系統(tǒng)；反之，同一時間內(nèi)最多允許一個用戶操作計算機，則稱為單用戶操作系統(tǒng)。常見的多用戶操作系統(tǒng)有Windows Server 2003 和Windows Server 2008等。系統(tǒng)資源的有限性及進程并發(fā)性是導(dǎo)致發(fā)生死鎖的原因，當(dāng)系統(tǒng)無法滿足進程的資源請求時，資源申請失敗導(dǎo)致發(fā)生死鎖。

1.2死鎖

在多用戶操作系統(tǒng)，進程是并發(fā)執(zhí)行的，但是存在一種危險—死鎖。若無內(nèi)部魯棒容錯或外部干預(yù)，系統(tǒng)將長期處于封鎖狀態(tài)。競爭資源及進程推進順序非法是導(dǎo)致死鎖的主要原因。在當(dāng)前資源限制下，尋找一組資源分配的執(zhí)行順序，從而避免產(chǎn)生死鎖，是本文研究的主要內(nèi)容。將銀行家算法為避免死鎖獲取安全進程序列的遞歸思想，借鑒到網(wǎng)絡(luò)爬蟲算法中。將請求集長度作為一個變量，邊界條件為請求集長度及節(jié)點狀態(tài)數(shù)組，從而能夠確定請求集節(jié)點的合法性。該算法的時間復(fù)雜度比urllib2算法較小，并且能夠獲得最優(yōu)請求集長度。

1.3安全狀態(tài)

只要保持系統(tǒng)時刻在安全狀態(tài)，便可避免死鎖。假設(shè)系統(tǒng)中并發(fā)存在n個進程，分別為P1，P2, …,Pn，如果按照某種序列順序進行分配資源，使得n個進程都能順利完成資源分配，則該序列稱為安全序列，此時系統(tǒng)處于安全狀態(tài)。通過一個實例說明，例如有4個進程共享20個同類資源，進程P1共需15個資源，進程P2共需5個資源，進程P3共需8個資源，進程P4共需10個資源。假設(shè)在Tn時刻，P1、P2、P3、P4分別已經(jīng)獲得8、4、4、2個資源，尚有2個空閑資源未分配。經(jīng)過分析，Tn時刻是安全的，因為存在一個安全序列< P1，P2，P3，P4>，只要系統(tǒng)按此進程序列分配資源，每個進程都可以完成資源分配；反之，系統(tǒng)處于不安全狀態(tài)。如果滿足系統(tǒng)安全性條件，則可以分配；否則暫不分配，以免系統(tǒng)進入不安全狀態(tài)。

綜上所述，本文借用安全性檢查算法，將剩余未分配的空閑資源K作為遞歸的邊界條件，不斷地尋找合法的節(jié)點進入請求集，判斷下一個節(jié)點進入的合法性可以確定當(dāng)前節(jié)點進入的合法性，進而確定出一組合理的安全序列防止死鎖問題的發(fā)生。這種思想在處理多用戶操作系統(tǒng)資源配置問題中是一個創(chuàng)新點和突破點，值得繼續(xù)優(yōu)化和深入研究。

2銀行家算法

銀行家算法可以有效避免死鎖，該算法最初是用于銀行貸款[9]。如果存在某個狀態(tài)序列，能滿足所有客戶的貸款需求，則該狀態(tài)是安全的；反之，則可能導(dǎo)致發(fā)生死鎖。若安全檢查結(jié)果表明系統(tǒng)處于危險狀態(tài)，則該請求不合法；反之，請求合法。

2.1算法數(shù)據(jù)結(jié)構(gòu)

算法中存在4類數(shù)據(jù)類型。1)第1類數(shù)據(jù)類型稱為可利用資源向量，該向量隨資源分配、回收動態(tài)變化，用含有m個元素的一維數(shù)組Av。2)第2類數(shù)據(jù)類型稱為最大需求矩陣，用M矩陣表示。3)第3類數(shù)據(jù)類型稱為分配矩陣，表示每一類資源已分配給每個進程的資源數(shù)量，用Al矩陣表示。4)第4類數(shù)據(jù)類型稱為需求矩陣，用N矩陣表示。

2.2銀行家算法流程

算法包括系統(tǒng)分配資源流程及系統(tǒng)安全性檢查流程。

1)系統(tǒng)分配資源步驟：

a)當(dāng)滿足Ri≤Nij條件時，執(zhí)行下一步操作，否則程序返回false；

b)初始化假設(shè)Fi=false，滿足一定條件則置為true；

c)假設(shè)系統(tǒng)試分配及安全性檢查通過，則可以進行分配，分配算法為

2)系統(tǒng)安全性算法步驟：

a)設(shè)置2個向量：工作向量與完成向量。W向量即工作向量，表示系統(tǒng)能夠提供給各個進程的資源數(shù)量；F向量即完成向量，表示系統(tǒng)能夠順利地為每個進程完成分配。初始化假設(shè)Fi=false，滿足一定條件則置為true。

b)當(dāng)某個進程滿足條件Fi=false以及Nij

c)當(dāng)進程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放該進程分配得到的資源，Wj=Wj+Alij；Fi=true，繼續(xù)執(zhí)行步驟b)。

d)如果所有進程的Fi=true都完成，則系統(tǒng)處于安全狀態(tài)，否則系統(tǒng)將處于一個不夠安全的狀態(tài)，此時不能完成資源分配工作。

本文提出的基于銀行家算法的網(wǎng)絡(luò)爬蟲資源分配算法一個重要的特點是將銀行家算法中核心的遞歸思想引入到請求集生成過程中。通過測試每個納入請求集數(shù)組是否合法來決定是否允許當(dāng)前節(jié)點進入。合法指的是當(dāng)前節(jié)點進入之后可以保障下一個節(jié)點進入請求集。這種遞歸思想可稱為全局遞歸思想或完全遞歸，消耗時間和系統(tǒng)資源較多。局部遞歸算法指的是：對經(jīng)過相應(yīng)初始化處理的請求集求差集，如果請求集不能覆蓋系統(tǒng)所有節(jié)點，則只對未被表示的節(jié)點遞歸，最后納入請求集。在初始化請求集的過程中，通過初始化請求集向量N的位置節(jié)點，可以減少初始化節(jié)點的差集重復(fù)率從而降低請求集長度。

2.3算法設(shè)計與實現(xiàn)

采用VisualC++ 6.0設(shè)計Windows界面程序。界面分為三部分：參數(shù)輸入?yún)^(qū)域、資源分配區(qū)域和結(jié)果顯示區(qū)域。用戶在參數(shù)輸入?yún)^(qū)域輸入可利用資源向量Av等信息，單擊動態(tài)添加按鍵添加進程資源，單擊安全檢查，可以檢查當(dāng)前所有進程對當(dāng)前資源的申請是否安全，是否會使系統(tǒng)因資源不足或其他原因進入不安全狀態(tài)從而不能完成分配。如果進程申請資源安全，軟件則提示安全，否則提示不安全。

軟件可以支持最多10類資源進行分配，如圖1所示?？衫觅Y源向量為[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]，完成輸入之后單擊“動態(tài)添加”按鍵添加進程成功。單擊“安全檢查”按鍵，即提示系統(tǒng)狀態(tài)安全，可以執(zhí)行分配操作。

圖1　軟件安全性檢查 Fig. 1　Software security check

開始執(zhí)行分配，在進程名稱文本框輸入“process0”以及申請資源量。假設(shè)輸入的申請資源量為[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]，單擊“申請資源”，軟件彈出“資源分配后安全，可以分配”的消息提示框，表明輸入的資源量可以滿足申請要求并執(zhí)行申請請求。單擊確認，進程process0已經(jīng)分配資源為[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],尚需分配資源為[0, 0, 1, 0, 0, 0, 0, 0, 0, 0]，表明process0申請資源成功。此時系統(tǒng)可用資源數(shù)向量由原來的[5, 5, 5, 5, 5, 5, 5, 5, 5, 5]變?yōu)閇4, 4, 4, 4, 4, 4, 4, 4, 4, 4]，系統(tǒng)為進程process0分配資源成功，如圖2所示。

圖2　進程分配資源成功 Fig. 2　Allocation successfulness for processes

2.4實驗結(jié)果

本文算法和urllib2爬蟲算法對死鎖問題進行測試實驗對比。urllib2是Python中處理HTTP協(xié)議的算法庫，可用于監(jiān)測網(wǎng)絡(luò)爬蟲資源的死鎖[16]。設(shè)置超時時間為2m，當(dāng)爬蟲資源發(fā)生死鎖后超時，記錄該任務(wù)的狀態(tài)為Locked，完成其他任務(wù)后重啟該任務(wù)；未發(fā)生死鎖從而完成任務(wù)請求，則記錄改任務(wù)的狀態(tài)為Completed，并記錄等待時間。urllib2爬蟲算法抓取日志如表1所示，本文算法抓取日志如表2所示。

表 1　 Urllib2爬蟲算法抓取日志

表 2　本文算法抓取日志

分別采用urllib2爬蟲算法和本文算法進行100次請求操作，如果在超時時間之內(nèi)，爬蟲資源完成請求操作，則日志中記錄該次請求操作為Completed，反之在所設(shè)置的超時時間之內(nèi)未能請求成功，則日志中記錄該次請求操作為Locked，表示發(fā)生死鎖。本文算法和urllib2爬蟲算法死鎖邊界時間如圖3所示，縱坐標(biāo)表示任務(wù)等待時間，橫坐標(biāo)表示測試實驗的時間范圍為19:47:08—22:08:43，等待時間等于2 min表明任務(wù)請求發(fā)生死鎖，小于2 min表明任務(wù)請求完成。

圖3　死鎖邊界時間 Fig. 3　Deadlock boundary time

Urllib2爬蟲算法等待時間合計為2 h 9 min 7 s，死鎖次數(shù)為30次，死鎖率為30%；銀行家算法等待時間合計為1 h 38 min 28 s，死鎖次數(shù)為2次，死鎖率為2%，算法對比實驗結(jié)果如表3所示。實驗結(jié)果表明，本文算法明顯降低了死鎖率，提高了系統(tǒng)運行效率。傳統(tǒng)資源配置算法死鎖率高、效率低下。

表 3　實驗結(jié)果對比

3結(jié)束語

本文基于銀行家算法，在多用戶操作系統(tǒng)中，提出一種新的網(wǎng)絡(luò)爬蟲資源配置策略。這種基于銀行家算法的網(wǎng)絡(luò)爬蟲資源配置策略不但提高了網(wǎng)絡(luò)爬蟲資源的利用率，而且能夠有效避免死鎖的發(fā)生。下一步的研究工作可以在目前己有的策略上有針對性、方向性地進一步分析和研究降低死鎖率的方法。

參考文獻:

[1]RICART G, AGRAWALA A K. An optimal algorithm for mutual exclusion in computer networks[J]. Communications of the ACM, 1981, 24(1): 9-17.

[2]WANG Hong. The study of banker's algorithm base on experiment[J]. Applied Mechanics and Materials, 2013, 442: 303-308.

[3]HAO Yue, HU Hesuan. Robust deadlock control using shared-resources for production systems with unreliable workstations[C]//2013 IEEE International Conference on Automation Science and Engineering. Madison, USA, 2013: 1095-1100.

[4]YUE Hao, HU Hesuan. A polynomial deadlock avoidance policy for a class of assembly processes based on petri nets[C]//2013 IEEE International Conference on Automation Science and Engineering. Madison, USA, 2013: 1151-1156.

[5]MA Xiaohui, YAN Junya. An improved parallel banker's algorithm based on petri net[C]//2011 International Conference on Electronic and Mechanical Engineering and Information Technology. Harbin, China, 2011: 1538-1541.

[6]XIAO Xiang, LEE J J. A true 0(1) parallel deadlock detection algorithm for single-unit resource systems and its hardware implementation[J]. IEEE Transaction on Parallel and Distributed System, 2010, 21(1): 4-19.

[7]LOU Lin, TANG Feilong, YOU I, et al. An effective deadlock prevention mechanism for distributed transaction management[C]//2011 Fifth International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing. Seoul, Korea, 2011: 120-127.

[8]REVELIOTIS S A, ROSZKOWSKA E. Conflict resolution in free-ranging multivehicle systems: a resource allocation paradigm[J]. IEEE Transactions on Robotics, 2011, 27(2): 283-296.

[9]LANG S D. An extended banker's algorithm for deadlock avoidance[J]. IEEE Transactions on Software Engineering, 1999, 25(3): 428-432.

[10]TANG Feilong, YOU I, YU Shui, et al. An efficient deadlock prevention approach for service oriented transaction processing[J]. Computers & Mathematics with Applications, 2012, 63(2): 458-468.

[11]DUDA C, PREY G, KOSSMANN D, et al. Ajax crawl: making Ajax applications searchable[C]//IEEE 25th International 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 Computer Science and Electronic Engineering. Hangzhou, China, 2012: 590-594.

[13]楊梅, 滕少華. 基于死鎖避免的資源安全分配算法[J]. 計算機工程與設(shè)計, 2011, 32(1): 40-43.

YANG Mei, TENG Shaohua. Improved safe resource allocation algorithm based on deadlock avoidance[J]. Computer Engineering and Design, 2011, 32(1): 40-43.

[14]陳昊成. 基于網(wǎng)格計算的資源管理與分配系統(tǒng)的設(shè)計與實現(xiàn)[D]. 哈爾濱: 哈爾濱工業(yè)大學(xué), 2010.

CHEN Haocheng. Design and implementation of resource management and allocation system based on grid computing[D]. Harbin, China: Harbin Institute of Technology, 2010.

[15]章韻, 湯楠. 服務(wù)計算中避免死鎖和活鎖的資源分配算法[J]. 微電子學(xué)與計算機, 2010, 27(12): 69-73, 77.

ZHANG Yun, TANG Nan. Deadlock and livelock free resource allocation algorithm in service oriented computing[J]. Microelectronics & Computer, 2010, 27(12): 69-73, 77.

[16]SHETTY K S, BHAT S, SINGH S. Symbolic verification of web crawler functionality and its properties[C]//2012 International Conference on Computer Communication and Informatics. Coimbatore, India, 2012: 1-6.

王慶紅，男，1976年生，高級設(shè)計師，技術(shù)情報所所長，主要研究方向為電力系統(tǒng)運行、規(guī)劃與設(shè)計以及企業(yè)情報系統(tǒng)建設(shè)與管理。

李廣凱，男，1975年生，副教授，博士，主要研究方向為電力系統(tǒng)企業(yè)技術(shù)情報咨詢及直流輸電技術(shù)。

周育忠，男，1974年生，高級工程師，主要研究方向為行業(yè)情報系統(tǒng)建設(shè)、運維管理和資源整合。