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 epsilon > 0, correctly decides either that the task system can be scheduled using the Earliest Deadline First algorithm on m speed-(2-1/m+epsilon) 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/epsilon. We also provide a generalized tight bound that trades off speed with additional machines.
A Constant-Approximate Feasibility Test for Multiprocessor Real-Time Scheduling / Bonifaci, Vincenzo; MARCHETTI SPACCAMELA, Alberto; Stiller, Sebastian. - In: ALGORITHMICA. - ISSN 0178-4617. - STAMPA. - 62:3-4(2012), pp. 1034-1049. [10.1007/s00453-011-9497-2]
A Constant-Approximate Feasibility Test for Multiprocessor Real-Time Scheduling
BONIFACI, VINCENZO;MARCHETTI SPACCAMELA, Alberto;
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 epsilon > 0, correctly decides either that the task system can be scheduled using the Earliest Deadline First algorithm on m speed-(2-1/m+epsilon) 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/epsilon. We also provide a generalized tight bound that trades off speed with additional machines.File | Dimensione | Formato | |
---|---|---|---|
VE_2012_11573-356919.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
616.3 kB
Formato
Adobe PDF
|
616.3 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.