Login

Response-Time Analysis of Limited-Preemptive Parallel DAG Tasks under Global Scheduling
Ref: CISTER-TR-190405       Publication Date: 9 to 12, Jul, 2019

Response-Time Analysis of Limited-Preemptive Parallel DAG Tasks under Global Scheduling

Ref: CISTER-TR-190405       Publication Date: 9 to 12, Jul, 2019

Abstract:
Most recurrent real-time applications can be modeled as a set of sequential code segments (or blocks) that must be (repeatedly) executed in a specific order. In this paper, we provide a schedulability analysis for such systems modeled as a set of parallel DAG tasks executed under any limited-preemptive global job-level fixed priority scheduling policy. More precisely, we derive response-time bounds for a set of jobs subject to precedence constraints, release jitter, and executiontime uncertainty, which enables support for a wide variety of parallel, limited-preemptive execution models (e.g., limited-preemptive periodic DAG tasks, generalized multi-frame tasks, distributed transactions, etc.). Our analysis explores the space of all possible schedules using a powerful new state abstraction and state-pruning technique. In an empirical evaluation, the analysis is able to identify between 10 to 90 percentage points more schedulable task sets than the state-of-the-art schedulability test for limited-preemptive sporadic DAG tasks. It scales to large systems of up to 64 cores with 20 DAG tasks. Moreover, while our analysis is almost as accurate as the state-of-the-art exact schedulability test based on model checking (for sequential non-preemptive tasks), it is three order-of-magnitude faster and hence capable of analyzing task sets with more than 60 tasks on 8 cores in less than a few seconds.

Authors:
Mitra Nasri
,
Geoffrey Nelissen
,
Björn B. Brandenburg


Events:

ECRTS 2019
9, Jul, 2019 >> 12, Jul, 2019
31th Conference on Real-Time Systems
Stuttgart, Germany


31st Conference on Real-Time Systems (ECRTS 2019), pp 21:1-21:23.
Stuttgart, Germany.

DOI:10.4230/LIPIcs.ECRTS.2019.21.
ISBN: 978-3-95977-110-8.
ISSN: 1868-8969.



Record Date: 4, Apr, 2019