Fixed-Priority Scheduling of Periodic Tasks on Multiprocessor Systems

Abstract

Consider the problem of periodic task scheduling, in which we seek to minimize the total number of processors required to execute a set of tasks such that task deadlines are guaranteed by the Rate-Monotonic (or RM) algorithm on each processor. This problem was first investigated by Dhall and Liu, and the previous lowest bound for the problem was 2.0. In this paper, an improved solution is given by designing a new algorithm for it. The algorithm, called RM-First-Fit-Decreasing-Utilization (or RM-FFDU), is shown to have a worst-case tight bound of 5/3 = 1.66..., the lowest upper bound ever derived for the scheduling problem. Simulation studies show that on the average, the new algorithm performs consistently better than those in the literature.