Delay composition in preemptive and non-preemptive real-time pipelines |
| |
Authors: | Praveen Jayachandran Tarek Abdelzaher |
| |
Affiliation: | (1) Department of Computer Science, University of Illinois, Urbana-Champaign, IL 61801, USA |
| |
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 multistage
pipeline as a function of job execution times on different stages under preemptive 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 component. This contribution effectively transforms the pipeline into a
single stage system. 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 we account for execution overlap among stages. We discuss
how previous approaches account for overlap and point out interesting differences that lead to different performance advantages
in different cases. Further, we also show that in certain cases non-preemptive scheduling can result in higher system utilization
than preemptive scheduling in pipelined systems. We hope that the pipeline delay composition rule, derived in this paper,
may be a step towards a general schedulability analysis foundation for large distributed systems.
|
| |
Keywords: | Schedulability End-to-end delay Pipelined distributed systems Delay composition |
本文献已被 SpringerLink 等数据库收录! |
|