Response Time Analysis of Tasking Framework Task Chains

Abstract

Multi-core processors have been increasingly utilized in general computing and modern embedded applications for their potential to maximize system throughput. Parallel frameworks allow programmers to make the most of parallelism without having the burden of understanding the underlying architecture. However, real-time systems comprise tasks governed by stringent timing requirements, which the parallel frameworks do not support. There is a need to analyze a computation model that adapts both advantages. The analysis of parallel real-time applications modeled as Directed Acyclic Graph (DAG) tasks scheduled on multi-core platforms has been intensively studied in recent years. A real-time task can be modeled as periodic and sporadic tasks. In recent years, sporadic tasks have been modeled as periodic by considering the maximum arrival frequency as the period. Current studies provide an analysis of the challenges faced for scheduling real-time tasks modeled as DAG tasks on multi-core processors where all the subtasks (fragments of the task) are consigned to and executed by the worker threads of a thread pool by restricting the maximum parallelism at any point of execution by the number of threads in the thread pool. However, the existing work dispatches the subtasks to the threads in a non-deterministic way, i.e., the execution order of the subtasks is not contemplated. The work done here proves that the intra-task priorities have a notable impact on the worst-case response time. Furthermore, it confirms that the upper bound of response time computed by modeling sporadic tasks as periodic is pessimistic. An algorithm is introduced that allows analyzing a safe upper bound for the response time by controlling the execution order. Moreover, a function is utilized to model sporadic tasks without maximal arrival frequency to achieve a less pessimistic result. An analysis is made to derive a worst-case response time for a task set scheduled by a preemptive global fixed-priority scheduler, wherein each task has intra-task priorities assigned. The work is further extended by providing experiments with randomly created DAG tasks showing that the proposed method outperforms the current state-of-the-art methods.