search menu icon-carat-right cmu-wordmark

Segment-Fixed Priority Scheduling for Self-Suspending Real-Time Tasks

August 2016 Technical Report
Junsung Kim, Björn Andersson (Carnegie Mellon University), Dionisio de Niz, Ragunathan (Raj) Rajkumar, Jian-Jia Chen, Wen-Hung Huang, Geoffrey Nelissen

This report describes schedulability analyses and proposes segment-fixed priority scheduling for self-suspending tasks.

Publisher:

Software Engineering Institute

CMU/SEI Report Number

CMU/SEI-2016-TR-002

Abstract

Recent trends in System-on-a-Chip show that an increasing number of special-purpose processors are being added to improve the efficiency of common operations. Unfortunately, the use of these processors may introduce suspension delays incurred by communication, synchronization, and external I/O operations. When these processors are used in real-time systems, conventional schedulability analyses incorporate these delays in the worst-case execution/response time, hence significantly reducing the schedulable utilization.

This report describes schedulability analyses and proposes segment-fixed priority scheduling for self-suspending tasks. We model the tasks as segments of execution separated by suspensions. We start from providing response-time analyses for self-suspending tasks under Rate Monotonic Scheduling (RMS). While RMS is shown to not be optimal, it can be used effectively in some special cases that we have identified. We then derive a utilization bound for the cases as a function of the ratio of the suspension duration to the period of the tasks. For general cases, we develop a segment-fixed priority scheduling scheme. Our scheme assigns individual segments different priorities and phase offsets that are used for phase enforcement to control the unexpected self-suspending nature.