Heuristic Scheduling

for Distributed

Hard Real-Time Systems

Gerhard Fohler?, Christian Koza
Institut f?ur Technische Informatik
Technische Universit?at Wien
[email protected],[email protected]

Abstract

In hard real-time systems it is of crucial importance to meet the specified timing constraints. For parallel execution of tasks the need for communication and synchronization among them has to be considered. These requirements of task-sets are represented in the form of precedence graphs. All tasks have to access the Cpu and the network such that the specified timing requirements can be guaranteed under all foreseen circumstances.

This paper describes the development of an off-line scheduling algorithm, which takes the dependencies and timing constraints of a task-set into account. It determines a schedule for that task-set before run-time. Thus a verification of the defined timing behavior can be performed before run-time. The algorithm is based on heuristic search. The heuristic function used for that search is derived.

?This work has been supported in part by ESPRIT Basic Research Action No. 3092 - Predictably Dependable Computer Systems and by Digital Equipment Corporation under contract EERP/AU-011.