MPI-INF D1 Publications: Journal Article: A Constant-Approximate Feasibility Test for Multiprocessor Real-Time Scheduling

Journal Article
@Article
Artikel in Fachzeitschrift

Show entries of:

this year (2023) | last year (2022) | two years ago (2021) | Notes URL

Action:

Options:

Library locked

Goto entry point

Author, Editor(s)

Author(s):

Bonifaci, Vincenzo
Marchetti-Spaccamela, Alberto
Stiller, Sebastian

dblp
dblp
dblp

Not MPG Author(s):

Marchetti-Spaccamela, Alberto
Stiller, Sebastian

BibTeX cite key*:

Bonifaci2012b

Title

Title*:	A Constant-Approximate Feasibility Test for Multiprocessor Real-Time Scheduling
Attachment(s):	sporadic-bms-algo.pdf (354.28 KB)

Journal

Journal Title*:	Algorithmica	Journal's URL:	http://www.springer.com/computer/theoretical+computer+science/journal/453
Download URL for the article:		Language:	English

Publisher

Publisher's Name:	Springer	Publisher's URL:	http://www.springer.com
Publisher's Address:	New York, NY	ISSN:	0178-4617

Vol, No, pp, Date

Volume*:	62	Number:	3-4
Publishing Date:	April 2012
Pages*:	1034-1049	Number of VG Pages:
Page Start:	1034	Page End:	1049
Sequence Number:		DOI:	10.1007/s00453-011-9497-2

Note, Abstract, ©

Note:
(LaTeX) 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.
URL for the Abstract:
Categories, Keywords:	Sporadic task system, Multiprocessor, Real-time scheduling, Feasibility test, Earliest Deadline First, Approximation algorithm
HyperLinks / References / URLs:
Copyright Message:
Personal Comments:
Download Access Level:	Public

Correlation

MPG Unit:	Max-Planck-Institut für Informatik

MPG Subunit:	Algorithms and Complexity Group
Appearance:	MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@ARTICLE{Bonifaci2012b,
AUTHOR = {Bonifaci, Vincenzo and Marchetti-Spaccamela, Alberto and Stiller, Sebastian},
TITLE = {A Constant-Approximate Feasibility Test for Multiprocessor Real-Time Scheduling},
JOURNAL = {Algorithmica},
PUBLISHER = {Springer},
YEAR = {2012},
NUMBER = {3-4},
VOLUME = {62},
PAGES = {1034--1049},
ADDRESS = {New York, NY},
MONTH = {April},
ISBN = {0178-4617},
DOI = {10.1007/s00453-011-9497-2},
}

Entry last modified by Anja Becker, 01/25/2013

Edit History (please click the blue arrow to see the details)

	Editor(s) [Library]	Created 01/23/2012 12:20:14
Revision 1. 0.	Editor Anja Becker Vincenzo Bonifaci	Edit Date 25.01.2013 15:24:48 01/23/2012 12:20:14 PM

Attachment Section

sporadic-bms-algo.pdf

sporadic-bms-algo.pdf