Distributed scheduling of tasks with deadlines and resource requirements

Abstract

A set of four heuristic algorithms is presented to schedule tasks that have headlines and resource requirements in a distributed system. When a task arrives at a node, the local scheduler at that node attempts to guarantee that the task will complete execution on that node before its deadline. If the attempt fails, the scheduling components on individual nodes cooperate to determine which other node in the system has sufficient resource surplus to guarantee the task. Simulation studies are performed to compare the performance of these algorithms with respect to each other as well to two baselines. The first baseline is the noncooperative algorithm where a task that cannot be guaranteed locally is not sent to any other node. The second is an (ideal) algorithm that behaves exactly like the bidding algorithm but incurs no communication overheads. The simulation studies examine how communication delay, task laxity, load differences on the nodes, and task computation times affect the performance of the algorithms. The results show that distributed scheduling is effective even in a hard real-time environment and that the relative performance of these algorithms is a function of the system state.