New Techniques For Real-Time OS On Multi-core Systems

Multi-core processors are widely used in all areas of computation. There is an increasing interest in deploying real-time systems on multi-core platforms. On a multi-core processor chip, multiple cores (i.e. CPUs) run independently with shared system resources including cache, memory, etc. Due to resource contention, the existing techniques for uni-processor systems can not be used to develop real-time applications on the new architectures.In the design of real-time systems, timing analysis and resource scheduling are two crucial tasks to ensure real-time requirements. For multi-core architectures, it is well-known that none of these is possible without the support of the underlining real-time operating system (RTOS). This thesis is devoted to the study on real-time scheduler and memory management, the two major components of RTOS for multi-core systems. In particular, we develop techniques for enabling predictable sharing of processor cores, caches as well as memory. Based on Linux platform, we have implemented and evaluated the proposed techniques. The main contributions of this thesis include:(1) Techniques to implement and evaluate semi-partitioned scheduling algorithms. Our study shows that semi-partitioned scheduling enables both high time-resolution and low run-time overheads, and outperforms other scheduling algorithms in the presence of realistic system overheads.(2) A memory management system with an address mapping control mechanism to support page coloring for resource mapping on multi-core architectures. The system is implemented based on Linux, which supports user-defined memory mapping. The system can be used as a platform for studying allocation policies for shared memories such as caches and memory banks.(3) A partition-based approach to cache sharing, which allows for partitioning shared caches among parallel applications and avoids cache contention in memory access on multi-core platforms. The advantage is that the existing execution time analysis techniques for uni-processor systems can be directly used on multi-core systems, thus reducing design complexity.(4) A semi-partition technique for memory banks on multi-core architectures to address the memory bank contention problems. Unlike the existing partitioning-based shared memory management schemes, our approach adopts a fine-grained assignment strategy, which only reserves banks for program segments with heavy memory accesses while allowing bank sharing among other program segments. In this way, memory can be utilized effectively.(5) A testing-based characterization technique to study the characteristics of new types of shared caches. Detailed hardware information is crucial for system developments. As an example, we have studied the cache address translation logic and replacement policy of a new Intel architecture, and discovered that a run-time adaptive cache replacement policy is used in the architecture, which is completely unknown in previous architectures. We have developed a method for generating benchmarks to characterize such adaptive caches and applied the method to build benchmarks for modeling memory parameters.In summary, scheduler design and shared resource management issues for multi-core real-time systems are studied in this thesis, as well as analysis techniques to characterize hardware architectural features. The work of this thesis can be used in real systems and further supports theoretical research in multi-core real-time systems.