第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图 ２ 进程分配资源成功 Ｆｉｇ． ２ Ａｌｌｏｃａｔｉｏｎ ｓｕｃｃｅｓｓｆｕｌｎｅｓｓ ｆｏｒ ｐｒｏｃｅｓｓｅｓ ２．４ 实验结果 本文算法和 ｕｒｌｌｉｂ２ 爬虫算法对死锁问题进行 测试实验对比。 ｕｒｌｌｉｂ２ 是 Ｐｙｔｈｏｎ 中处理 ＨＴＴＰ 协议 的算法库，可用于监测网络爬虫资源的死锁［１６］ 。 设 置超时时间为 ２ ｍ，当爬虫资源发生死锁后超时，记 录该任务的状态为 Ｌｏｃｋｅｄ，完成其他任务后重启该 任务；未发生死锁从而完成任务请求，则记录改任务 的状态为 Ｃｏｍｐｌｅｔｅｄ，并记录等待时间。 ｕｒｌｌｉｂ２ 爬虫 算法抓取日志如表 １ 所示，本文算法抓取日志如表 ２ 所示。 表 １ Ｕｒｌｌｉｂ２ 爬虫算法抓取日志 Ｔａｂｌｅ １ Ｕｒｌｌｉｂ２ ｃｒａｗｌｅｒ ａｌｇｏｒｉｔｈｍ ｃｒａｗｌ ｌｏｇ 事 件 任务 开始时间 等待时间 死锁 边界时间 Ｌｏｃｋｅｄ：Ｒｅｑｕｅｓｔ１ １９：４７：０８ ０：０２：００ ０：０２：００ Ｌｏｃｋｅｄ：Ｒｅｑｕｅｓｔ２ １９：４９：５２ ０：０２：００ ０：０２：００ Ｌｏｃｋｅｄ：Ｒｅｑｕｅｓｔ３ １９：５２：１３ ０：０２：００ ０：０２：００ Ｃｏｍｐｌｅｔｅｄ：Ｒｅｑｕｅｓｔ４ １９：５４：３８ ０：０１：２１ ０：０２：００ Ｃｏｍｐｌｅｔｅｄ：Ｒｅｑｕｅｓｔ５ １９：５５：５９ ０：０２：００ ０：０２：００ Ｃｏｍｐｌｅｔｅｄ：Ｒｅｑｕｅｓｔ６ １９：５８：４２ ０：０１：０６ ０：０２：００ Ｌｏｃｋｅｄ：Ｒｅｑｕｅｓｔ７ １９：５９：４８ ０：０２：００ ０：０２：００ Ｃｏｍｐｌｅｔｅｄ：Ｒｅｑｕｅｓｔ８ ２０：０２：０１ ０：００：４１ ０：０２：００ Ｃｏｍｐｌｅｔｅｄ：Ｒｅｑｕｅｓｔ９ ２０：０２：４２ ０：００：２７ ０：０２：００ Ｃｏｍｐｌｅｔｅｄ：Ｒｅｑｕｅｓｔ１０ ２０：０３：０９ ０：０１：１２ ０：０２：００ Ｃｏｍｐｌｅｔｅｄ：Ｒｅｑｕｅｓｔ１１ ２０：０４：２０ ０：０１：５８ ０：０２：００ Ｌｏｃｋｅｄ：Ｒｅｑｕｅｓｔ１２ ２０：０６：１８ ０：０２：００ ０：０２：００ Ｃｏｍｐｌｅｔｅｄ：Ｒｅｑｕｅｓｔ１３ ２０：０９：００ ０：００：３６ ０：０２：００ Ｃｏｍｐｌｅｔｅｄ：Ｒｅｑｕｅｓｔ１４ ２０：０９：３６ ０：００：３６ ０：０２：００ Ｌｏｃｋｅｄ：Ｒｅｑｕｅｓｔ１５ ２０：１０：１２ ０：０２：００ ０：０２：００ Ｌｏｃｋｅｄ：Ｒｅｑｕｅｓｔ１６ ２０：１２：２６ ０：０２：００ ０：０２：００ Ｌｏｃｋｅｄ：Ｒｅｑｕｅｓｔ１７ ２０：１５：１７ ０：０２：００ ０：０２：００ ︙ ︙ ︙ ︙ Ｃｏｍｐｌｅｔｅｄ：Ｒｅｑｕｅｓｔ１００ ２２：０８：４３ ０：００：３６ ０：０２：００ 表 ２ 本文算法抓取日志 Ｔａｂｌｅ ２ Ｂａｎｋｅｒ＇ｓ ａｌｇｏｒｉｔｈｍ ｃｒａｗｌ ｌｏｇ 事 件 任务 开始时间 等待时间 死锁 边界时间 Ｃｏｍｐｌｅｔｅｄ：Ｒｅｑｕｅｓｔ１ １９：４７：０８ ０：００：４１ ０：０２：００ Ｃｏｍｐｌｅｔｅｄ：Ｒｅｑｕｅｓｔ２ １９：４９：５２ ０：０１：０１ ０：０２：００ Ｃｏｍｐｌｅｔｅｄ：Ｒｅｑｕｅｓｔ３ １９：５２：１３ ０：０１：０５ ０：０２：００ ︙ ︙ ︙ ︙ Ｌｏｃｋｅｄ：Ｒｅｑｕｅｓｔ３６ ２０：４２：２９ ０：０２：００ ０：０２：００ ︙ ︙ ︙ ︙ Ｌｏｃｋｅｄ：Ｒｅｑｕｅｓｔ４８ ２０：５８：３８ ０：０２：００ ０：０２：００ ︙ ︙ ︙ ︙ Ｃｏｍｐｌｅｔｅｄ：Ｒｅｑｕｅｓｔ１００ ２２：０８：４３ ０：００：３６ ０：０２：００ 分别采用 ｕｒｌｌｉｂ２ 爬虫算法和本文算法进行 １００ 次请求操作，如果在超时时间之内，爬虫资源完成请 求操作，则日志中记录该次请求操作为 Ｃｏｍｐｌｅｔｅｄ， 反之在所设置的超时时间之内未能请求成功，则日 志中记录该次请求操作为 Ｌｏｃｋｅｄ，表示发生死锁。 本文算法和 ｕｒｌｌｉｂ２ 爬虫算法死锁边界时间如图 ３ 所示，纵坐标表示任务等待时间，横坐标表示测试实 验的时间范围为 １９：４７：０８—２２：０８：４３，等待时间等 于 ２ ｍｉｎ 表明任务请求发生死锁，小于 ２ ｍｉｎ 表明任 务请求完成。 图 ３ 死锁边界时间 Ｆｉｇ． ３ Ｄｅａｄｌｏｃｋ ｂｏｕｎｄａｒｙ ｔｉｍｅ Ｕｒｌｌｉｂ２ 爬虫算法等待时间合计为 ２ ｈ ９ ｍｉｎ ７ ｓ， 死锁次数为 ３０ 次，死锁率为 ３０％；银行家算法等待时 间合计为 １ ｈ ３８ ｍｉｎ ２８ ｓ，死锁次数为 ２ 次，死锁率为 ２％，算法对比实验结果如表 ３ 所示。 实验结果表明， 本文算法明显降低了死锁率，提高了系统运行效率。 传统资源配置算法死锁率高、效率低下。 表 ３ 实验结果对比 Ｔａｂｌｅ ３ Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ 算 法 等待时间合计 死锁次数 死锁率／ ％ ｕｒｌｌｉｂ２ 算法 ２：０９：０７ ３０ ３０ 银行家算法 １：３８：２８ ２０ ２ 第 ３ 期 王庆红，等：一种基于银行家算法的网络爬虫资源配置策略 ·４９７·