Real-time Scheduling for Multi-cores

Motivation

During the past four decades, the real-time scheduling theory based on uni-processors has been intensively studied and very well estabilished. As the multi-core architectures are widely used in embedded systems, it becomes more and more clear that futhure real time systems will be deployed on multi-core architectures. However, the real-time scheduling problem on multiprocessor models is very different from and significantly more difficult than uni-processor scheduling. The study of multiprocessor scheduling theory is far from amature, and many fundamental problems in the theory are still open. On the other hand, design of real-time scheduling on multi-cores also needs to consider the new architecture features of multi-cores. For example, programs executing on different cores usually shared fine-grained resources, like shared cache and shared memory bandwidth. These new architecture features make the conventional design practise not sutiable to multi-cores. In summary, the multi-core architectures bring significant challenge to the design, analysis and implementation of real-time systems. New abstractions, scheduling paradigms, analysis techniques and implementation principle of real-time OS are of highly demand to build a formal fundation of the design and analysis of real time systems on multi-cores.

Long Term Goal

Gain a better understanding on how to design, analyze and implement real-time systems on multi-core architectures.

Expected Results

We expect to develop new abstractions, scheduling paradigms and analysis techniques for real-time systems on multi-cores. Our research results will be delivered with a real-time operating system for multi-cores.

Approach

  • Investigate the common features of real-time systems on multi-cores, to develop new abstractions to precisely model the system timing behavior.
  • Investigate the multi-core architecture features, and study the influence of these new features on the system timing behavior.
  • Generalize the estabilished results in uni-processor scheduling theory to multiprocessor scheduling.
  • Quantitatively identify the real-time performance of varies of scheduling paradigms using metrics like utilization bounds and speedup factors.
  • Study design principles for implementing realtime system on multicore platform. We plan to provide an experimental platform that could evaluate and domenstrate the performance of desired system design.
  • Study the effect of shared resources (shared cache, shared memory, etc.) to multi-core scheduling in realistic systems. Design novel resource management strategies to guarantee real-time performance in presence of these effects.
  • Use Linux as our software platform. For hardware platform, we are using both commerial machine and simulators, currently they are Intel Core i7, Simics and GEMS.

Achievements

  • We have developed an partitioning-based multiprocessor scheduling algorithm, which solves the open problem of generalizing the well-known Liu and Layland's utilization bound for uni-processor scheduling to multiprocessor scheduling. We have implemented this novel algorithm in Linux and conduct empirical evaluations, which shows that our new algorithm not only has the best theoretical utilization bound, but also significantly outperforms other scheduling paradigms in average-case real-time performance.
  • We have developed a new schedulability/response time analysis technique for global multiprocessor scheduling to significantly improve the analysis precision. The technique established a concept similar to the "critical instance" concept in uniprocessor scheduling, which facilitate an efficient and precise analysis for global fixed priority multiprocessor scheduling. This work won the Best Paper Award of the 30th IEEE Real-Time Systems Symposium.
  • We also developed new scheduling algorithms using page coloring to avoid the interfereing on shared cache, which enables a separate estimation of the worst-case execution time of each individual task. This new algorithm also has been implemented in Linux. Experiments show that our new algorithm has significantly improved system predictability, and sometimes even have better average-case performance than other algorithms without cache partitioning.

Publications

  • Nan Guan, Martin Stigge, Wang Yi, Ge Yu "Parametric Utilization Bounds for Fixed-Priority Multiprocessor Scheduling", 26th IEEE International Parallel & Distributed Processing Symposium (IPDPS), 2012.
  • Nan Guan, Pontus Ekberg, Martin Stigge, Wang Yi "Effective and Efficient Scheduling for Certifiable Mixed Criticality Sporadic Task Systems", The 32nd IEEE Real-Time Systems Symposium (RTSS), 2011.
  • Yi Zhang, Nan Guan, Yanbin Xiao, Wang Yi. "Implementation and Empirical Comparison of Partitioning-based Multi-core Scheduling". In the proc. of the 6th IEEE International Symposium on Industrial Embedded Systems (SIES), 2011.
  • Nan Guan, Pontus Ekberg, Martin Stigge and Wang Yi. "Resource Sharing Protocols for Real-Time Task Graph Systems". In the proc. of the 23rd Euromicro Conference on Real-Time Systems (ECRTS), 2011.
  • Nan Guan, Martin Stigge, Wang Yi and Ge Yu, "Fixed Priority Multiprocessor Scheduling with Liu & Layland's Utilization Bound", The 16th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), 2010. Best Paper Nomination
  • Nan Guan, Martin Stigge, Wang Yi and Ge Yu, "New Response Time Bounds of Fixed Priority Multiprocessor Scheduling", The 30th IEEE Real-Time Systems Symposium (RTSS'09), 2009. Best Paper Award
  • Nan Guan, Martin Stigge, Wang Yi and Ge Yu, "Cache-Aware Scheduling and Analysis for Multicores", The 7th International Conference on Embedded Software (EMSOFT'09), 2009.
  • Nan Guan, Wang Yi, Zonghua Gu, Qingxu Deng and Ge Yu, "New Schedulability Test Conditions for Non-Preemptive Scheduling on Multiprocessor Platforms", The 29th IEEE Real-Time Systems Symposium (RTSS'08), 2008.
  • Nan Guan, Wang Yi, Qingxu Deng, Zonghua Gu, Ge Yu "Schedulability Analysis for Non-preemptive Fixed-Priority Multiprocessor Scheduling", Journal of Systems Architecture.
  • Jeremy Erickson, Nan Guan, Sanjoy Baruah "Tardiness Bounds for Global EDF with Deadlines Different from Periods", The 14th International Conference On Principles Of Distributed Systems (OPODIS'10), 2010.

Staff

Senior: Wang Yi (Contact)
Ph.D. students: Pontus Ekberg, Nan Guan, Martin Stigge, Yi Zhang

Internal page