一种负载均衡的网格在线调度算法
2014-09-29孙立斌陈闳中
计算机工程 2014年2期
关键词:资源
孙立斌,陈闳中,邓 蓉
(1.同济大学计算机科学与技术系,上海 201804;2.同济大学嵌入式系统与服务计算教育部重点实验室,上海 200092)
1 概述
网格任务调度[1]是网格领域的一个核心问题,也是一个NP完全问题。国内外有许多关于网格调度的研究,调度算法可以分为2类,即批处理调度和在线调度[2]。目前绝大多数算法针对的都是批处理调度问题。
在批处理调度中,当被调度任务集中累积了一定的数量任务,或者到了一定时间间隔时,才开始调度,对于先到达的任务来说,即使有空闲的资源存在,它也不会被映射执行,这不仅浪费了资源的处理能力,也不利于缩短任务的周转时间。
任务的周转时间由执行时间和等待时间构成。对于小任务,等待调度时间对周转时间的影响尤为重要。目前成熟的批处理调度算法有 Min-Min、Max-Min[3-4]、Sufferage[5]、遗传算法[6-7]、模拟退火[4]、蚁群算法[8]等。
与批处理调度不同,在线调度采用了立即调度的方式,当任务到达后,立即为其分配处理资源。目前,已有的在线任务调度算法主要有 MCT、OLB、MET、SA、KPB[5],在这些算法中,MCT常作为衡量在线算法优劣的基准[5],而MET、SA、KPB适用于资源不一致性异构的情况。所谓不一致性异构,指的是如果有些任务在资源A上执行得比资源B快,而另一些任务在资源B上执行得比资源A快,那么资源A和资源B就是不一致异构的[5]。
本文考虑任务在线到达、资源一致性异构的情况,设计一种负载平衡的在线调度(Balanced Online Scheduling,BOS)算法,在为任务分配资源时,综合考虑任务到达频率、任务开始执行时刻、完成时刻等因素。……
登录APP查看全文
