A Constant-Approximate Feasibility Test for Multiprocessor Real-Time Scheduling

Bonifaci, Vincenzo; Marchetti-Spaccamela, Alberto; Stiller, Sebastian

doi:10.1007/s00453-011-9497-2

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Journal Article

A Constant-Approximate Feasibility Test for Multiprocessor Real-Time Scheduling

MPS-Authors

/persons/resource/persons44160

Bonifaci, Vincenzo
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

Supplementary Material (public)

There is no public supplementary material available

Citation

Bonifaci, V., Marchetti-Spaccamela, A., & Stiller, S. (2012). A Constant-Approximate Feasibility Test for Multiprocessor Real-Time Scheduling. Algorithmica, 62(3-4), 1034-1049. doi:10.1007/s00453-011-9497-2.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0014-C4DE-2

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.