direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 17-2008

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Title
A Constant-Approximate Feasibility Test for Multiprocessor Real-Time Scheduling
Authors
Vincenzo Bonifaci, Alberto Marchetti-Spaccamela, and Sebastian Stiller
Classification
not available
Keywords
Scheduling; Real-Time Scheduling; Approximation Algorithms; Resource Augmentation
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 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.
Source
Download as [PDF]
Title: Source

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe