We study the preemptive scheduling of real-time sporadic tasks on a uniprocessor. We consider both fixed priority (FP) scheduling as well as dynamic priority scheduling by the Earliest Deadline First (EDF) algorithm. We investigate the problems of testing schedulability and computing the response time of tasks. Generally these problems are known to be computationally intractable for task systems with constrained deadlines. In this paper, we focus on the particular case of task systems with harmonic period lengths, meaning that the periods of the tasks pair wise divide each other. This is a special case of practical relevance. We present provably efficient exact algorithms for constrained-deadline task systems with harmonic periods. In particular, we provide an exact polynomial-time algorithm for computing the response time of a task in a system with an arbitrary fixed priority order. This also implies an exact FP-schedulability test. For dynamic priority scheduling, we show how to test EDF-schedulability in polynomial time. Additionally, we give a very simple EDF-schedulability test for the simpler case where relative deadlines and periods are jointly harmonic. © 2013 IEEE.

Bonifaci, V., Marchetti-Spaccamela, A., Megow, N., Wiese, A. (2013). Polynomial-time exact schedulability tests for harmonic real-time tasks. In Proc. 34th IEEE Real-Time Systems Symposium (pp.236-245). New York, NY : IEEE [10.1109/RTSS.2013.31].

Polynomial-time exact schedulability tests for harmonic real-time tasks

Bonifaci V.;
2013-01-01

Abstract

We study the preemptive scheduling of real-time sporadic tasks on a uniprocessor. We consider both fixed priority (FP) scheduling as well as dynamic priority scheduling by the Earliest Deadline First (EDF) algorithm. We investigate the problems of testing schedulability and computing the response time of tasks. Generally these problems are known to be computationally intractable for task systems with constrained deadlines. In this paper, we focus on the particular case of task systems with harmonic period lengths, meaning that the periods of the tasks pair wise divide each other. This is a special case of practical relevance. We present provably efficient exact algorithms for constrained-deadline task systems with harmonic periods. In particular, we provide an exact polynomial-time algorithm for computing the response time of a task in a system with an arbitrary fixed priority order. This also implies an exact FP-schedulability test. For dynamic priority scheduling, we show how to test EDF-schedulability in polynomial time. Additionally, we give a very simple EDF-schedulability test for the simpler case where relative deadlines and periods are jointly harmonic. © 2013 IEEE.
2013
978-1-4799-2006-8
Bonifaci, V., Marchetti-Spaccamela, A., Megow, N., Wiese, A. (2013). Polynomial-time exact schedulability tests for harmonic real-time tasks. In Proc. 34th IEEE Real-Time Systems Symposium (pp.236-245). New York, NY : IEEE [10.1109/RTSS.2013.31].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11590/381600
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 28
  • ???jsp.display-item.citation.isi??? 16
social impact