Tight Performance Bounds of Heuristics for a Real-Time Scheduling ProblemReport
The problem of scheduling a set of periodic tasks on a number of processors using a fixed-priority assignment scheme was first studied by Dhall and Liu in their paper entitled "On a real-time scheduling problem". Two scheduling heuristics ⎯ Rate-Monotonic-Next-Fit (RMNF) and Rate-Monotonic-First-Fit (RMFF) were proposed, and their worst-case performance was proven to have an upper bound of 2.67 and 2.2, and a lower bound of 2.4 and 2.0, respectively. In this paper, we first tighten up the worst-case bounds for both RMNF and RMFF, and at the same time, correct some errors existing in the original proof of the upper bound for RMFF. The tight worst-cast bounds of RMNF and RMFF are proven to be 2.67 and 2.33, respectively. Then, in an effort to find a more efficient algorithm, we propose a new scheduling heuristic ⎯ Rate-Monotonic-Best-Fit (RMBF), and study its worst-case performance. Surprisingly, RMBF also has a tight worst case bound of 2.33.
Note: Abstract extracted from PDF text
All rights reserved (no additional license for public reuse)
Oh, Yingfeng, and Sang Son. "Tight Performance Bounds of Heuristics for a Real-Time Scheduling Problem." University of Virginia Dept. of Computer Science Tech Report (1993).
University of Virginia, Department of Computer Science