On the Evaluation of Schedulability Tests for Real-Time Scheduling Algorithms

TY - CONF

T1 - On the Evaluation of Schedulability Tests for Real-Time Scheduling Algorithms

AU - Davis, Robert Ian

PY - 2016/7

Y1 - 2016/7

N2 - This short paper discusses the criteria and methods that can be used to evaluate the performance of schedulability tests for real-time scheduling algorithms. We summarize the different theoretical and empirical methods that can be used and outline their advantages and disadvantages. The main focus of the paper is on empirical techniques. Here we set out some of the potential pitfalls, and describe a defacto standard approach based on visualizing results using success ratio and weighted schedulability plots. We discuss how these can be augmented using other graphs such as difference plots and frequency distributions for breakdown utilization. For more complex task models, we note that a consistent set of parameters can be obtained from benchmarks, and we show how a moderate number of benchmarks can be used to produce a large number of related task sets with a variety of utilization levels suitable for use in empirical evaluation. Finally, we remark on the dearth of real-time benchmarks, and call for morebenchmarks or benchmark generators to be developed in conjunction with industry. This paper accompanies an invited talk given at the WATERS workshop in 2016.

AB - This short paper discusses the criteria and methods that can be used to evaluate the performance of schedulability tests for real-time scheduling algorithms. We summarize the different theoretical and empirical methods that can be used and outline their advantages and disadvantages. The main focus of the paper is on empirical techniques. Here we set out some of the potential pitfalls, and describe a defacto standard approach based on visualizing results using success ratio and weighted schedulability plots. We discuss how these can be augmented using other graphs such as difference plots and frequency distributions for breakdown utilization. For more complex task models, we note that a consistent set of parameters can be obtained from benchmarks, and we show how a moderate number of benchmarks can be used to produce a large number of related task sets with a variety of utilization levels suitable for use in empirical evaluation. Finally, we remark on the dearth of real-time benchmarks, and call for morebenchmarks or benchmark generators to be developed in conjunction with industry. This paper accompanies an invited talk given at the WATERS workshop in 2016.

KW - real-time

KW - scheduling

KW - schedulability tests

KW - evaluation

UR - https://www-users.cs.york.ac.uk/~robdavis/

UR - https://www-users.cs.york.ac.uk/~robdavis/papers/WATERS2016EvalSchedTests.pdf

UR - https://www-users.cs.york.ac.uk/~robdavis/papers/WATERS2016EvalSchedTestsPresentation.pdf

M3 - Paper

T2 - International Workshop on Analysis Tools and Methodologies for Embedded and Real-time Systems (WATERS)

Y2 - 5 July 2016

ER -