A new algorithm for scheduling periodic, real-time tasks

A new algorithm for scheduling periodic, real-time tasks

0.00 Avg rating0 Votes
Article ID: iaor19881016
Country: United States
Volume: 4
Start Page Number: 200
End Page Number: 219
Publication Date: Jun 1989
Journal: Algorithmica
Authors:
Keywords: combinatorial analysis
Abstract:

The paper considers the problem of preemptively scheduling a set of periodic, real-time tasks on a multiprocessor computer system. It gives a new scheduling algorithm, the so-called Slack-Time Algorithm, and shows that it is more effective than the known Deadline Algorithm. The paper also gives an (exponential-time) algorithm to decide if a task system is schedulable by the Slack-Time or the Deadline Algorithm. The same algorithm can also be used to decide if a task system is schedulable by any given fixed-priority scheduling algorithm. This resolves an open question posed by Leung and Whitehead. Finally, it is shown that the problem of deciding if a task system is schedulable by the Slack-Time, the Deadline, or any given fixed-priority scheduling algorithm is co-NP-hard for each fixed m≥1.

Reviews

Required fields are marked *. Your email address will not be published.