On-Line Harmonic-Aware Partitioned Scheduling For Real-Time Multi-Core Systems Under RMS

Ming Fan1, Rong Rong2, Xinwei Niu3
1Broadcom Corporation, 2Florida International University, 3Penn State Erie, The Behrend College


For multi-core partitioned scheduling problem, bin-packing based techniques (First-Fit, Best-Fit and Worst- Fit) are dominated, through which the utilization of a task modeled as the “size” of the object and the utilization bound of a processor modeled as the “capacity” of the bin. However, any traditional bin-packing techniques can not perfectly represent the characteristics of the processors and tasks, as well as the implicit relations between tasks, i.e. the harmonic relationship with respect of periods. In this paper, we present a novel on-line harmonic-aware multi-core partitioned scheduling algorithm (no migration/split) for fixed-priority sporadic real-time tasks based on the Rate Monotonic Scheduling (RMS) policy. Our approach takes advantage of the fact that harmonic tasks can achieve a much higher processor utilization than that defined by a utilization bound. Moreover, the approach is fast, which is important specifically for on-line algorithm, by pre-building a hash table for on-line harmonicity searching. As demonstrated in our experimental results, by taking the task period relationship into consideration, our algorithm can achieve a significant improvement over previous work that based on traditional bin-packing techniques.