一种基于冗余分配的网格计算任务调度方法的研究

２ＯＯ７年３月　第２１卷第１期　南昌航空工业学院学报（自然科学版）　Ｊｏｕｒｎａｌ　ｏｆＮ￣ｃｈｎｇ　ａＩｎｓｉｔｔｕｔｅ　ｏｆＡｅｒｏｎａｕｔｉｃａｌ　Ｔｅｃｈｎｏｌｏｇｙ（Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ）　Ｍａｒ．，２００７　ｖ０１．２１　Ｎｏ．１　一种基于冗余分配的网格计算任务调度方法的研究　、　黄华　，张立东２　（１．南昌航空工业学院，江西南昌　３３００６３；２．嘉昭科技有限公司，广东深圳５１８０３３）　［关键词］网格计算；任务调度；冗余分配　［摘要］提出了一种基于冗余分配的网格计算任务调度方法，包含资源预测、资源调度和任务分配三部分，并将其应用于　用二分法求解高次方程中，取得了运行时间短和兼顾负载平衡的应用效果，验证了该算法的有效性。　［中图分类号］ＴＰ３９３．１　［文献标识码］Ａ　［文章编号］１００１—４９２６（２００７）０１—００６１—０３　Ｒｅｓｅａｒｃｈ　ｏｆ　ｔａｓｋ　ｓｃｈｅｄｕｌｉｎｇ　ｆｏｒ　ｇｒｉｄ　ｃｏｍｐｕｔｉｎｇ　ｂａｓｅｄ　ｏｎ　ｒｅｄｕｎｄａｎｔ　ｄｉｓｔｒｉｂｕｔｉｏｎ　ＨＵＡＮＧ　Ｈｕａ　．ＺＨＡＮＧ　Ｌｉ—Ｄｏｎ￣ｚ　（１．Ⅳ（眦＾０昭Ｉｎｓｔｉｔｕｔｅ　ｏｆＡｅｒｏｎａｕｔｉｃａｌ　Ｔｅｃｈｎｏｌｏｇｙ，Ⅳ（忧　昭，Ｊｉａｎ￣ｉ　３３００６３　２．Ｃｏｒａｃｔ　Ｔｅｃｈｎｏｌｏｇｙ　Ｃｏｍｐａｎｙ，／ｔｄ．Ｓｈｅｎｚｈｅｎ，Ｇｕａｎｇａｂｎｇ　５１８０３３，Ｃ／ａｎａ）　Ｋｅｙ　ｗｏｒｄｓ：ｇａｄ　ｃｏｍｐｕｔｉｎｇ；ｔａｓｋ　ｓｃｈｅｄｕｌｉｎｇ；ｒｅｄｕｎｄａｎｔ　ｄｉｓｔｒｉｂｕｔｉｏｎ　Ａｂｓｔｒａｃｔ：１１ｌｉｓ　ｐａｐｅｒ　ｐｒｅｓｅｎｔｓ　ａｎ　ａｐｐｒｏａｃｈ　ｏｆ　ｔａｓｋ　ｓｃｈｅｄｕｌｉｎｇ　ｆｏｒ　ｇｒｉｄ　ｃｏｍｐｕｔｉｎｇ　ｂａｓｅｄ　ｏｎ　ｒｅｄｕｎｄａｎｔ　ｄｉｓｔｒｉｂｕｔｉｏｎ。ｗｈｉｃｈ　ｉｓ　ｃｏｍｐｏｓｅｄ　ｏｆ　ｒｅ—　ｓｏｕｒｃｅ　ｐｒｅｄｉｃｔｉｏｎ．Ｉｅｓｏｕｒｃｅ　ｓｃｈｅｄｕｌｉｎｇ　ａｎｄ　ｔａｓｋ　ｄｉｓｔｉｒｂｕｔｉｏｎ．Ａｎｄ　ｔｈｅｎ　ｉｔ　ｉｓ　ａｐｐｌｉｄ　ｉｅｎ　ｔｈｅ　ｓｉｍ￣ａｔｉｏｎ　ｏｆ　ｓｏｌｖｉｎｇ　ａ　ｈｉｓｈ—ｐｏｗｅｒ　ｅｑｕａｔｉｏｎ　ｉｎ　ｄｉ—　ｃｈｏｔｏｍｙ．Ｔｈｅ　ｒｅｓｕｌｔ　ｉｓ　ｓｈｏａ　ｅｘｅｃｕｔｉｖｅ—ｔｉｍｅ　ｎｄ　ａｆａｖｏｒａｂｌｅ　ｌｏａｄ　ｂａｌａｎｃ￣．Ｓｏ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｐｒａｃｉｔｃａｌ　ａｎｄ　ｅｆｆｅｃｔｉｖｅ．　网格是一个集成的计算与资源环境，能够充分吸收分布在不同地方的各种资源，转化为一个虚拟的、统　一的和强大的计算环境，这种计算方式称为“网格计算”。网格计算强调计算资源和计算能力的动态共享，任　务调度问题是其研究领域中的一个关键问题。网格任务调度的目标是将ｎ个任务分配到ｍ个异构可用资　源上，使得总任务的完成时间最小以及资源得到充分利用【１，３Ｊ。　本文在研究现有网格任务调度算法的基础上，针对网格计算结果的正确性问题，提出了一种基于冗余分　配的任务调度算法。该算法建立在资源预测和资源调度的基础上，采用冗余分配任务的方式，以保证所获得　的可用计算资源能够计算出正确的结果。　１基于冗余分配的任务调度方法　１．１网格计算任务调度　网格环境是异构的且动态性很强。任何计算节点在任何时刻都不一定稳定，所以必须随时对其性能变　化进行预测，及时收集各节点的参数信息，并需考虑任务调度算法的移植性和可扩展性。　（１）异构性。任务调度是面向异构平台的。由于网格系统是由分布在Ｉｎｔｅｍｅｔ上的各类资源组成的。　包括各类主机、工作站甚至ＰＣ机，它们是异构的，可运行在Ｕｎｉｘ或Ｗｉｎｄｏｗｓ　ＮＴ等各种操作系统下，也可以　是上述机型的机群系统、大型存储设备、数据库或其他设备。　（２）非集中式。任务调度是大规模非集中式的。网格系统是一个大到整个Ｉｎｔｅｍｅｔ的分布式巨系统。网　格的任务调度必须以分布、并行方式进行任务的管理与调度。　（３）可扩展性。在网格资源规模不断扩大、应用不断增长的情况下，网格系统的仟务调度必须具有可扩　［收稿日期］２００７一Ｏ１—２０　［基金项目］省重大攻关项目资助（（２００５１Ａ０１００６），江西省自然科学基金资助（０５１１０７）　［作者简介］黄华（１９７２一），女，汉族，南昌航空工业学院计算机学院副教授，主要从事：计算机应用　维普资讯 http://www.cqvip.com

