Preemptive Scheduling of Periodic Tasks on Multiprocessor: Dynamic Algorithms and Their PerformanceReport
In this paper, the problem of preemptively scheduling a set of periodic tasks on a multiprocessor is considered. Three dynamic algorithms are proposed, and their performance is studied. These algorithms are Rate-Monotonic-NextFit-WC (RMNF-WC), Rate-Monotonic-First-Fit-WC (RMFF-WC), and RateMonotonic-Best-Fit-WC (RMBF-WC), and their worst-case performance is shown to be tightly bounded by 2.88, 2.33, and 2.33, respectively. The major contributions of this papers are (1) These algorithms are the few truly dynamic algorithms for scheduling periodic tasks on a multiprocessor system, and they are the few algorithms, the worst-case performance of which is investigated. (2) The worst-case performance bound is shown to be tight. (3) The worst-case performance bound of RMFF-WC is as good as that of its static counterpart ⎯ RMFF studied by Dhall and Liu. (4) A new scheduling heuristic ⎯ RMBF-WC is proposed and its worst-case performance investigated.
Note: Abstract extracted from PDF text
All rights reserved (no additional license for public reuse)
Oh, Yingfeng, and Sang Son. "Preemptive Scheduling of Periodic Tasks on Multiprocessor: Dynamic Algorithms and Their Performance." University of Virginia Dept. of Computer Science Tech Report (1993).
University of Virginia, Department of Computer Science