Optimal Multiprocessor Scheduling of Periodic Tasks in a Real-Time Environment

摘要

This investigation has addressed the problem of constructing a nonpreemptive schedule that requires the minimal number of processors for a given set of periodic tasks. Each periodic task is characterized by an integer period and an execution time. It is assumed that the period between each inititation and termination of a task must not vary once the first is specified. A compatibility relation is defined on the set of tasks such that any pair of tasks may be scheduled on the same processor only if they are compatible. An algorithm is defined which constructs a minimal processor schedule for a given set of tasks. The algorithm determines both upper and lower bounds on the number of processors required.