We devise an approximate feasibility test for multiprocessor real-time scheduling in the sporadic task model.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 not schedulable by any algorithm on m unit speed machines. This speedup bound is known to be the best possible for EDF. The running time of the algorithm is polynomial in the size of the task system and 1/ϵ. We also provide a generalized tight bound that trades off speed with additional machines.

Bonifaci, V., Marchetti-Spaccamela, A., & Stiller, S. (2012). A constant-approximate feasibility test for multiprocessor real-time scheduling. ALGORITHMICA, 62(3-4), 1034-1049 [10.1007/s00453-011-9497-2].

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

Bonifaci V.
;
2012

Abstract

We devise an approximate feasibility test for multiprocessor real-time scheduling in the sporadic task model.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 not schedulable by any algorithm on m unit speed machines. This speedup bound is known to be the best possible for EDF. The running time of the algorithm is polynomial in the size of the task system and 1/ϵ. We also provide a generalized tight bound that trades off speed with additional machines.
Bonifaci, V., Marchetti-Spaccamela, A., & Stiller, S. (2012). A constant-approximate feasibility test for multiprocessor real-time scheduling. ALGORITHMICA, 62(3-4), 1034-1049 [10.1007/s00453-011-9497-2].
File in questo prodotto:
File Dimensione Formato  
bomast-journal.pdf

accesso aperto

Tipologia: Documento in Pre-print
Licenza: DRM non definito
Dimensione 364.88 kB
Formato Adobe PDF
364.88 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/381274
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 11
  • ???jsp.display-item.citation.isi??? 9
social impact