We devise the first constant-approximate feasibility test for sporadic multiprocessor real-time scheduling. We give an algorithm that, given a task system and ε > 0, correctly decides either that the task system can be scheduled using the earliest deadline first algorithm on m speed-(2 - 1/m + ε) machines, or that the system is infeasible for m speed-1 machines. The running time of the algorithm is polynomial in the size of the task system and 1/ε. We also provide an improved bound trading off speed for additional machines. Our analysis relies on a new concept for counting the workload of an interval, that might also turn useful for analyzing other types of task systems. © 2008 Springer-Verlag Berlin Heidelberg.

Bonifaci, V., Marchetti-Spaccamela, A., Stiller, S. (2008). A constant-approximate feasibility test for multiprocessor real-time scheduling. In Proc. 16th European Symposium on Algorithms (pp.210-221). Berlin : Springer [10.1007/978-3-540-87744-8_18].

A constant-approximate feasibility test for multiprocessor real-time scheduling

Bonifaci V.;
2008-01-01

Abstract

We devise the first constant-approximate feasibility test for sporadic multiprocessor real-time scheduling. We give an algorithm that, given a task system and ε > 0, correctly decides either that the task system can be scheduled using the earliest deadline first algorithm on m speed-(2 - 1/m + ε) machines, or that the system is infeasible for m speed-1 machines. The running time of the algorithm is polynomial in the size of the task system and 1/ε. We also provide an improved bound trading off speed for additional machines. Our analysis relies on a new concept for counting the workload of an interval, that might also turn useful for analyzing other types of task systems. © 2008 Springer-Verlag Berlin Heidelberg.
978-3-540-87743-1
Bonifaci, V., Marchetti-Spaccamela, A., Stiller, S. (2008). A constant-approximate feasibility test for multiprocessor real-time scheduling. In Proc. 16th European Symposium on Algorithms (pp.210-221). Berlin : Springer [10.1007/978-3-540-87744-8_18].
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/380500
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 14
  • ???jsp.display-item.citation.isi??? 13
social impact