The partitioned dynamic-priority scheduling of sporadic task systems

Sanjoy K. Baruah; Nathan Wayne Fisher

doi:10.1007/s11241-007-9022-5

The partitioned dynamic-priority scheduling of sporadic task systems

Sanjoy K. Baruah
, Nathan Wayne Fisher

Department of Computer Science & Engineering

Research output: Contribution to journal › Article › peer-review

37 Scopus citations

Abstract

A polynomial-time algorithm is presented for partitioning a collection of sporadic tasks among the processors of an identical multiprocessor platform. Since the partitioning problem is NP-hard in the strong sense, this algorithm is unlikely to be optimal.A quantitative characterization of its worst-case performance is provided in terms of resource augmentation.

Original language	English
Pages (from-to)	199-226
Number of pages	28
Journal	Real-Time Systems
Volume	36
Issue number	3
DOIs	https://doi.org/10.1007/s11241-007-9022-5
State	Published - May 2007

Keywords

Multiprocessors
Partitioned scheduling
Sporadic tasks

Access to Document

10.1007/s11241-007-9022-5

Cite this

@article{d9e41bb034b64c28a2c28bd4f8b67dd8,

title = "The partitioned dynamic-priority scheduling of sporadic task systems",

abstract = "A polynomial-time algorithm is presented for partitioning a collection of sporadic tasks among the processors of an identical multiprocessor platform. Since the partitioning problem is NP-hard in the strong sense, this algorithm is unlikely to be optimal.A quantitative characterization of its worst-case performance is provided in terms of resource augmentation.",

keywords = "Multiprocessors, Partitioned scheduling, Sporadic tasks",

author = "Baruah, \{Sanjoy K.\} and Fisher, \{Nathan Wayne\}",

year = "2007",

month = may,

doi = "10.1007/s11241-007-9022-5",

language = "English",

volume = "36",

pages = "199--226",

journal = "Real-Time Systems",

issn = "0922-6443",

number = "3",

}

TY - JOUR

T1 - The partitioned dynamic-priority scheduling of sporadic task systems

AU - Baruah, Sanjoy K.

AU - Fisher, Nathan Wayne

PY - 2007/5

Y1 - 2007/5

N2 - A polynomial-time algorithm is presented for partitioning a collection of sporadic tasks among the processors of an identical multiprocessor platform. Since the partitioning problem is NP-hard in the strong sense, this algorithm is unlikely to be optimal.A quantitative characterization of its worst-case performance is provided in terms of resource augmentation.

AB - A polynomial-time algorithm is presented for partitioning a collection of sporadic tasks among the processors of an identical multiprocessor platform. Since the partitioning problem is NP-hard in the strong sense, this algorithm is unlikely to be optimal.A quantitative characterization of its worst-case performance is provided in terms of resource augmentation.

KW - Multiprocessors

KW - Partitioned scheduling

KW - Sporadic tasks

UR - https://www.scopus.com/pages/publications/34249914236

U2 - 10.1007/s11241-007-9022-5

DO - 10.1007/s11241-007-9022-5

M3 - Article

AN - SCOPUS:34249914236

SN - 0922-6443

VL - 36

SP - 199

EP - 226

JO - Real-Time Systems

JF - Real-Time Systems

IS - 3

ER -

The partitioned dynamic-priority scheduling of sporadic task systems

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this