Scheduling Periodic Tasks In a Hard Real-Time Environment

Abstract

Consider the traditional problem of scheduling a set of periodic tasks on a multiprocessor system, where task deadlines must be guaranteed. We first derive a general schedulability condition for Rate-Monotonic, which reduces the uniprocessor schedulability condition obtained by Liu and Layland and by Serlin, and the multiprocessor schedulability condition recently derived by Burchard, Liebeherr, Oh, and Son to its two specific cases. Then a tight upper bound is obtained for the number of processors required in an optimal schedule for any given set of tasks with a fixed number of tasks and a fixed utilization. Finally, similar conditions are derived for the Earliest Deadline First scheduling. These conditions shed new light on the periodic task scheduling problem.