Semi-Partitioned Scheduling for Resource-Sharing Hard-Real-Time Tasks
Mayank Shekhar, Harini Ramaprasad, Frank Mueller · 2014
As real-time embedded systems integrate more and more functionality, they are demanding increasing amounts of com-putational power that can only be met by deploying them on powerful multi-core architectures. Efficient task allocation and scheduling on such architectures is paramount. Multi-core scheduling algorithms for independent real-time tasks has been the focus of much research over the years. However, in practice, tasks typically share software resources among each other. One of the foremost bottlenecks in successfully scheduling resource sharing tasks on multi-core architectures is the blocking times, especially remote blocking, that tasks may suffer from. In this paper, we present a novel semi-partitioned scheduling algorithm that significantly reduces blocking times of tasks by splitting a task into subtasks based on resource usage and executing resource independent and resource sharing subtasks on mutually exclusive cores. We demonstrate the effectiveness of our algorithm and eval-uate it alongside the classic Distributed Priority Ceiling Pro-tocol (DPCP) that uses a similar approach with “synchro-nization ” cores and alongside a recent partitioned schedul-ing approach called Greedy Slacker. Results demonstrate that our algorithm achieves a higher scheduled utilization in a majority of task sets, with average improvements in the range of 10 % to 15 % over DPCP and Greedy Slacker. 1.