Schedulability Analysis of Task Sets with Upper and Lowerbound Temporal Constraints

TitleSchedulability Analysis of Task Sets with Upper and Lowerbound Temporal Constraints
Publication TypeJournal Article
Year of Publication2014
AuthorsGombolay, M. C., and J. A. Shah
JournalJournal of Aerospace Information Systems (JAIS)
KeywordsReal-Time Systems, Schedulability Analysis, Scheduling
Abstract

Increasingly real-time systems must handle the self-suspension of tasks, i.e. lowerbound wait times between subtasks, in a timely and predictable manner. A fast schedulability test that does not signi cantly overestimate the temporal resources needed to execute self-suspending task sets would be of bene t to these modern computing systems. In this paper, we present a polynomial-time test that, to our knowledge, is the rst to handle non-preemptive, self-suspending tasks sets with hard deadlines, where each task has any number of self-suspensions. To construct our test, we leverage a novel priority scheduling policy, jth Subtask First (JSF), which restricts the behavior of the self-suspending model to provide an analytical basis for an informative schedulability test. In general, the problem of sequencing according to both upperbound and lowerbound temporal constraints requires an idling scheduling policy and is known to be NP-Hard. However we empirically validate the tightness of our schedulability test and scheduling algorithm, and show that the processor is able to e ectively utilize up to 95% of the self-suspension time to execute tasks.

URLhttp://interactive.mit.edu/sites/default/files/documents/JAIS_Gombolay_Shah_with_Hyperlinks.pdf
DOI10.2514/1.I010202