• German
German

Main Navigation

Chen/2016b: Partitioned Multiprocessor Fixed-Priority Scheduling of Sporadic Real-Time Tasks

Bibtype Inproceedings
Bibkey Chen/2016b
Author Chen, Jian-Jia
Title Partitioned Multiprocessor Fixed-Priority Scheduling of Sporadic Real-Time Tasks
Booktitle Euromicro Conference on Real-Time Systems (ECRTS)
Address Toulouse, France
Abstract Partitioned multiprocessor scheduling has been widely accepted in academia and industry to statically assign and partition real-time tasks onto identical multiprocessor systems. This paper studies fixed-priority partitioned multiprocessor scheduling for sporadic real-time systems, in which deadline-monotonic scheduling is applied on each processor. Prior to this paper, the best known results are by Fisher, Baruah, and Baker with speedup factors $4-\frac{2}{M}$ and $3-\frac{1}{M}$ for arbitrary-deadline and constrained-deadline sporadic real-time task systems, respectively, where $M$ is the number of processors. We show that a greedy mapping strategy has a speedup factor $3-\frac{1}{M}$ when considering task systems with arbitrary deadlines. Such a factor holds for polynomial-time schedulability tests and exponential-time (exact) schedulability tests. Moreover, we also improve the speedup factor to $2.84306$ when considering constrained-deadline task systems. We also provide tight examples when the fitting strategy in themapping stage is arbitrary and $M$ is sufficiently large. For both constrained- and arbitrary-deadline task systems, the analytical result surprisingly shows that using exact tests does not gain theoretical benefits (with respect to speedup factors) if the speedup factor analysis is oblivious of the particular fitting strategy used.
Note (Outstanding Paper Award) An extended version is available via arXiv: http://arxiv.org/abs/1505.04693
Month 05-08, July
Year 2016
Projekt SFB876-B2
Url http://ls12-www.cs.tu-dortmund.de/daes/media/documents/publications/downloads/2016-chen-ecrts16-partition.pdf
Bibtex Here you can get this literature entry as BibTeX format.