The partitioned dynamic-priority scheduling of sporadic task systems

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...

Full description

Saved in:
Bibliographic Details
Published in:Real-time systems 2007-08, Vol.36 (3), p.199-226
Main Authors: Baruah, Sanjoy K, Fisher, Nathan Wayne
Format: Article
Language:English
Subjects:
Algorithms
Multiprocessing
Partitioning
Polynomials
Priority scheduling
Task scheduling
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0922-6443
1573-1383
DOI:10.1007/s11241-007-9022-5