Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:




Library Locked Library locked




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


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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]
Created
01/23/2012 12:20:14 PM
Revision
1.
0.


Editor
Anja Becker
Vincenzo Bonifaci


Edit Date
25.01.2013 15:24:48
01/23/2012 12:20:14 PM


Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
sporadic-bms-algo.pdf