Tardiness Bounds for FIFO Scheduling on Multiprocessors

FIFO scheduling is often considered to be inappropriate for scheduling workloads that are subject to timing constraints. However, FIFO is implemented in many general-purpose OSs, and is more widely supported than other priority-based scheduling methods. In this paper, we show that, when the global FIFO scheduling algorithm is used to schedule sporadic real-time tasks on a multiprocessor, deadline tardiness is bounded. This result shows that global FIFO may in fact be useful for scheduling soft real-time workloads.