Memory Aware Scheduling and Analysis of Phased Tasks for Predictable Execution on Multi-Core Platforms

QC 20260930

Abstract

Multi-core platforms offer high performance and a large availability of processing resources. However, increased contention when accessing shared resources is a result of the high parallelism, and one of the main challenges when real-time applications are deployed to these platforms. As a result, execution models have been proposed to minimize contention by separating access to shared resources from execution,i.e., phased execution models. Memory access and computation are performed in dedicated phases to make the execution of tasks more predictable. This thesis is focused on memory-centric scheduling of phased-execution models, such as the PRedictable Execution Model (PREM) and Acquisition-Execution-Restitution (AER)model for multi-core platforms to improve the satisfaction of both application and platform constraints.

In this thesis, scheduling and analysis of task sets that follow phased execution models are focused on to improve schedulability while improving their applicability to memory-limited embedded multi-core platforms. The work presented in the thesis aims to improve schedulability in two main ways: 1) by using preemptive scheduling to improve the schedulability ratio, and 2) by reducing the pessimism in the schedulability analysis and the execution model to improve the percentage of task sets identified as schedulable.

This thesis emphasizes the importance of handling local data of phased tasks under preemptive scheduling, given the limited size of the local memory. Accordingly, different preemption approaches that preserve the predictable execution semantics of the phased execution model are proposed and discussed. In addition, worst-case local memory usage analyses are proposed to be used at design time to analyze the local memory feasibility for preemptively scheduled phased tasks on memory-constrained embedded platforms. A key takeaway is that limiting preemptions significantly helps the phased tasks to achieve schedulability under local memory constraints. We propose limited preemption for both time-triggered and online scheduling. Preemption threshold scheduling, a method that limits preemptions by allowing preemption only from tasks with a priority above a certain threshold, is proposed for the phased tasks. To enable the use of preemption thresholds, preemption threshold assignment algorithms, schedulability, and local memory feasibility analysis are proposed. The experimental results show that preemption thresholds improve schedulability and memory feasibility over both non-preemptive and fully-preemptive scheduling for phased tasks.

Aiming only to improve schedulability is not effective unless there exists a schedulability test that identifies the schedulable task sets. Accordingly, this thesis defines the schedulability of phased tasks under global non-preemptive scheduling as a reachability problem using timed automata in UPPAAL to eliminate pessimism in schedulability analysis. Moreover, among other things, the pessimism in the schedulability test is reduced by adopting a simpler execution model that is easier to analyze for phased tasks under preemption threshold scheduling. In both cases, the identified schedulable task sets are significantly improved compared to their counterparts.

Link to DiVA