Buffered Scheduling: Hiding Decision Latency with Asynchronous Scheduling

Abstract

Most work on real-time schedulers assume a synchronous scheduler, in which the scheduling decision is determined and applied at once. This ensures that the highest-priority task(s) are always scheduled when ready. This paper investigates buffered scheduling, a form of asynchronous scheduling in which the determination of scheduling decisions is separate from the application of those decisions. In particular, jobs to be scheduled are buffered such that they can be quickly started after the completion of prior work. Buffered scheduling is motivated by applications with high scheduling overheads. For example, global scheduling with high core counts can have high scheduling costs due to contention for shared variables such as the run queue. As another example, many modern real-time systems employ accelerators such as GPUs where they may be high overheads associated with transferring relevant scheduling decisions and/or job data to the off-chip accelerator. In these cases, it may be advantageous to keep a processor or accelerator busy running lower-priority work than to wait for the determination (or communication) of the highest-priority job to run. Prior work has shown that global EDF (with and without preemptions) is soft real-time optimal in that it guarantees bounded deadline tardiness when assuming zero overheads. The main result of this paper is to demonstrate that when global EDF scheduling decisions are buffered, soft real-time optimality is preserved, albeit at the cost of higher tardiness bounds. Experimental results are then presented to demonstrate that when scheduling overheads are considered that buffered scheduling can significantly reduce overhead-related utilization loss.