Precautious-RM: A predictable non-preemptive scheduling algorithm for harmonic tasks

Mitra Nasri, Mehdi Kargahi

Research output: Contribution to journalArticleAcademicpeer-review

21 Citations (Scopus)

Abstract

A major requirement of many real-time embedded systems is to have time-predictable interaction with the environment. More specifically, they need fixed or small sampling and I/O delays, and they cannot cope with large delay jitters. Non-preemptive execution is a known method to reduce the latter delay; however, the corresponding scheduling problem is NP-Hard for periodic tasks. In this paper, we present Precautious-RM as a predictable linear-time online non-preemptive scheduling algorithm for harmonic tasks which can also deal with the former delay, namely sampling delay. We derive conditions of optimality of Precautious-RM and show that satisfying those conditions, tight bounds for best- and worst-case response times of the tasks can be calculated in polynomial-time. More importantly, response time jitter of the tasks is analyzed and it is proven that under specific conditions, each task has either one or two values for response time, which leads to improving the predictability of the system interaction with the environment. Simulation results demonstrate efficiency of Precautious-RM in increasing accuracy of control applications.

Original languageEnglish
Pages (from-to)548-584
Number of pages37
JournalReal-Time Systems
Volume50
Issue number4
DOIs
Publication statusPublished - Jul 2014
Externally publishedYes

Keywords

  • Accuracy enhancement
  • Control applications
  • Delay and jitter
  • Harmonic tasks
  • Non-preemptive scheduling
  • Real-time systems

Fingerprint

Dive into the research topics of 'Precautious-RM: A predictable non-preemptive scheduling algorithm for harmonic tasks'. Together they form a unique fingerprint.

Cite this