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

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

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

1 Citation (Scopus)
62 Downloads (Pure)

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.

Original languageEnglish
Title of host publication31st Euromicro Conference on Real-Time Systems, ECRTS 2019
EditorsSophie Quinton
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages1-23
Number of pages23
Volume133
ISBN (Electronic)9783959771108
DOIs
Publication statusPublished - 2019
Event31st Euromicro Conference on Real-Time Systems, ECRTS 2019 - Stuttgart, Germany
Duration: 9 Jul 201912 Jul 2019

Conference

Conference31st Euromicro Conference on Real-Time Systems, ECRTS 2019
CountryGermany
CityStuttgart
Period9/07/1912/07/19

Keywords

  • Global multiprocessor scheduling
  • Non-preemptive jobs
  • OpenMP
  • Parallel DAG tasks
  • Precedence constraints
  • Schedulability analysis
  • Worst-case response time

Fingerprint Dive into the research topics of 'Response-time analysis of limited-preemptive parallel DAG tasks under global scheduling'. Together they form a unique fingerprint.

Cite this