Response-time analysis of limited-preemptive parallel DAG tasks under global scheduling

Conference Paper (2019)
Author(s)

Mitra Nasri (TU Delft - Embedded Systems)

Geoffrey Nelissen (University of Sfax, Tunisia and CISTER)

Bjorn B. Brandenburg (Max Planck Institute for Software Systems)

Research Group
Embedded Systems
Copyright
© 2019 Mitra Nasri, Geoffrey Nelissen, Björn B. Brandenburg
DOI related publication
https://doi.org/10.4230/LIPIcs.ECRTS.2019.21
More Info
expand_more
Publication Year
2019
Language
English
Copyright
© 2019 Mitra Nasri, Geoffrey Nelissen, Björn B. Brandenburg
Research Group
Embedded Systems
Volume number
133
Pages (from-to)
1-23
ISBN (electronic)
9783959771108
Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

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. This paper provides 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 execution-time uncertainty, which enables support for a wide variety of parallel, limited-preemptive execution models (e.g., periodic DAG tasks, transactional tasks, generalized multi-frame tasks, etc.). Our analysis explores the space of all possible schedules using a powerful new state abstraction and state-pruning technique. An empirical evaluation shows the analysis 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 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 orders of magnitude faster and hence capable of analyzing task sets with more than 60 tasks on 8 cores in a few seconds.