HomePublicationsPhD Thesis

Shared Resource Contention-Aware Schedulability Analysis of Hard Real-Time Systems
Ref: CISTER-TR-231001       Publication Date: 8, Sep, 2023

Abstract:
Modern commercial-off-the-shelf (COTS) multicore processors were introduced to provide raw computing power and to build energy-efficient and cost-effective solutions. As a consequence, they have been used in most modern computing systems. However, the adoption of multicore platforms in hard real-time systems, i.e., systems that run applications with stringent time requirements, is still under the scrutiny of the real-time systems research community. One of the main challenges that hinder the use of COTS multicore platforms in hard real-time systems is their unpredictability, which originates from the sharing of different hardware resources such as shared caches, interconnect (e.g., memory bus), and the main memory. Specifically, a task executing on one core of a multicore platform has to compete with other co-running tasks (tasks running on other cores) to access these shared resources. This contention between tasks to access shared resources is formally known as the shared resource contention. Shared resource contention is problematic as it can negatively influence the temporal behavior of tasks in a non-deterministic manner. To safely determine whether all tasks running in the system can execute without violating their respective timing constraints, one of the most important factors is to analyze and derive a safe bound on the maximum shared resource contention that tasks can suffer.
The main objective of this dissertation is to build novel solutions to accurately quantify the shared resource contention that can be suffered by tasks due to the sharing of resources such as the memory bus and the main memory.
Among all the existing solutions that eliminate/allow analyzing the shared resource contention, the phased execution model has been identified as a good solution that enables a more precise analysis of the shared resource contention. Specifically, the idea of the phased execution model is to divide the task execution into distinct computation and memory phases such that a shared resource, e.g., main memory, can be accessed by the tasks only during their memory phases. However, shared resource contention can still occur even when tasks comply with the phased execution model, e.g., when memory phases of tasks running on different cores execute concurrently.
In this dissertation, we start by modeling and analyzing the maximum memory bus contention, i.e., contention due to the sharing of memory bus that can be suffered by tasks under the phased execution model. We then evaluate the impact of the bus arbitration policy on the bus contention that tasks can suffer by varying the bus arbitration policy. Results show that the use of a fairer bus arbitration scheme along with the phased execution model can lead to a tighter bound on the memory bus contention.
We also investigate the relationship between the memory bus and the cache memories. Specifically, we show that the bus contention strongly relates to the number of bus requests which further depends on the content of cache memories. Building on this, we propose the holistic bus contention analysis that analyzes the cache memories to bound the maximum number of cache misses and integrate them in the computation of the maximum bus contention that phased tasks can suffer.
Furthermore, we improve the bounds on the main memory contention of phased tasks considering dynamic random access-based memory systems. We first identify the pessimism in the existing analysis that lies in the overestimation of the memory contention that can be caused by the write memory requests. We then propose a memory contention analysis that accurately quantifies the memory contention that can be suffered by tasks. We also show how the memory address mapping of tasks can impact the maximum memory contention that tasks can suffer.
Finally, we focus on the memory-centric scheduling that schedules the memory phases of all tasks running on the system such that multiple tasks cannot access the main memory concurrently to avoid shared resource contention. However, tasks can still be delayed, for example, if the memory scheduler is currently serving a memory phase of a task on another core. We first identify the sources of pessimism in the recent memory-centric scheduling-based analysis. We then provide insights on how such pessimism can be addressed. Building on this, we propose an improved memory-centric scheduling-based analysis that addresses the pessimism of the existing analysis.
Keywords: Real-time systems, Hard real-time systems, Multicore processors, Shared resources, Bus contention, Memory contention, Timing analysis.

Jatin Arora

Document:

View
PDF Download
PDF