关键词: 移动网格, 任务调度, 动态资源, DAG图, 重调度

Abstract:

Taking mobile grid as background, the problem of scheduling related tasks on dynamic resource environment was studied. During scheduling, not only dependencies between tasks, but also resources’ dynamic behavior such as joining, leaving and performance changes are considered. Dynamic scheduling policy was proposed, which includes task subset scheduling and rescheduling. Dynamic partition of subset mainly focuses on dependencies between tasks and helps reduce the number of rescheduling. Subset scheduling objective and constraints were described and particle swarm scheduling algorithm was put forward, which integrates the idea of simulated annealing. Rescheduling further improves the adaptability of scheduling policy to the dynamic behavior of resources. Rescheduling trigger conditions was explained. The complete process of related tasks scheduling in mobile grid was given, as well as complexity analysis and experimental analysis of the proposed algorithm. Experiment results demonstrate the effectiveness of scheduling policy.

Key words: mobile grid;task scheduling;dynamic resources;DAG graph;reschedule