Item Details

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

Oh, Yingfeng; Son, Sang
Format
Report
Author
Oh, Yingfeng
Son, Sang
Abstract
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
Language
English
Date Received
20121029
Published
University of Virginia, Department of Computer Science, 1993
Published Date
1993
Collection
Libra Open Repository
Logo for In CopyrightIn Copyright

Availability

Access Online