[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

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

  • Published:
Real-Time Systems Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Abdelzaher T, Sharma V, Lu C (2004) A utilization bound for aperiodic tasks and priority driven scheduling. IEEE Trans Comput 53(3):334–350

    Article  Google Scholar 

  • Audsley AN, Burns A, Richardson M, Tindell K (1993) Applying new scheduling theory to static priority pre-emptive scheduling. Softw Eng J 8(5):284–292

    Article  Google Scholar 

  • Bettati R, Liu JWS (1990) Algorithms for end-to-end scheduling to meet deadlines. In: Proceedings of the IEEE symposium on parallel and distributed processing, pp 62–67, December 1990

  • Bini E, Buttazzo G, Buttazzo G (2001) A hyperbolic bound for the rate monotonic algorithm. In: Proceedings of the 13th euromicro conference on real-time systems (ECRTS), pp 59–66, June 2001

  • Chatterjee S, Strosnider J (1995) Distributed pipeline scheduling: end-to-end analysis of heterogeneous multi-resource real-time systems. In: Proceedings of the IEEE international conference on distributed computing systems (ICDCS), pp 204–211, May 1995

  • Chetto H, Silly M, Bouchentouf T (1990) Dynamic scheduling of real-time tasks under precedence constraints. Real-Time Syst 2(3):181–194

    Article  Google Scholar 

  • Cruz RL (1991) A calculus for network delay, part II: network analysis. IEEE Trans Inf Theory 37(1):132–141

    Article  MATH  MathSciNet  Google Scholar 

  • Fohler G, Ramamritham K (1997) Static scheduling of pipelined periodic tasks in distributed real-time systems. In: Proceedings of the 9th euromicro workshop on real-time systems (ECRTS), pp 128–135, June 1997

  • Harbour MG, Klein MH, Lehoczky JP (1991) Fixed priority scheduling periodic tasks with varying execution priority. In: Proceedings of the IEEE real-time systems symposium (RTSS), pp 116–128, December 1991

  • Hawkins W, Abdelzaher T (2005) Towards feasible region calculus: an end-to-end schedulability analysis of real-time multistage execution. In: Proceedings of the IEEE real-time systems symposium (RTSS), pp 75–86, December 2005

  • Koubaa A, Song Y-Q (2004) Evaluation and improvement of response time bounds for real-time applications under non-preemptive fixed priority scheduling. Int J Prod Res 42(14):2899–2913

    Article  MATH  Google Scholar 

  • Lehoczky J, Sha L, Ding Y (1989) The rate monotonic scheduling algorithm: exact characterization and average case behavior. In: Proceedings of the IEEE real-time systems symposium (RTSS), pp 166–171, December 1989

  • Liu CL, Layland JW (1973) Scheduling algorithms for multiprogramming in a hard real-time environment. J ACM 20(1):46–61

    Article  MATH  MathSciNet  Google Scholar 

  • Palencia JC, Harbour MG (2003) Offset-based response time analysis of distributed systems scheduled under EDF. In: Proceedings of the euromicro conference on real-time systems (ECRTS), pp 3–12, July 2003

  • Pellizzoni R, Lipari G (2005) Improved schedulability analysis of real-time transactions with earliest deadline scheduling. In: Proceedings of the IEEE real-time and embedded technology and applications symposium (RTAS), pp 66–75, March 2005

  • Ramamritham K (1990) Allocation and scheduling of complex periodic tasks. In: Proceedings of the IEEE international conference on distributed computing systems (ICDCS), pp 108–115, 1990

  • Schneider J (2000) Cache and pipeline sensitive fixed priority scheduling for preemptive real-time systems. In: Proceedings of the IEEE real-time systems symposium (RTSS), pp 195–204, November 2000

  • Spuri M (1996) Holistic analysis of deadline scheduled real-time distributed systems. Technical report RR-2873, INRIA, France

  • Tindell K, Clark J (1994) Holistic schedulability analysis for distributed hard real-time systems. Elsevier Microprocess Microprogram 40(2–3):117–134

    Article  Google Scholar 

  • Xu J (1993) Multiprocessor scheduling of processes with release times, deadlines, precedence, and exclusion relations. IEEE Trans Softw Eng 19(2):139–154

    Article  Google Scholar 

  • Xu J, Parnas DL (1993) On satisfying timing constraints in hard real-time systems. IEEE Trans Softw Eng 19(1):70–84

    Article  Google Scholar 

  • Zhang N, Burns A, Nicholson M (1993) Pipelined processors and worst case execution times. Real-Time Syst 5(4):319–343

    Article  Google Scholar 

  • Zhang Y, Lu C, Gill C, Lardieri P, Thaker G (2005) End-to-end scheduling strategies for aperiodic tasks in middleware. Technical report WUCSE-2005-57, University of Washington at St. Louis, December 2005

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Illinois, Urbana-Champaign, IL, 61801, USA

    Praveen Jayachandran & Tarek Abdelzaher

Authors
  1. Praveen Jayachandran
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Tarek Abdelzaher
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Praveen Jayachandran.

Additional information

The work reported in this paper was supported in part by the National Science Foundation under grants CNS 07-20513, CNS 05-53420, and CNS 06-13665.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Jayachandran, P., Abdelzaher, T. Delay composition in preemptive and non-preemptive real-time pipelines. Real-Time Syst 40, 290–320 (2008). https://doi.org/10.1007/s11241-008-9056-3

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11241-008-9056-3

Keywords