Enhanced fixed-priority real-time scheduling on multi-core platforms by exploiting task period relationship

• The utilization bound of task sets increases as task periods are closer to harmonic.
• We present two scheduling algorithms for real-time tasks on multi-core platforms.
• We take the period relationship among tasks into consideration.
• We formally prove the schedulability of our proposed scheduling algorithms.
• The proposed algorithms significantly outperform the existing related work.

One common approach for multi-core partitioned scheduling problem is to transform this problem into a traditional bin-packing problem, with the utilization of a task being the “size” of the object and the utilization bound of a processing core being the “capacity” of the bin. However, this approach ignores the fact that some implicit relations among tasks may significantly affect the feasibility of the tasks allocated to each local core. In this paper, we study the problem of partitioned scheduling of periodic real-time tasks on multi-core platforms under the Rate Monotonic Scheduling (RMS) policy. We present two effective and efficient partitioned scheduling algorithms, i.e. PSER and HAPS, by exploiting the fact that the utilization bound of a task set increases as task periods are closer to harmonic on a single-core platform. We formally prove the schedulability of our partitioned scheduling algorithms. Our extensive experimental results demonstrate that the proposed algorithms can significantly improve the scheduling performance compared with the existing work.