## Abstract

We consider the problem of preemptively scheduling a set of periodic, real-time tasks on a multiprocessor computer system. We give a new scheduling algorithm, the so-called Slack-Time Algorithm, and show that it is more effective than the known Deadline Algorithm. We also give 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≥.

Original language | English (US) |
---|---|

Pages (from-to) | 209-219 |

Number of pages | 11 |

Journal | Algorithmica |

Volume | 4 |

Issue number | 1 |

DOIs | |

State | Published - Dec 1989 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- General Computer Science
- Computer Science Applications
- Applied Mathematics

## Keywords

- Multiprocessor system
- Periodic
- Real-time tasks
- Schedulability
- co-NP-hard