Handling mixed sets of tasks in combined offline and online scheduled real-time systems. (English) Zbl 1192.68101

Summary: Many industrial applications with real-time demands are composed of mixed sets of tasks with a variety of requirements. These can be in the form of standard timing constraints, such as period and deadline, or complex, e.g., to express application specific or nontemporal constraints, reliability, performance, etc. As many algorithms focus on specific sets of task types and constraints only, system design has to focus on those supported by a particular algorithm, at the expense of the rest. In this paper, we present a method to deal with a combination of mixed sets of tasks and constraints: periodic tasks with complex and simple constraints, soft and firm aperiodic, and sporadic tasks. We propose the use of an offline scheduler to manage complex timing and resource constraints of periodic tasks and transform these into a simple EDF model with start-times and deadlines. At run-time, the execution of the offline scheduled tasks is flexibly shifted in order to allow for feasible inclusion of dynamically arriving sporadic and aperiodic tasks. Sporadic tasks are guaranteed offline based on their worst-case activation frequencies. At run-time, this pessimism is reduced by the online algorithm which uses the exact knowledge about sporadic arrivals to reclaim resources and improve response times and acceptance of firm aperiodic tasks.


68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
Full Text: DOI


[1] Audsley N, Burns A, Richardson M, Wellings A (1992) Deadline monotonic scheduling theory. In: WRTP’92. Preprints of the IFAC workshop. Pergamon, UK
[2] Baruah S, Buttazzo G, Gorinsky S, Lipari G (1999) Scheduling periodic task systems to minimize output jitter. In: Sixth international conference on real-time computing systems and applications, Dec. 1999
[3] Baruah S, Rosier L, Howell R (1990) Algorithms and complexity concerning the preemptive scheduling of periodic, real-time tasks on one processor · Zbl 0734.68018
[4] Burns A, Audsley N, Richardson M, Wellings A (1992) Hard real-time scheduling: the deadline monotonic approach. In: Proc. of the IFAC/IFIP workshop, UK
[5] Buttazzo G, Lipari G, Abeni L (1998) A bandwidth reservation algorithm for multi-application systems. In: Proc. of the intl. conf. on real-time computing systems and applications, Japan
[6] Caccamo M, Buttazzo G, Sha L (2000) Capacity sharing for overrun control. In: IEEE proceedings of the 21st. IEEE real-time systems symposium, Orlando, Florida, USA, December 2000
[7] Davis R, Tindell K, Burns A (1993) Scheduling slack time in fixed priority pre-emptive systems. In: Proceedings of the real-time symposium, Dec. 1993, pp. 222–231
[8] Fohler G (1994) Flexibility in statically scheduled hard real-time systems. PhD thesis. Technische Universität Wien, Austria, Apr. 1994
[9] Fohler G (1995) Joint scheduling of distributed complex periodic and hard aperiodic tasks in statically scheduled systems. In: Proc. 16th real-time systems symposium, Pisa, Italy, 1995
[10] Fohler G, Isovic D, Lennvall T, Vuolle R (2002) Salsart – a web based cooperative environment for offline real-time schedule design. In: Proceedings of the 10th international Euromicro workshop on parallel, distributed and network-based processing (PDP 02), January 2002
[11] Garey M, Johnson D, Simons B, Tarjan R (1981) Scheduling unit-time tasks with arbitrary release times and deadlines. IEEE Trans Soft Eng, May 1981 · Zbl 0472.68021
[12] Lipari G, Baruah S (2000) Greedy reclaimation of unused bandwidth in constant bandwidth servers. In: IEEE proceedings of the 12th Euromicro conference on real-time systems, Stockholm, Sweden, June 2000
[13] Isovic D (2004) Flexible scheduling for media processing in resource constrained real-time systems. PhD thesis, Mälardalen University, Sweden, November 2004
[14] Jahanian F, Lee R, Mok A (1998) Semantics of modechart in real time logic. In: Proc. of the 21st Hawaii international conference on systems sciences, Jan. 1988, pp 479–489
[15] Jeffay K (1992) Scheduling sporadic tasks with shared resources in hard real-time systems. Dept. of Comp. Sci., Univ. of North Carolina at Chapel Hill
[16] Kopetz H (1992) Sparse time versus dense time in distributed real time systems. In: Proc. of the second int. workshop on responsive comp. sys., Saitama, Japan, Oct. 1992
[17] Mok AK (1983) Fundamental design problems of distributed systems for the hard real-time environment. PhD thesis, MIT, Report MIT/LCS/TR-297
[18] Ramamritham K (1990) Allocation and scheduling of complex periodic tasks. In: 10th Int. conf. on distributed computing systems
[19] Sprunt B, Sha L, Lehoczky J (1989) Aperiodic task scheduling for hard real-time systems. Real-Time Syst J 1(1):27–60
[20] Spuri M, Buttazzo GC, Sensini F (1995) Robust aperiodic scheduling under dynamic priority systems. In: Proceedings of the IEEE real-time systems symposium (RTSS), Dec. 1995
[21] Stankovic J, Ramamritham K, Cheng C-S (1995) Evaluation of a flexible task scheduling algorithm for distributed hard real-time systems. IEEE Trans Comput 34(12), Dec. 1995
[22] Thuel SR, Lehoczky J (1994) Algorithms for scheduling hard aperiodic tasks in fixed-priority systems using slack stealing. In: Proceedings of the real-time symposium, San Juan, Puerto Rico, Dec. 1994, pp 22–33
[23] Tia T, Liu W, Sun J, Ha R (1994) A linear-time optimal acceptance test for scheduling of hard real-time tasks. Dept. of Comp. Sc., Univ. of Illinois at Urbana-Champaign
[24] Törngren M (1997) Fundamentals of implementing real-time control applications in distributed computer systems. Real-Time Syst 14(3):219–250
[25] Wurtz J, Schild K (1997) Scheduling of time-triggered real-time systems. Technical report, German Research centre for Artificial Intelligence–DKFI GmbH
[26] Yodaiken V (1998) Rough notes on priority inheritance. Technical report. New Mexico Institut of Mining
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.