Response Time Analysis of Parallel Real-Time DAG Tasks Scheduled by Thread Pools

Modern high-end embedded systems nowadays have to process enormous amounts of data. In order to speed up the computations and fully exploit the resources of the underlying hardware architectures, software developers can avail parallelism frameworks such as Intel Threading Building Blocks or compiler extensions as OpenMP. They ease the development of parallel applications by providing interfaces for common parallel design patterns and by internally distributing the work among the workers of a thread pool. However, such frameworks and compiler extensions do not yet support the stringent timing requirements of real-time systems and therefore, an adaption of their computation model to the sector of real-time systems needs to be conducted.

In this paper, we address the problem of scheduling parallel real-time directed acyclic graphs tasks on multiprocessor architectures where the subtasks are dispatched among and executed by the workers of a thread pool. In contrast to existing work in the state-of-the-art, we limit the maximum parallelism of real-time tasks not by the number of processors in the system, but by the number of worker threads used in the thread pool of each real-time application. For this model, we derive a worst-case response time analysis for task sets scheduled by a preemptive global fixed-priority scheduler. In order to evaluate the performance of our response time analysis, we further perform schedulability tests on generated task sets and compare the results to existing feasibility analyses in the current state-of-the-art.