Generating Utilization Vectors for the Systematic Evaluation of Schedulability Tests

TY - GEN

T1 - Generating Utilization Vectors for the Systematic Evaluation of Schedulability Tests

AU - Griffin, David Jack

AU - Bate, Iain John

AU - Davis, Robert Ian

N1 - This is an author-produced version of the published paper. Uploaded in accordance with the publisher’s self-archiving policy. Further copying may not be permitted; contact the publisher for details.

PY - 2020/12/1

Y1 - 2020/12/1

N2 - —This paper introduces the Dirichlet-Rescale (DRS) algorithm. The DRS algorithm provides an efficient general-purpose method of generating n-dimensional vectors of components (e.g. task utilizations), where the components sum to a specified total, each component conforms to individual constraints on the maximum and minimum values that it can take, and the vectors are uniformly distributed over the valid region of the domain of all possible vectors, bounded by the constraints. The DRS algorithm can be used to improve the nuance andquality of empirical studies into the effectiveness of schedulability tests for real-time systems; potentially making them more realistic, and leading to new conclusions. It is efficient enough for use in large-scale studies where millions of task sets need to be generated. Further, the constraints on individual task utilizations can be used for fine-grained control of task set parameters enabling more detailed exploration of schedulability test behavior. Finally, the real power of the algorithm lies in the fact that it can be applied recursively, with one vector acting as a set of constraints for the next. This is particularly useful in task set generation for mixed criticality systems and multi-core systems, where task utilizations are either multi-valued or can be decomposed into multiple constituent parts

AB - —This paper introduces the Dirichlet-Rescale (DRS) algorithm. The DRS algorithm provides an efficient general-purpose method of generating n-dimensional vectors of components (e.g. task utilizations), where the components sum to a specified total, each component conforms to individual constraints on the maximum and minimum values that it can take, and the vectors are uniformly distributed over the valid region of the domain of all possible vectors, bounded by the constraints. The DRS algorithm can be used to improve the nuance andquality of empirical studies into the effectiveness of schedulability tests for real-time systems; potentially making them more realistic, and leading to new conclusions. It is efficient enough for use in large-scale studies where millions of task sets need to be generated. Further, the constraints on individual task utilizations can be used for fine-grained control of task set parameters enabling more detailed exploration of schedulability test behavior. Finally, the real power of the algorithm lies in the fact that it can be applied recursively, with one vector acting as a set of constraints for the next. This is particularly useful in task set generation for mixed criticality systems and multi-core systems, where task utilizations are either multi-valued or can be decomposed into multiple constituent parts

KW - real-time systems

KW - utilization vector generation

KW - unbiased distribution

KW - UUnifast

KW - RandFixedSum

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

M3 - Conference contribution

BT - 2020 IEEE Real-Time Systems Symposium (proceedings)

T2 - 2020 IEEE Real-Time Systems Symposium

Y2 - 1 December 2020 through 4 December 2020

ER -