direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Preprints 2008

A Constant-Approximate Feasibility Test for Multiprocessor Real-Time Scheduling
Zitatschlüssel Report-017-2008
Autor Vincenzo Bonifaci and Alberto Marchetti-Spaccamela and Sebastian Stiller
Jahr 2008
Nummer 017
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung We devise the first constant-approximate feasibility test for sporadic multiprocessor real-time scheduling. We give an algorithm that, given a task system and e > 0, correctly decides either that the task system can be scheduled using the earliest deadline first algorithm on m speed-(2-1/m+e) 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/e. 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.
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag