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

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. I. Introduction The problem of preemptiv..