Delay composition in preemptive and non-preemptive real-time pipelines

Abstract Uniprocessor schedulability theory made great strides, in part, due to the simplicity of composing the delay of a job from the execution times of higher-priority jobs that preempt it. In this paper, we bound the end-to-end delay of a job in a mul-tistage pipeline as a function of job execution times on different stages under pre-emptive as well as non-preemptive scheduling. We show that the end-to-end delay is bounded by that of a single virtual “bottleneck ” stage plus a small additive com-ponent. This contribution effectively transforms the pipeline into a single stage sys-tem. The wealth of schedulability analysis techniques derived for uniprocessors can then be applied to decide the schedulability of the pipeline. The transformation does not require imposing artificial per-stage deadlines, but rather models the pipeline as a whole and uses the end-to-end deadlines directly in the single-stage analysis. It also does not make assumptions on job arrival patterns or periodicity and thus can be applied to periodic and aperiodic tasks alike. We show through simulations that this approach outperforms previous pipeline schedulability tests except for very short pipelines or when deadlines are sufficiently large. The reason lies in the way w