[1]王庆红,李广凯,周育忠,等.一种基于银行家算法的网络爬虫资源配置策略[J].智能系统学报,2015,10(3):494-498.[doi:10.3969/j.issn.1673-4785.201409021]
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.[doi:10.3969/j.issn.1673-4785.201409021]
点击复制
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.[doi:10.3969/j.issn.1673-4785.201409021]
一种基于银行家算法的网络爬虫资源配置策略
《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷:
10
期数:
2015年第3期
页码:
494-498
栏目:
学术论文—机器学习
出版日期:
2015-06-25
- Title:
- A web crawler resource allocation strategy based on the Banker’s algorithm
- Keywords:
- operating system; resource allocation; deadlock; system safety; Banker’s algorithm; web crawler
- 分类号:
- TP361;TM75
- 文献标志码:
- A
- 摘要:
- 死锁是多用户操作系统正常运行的一个重要问题,系统资源不足会导致爬虫算法进入不安全状态,进而引发死锁等问题.引入被广泛用于操作系统的银行家算法,调度多个网络爬虫进程并发运行,并且为每个进程合理分配系统资源,当进程无法获取系统资源时,则等待其他进程分配完成后释放系统资源,从而完成资源分配,有效降低死锁率.采用C++编程,设计并实现基于银行家算法的网络爬虫配置策略.通过2 h 21 min 35 s工程测试,urllib2算法死锁率为30%,新算法死锁率仅为2%,测试证明该策略能够有效降低死锁率,能高效完成多个任务进程的资源分配.
- 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.
- 参考文献/References:
-
[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]. 计算机工程与设计, 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] 陈昊成. 基于网格计算的资源管理与分配系统的设计与实现[D]. 哈尔滨: 哈尔滨工业大学, 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] 章韵, 汤楠. 服务计算中避免死锁和活锁的资源分配算法[J]. 微电子学与计算机, 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.
- 相似文献/References:
-
[1]齐小刚,方魁,宋卫星,等.装备维修保障资源配置综述[J].智能系统学报,2022,17(2):221.[doi:10.11992/tis.202109010]
QI Xiaogang,FANG Kui,SONG Weixing,et al.Summary of equipment maintenance support resource configuration[J].CAAI Transactions on Intelligent Systems,2022,17():221.[doi:10.11992/tis.202109010]
[2]秦敏敏,刘立芳,齐小刚.面向维修资源分配调度的遗传-长鼻浣熊混合优化算法[J].智能系统学报,2023,18(6):1322.[doi:10.11992/tis.202303035]
QIN Minmin,LIU Lifang,QI Xiaogang.Hybrid genetic long-nosed raccoon optimization algorithm for maintenance resource allocation and scheduling[J].CAAI Transactions on Intelligent Systems,2023,18():1322.[doi:10.11992/tis.202303035]
备注/Memo
收稿日期:2014-9-12;改回日期:。
作者简介:王庆红,男,1976年生,高级设计师,技术情报所所长,主要研究方向为电力系统运行、规划与设计以及企业情报系统建设与管理.李广凯,男,1975年生,副教授,博士,主要研究方向为电力系统企业技术情报咨询及直流输电技术.周育忠,男,1974年生,高级工程师,主要研究方向为行业情报系统建设、运维管理和资源整合.
通讯作者:王庆红. E-mail: wangqh@csg.cn.
更新日期/Last Update:
2015-07-15