Schedulability analysis of DAG tasks with arbitrary deadlines under global fixed-priority scheduling

摘要

One of the major sources of pessimism in the response time analysis (RTA) of globally scheduled real-time tasks is the computation of an upper-bound on the inter-task interference. This problem is further exacerbated when intra-task parallelism is permitted because of the complex internal structure of parallel tasks. This paper considers the global fixed-priority (G-FP) scheduling of sporadic real-time tasks when each task is modeled by a directed acyclic graph (DAG) of concurrent subtasks. We present a RTA based on the concept of problem window, a technique that has been extensively used to study the schedulability of sequential task in multiprocessor systems. The problem window approach of RTA usually categorizes interfering jobs in three different groups: carry-in, carry-out and body jobs. In this paper, we propose two novel techniques to derive less pessimistic upper-bounds on the workload produced by the carry-in and carry-out jobs of the interfering tasks. Those new bounds take into account the precedence constraints between subtasks pertaining to the same DAG. We show that with this new characterization of the carry-in and carry-out workload, the proposed schedulability test offers significant improvements on the schedulability of DAG tasks for randomly generated task sets in comparison to state-of-the-art techniques. In fact, we show that, while the state-of-art analysis does not scale with an increasing number of processors when tasks have constrained deadlines, the results of our analysis are barely impacted by the processor count in both the constrained and the arbitrary deadline case.