An Exact Schedulability Test for Non-Preemptive Self-Suspending Real-Time Tasks

Beyazit Yalcinkaya, Mitra Nasri, Björn B. Brandenburg

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

25 Citations (Scopus)
141 Downloads (Pure)

Abstract

Exact schedulability analysis of limited-preemptive (or non-preemptive) real-time workloads with variable execution costs and release jitter is a notoriously difficult challenge due to the scheduling anomalies inherent in non-preemptive execution. Furthermore, the presence of self-suspending tasks is well-understood to add tremendous complications to an already difficult problem. By mapping the schedulability problem to the reachability problem in timed automata (TA), this paper provides the first exact schedulability test for this challenging model. Specifically, using TA extensions available in UPPAAL, this paper presents an exact schedulability test for sets of periodic and sporadic self-suspending tasks with fixed preemption points that are scheduled upon a multiprocessor under a global fixed-priority scheduling policy. To the best of our knowledge, this is the first exact schedulability test for non- and limited-preemptive self-suspending tasks (for both uniprocessor and multiprocessor systems), and thus also the first exact schedulability test for the special case of global non-preemptive fixed-priority scheduling (for either periodic or sporadic tasks). Additionally, the paper highlights some subtle pitfalls and limitations in existing TA-based schedulability tests for non-preemptive workloads.

Original languageEnglish
Title of host publication2019 Design, Automation & Test in Europe Conference & Exhibition (DATE)
Subtitle of host publicationPorceedings
PublisherIEEE
Pages1228-1233
Number of pages6
ISBN (Electronic)978-3-9819263-2-3
ISBN (Print)978-1-7281-0331-0
DOIs
Publication statusPublished - 2019
Event22nd Design, Automation and Test in Europe Conference and Exhibition, DATE 2019 - Florence, Italy
Duration: 25 Mar 201929 Mar 2019

Conference

Conference22nd Design, Automation and Test in Europe Conference and Exhibition, DATE 2019
Country/TerritoryItaly
CityFlorence
Period25/03/1929/03/19

Bibliographical note

Accepted author manuscript

Fingerprint

Dive into the research topics of 'An Exact Schedulability Test for Non-Preemptive Self-Suspending Real-Time Tasks'. Together they form a unique fingerprint.

Cite this