南昌航空工业学院学报（自然科学版）　展性，不致降低网格系统的性能。　（４）动态自适应。任务调度能够动态自适应，网格中的资源不但是异构的而且网格的结构总是不停地　改变，网格的动态性很明显。任务调度系统必须适应网格的这种动态性。　针对上述网格计算中任务调度算法的特点，兼顾到负载平衡和计算结果正确性的问题，本文提出的调度　方法包含下列三部分内容：资源预测、资源调度和冗余任务分配。通过资源预测和资源调度方法，保证从现　有网格计算资源中找出合适的资源；通过冗余任务分配方法，保证将任务安排到合适的机器上，在充分利用　计算资源的同时实现验证计算结果正确的功能ｌ２Ｊ。　１．２资源预测方法　资源状态预测的作用是收集网格各计算节点的信息并为资源调度提供系统的预测值，由于需要消耗一　定的计算资源，因而采用短期资源预测。　短期资源预测算法思想为：　（１）设置一个线程，每隔１秒收集一次节点状态信息，主要是ＣＰＵ和内存的使用率。　（２）设置一个循环队列，将一分钟内的得到的信息平均值不断地写入该队列。　（３）当资源调度方法有预测需求时，将队列中的数值读出再取平均值作为预测值。　为了描述计算节点的状态变化，采用模糊定性方式定义　各计算节点状态。共分为五种状态：ｖｅｒｙ　ｂｕｓｙ、ｂｕｓｙ、ｍｅｄｉｕｍ、　ｖａｃａｎｔ、ｖｅｒｙ　ｖａｃａｎｔ。当预测值Ｐ≥９０，将其状态定为ｖｅｒｙ　ｂｕｓｙ；　ｖｅｒｙ　ｂｕｓｙ　—一网络节点一　当预测值ｐＥ［７０，９０），将其状态定为ｂｕｓｙ；当预测值ｐＥ［５０，　７０），将其状态定为ｍｅｄｉｍ；ｕ当预测值ｐＥ［３０，５０），将其状态定　为ｖａｃａｎｔ；当预测值ｐ＜３０，将其状态定为ｖｅｒｙ　ｖａｃａｎｔ。而为了　描述处于同一状态的计算节点集信息，采用哈希表的组织形　式，如图１所示。　ｂｕｓｙ　ｍｅｄｉｕｍ　ｖａｃａｎｔ　—一－４网络节点一　—－一　网络节点一　—－Ｊ　网络节点一　１．３资源调度方法　Ｖｅｒｇ　ｖａｃａｎｔ　—－一　网络节点一　资源调度就是为某一任务找到合适的计算节点，其思想　图ｌ网格计算资源组织形式　为当要分配某一节点时再次通过资源预测获取它的信息，以　该最新信息作为调度的标准，若最新状态差于原有状态，则不分配该节点，否则进行分配　，引。　资源调度方法的描述为：　（１）根据任务分割结果获得子任务数，并将其作为资源个数的最大请求数。　（２）在哈希表中从资源状态最好的队列中开始查询，从队列中依次取出节点，再用资源预测获得其现有　状态。　（３）若现有状态差于原先状态，则不分配该节点，并将其插入到与其状态一致的队列中；若优于原先状　态，则分配该节点，并将其插入到与其状态一致的队列中；若等同于原先状态，则分配；若探测不到该节点，则　将其从队列中删除。　（４）结束条件为当找到的可用资源等于或小于最大请求数时，直接把所有资源分配给任务。　１．４冗余任务分配算法　ＰＣ网格是一个计算资源非常丰富的动态网络，ＰＣ机可随时加入或退出，如果一个任务只分配给一台机　器，将极有可能由于该机器的退出而导致计算延误或无法完成计算任务。为了提高计算引擎的工作可靠性　和计算成功率，必须在计算引擎中加入容错机制。如在考虑计算模式容错性时，可在计算引擎的任务调度中　加入适度冗余，即把同一任务分配到多台ＰＣ机上执行，然后再对多台计算机返回的结果进行比较获得最终　计算结果。也就是说把同一任务分配到多台ＰＣ机上执行，用分配状态标记分配次数，任务执行结果标记在　计算结果中，再对多台计算机返回的结果进行比较，相同则在删除标记上置１，完成此任务的执行，直至所有　任务的删除标记均为ｌ时，任务分配结束［１，２ｊ。在本算法中，任务表的形式如表１所示。　维普资讯 http://www.cqvip.com

