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

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

Research output: Contribution to conferencePaperAcademic

4 Citations (Scopus)

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
Pages1228-1233
Number of pages6
DOIs
Publication statusPublished - 14 May 2019
Externally publishedYes

Bibliographical note

DBLP's bibliographic metadata records provided through http://dblp.org/search/publ/api are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.

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