BROWSE
Detail
Conference Paper
An Optimal Real-Time Scheduling Algorithm for Multiprocessors
Cited 173 time in 
Share 
Share
- Authors
- Hyeon Joong Cho, Binoy Ravindran, E. Douglas Jensen
- Issue Date
- 2006-12
- Citation
- International Real-Time Systems Symposium (RTSS) 2006, pp.101-110
- Language
- English
- Type
- Conference Paper
- Abstract
- We present an optimal real-time scheduling algorithm for multiprocessors - one that satisfies all task deadlines, when the total utilization demand does not exceed the utilization capacity of the processors. The algorithm called LLREF, is designed based on a novel abstraction for reasoning about task execution behavior on multiprocessors: the Time and Local Execution Time Domain Plane (or T-L plane). LLREF is based on the fluid scheduling model and the fairness notion, and uses the T-L plane to describe fluid schedules without using time quanta, unlike the optimal Pfair algorithm (which uses time quanta). We show that scheduling for multiprocessors can be viewed as repeatedly occurring T-L planes, and feasibly scheduling on a single T-L plane results in the optimal schedule. We analytically establish the optimality of LLREF. Further, we establish that the algorithm has bounded overhead, and this bound is independent of time quanta (unlike Pfair). Our simulation results validate our analysis on the algorithm overhead. © 2006 IEEE.
- KSP Keywords
- Local execution, Optimal real-time scheduling, Scheduling algorithm, Scheduling model, execution time, optimal schedule, simulation results, task execution, time-domain