We investigate the preemptive scheduling of periodic tasks with hard deadlines. We show that, even in the uniprocessor case, no polynomial 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 profit maximization variant of the feasibility problem, where every task has a non-negative profit, and the goal is to find a subset of tasks that can be scheduled feasibly with maximum profit. We give the first constant-speed, constant-approximation algorithm for the case of synchronous task systems, together with related hardness results. Copyright © by SIAM.

Bonifaci, V., Chan, H.-., Marchetti-Spaccamela, A., & Megow, N. (2010). Algorithms and complexity for periodic real-time scheduling. In Proc. of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (pp.1350-1359). Association for Computing Machinery (ACM) [10.1137/1.9781611973075.109].

Algorithms and complexity for periodic real-time scheduling

Bonifaci V.;
2010

Abstract

We investigate the preemptive scheduling of periodic tasks with hard deadlines. We show that, even in the uniprocessor case, no polynomial 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 profit maximization variant of the feasibility problem, where every task has a non-negative profit, and the goal is to find a subset of tasks that can be scheduled feasibly with maximum profit. We give the first constant-speed, constant-approximation algorithm for the case of synchronous task systems, together with related hardness results. Copyright © by SIAM.
978-0-89871-701-3
Bonifaci, V., Chan, H.-., Marchetti-Spaccamela, A., & Megow, N. (2010). Algorithms and complexity for periodic real-time scheduling. In Proc. of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (pp.1350-1359). Association for Computing Machinery (ACM) [10.1137/1.9781611973075.109].
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: http://hdl.handle.net/11590/381239
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 5
social impact