Publication
Response-Time Analysis of Limited-Preemptive Parallel DAG Tasks under Global Scheduling
| dc.contributor.author | Nasri, Mitra | |
| dc.contributor.author | Nelissen, Geoffrey | |
| dc.contributor.author | Brandenburg, Björn B. | |
| dc.date.accessioned | 2020-01-16T14:58:12Z | |
| dc.date.available | 2020-01-16T14:58:12Z | |
| dc.date.issued | 2019 | |
| dc.description.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. | pt_PT |
| dc.description.version | info:eu-repo/semantics/publishedVersion | pt_PT |
| dc.identifier.doi | 10.4230/LIPIcs.ECRTS.2019.21 | pt_PT |
| dc.identifier.issn | 1868-8969 | |
| dc.identifier.uri | http://hdl.handle.net/10400.22/15291 | |
| dc.language.iso | eng | pt_PT |
| dc.peerreviewed | yes | pt_PT |
| dc.publisher | Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik | pt_PT |
| dc.relation | PReFECT, ref. POCI-01-0145-FEDER-029119 | pt_PT |
| dc.relation | THERMAC, ref. H2020-CS2-CFP08-2018-01 | pt_PT |
| dc.relation.publisherversion | http://drops.dagstuhl.de/opus/volltexte/2019/10758 | pt_PT |
| dc.subject | Parallel DAG tasks | pt_PT |
| dc.subject | Global multiprocessor scheduling | pt_PT |
| dc.subject | Schedulability analysis | pt_PT |
| dc.subject | Non-preemptive jobs | pt_PT |
| dc.subject | Precedence constraints | pt_PT |
| dc.subject | Worst-case response time | pt_PT |
| dc.title | Response-Time Analysis of Limited-Preemptive Parallel DAG Tasks under Global Scheduling | pt_PT |
| dc.type | conference object | |
| dspace.entity.type | Publication | |
| oaire.citation.endPage | 21:23 | pt_PT |
| oaire.citation.startPage | 21:1 | pt_PT |
| oaire.citation.title | Proceedings of the 31st Euromicro Conference on Real-Time Systems (ECRTS 2019) | pt_PT |
| oaire.citation.volume | 133 | pt_PT |
| person.familyName | Nelissen | |
| person.givenName | Geoffrey | |
| person.identifier.ciencia-id | E51E-C723-0D77 | |
| person.identifier.orcid | 0000-0003-4141-6718 | |
| person.identifier.scopus-author-id | 41561808600 | |
| rcaap.rights | openAccess | pt_PT |
| rcaap.type | conferenceObject | pt_PT |
| relation.isAuthorOfPublication | e23673cc-6b82-4d9c-94fb-4b4fca051b0d | |
| relation.isAuthorOfPublication.latestForDiscovery | e23673cc-6b82-4d9c-94fb-4b4fca051b0d |