We investigate the preemptive scheduling of periodic tasks with hard deadlines. We show that, even in the uniprocessor case, no pseudopolynomial-time algorithm can test the feasibility of a task system within a constant speedup bound, unless P = NP. This result contrasts with recent results for sporadic task systems. For two special cases, synchronous task systems and systems with a constant number of different task types, we provide the first polynomial-time constant-speedup feasibility tests for multiprocessor platforms. Furthermore, we show that the problem of testing feasibility is coNP-hard for synchronous multiprocessor task systems. The complexity of some of these problems has been open for a long time. We also propose a weight maximization variant of the feasibility problem, where every task has a nonnegative weight, and the goal is to find a subset of tasks that can be scheduled feasibly and has maximum weight. We give the first constant-speed, constant-approximation algorithm for the case of synchronous task systems, together with related hardness results. © 2012 ACM.

Bonifaci, V., Chan, H.-., Marchetti-Spaccamela, A., & Megow, N. (2012). Algorithms and complexity for periodic real-time scheduling. ACM TRANSACTIONS ON ALGORITHMS, 9(1), 1-19 [10.1145/2390176.2390182].

Algorithms and complexity for periodic real-time scheduling

Bonifaci V.;
2012

Abstract

We investigate the preemptive scheduling of periodic tasks with hard deadlines. We show that, even in the uniprocessor case, no pseudopolynomial-time algorithm can test the feasibility of a task system within a constant speedup bound, unless P = NP. This result contrasts with recent results for sporadic task systems. For two special cases, synchronous task systems and systems with a constant number of different task types, we provide the first polynomial-time constant-speedup feasibility tests for multiprocessor platforms. Furthermore, we show that the problem of testing feasibility is coNP-hard for synchronous multiprocessor task systems. The complexity of some of these problems has been open for a long time. We also propose a weight maximization variant of the feasibility problem, where every task has a nonnegative weight, and the goal is to find a subset of tasks that can be scheduled feasibly and has maximum weight. We give the first constant-speed, constant-approximation algorithm for the case of synchronous task systems, together with related hardness results. © 2012 ACM.
Bonifaci, V., Chan, H.-., Marchetti-Spaccamela, A., & Megow, N. (2012). Algorithms and complexity for periodic real-time scheduling. ACM TRANSACTIONS ON ALGORITHMS, 9(1), 1-19 [10.1145/2390176.2390182].
File in questo prodotto:
File Dimensione Formato  
periodic-talg.pdf

accesso aperto

Tipologia: Documento in Post-print
Licenza: DRM non definito
Dimensione 266.92 kB
Formato Adobe PDF
266.92 kB Adobe PDF Visualizza/Apri

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: http://hdl.handle.net/11590/381331
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 2
social impact