Print Email Facebook Twitter Response-time analysis of limited-preemptive parallel DAG tasks under global scheduling Title Response-time analysis of limited-preemptive parallel DAG tasks under global scheduling Author Nasri, Mitra (TU Delft Embedded Systems) Nelissen, Geoffrey (University of Sfax, Tunisia and CISTER) Brandenburg, Björn B. (Max Planck Institute for Software Systems) Contributor Quinton, Sophie (editor) Date 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. 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. Subject Global multiprocessor schedulingNon-preemptive jobsOpenMPParallel DAG tasksPrecedence constraintsSchedulability analysisWorst-case response time To reference this document use: http://resolver.tudelft.nl/uuid:0097c45a-c62a-441f-aba1-e0f8c6f90710 DOI https://doi.org/10.4230/LIPIcs.ECRTS.2019.21 Publisher Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing ISBN 9783959771108 Source 31st Euromicro Conference on Real-Time Systems, ECRTS 2019, 133 Event 31st Euromicro Conference on Real-Time Systems, ECRTS 2019, 2019-07-09 → 2019-07-12, Stuttgart, Germany Part of collection Institutional Repository Document type conference paper Rights © 2019 Mitra Nasri, Geoffrey Nelissen, Björn B. Brandenburg Files PDF LIPIcs_ECRTS_2019_21.pdf 1.77 MB Close viewer /islandora/object/uuid:0097c45a-c62a-441f-aba1-e0f8c6f90710/datastream/OBJ/view