Abstract
A polynomial-time algorithm is presented for partitioning a collection of sporadic tasks, each constrained to have its relative-deadline parameter be no larger than its period parameter, among the processors of an identical multiprocessor platform. Since the partitioning problem is easily seen to be 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: It is shown that any set of sporadic tasks that can be partitioned among the processors of an m-processor identical multiprocessor platform will be partitioned by this algorithm on an m-processor platform in which each processor is (3-1/m) times as fast.
| Original language | English |
|---|---|
| Pages (from-to) | 918-923 |
| Number of pages | 6 |
| Journal | IEEE Transactions on Computers |
| Volume | 55 |
| Issue number | 7 |
| DOIs | |
| State | Published - Jul 2006 |
Keywords
- Multiprocessors
- Partitioned scheduling
- Resource augmentation
- Sporadic tasks
Fingerprint
Dive into the research topics of 'The partitioned multiprocessor scheduling of deadline-constrained sporadic task systems'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver