Preemptive Scheduling of Real-Time Tasks on Multiprocessor Systems

Abstract

The use of multiprocessor systems consisting of identical and autonomous processors is a promising approach to the practical solution of problems arising in real-time applications and large compute-bound problems in general. However, finding techniques for obtaining efficient solutions to the related multiprocessor scheduling problems is a little-understood problem. The authors study the problem of scheduling a set of tasks whose operational precedence structure is representable as an acyclic directed graph. In scheduling tasks it is assumed that preemptions are allowed. The major results consist of the statement and proof of an efficient algorithm for finding the minimal-length preemptive schedule for tree-structured computations.