Abstract-In the design of distributed computer systems, the scheduling problem is considered to be an important one and has been addressed by many researchers. However, most approaches have not dealt with tasks' timing and resource requirements. In this paper, we describe a set of heuristic algorithms to schedule tasks that have deadlines and resource requirements, in a distributed system. These algorithms are dynamic and function in a decentralized manner. When a task arrives at a node, the local scheduler at that node attempts to guarantee that the task will complete execution before its deadline, on that node. 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. In this paper, four algorithms for cooperation are evaluated. They differ in the way a node treats a task that cannot be guaranteed locally. The random scheduling algorithm: The task is sent to a randomly selected node. The focused addressing algorithm: The task is sent to a node that is estimated to have sufficient surplus to complete the task before its deadline. The bidding algorithm: The task is sent to a node based on the bids received for the task from nodes in the system. Theflexible algorithm: The task is sent to a node based on a technique that combines bidding and focused addressing. Simulation studies were performed to compare the performance of these algorithms relative to each other as well as with respect 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.
Krithi Ramamritham et al. describe in REF a set of heuristics to schedule tasks with deadlines in a distributed system.
Distributed Scheduling of Tasks with Deadlines and Resource Requirements
IEEE Trans. Computers
IEEE Trans. Computers
Computer Science