IEEE Transactions on Software Engineering · 1989 · 430 citations · 6 references
ComputingComputer EngineeringComputer ScienceParallel ComputingReal-time SystemsSchedulingOnline SchedulingReal-time SchedulingReal-time Systems DesignResource-constrained SchedulingSchedulability AnalysisTask SchedulingMultiprocessor Real-time SchedulingMultiprocessor SchedulabilityMultiprocessor SchedulingMutual ExclusionOnline Real-time SchedulingReal-time Task SchedulingScheduling AlgorithmsScheduling Under Precedence Constraints
The problems of hard-real-time task scheduling in a multiprocessor environment are discussed in terms of a scheduling game representation of the problem. It is shown that optimal scheduling without a priori knowledge is impossible in the multiprocessor case even if there is no restriction on preemption owing to precedence or mutual exclusion constraints. Sufficient conditions that permit a set of tasks to be optimally scheduled at run time are derived.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
6
Two-Processor Scheduling with Start-Times and Deadlines
M. R. Garey, David S. Johnson · SIAM Journal on Computing · 1977 · 237 citations