Generating Utilization Vectors for the Systematic Evaluation of Schedulability Tests

Research output: Chapter in Book/Report/Conference proceedingConference contribution


—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 and
quality 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
Original languageEnglish
Title of host publication2020 IEEE Real-Time Systems Symposium (proceedings)
Number of pages13
Publication statusPublished - 1 Dec 2020
Event2020 IEEE Real-Time Systems Symposium - Virtual
Duration: 1 Dec 20204 Dec 2020


Conference2020 IEEE Real-Time Systems Symposium
Abbreviated titleRTSS 2020
Internet address

Bibliographical note

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.


  • real-time systems
  • utilization vector generation
  • unbiased distribution
  • UUnifast
  • RandFixedSum

Cite this