Some Results of the Earliest Deadline Scheduling Algorithm

Abmw&-Task scheduling is an important issue in the design of a renl-timc computer system because tasks have execution deadlines that must be met, otherwise the system fails with severe consequences upon the environment. In this paper, we study the problem of scheduling periodic time critical tasks on a monoprocessor system. A periodic time critkal task consists of an infinite number of -quests, each of whieh has a prescribed deadline. Tasks are assumed to meet their timing requirements when scheduled by the Earliest Deadline algorithm and preemptions are allowed. We report results from some investigations into the problem of making optimum use of the remaining processor idle time in scheduling perlodk tasks either as soon as possible M as late as possible. The major results consist of the statement and proof of properties relating to bcdhtion and duration of idle time intervals and enable us to provide an elRcient algorlthm lor determining maximum quantity of total idle time available between any two instants. We describe how these results can be applied, Brst to the decision problem that arises when a sporadic time critical task occurs and requires to be run at an unpredictable time and second, to the scheduling problem that arises in a fault tolerant system using the deadline mechanism for which each task implements primary and alternate algorithms. Index Terms-Deadline mechanism, idle time, preemptive schedul