EVALUATION OF REAL~TIME SCHEDULING ALGORITHMS UNDER OVERLOAD CONDITIONS

Abstract

In real-time systems, each task has deadline before which it must be completed. For -uniprocessor system earliest deadline first (EDF) algorithm is optimal for scheduling preemptible tasks with arbitrary arrival times, however, EDF performs very poorly under conditions of overload. From scheduling theory of real-time systems,it is known that no on-line scheduling algorithm operating in an uniprocessor environment can guarantee to obtain- a useful processor utilization greater than 0.25 under condition of overload. This result holds in the general case where the deadlines of input tasks can be arbitrarily tight The dissertation addresses the problem of scheduling under overload conditions in environments where there is a limit on the tightness of task deadlines. Performance of scheduling algorithm, ROBUST, which works efficiently under overload condition is evaluated and analysed. A new scheduling algorithm, Modified EDF, is then presented which works efficiently under both normal (non overload) and overload conditions. The Modified EDF algorithm has been proved to perform as efficiently as the ROBUST algorithm during overload interval. Finally performance of Modified EDF algorithm as a deadline guarantee scheme (in a distributed real-time system) has been investigated. It is found through simulation that Modified EDF guarantee scheme 'gives improved useful processor utilization.