Response time analysis of sporadic DAG tasks under partitioned scheduling

Jose Fonseca, Geoffrey Nelissen, Vincent Nelis, Luis Miguel Pinho

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

20 Citations (Scopus)

Abstract

Several schedulability analyses have been proposed for a variety of parallel task systems with real-Time constraints. However, these analyses are mostly restricted to global scheduling policies. The problem with global scheduling is that it adds uncertainty to the lower-level timing analysis which on multicore systems are heavily context-dependent. As parallel tasks typically exhibit intense communication and concurrency among their sequential computational units, this problem is further exacerbated. This paper considers instead the schedulability of partitioned parallel tasks. More precisely, we present a response time analysis for sporadic DAG tasks atop multiprocessors under partitioned fixed-priority scheduling. We assume the partitioning to be given. We show that a partitioned DAG task can be modeled as a set of self-suspending tasks. We then propose an algorithm to traverse a DAG and characterize such worst-case scheduling scenario. With minor modifications, any state-of-The-Art technique for sporadic self-suspending tasks can thus be used to derived the worst-case response time of a partitioned DAG task. Experiments show that the proposed approach significantly tightens the worst-case response time of partitioned parallel tasks comparatively to the state-of-The-Art when the most accurate technique is chosen.

Original languageEnglish
Title of host publication2016 11th IEEE International Symposium on Industrial Embedded Systems, SIES 2016 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers
ISBN (Electronic)9781509022823
DOIs
Publication statusPublished - 11 Jul 2016
Externally publishedYes
Event11th IEEE International Symposium on Industrial Embedded Systems, SIES 2016 - Krakow, Poland
Duration: 23 May 201625 May 2016

Publication series

Name2016 11th IEEE International Symposium on Industrial Embedded Systems, SIES 2016 - Proceedings

Conference

Conference11th IEEE International Symposium on Industrial Embedded Systems, SIES 2016
CountryPoland
CityKrakow
Period23/05/1625/05/16

Fingerprint Dive into the research topics of 'Response time analysis of sporadic DAG tasks under partitioned scheduling'. Together they form a unique fingerprint.

  • Cite this

    Fonseca, J., Nelissen, G., Nelis, V., & Pinho, L. M. (2016). Response time analysis of sporadic DAG tasks under partitioned scheduling. In 2016 11th IEEE International Symposium on Industrial Embedded Systems, SIES 2016 - Proceedings [7509443] (2016 11th IEEE International Symposium on Industrial Embedded Systems, SIES 2016 - Proceedings). Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/SIES.2016.7509443