Multiprocessor scheduling of periodic tasks in a hard real-time environment

Abstract

The problem of preemptive scheduling a set of periodic tasks on multiprocessors is studied from the point of view of meeting their service requirements before their respective deadlines. Sufficient conditions which permit full utilization of the multiprocessor using the given scheduling algorithms are derived. The complexity of the scheduling algorithms in terms of the number of scheduled tasks and the number of processors and upper bounds on the number of preemptions in a given time interval and for any single task are also derived. We also give a schema for modifying existing schedules at little run-time cost when tasks arrive or leave the system on-line.