| Jian-Jia Chen, Geoffrey Nelissen, Wen-Hung Huang, Maolin Yang, Björn Brandenburg, Konstantinos Bletsas, Cong Liu, Pascal Richard, Frédéric Ridouard, Neil Audsley, Raj Rajkumar, Dionisio Niz and Georg von der Brüggen.
Many Suspensions, Many Problems: A Review of Self-Suspending Tasks in Real-Time Systems.
Technical Report #854, Department of Computer Science, TU Dortmund
March 2017, (Status: Preprint, 2nd Version) The first version was published in May 2016.
[BibTeX][PDF][Abstract]@techreport { ChenReport854-2016,
author = {Chen, Jian-Jia and Nelissen, Geoffrey and Huang, Wen-Hung and Yang, Maolin and Brandenburg, Bj\"orn and Bletsas, Konstantinos and Liu, Cong and Richard, Pascal and Ridouard, Fr\'ed\'eric and Audsley, Neil and Rajkumar, Raj and Niz, Dionisio and Br\"uggen, Georg von der},
title = {Many Suspensions, Many Problems: A Review of Self-Suspending Tasks in Real-Time Systems},
institution = {Department of Computer Science, TU Dortmund},
year = {2017},
number = {854},
month = {March},
note = { (Status: Preprint, 2nd Version) The first version was published in May 2016.},
keywords = {kevin, Georg},
file = {http://ls12-www.cs.tu-dortmund.de/daes/media/documents/publications/downloads/2017-chen-techreport-854-v2.pdf},
confidential = {n},
abstract = {In general computing systems, a job (process/task) may suspend itself whilst it is waiting for some activity to complete, e.g., an accelerator to return data. % or results from offloaded computation. In real-time systems, such self-suspension can cause substantial performance/schedulability degradation. This observation, first made in 1988, has led to the investigation of the impact of self-suspension on timing predictability, and many relevant results have been published since. Unfortunately, as it has recently come to light, a number of the existing results are flawed.
To provide a correct platform on which future research can be built, this paper reviews the state of the art in the design and analysis of scheduling algorithms and schedulability tests for self-suspending tasks in real-time systems. We provide (1)~a systematic description of how self-suspending tasks can be handled in both soft and hard real-time systems; (2)~an explanation of the existing misconceptions and their potential remedies; (3)~an assessment of the influence of such flawed analyses on partitioned multiprocessor fixed-priority scheduling when tasks synchronize access to shared resources; and (4)~a discussion of the computational complexity of analyses for different self-suspension task models.
},
}
In general computing systems, a job (process/task) may suspend itself whilst it is waiting for some activity to complete, e.g., an accelerator to return data. % or results from offloaded computation. In real-time systems, such self-suspension can cause substantial performance/schedulability degradation. This observation, first made in 1988, has led to the investigation of the impact of self-suspension on timing predictability, and many relevant results have been published since. Unfortunately, as it has recently come to light, a number of the existing results are flawed.
To provide a correct platform on which future research can be built, this paper reviews the state of the art in the design and analysis of scheduling algorithms and schedulability tests for self-suspending tasks in real-time systems. We provide (1) a systematic description of how self-suspending tasks can be handled in both soft and hard real-time systems; (2) an explanation of the existing misconceptions and their potential remedies; (3) an assessment of the influence of such flawed analyses on partitioned multiprocessor fixed-priority scheduling when tasks synchronize access to shared resources; and (4) a discussion of the computational complexity of analyses for different self-suspension task models.
|
| Georg von der Brüggen, Jian-Jia Chen, Robert I. Davis and Wen-Hung Kevin Huang.
Exact Speedup Factors for Linear-Time Schedulability Tests for Fixed-Priority Preemptive and Non-preemptive Scheduling.
Information Processing Letters (IPL) 117, pages 1-5
January 2017
[BibTeX][PDF][Link][Abstract]@article { IPL2017-speedup,
author = {Br\"uggen, Georg von der and Chen, Jian-Jia and Davis, Robert I. and Huang, Wen-Hung Kevin},
title = {Exact Speedup Factors for Linear-Time Schedulability Tests for Fixed-Priority Preemptive and Non-preemptive Scheduling},
journal = {Information Processing Letters (IPL)},
year = {2017},
volume = {117},
pages = {1-5},
month = {Jan},
url = {http://dx.doi.org/10.1016/j.ipl.2016.08.001},
keywords = {kevin, Georg},
file = {http://ls12-www.cs.tu-dortmund.de/daes/media/documents/publications/downloads/2016-IPL-speedup.pdf},
confidential = {n},
abstract = {In this paper, we investigate the quality of several linear-time schedulability tests for preemptive and non-preemptive fixed-priority scheduling of uniprocessor systems. The metric used to assess the quality of these tests is the resource augmentation bound commonly known as the processor speedup factor. The speedup factor of a schedulability test corresponds to the smallest factor by which the processing speed of a uniprocessor needs to be increased such that any task set that is feasible under an optimal preemptive (non-preemptive) work-conserving scheduling algorithm is guaranteed to be schedulable with preemptive (non-preemptive) fixed priority scheduling if this scheduling test is used, assuming an appropriate priority assignment. We show the surprising result that the exact speedup factors for Deadline Monotonic (DM) priority assignment combined with sufficient linear-time schedulability tests for implicit-, constrained-, and arbitrary-deadline task sets are the same as those obtained for optimal priority assignment policies combined with exact schedulability tests. Thus in terms of the speedup-factors required, there is no penalty in using DM priority assignment and simple linear schedulability tests.
},
}
In this paper, we investigate the quality of several linear-time schedulability tests for preemptive and non-preemptive fixed-priority scheduling of uniprocessor systems. The metric used to assess the quality of these tests is the resource augmentation bound commonly known as the processor speedup factor. The speedup factor of a schedulability test corresponds to the smallest factor by which the processing speed of a uniprocessor needs to be increased such that any task set that is feasible under an optimal preemptive (non-preemptive) work-conserving scheduling algorithm is guaranteed to be schedulable with preemptive (non-preemptive) fixed priority scheduling if this scheduling test is used, assuming an appropriate priority assignment. We show the surprising result that the exact speedup factors for Deadline Monotonic (DM) priority assignment combined with sufficient linear-time schedulability tests for implicit-, constrained-, and arbitrary-deadline task sets are the same as those obtained for optimal priority assignment policies combined with exact schedulability tests. Thus in terms of the speedup-factors required, there is no penalty in using DM priority assignment and simple linear schedulability tests.
|
DAES