search menu icon-carat-right cmu-wordmark

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

Technical Report
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
DOI (Digital Object Identifier)
10.1184/R1/6583718.v1

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.

Cite This Technical Report

Kim, J., Andersson, B., de Niz, D., Rajkumar, R., Chen, J., Huang, W., & Nelissen, G. (2016, August 18). Segment-Fixed Priority Scheduling for Self-Suspending Real-Time Tasks. (Technical Report CMU/SEI-2016-TR-002). Retrieved March 4, 2024, from https://doi.org/10.1184/R1/6583718.v1.

@techreport{kim_2016,
author={Kim, Junsung and Andersson, Bjorn and de Niz, Dionisio and Rajkumar, Ragunathan (Raj) and Chen, Jian-Jia and Huang, Wen-Hung and Nelissen, Geoffrey},
title={Segment-Fixed Priority Scheduling for Self-Suspending Real-Time Tasks},
month={Aug},
year={2016},
number={CMU/SEI-2016-TR-002},
howpublished={Carnegie Mellon University, Software Engineering Institute's Digital Library},
url={https://doi.org/10.1184/R1/6583718.v1},
note={Accessed: 2024-Mar-4}
}

Kim, Junsung, Bjorn Andersson, Dionisio de Niz, Ragunathan (Raj) Rajkumar, Jian-Jia Chen, Wen-Hung Huang, and Geoffrey Nelissen. "Segment-Fixed Priority Scheduling for Self-Suspending Real-Time Tasks." (CMU/SEI-2016-TR-002). Carnegie Mellon University, Software Engineering Institute's Digital Library. Software Engineering Institute, August 18, 2016. https://doi.org/10.1184/R1/6583718.v1.

J. Kim, B. Andersson, D. de Niz, R. Rajkumar, J. Chen, W. Huang, and G. Nelissen, "Segment-Fixed Priority Scheduling for Self-Suspending Real-Time Tasks," Carnegie Mellon University, Software Engineering Institute's Digital Library. Software Engineering Institute, Technical Report CMU/SEI-2016-TR-002, 18-Aug-2016 [Online]. Available: https://doi.org/10.1184/R1/6583718.v1. [Accessed: 4-Mar-2024].

Kim, Junsung, Bjorn Andersson, Dionisio de Niz, Ragunathan (Raj) Rajkumar, Jian-Jia Chen, Wen-Hung Huang, and Geoffrey Nelissen. "Segment-Fixed Priority Scheduling for Self-Suspending Real-Time Tasks." (Technical Report CMU/SEI-2016-TR-002). Carnegie Mellon University, Software Engineering Institute's Digital Library, Software Engineering Institute, 18 Aug. 2016. https://doi.org/10.1184/R1/6583718.v1. Accessed 4 Mar. 2024.

Kim, Junsung; Andersson, Bjorn; de Niz, Dionisio; Rajkumar, Ragunathan (Raj); Chen, Jian-Jia; Huang, Wen-Hung; & Nelissen, Geoffrey. Segment-Fixed Priority Scheduling for Self-Suspending Real-Time Tasks. CMU/SEI-2016-TR-002. Software Engineering Institute. 2016. https://doi.org/10.1184/R1/6583718.v1