APP下载

一种负载均衡的网格在线调度算法

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查看全文

猜你喜欢

资源
让有限的“资源”更有效
污水磷资源回收
基础教育资源展示
崛起·一场青铜资源掠夺战
我给资源分分类
资源回收
做好绿色资源保护和开发
资源再生 欢迎订阅
激活村庄内部治理资源
资源三号卫星控制系统概述及在轨验证