摘要： 任务调度是网格领域的一个核心问题。针对网格资源及任务高度异构环境下的负载失衡问题，设计一种负载均衡的在线任务调度算法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

中图分类号: 

• TP311