On a Real-Time Scheduling Problem

This work studies the problem of scheduling periodic-time-critical tasks on multiprocessor computing systems and considers two heuristic algorithms that are easy to implement and yield a number of processors that is reasonably close to the minimum number.

Abstract

We study the problem of scheduling periodic-time-critical tasks on multiprocessor computing systems. A periodic-time-critical task consists of an infinite number of requests, each of which has a prescribed deadline. The scheduling problem is to specify an order in which the requests of a set of tasks are to be executed and the processor to be used, with the goal of meeting all the deadlines with a minimum number of processors. Since the problem of determining the minimum number of processors is difficult, we consider two heuristic algorithms. These are easy to implement and yield a number of processors that is reasonably close to the minimum number. We also analyze the worst-case behavior of these heuristics.