Item Details

Fixed-Priority Scheduling of Periodic Tasks on Multiprocessor Systems

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

Availability

Access Online