Research On Real-Time Scheduling Algorithms With Shared Resources

Multicores have been the mainstream of modern computer architecture. With the increasing requirements for real-time processing in embedded systems, more and more real-time systems will be built upon multicore platforms.In multicore real-time systems, scheduling algorithms, locking protocols, and the corresponding schedulability analysis are fundamental techniques to guarantee the timeliness of the system. In order to fully exploit the strong computing power provided by multicores, coordinated and optimized task scheduling and resource sharing are required. However, the vast majority of prior work on real-time scheduling algorithms assumes that tasks are independent, thus do not take into account the shared-resource constraints. Whereas, most prior work on real-time locking protocols focuses on the locking mechanisms or on the worst-case blocking time analysis. From a systematic point of view, how to improve the schedulability analysis and how to optimize task scheduling on multicore platforms with shared resources are still key issues in multicore real-time systems.In this thesis, a systematic research on multicore real-time scheduling with shared resources was carried out. Specifically, multicore real-time scheduling algorithms, real-time locking protocols, and the corresponding schedulability analysis were studied. The main contributions of this thesis are summarized as follows:(1) Two fundamental misconceptions in the analyses for the classic multiprocessor real-time locking protocols were pointed out, and simple remedies for such flaws were provided. The original worst-case blocking time analyses for the Distributed Priority Ceiling Protocol (DPCP) and the Multiprocessor Priority Ceiling Protocol (MPCP) were shown to be flawed. A recent worst-case response time analysis for semaphore protocols under Partitioned Fixed-Priority (P-FP) scheduling was also shown to be incorrect. The sources and the consequences of the flaws, and the fixes to the flaws were discussed.(2) An unified worst-case response time analysis for semaphore protocols under Global Fixed-Priority (G-FP) scheduling was proposed, and conclusive comparisons for all major global semaphore protocols were conducted. According to the common characteristics of task executions under G-FP scheduling, six types of delays were defined, based on which a unified framework for the worst-case response time analysis was proposed. Based on this framework, a linear-programming-based analysis was proposed. This analysis is general enough to analyze all major semaphore protocols under G-FP scheduling, including the uncontrolled priority inversions. According to large-scale schedulability experiments, the proposed analysis was shown to improve upon prior works significantly in terms of schedulability. Further, all major global semaphore protocols were directly compared. It is shown empirically that that the classic Priority Inheritance Protocol (PIP) and the simplest Flexible Multiprocessor Locking Protocol (FMLP) outperform the recent alternatives.(3) A worst-case blocking time analysis for semaphore protocols under P-FP scheduling was proposed. A novel analysis that upper-bounds the critical section execution time of tasks was established. By counting the maximum shared-resource usage for any task in an interval of any length, the accuracy of the worst-case blocking analysis was improved. Based on this method, a worst-case response time analysis was presented for the MPCP. According to the experiments, the proposed analysis outperforms prior analyses in terms of schedulability.(4) A shared-resource-aware task allocation algorithm under P-FP scheduling and spin-based locking protocols was proposed. For non-preemptive First-In-First-Out (FIFO) spinlocks, novel methods that respectively measure the relevancy between two tasks and the utilization-lose were proposed. Based on these methods, a task allocation algorithm was proposed. According to the experiments, the number of processors required by the proposed algorithm to schedule given task sets is less than the existing algorithms. Further, it is shown that load-unbalanced bin-packing heuristics could potentially incur a so-called remote clash problem during task allocation.(5) A resource-oriented partitioning algorithm for fixed-priority scheduling on multicore processors was proposed. An semi-partitioned scheduling framework was proposed for task scheduling, and shared-resource agents were used to manage resource sharing. It is shown that this algorithm has a speedup factor of 11 - 6/(m+1), where m is the number of processors, when each task has at most one critical section. This speedup factor is currently the minimum among the existing multicore real-time scheduling methods with shared resources. When each task has more than one critical sections, it is shown in the experiments that the proposed algorithm outperforms existing methods in terms of schedulability. The proposed algorithm, with bounded speedup factor, provided a new angle for a fundamental problem on how to share resources and how to schedule tasks in multicore real-time systems.