Global Scheduling Not Required: Simple, Near Optimal Multiprocessor Real Time Scheduling with Semi Partitioned Reservations
Prior work has identified several optimal algorithms for scheduling independent, implicit deadline sporadic (or periodic) real time tasks on identical multiprocessors. These algorithms, however, are subject to high conceptual complexity and typically incur considerable runtime overheads. This paper establishes that, empirically, near optimal schedulability can also be achieved with a far simpler approach that combines three well known techniques (reservations, semi partitioned scheduling, and period transformation) with some novel task placement heuristics.In large scale schedulability experiments, the proposed approach is shown to achieve near optimal hard real time schedulability (99+ schedulable utilization) across a wide range of processor and task counts. With an implementation in LITMUSRT, the proposed approach is shown to be practical and to incur only low runtime overheads, comparable to a conventional partitioned scheduler. It is further shown that basic slack management techniques can help to avoid more than 50% of all migrations of semi partitioned reservations if tasks execute on average for less than their provisioned worst case execution time.Two main conclusions are drawn: pragmatically speaking, global scheduling is not required to support static workloads of independent, implicit deadline sporadic (or periodic) tasks; and since such simple workloads are well supported, future research on multiprocessor real time scheduling should consider more challenging workloads (e.g. adaptive workloads, dynamic task arrivals or mode changes, shared resources, precedence constraints, etc.
2016 IEEE Real Time Systems Symposium (RTSS)