doi: 10.7873/DATE.2015.0912

Multi-Core Fixed-Priority Scheduling of Real-Time Tasks with Statistical Deadline Guarantee

Tianyi Wang1,a, Linwei Niu2, Shaolei Ren1,b and Gang Quan1,c

1Department of Electrical&Computer Engineering, Florida International University, FL USA.

2Department of Mathematics&Computer Science, West Virginia State University, WV USA.


The rising performance variance of IC chips and increased resource sharing in multi-core platforms have significantly degraded the predictability of real-time systems. The traditional deterministic approaches can be extremely pessimistic, if not infeasible at all. In this paper, we adopt a probabilistic approach for fixed-priority preemptive scheduling of real-time tasks on multi-core platforms with statistical deadline miss probability guarantee. Rather than a single-valued worstcase execution time (WCET), we formulate the task execution time as a probabilistic distribution. We develop a novel algorithm to partition real-time tasks on multiple homogenous cores, which takes not only task execution time distributions but their period relationships into considerations. Our extensive experimental results show that our proposed methods can greatly improve the schedulability of real-time tasks when compared with the traditional bin packing approaches.

Keywords: Probabilistic, Multi-core, Task partitions, Harmonic, Real-time systems.

Full Text (PDF)