Preemptive Scheduling of Periodic Tasks on Multiprocessor: Dynamic Algorithms and Their Performance

Report
Authors:Oh, Yingfeng, Department of Computer ScienceUniversity of Virginia Son, Sang, Department of Computer ScienceUniversity of Virginia
Abstract:

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

Rights:
All rights reserved (no additional license for public reuse)
Language:
English
Source Citation:

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).

Publisher:
University of Virginia, Department of Computer Science
Published Date:
1993