Low-Overhead Non-Preemptive Scheduling of Real-Time Tasks upon Multiprocessor Platforms

While multiprocessor platforms have been widely adopted by the embedded systems industry in the past couple of years, there are still fundamental challenges about their timing predictability for applications with real-time timing constraints. The common-off-the-shelf (COTS) multiprocessor platforms typically use complex hardware components, interconnects and multi-level caches which are designed to deliver higher average-case performance. However, these features negatively impact the worst-case performance as they increase the interference of tasks on shared hardware resources. One effective software-based solution to counteract these issues is to use the non-preemptive execution model. Despite its positive impact on timing predictability, non-preemptive execution causes a potential blocking problem which can decrease the ability to guarantee all timing constraints of the system. It is also known that scheduling non-preemptive periodic tasks on multiprocessor platforms is an NP-hard problem. In this thesis, we focus on non-preemptive execution of sequential as well as parallel real-time tasks upon multiprocessor platforms and investigate, extend, and improve the state of the art on global, partitioned, and semi-partitioned scheduling approaches for the problem. We provide the first necessary test for partition-ability, i.e., a test that can determine whether a given task set cannot be partitioned on a given number of cores regardless of the partitioning policy. This test allows us to quantify the pessimism of the existing partitioning heuristics as well as obtain the limits of partitioned scheduling. We further introduce the first non-work-conserving global scheduling policy and show that despite the fact that it improves over the existing global scheduling policies, it is not as effective as the partitioned scheduling strategies. We extend a sustainable scheduling algorithm designed for uni-processor platforms to multiprocessor ones to improve the performance of partitioning heuristics. A sustainable scheduling algorithm does not have timing anomalies and hence it is easier to analyze and can have better scheduling results. Furthermore, we introduce the first semi-partitioned non-preemptive scheduling solution for multiprocessor platforms. Our solution is able to schedule some of the task sets for which it is impossible to find a partitioning solution. Finally, we compare the overheads and memory consumption of various scheduling approaches (including ours) on a bare-metal multiprocessor hardware platform, i.e., a 4 processor Raspberry Pi board. We show that our sustainable scheduler has a very low overhead while it out-performs other solutions in terms of schedulability.Electrical Engineering | Embedded System