计算机工程

• 先进计算与数据处理 • 上一篇    下一篇

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

孙立斌1,2,陈闳中1,2,邓 蓉1,2   

  1. (1. 同济大学计算机科学与技术系,上海 201804;2. 同济大学嵌入式系统与服务计算教育部重点实验室,上海 200092)
  • 收稿日期:2012-12-29 出版日期:2014-02-15 发布日期:2014-02-13
  • 作者简介:孙立斌(1989-),男,硕士,主研方向:网格计算,操作系统,分布式计算;陈闳中,教授、博士生导师;邓 蓉,讲师
  • 基金项目:
    国家科技支撑计划基金资助项目(2012BAH15F03)

A Load Balanced Online Scheduling Algorithm in Grids

SUN Li-bin 1,2, CHEN Hong-zhong 1,2, DENG Rong 1,2   

  1. (1. Department of Computer Science and Technology, Tongji University, Shanghai 201804, China; 2. Key Laboratory of Embedded System and Service Computing, Ministry of Education, Tongji University, Shanghai 200092, China)
  • Received:2012-12-29 Online:2014-02-15 Published:2014-02-13

摘要: 任务调度是网格领域的一个核心问题。针对网格资源及任务高度异构环境下的负载失衡问题,设计一种负载均衡的在线任务调度算法BOS。BOS算法在进行任务调度时,综合考虑任务到达频率、任务计算量、任务的完成时刻以及任务开始执行时刻等因素。任务周转时间由执行时间和等待时间2个部分组成。对于长任务,执行时间占更大比重。而对于短任务,等待时间的影响更大。算法根据长任务和短任务的各自特点,引入适应度的概念来指导调度。实验结果表明,与MCT算法相比,BOS算法的调度跨度、任务周转时间、响应比更小,资源利用率更高,负载也更加均衡。

关键词: 网格计算, GridSim仿真器, 任务调度, 负载均衡, 资源利用率

Abstract: Task scheduling is a core issue in grid computing. In view of the load imbalance problem caused by the high heterogeneity of grid resources and tasks, a Balanced Online Scheduling(BOS) algorithm is proposed. The algorithm comprehensively considers task arrival frequencies, task size, task completion time and task execution moment. A task’s turnaround time consists of two parts, such as waiting time and executing time. For a long task, executing time accounts for a greater proportion, while for a short task, waiting time is more critical. Thus, different policies are used for short and long tasks. Experimental results show that compared with MCT algorithm, BOS shortens makespan, average task turnaround time, and average stretch. Resource utilization and load balance factor are improved.

Key words: grid computing, GridSim simulator, task scheduling, load balance, resource utilization

中图分类号: