Item Details

Tight Performance Bounds of Heuristics for a Real-Time Scheduling Problem

Oh, Yingfeng; Son, Sang
Oh, Yingfeng
Son, Sang
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
University of Virginia, Department of Computer Science, 1993
Published Date
Libra Open Repository
Logo for In CopyrightIn Copyright


Access Online