Worst Case Analysis for On-Line Scheduling in Real-Time Systems

On-line scheduling in real-time environments has been studied by a number of researchers [8, 16, 13, 4, 10, 1]. If the system is not overloaded, there exist several optimal uniprocessor on-line scheduling algorithms for real-time tasks, such as Earliest-DeadlineFirst and Least-Laxity-First. However, it has been proven that there are no optimal multiprocessor on-line scheduling algorithms for real-time tasks [8]. On the other hand, if overload is allowed, no optimal on-line scheduling algorithms exist, even for uniprocessors. Many researchers have turned to approximation algorithms [8, 16, 13, 4]. Therefore, it is important to study the behavior of approximation algorithms. A good on-line scheduling algorithm should have both good average performance and good worst case performance. If we know the performance range of an on-line scheduling algorithm, it will greatly help in designing predictable real-time systems. In this paper, we study the performance bounds for both uniprocessor and ..