Research On Real-Time Scheduling For Multi-core Systems

The rapid development of multi-core processors leads to a constantly increasing trend of deploying real-time systems on multi-core platforms, to satisfy the dramatically increasing high-performance and low-power requirements. This trend demands effective and efficient multiprocessor real-time scheduling techniques. The uniprocessor scheduling problem has been well studied during the last40years. However, the multiprocessor scheduling problem to schedule tasks onto parallel architectures is a much harder challenge.This thesis studied the design and analysis of real-time scheduling algorithms for multi-core processor systems. The major target of this thesis is to solve several fundamental theoretical problems in the multiprocessor scheduling model, as well as to consider various aspects in constructing practical real-time systems on multi-core processors. Multiprocessor scheduling is usually categorized into two paradigms:global scheduling and (semi-) partitioned scheduling. This thesis contributes to both with new fundamental results (including the critical instant in global scheduling, conditions for bounded response time in global scheduling, and utilization bounds in semi-partitioned scheduling), as well as proposing several techniques to improve the average-case real-time performance in multiprocessor scheduling (including non-preemptive global scheduling, instance-level priority assignment in global scheduling, semi-partitioned scheduling based on response time analysis and parametric utilization bounds). The main contribution of this thesis can be summarized as follows:(1) This thesis proposed a novel response time analysis technique for preemptive global fixed-priority scheduling, based on a concept similar to the well-known critical instant in single-processor scheduling. This new technique can significantly improve the analysis accuracy without degrade the efficiency. Futher, a general condition guaranteeing the bounded response time of tasks in global fixed-priority scheduling is established based on the above technique.(2) This thesis proposed a novel schedulability analysis technique for non-preemptive global fixed-priority scheduling, and conducts empirical simulation experiments, which disclose that in multiprocessor scheduling non-preemptive scheduling can outperform preemptive scheduling in many cases. This counters the widely accepted knowledge originating from single-processor scheduling that preemptive scheduling is superior to non-preemptive scheduling for real-time systems. The thesis also dicussed under what kind of circumstance non-preemptive can greatly improve the system real-time performance.(3) This thesis proposed a novel instance-level fixed-priority scheduling algorithm and its schedulability analysis techniques. The proposed algorithm can greatly improve the system real-time performance by exploring the priority order among task instances, and can be viewed as a combination of the advantage of both fixed-priority scheduling and EDF scheduling. This algorithm offline constructs the abstract system workload and only assign priorities to a limited number of task instances, by which the runtime scheduler can dispatch instance priorities and guarantee the timing correctness of the system.(4) This thesis generalized the famous Liu&Layland utilization bound for single-processor scheduling to multiprocessor scheduling. It proposed a semi-partitioned fixed-priority scheduling algorithm with the Liu&Layland utilization bound. This algorithm is based on a partitioning approach similar to the "worst-fit decreasing" heuristics in bin-packing problem, such that task splitting only happens with high priority tasks, which solves the workload increase caused by task splitting. This algorithm solves a40-years long-standing open problem in real-time scheduling.(5) This thesis generalized most parametric utilization bounds in single-processor scheduling to multiprocessor scheduling. It proposed a semi-partitioning fixed-priority scheduling algorithm, which can generalized most known parametric utilization bounds in single-processor scheduling to the multiprocessor scheduling setting.This algorithm uses response time analysis, instead of the utilization bound test, to decide the maximal workload that can be assigned to a processor, and thus it has a much better average-case real-time performance then previous algorithms.Moreover, this thesis also studied cache-aware real-time scheduling on multi-core processors. An important new feature of multi-core processors is using many on-chip shared resources (like shared cache). The timing behavior of a task depends on other co-running tasks due to the accessing to shared resources, which invalidates a basic assumption in traditional real-time scheduling research that the worst-case execution time of each individual task is known. This thesis proposed a novel cache-aware real-time scheduling technique, which guarantees the system timing precictability by avoiding inter-task shared cache contention, and presented sufficient schedulability test conditions for the novel scheduling which require both processors and cache blocks as processing resources.In summary, this thesis studied various real-time scheduling algorithms for multi-core systems, covering different scheduling paradigms (global and partitioned, preemptive and non-preemptive, fixed-task priority and fixed-instance priority). The results of this thesis serve as theoretical foundations as well as provides practical insights for the design and analysis of real-time systems on multi-cores.