第１期　黄华、张立东：一种基于冗余分配的网格计算任务调度方法的研究　表１任务表　６３　分配算法描述如下：　基于冗余分配的网格计算任务调度算法　初始化操作，即设置任务表中的分配状态标记位均为０，计算结果均为ＮＵＬＬ，删除标记位均为０　Ｆｏｒ任务队列中所有子任务　Ｆｏｒ所有可用计算资源　将子任务分配到资源节点，同时任务表中的子任务分配状态标记为１　Ｅｎｄ　Ｆｏｒ　Ｅｎｄ　Ｆｏｒ　Ｄｏ　Ｕｎｔｉｌ任务表中所有子任务删除标记都为１　执行子任务　Ⅱ计算节点返回子任务执行结果　Ｔｈｅｎ将计算结果记录到任务表中的子任务计算结果标志位　ｎｄ　Ｉｆ　ＥⅡ存在相等的计算结果　ｈｅｎ将任务表中该子任务的删除标记位置为１，Ｔ　取消此子任务在其他计算节点上的执行，　随机选择一个删除标记位为０的子任务将其分配到刚送回结果的计算资源上，分配状态加　１　ｎｄ　ＩＥｆ　Ｅｎｄ　Ｄｏ　２实验与结果　将上述基于冗余分配的网格计算任务调度算法应用于二分法求解高次方程中，网格计算环境为局域网。　以求高次方程ｘ６一Ｘ一１＝０在［１，２］闭区间上的一个解为测试用例，要求结果精确Ｎ／Ｊ，数点后２０位。其模　拟计算引擎的运行界面如图２所示。　３　结论　通过网格测试实例分析，利用冗余分配算法进行网格计算任务调度时，既减轻预测的工作量，又达到负　载平衡的效果，保证较高的执行效率和较低的资源占用率，适合于网格计算环境的任务调度。以后如能进一　步将任务预测和任务调度策略结合起来，将更能提高算法的性能。　［　参考文献　］　［１］李相朋．动态负载均衡算法在校园网格中的应用［Ｊ］．微计算机信息，２ＯＯ６，（２２）．　［２］尚明生．网格计算中的任务调度模型研究［Ｊ］．计算机工程，２ＯＯ６，（２）．　［３］ｃａ蛐ｏｖ丑Ｈ．Ｍｏｄｅｌｉｎｇ　Ｉ丑增ｅ—ｓｃａｌｅ　Ｐｌａｔｆｏｌｌｌｌｓ　ｆｏｒ　ｔｈｅ　Ａｎａｌｙｓｉｓ　ａｎｄ　ｈｔｅ　Ｓｉｍｕｌａｔｉｏｎ　ｏｆ　ＳｃｈｅｄｕｌｉｒＩｇ　ｓｈ劬ｅｇｉｅｓ［ｃ］．Ｐｒｔｘ：ｅｅｄｉｎ￣ｏｆ　ｈｔｅ　６ｔｈ　Ｗｏｒｋｓｈｏｐ　Ｏｔ＇ｌ　Ａｄ一　啪嘲ｉｎ　Ｐａｒａｌｌｅｌ　ａｎｄ　Ｄｉｓｔｒｉｂｕｔｅｄ　Ｃ￣ｎｔｍｔａｔｉ０ｎａｌ　Ｍｏｄｅｌｓ，Ａ　１．２ＯＯ４．　（下转第８６页）　维普资讯 http://www.cqvip.com

南昌航空工业学院学报（自然科学版）　测量的要求，有推广应用价值。　读采样数据ｌ　ｌ　ｌ　数据量＝　２５６７　＝＝＝—　＼Ｙ　／　　ｌＩ　ｌ　数据送缓冲区　ｉ　采数标志置１　ｌ一　１　图５主函数流程框图　图６中断服务程序流程框图　［　参考文献　］　［１］－ｑ￣ｌＡ．，申莉，傅士冀　高精度工频相位计的研制［Ｊ］．电测与仪表，２００６，１　［２］苏奎峰，吕强，等．￣３２０Ｆ２８１２原理与开发［Ｍ］．电子工业出版社，２Ｏ０５，４．　［３］姚彬．传感器电路的抗干扰技术［Ｊ］　煤炭技术，２Ｏ０４，２３，（３）．　［４］张贤达　现代信号处理［Ｍ］　清华出版社，２Ｏ０２．　、　驴　驴驴驴驴驴驴　（上接第６３页）　图２模拟计算引擎运行界面