Toward time-predictable execution of multi-task real-time systems

Guaranteeing time-predictable execution in real-time systems involves the management of not only processors but also other supportive components such as cache memory, network on chip (NoC), memory controllers. These three components are designed to improve the system computational throughput through either bringing data closer to the processors (e.g cache memory) or maximizing concurrency in moving data inside the systems (e.g. NoC and memory controllers). We observe that these components can be sources of significant unpredictability in task executions if they are not operated in a deterministic manner. In particular, our analysis and experiments in [6, 35] show that with the standard cache and memory controller sharing mechanism, the execution time of a task may be unpredictably extended up to 33 to 44% in a single-core processor. We also show that analysis techniques and scheduling algorithms that have been proposed to account for and/or to mitigate this unpredictability often do not adequately address the problem at hand. As the consequence, those techniques and algorithms can only guarantee real-time execution in systems with under-utilized shared resources. In this dissertation, we study the software and hardware infrastructure, optimization techniques and scheduling algorithms that guarantee predictable execution in real-time systems that use cache memory, network on chip (NoC), and memory controllers. The main challenge is how to guarantee system predictability in such a way that maximizes the benefits and the utilization of these components. We achieve that by carefully analyzing both theoretical and practical assumptions in the use of these components and deriving novel solutions based on this understanding. For cache memory, we propose the use of softwarebased cache partitioning techniques and a real-time optimization method to minimize the system real-time utilization. The proposed solution renders better performance because of its fully utilization of available cache area. For NoC scheduling, we proposed novel scheduling algorithms that are designed to cope directly with the unique assumption on resource sharing in NoC. As will be shown, in practical systems, these scheduling algorithms can achieve near optimal performance. For memory controllers, we propose a software and hardware infrastructure and coscheduling algorithms that are used to control the accesses of the DMA-enabled peripherals to the main memory. The goal is to prevent these accesses from delaying tasks’ execution beyond the worst-case execution while still maximizing the I/O throughput