The Dirichlet Rescale (DRS) algorithm: a general-purpose method underpinning synthetic task set generation

Generating utilization vectors

The real-time systems research literature is full of papers on scheduling policies and schedulability analyses, covering a wide variety of different task and systems models, and analysis methods. There is however one key aspect that the vast majority of these works have in common, and that is the need for a systematic empirical evaluation of the effectiveness of the proposed schedulability tests. This requires a method of synthesizing large numbers of task sets to which the schedulability tests can be applied. Further, the parameters of these task sets must cover in an unbiased way, the range of possible task sets that could potentially occur in practice, otherwise the validity of the empirical evaluation and its conclusions could be undermined, and may not be valid.

Underpinning synthetic task set generation is the problem of generating vectors of individual task utilization values, where utilization is a measure of the amount of bandwidth of a particular (processing) resource that a task uses. It is essential that the generation of utilization vectors is unbiased, in other words the vectors produced are uniformly distributed within the domain of all such vectors, otherwise bias could be created in the empirical evaluation. Generating unbiased utilization vectors is, however, not straightforward and unfortunately almost all of the early research into scheduling and schedulability analysis for real-time systems used simple but naïve methods that can result in bias.

UUnifast

The problem of unbiased utilization vector generation for tasks with a single execution parameter (i.e. a single utilization value) running on uniprocessors has been efficiently solved by the UUnifast algorithm. UUnifast(n, U) outputs a vector of n individual utilization values that sum to the total utilization required U, with each component value constrained to be within the range 0 to U.

RandFixedSum

For multiprocessor systems, UUnifast cannot be directly applied, since the total required utilization may be as much as m (the number of processors), while the utilization of a valid task cannot exceed 1. The RandFixedSum algorithm efficiently solves this problem. RandFixedSum(n, U, ub, lb) outputs a vector of n individual utilization values that sum to U, with each component value in the range lb to ub, where the lower bound lb is usually set to 0, and the upper bound ub to 1. Thus, RandFixedSum support symmetric constraints that are applied to every component in the output vector.

Dirichlet Rescale (DRS)

The natural generalization of the problem is to support asymmetric constraints, in other words to cater for individual upper and lower bounds on the value of each individual component in the output vector. The Dirichlet Rescale or DRS algorithm efficiently solves this problem. DRS(n, U, ub, lb)) outputs a vector of n individual utilization values that sum to U, with each individual component value in the range given by the corresponding components of the upper bound and lower bound vectors ub and lb.

Use Cases

The DRS algorithm has a plethora of uses in synthetic task set generation, supporting a wide variety of different task models. As a very simple example of its use, consider generating synthetic task sets for a specific application domain using a multicore system. For the purposes of this example, each task set is required to have 4 heavy tasks with utilizations in the range [0.5, 0.9], and 20 light tasks with utilization in the range [0.01, 0.25], and a total utilization of 3.5. The DRS algorithm can be directly used to generate vectors of utilization values that conform to these requirements and are unbiased (i.e. uniformly distributed within the valid region of all possible vectors that are compliant with the constraints).

The real power of the DRS algorithm, however, comes via its recursive or iterative use in modelling tasks that have more than one execution parameter (i.e. more than one utilization value). Examples include: typical and worst-case execution times, mixed criticality systems with high and low criticality execution times, the predictable execution model where task execution is divided into read-execute-write phases, self-suspending tasks that have execution and suspension phases, and tasks that have resource locking times or non-preemptable regions. Further examples include tasks models where the utilization of each task is made up of multiple parts, for example in multicore systems where overall execution times are composed of CPU demand, bus demand, memory demand, etc.

As an example of its use on task models with more than one execution parameter, consider the use of the DRS algorithm to generate typical and worst-case utilization values. First, DRS is called to generate a vector uw of worst-case utilization values that sum to the total worst-case utilization UW required. Then uw is passed to a second call of DRS as a vector of upper bounds, and used in the generation of a vector ut of typical utilization values that sum to the total typical utilization UT required (with UT < UW ). The result is that each component of ut is no greater than the corresponding component of uw, the components of ut sum to UT, the components of uw sum to UW, and the distribution of utilization vectors produced is unbiased.

Python open source implementation

The DRS algorithm can be used as a more general-purpose replacement for existing approaches, such as UUnifast and RandFixedSum. The DRS algorithm supports efficient utilization vector generation up to dimensionality of 100, and up to 200 with a commensurate slowdown in performance. The Python source code is publicly available and permanently archived, with the latest version always available. It can be installed via: pip install drs from here, and includes a C library enabling the DRS algorithm in Python to be called directly from any language that supports calling C ABI functions, for example C/C++, Java, Ruby, Rust, Ada, and Matlab.

Find out more

For more information on the DRS algorithm, see the RTSS 2020 paper, “Generating Utilization Vectors for the Systematic Evaluation of Schedulability Tests”, which is freely available from the authors’ institutional repository, along with a narrated video presentation on YouTube.

We believe that work on scheduling and schedulability analysis for real-time systems can benefit from using the DRS algorithm, and we hope that researchers in our community will make good use of the open source implementation provided.

Rob Davis (on behalf of the authors: David Griffin, Iain Bate, and Robert Davis)

Robert Davis is a Reader in the Real-Time Systems Research Group at the University of York, UK. His research interests include scheduling algorithms and analysis for single processor, multiprocessor, and networked real-time systems. Robert has also been involved in founding three start-up companies, all of which succeeded in transferring real-time systems research into commercial products.

Disclaimer: Any views or opinions represented in this blog are personal, belong solely to the blog post authors and do not represent those of ACM SIGBED or its parent organization, ACM.