Fine-grained Scheduling of Real-Time Recurrent DAG Tasks upon Multiprocessor Platforms

Abstract

With the strong demand for computing capacity in industrial applications and the rapid development of the hardware industry in recent years, multiprocessor platforms have been widely used in real-time embedded systems. The quest for performance has led to existing multiprocessor platforms often featuring complex interconnected hardware components and multiple levels of cache. This brings negative interference to the execution of tasks and challenges the predictability of real-time systems. However, existing non-preemptive execution models are an effective solution to eliminate these negative effects. In addition to this, the tasks that modern real-time systems process are becoming increasingly complex. Traditional sequential task models cannot cope with this situation and a stronger expressive model is required. A directed acyclic graph (DAG) that can express the complexity and parallelism of these tasks is a suitable model.

In this thesis, we focus on priority-based scheduling algorithms for multiple parallel DAG tasks on non-preemptive multiprocessor platforms, investigating, analysing, and improving existing global and partitioned scheduling algorithms.

We propose the concept of stacks to simulate a multi-processor platform and apply release-time tuning techniques based on its simulation of a task set in a hyperperiod. This allows us to impose tighter constraints on the execution of each job released from a task set in a fine-grained manner. We improved the existing priority-based global scheduling algorithm through the release-time tuning technique mentioned above. We also tried to construct a partitioned scheduling algorithm using the simulation results of stacks, i.e. so that all jobs are restricted to run on only one processor, consistent with the simulation results. Furthermore, to compare different scheduling algorithms more efficiently and to facilitate future researchers, we have developed the evaluation framework, a customisable experimental platform that includes DAG generation, application of scheduling algorithms, generation and analysis of the test results, allowing users to specify their experiments according to their goals.

Experiments with randomly generated workloads show that our improved algorithm consistently outperforms the state-of-the-art priority-based scheduling algorithm for different task graph structures and parameter configurations.