[plt-scheme] Scheduling fairness

From: Chris Uzdavinis (chris at atdesk.com)
Date: Wed May 13 13:15:05 EDT 2009

"Paulo J. Matos" <pocmatos at gmail.com> writes:

> Hi all,
> I have a simple scheduler, which has a list of function, all of which
> receive a single argument, a state structure and throughout the
> execution of my program I have to run this functions in a 'fair' way,
> meaning that they should all be ran the same amount of times when the
> program has been running 'long enough' but they are also ran in a
> random order. If I choose the procedure to execute at a given time by
> generating a random number and then selecting the one on the nth
> position of the list to be executed, will it be fair or is there a
> better way?

If you only judge fairness by counting the number of invocations, then
your algorithm will be approximately fair, depending on your RNG.
However, even with a perfectly fair RNG, it could still pick some
functions more frequently than others, distorting the distribution,
though with a large enough number of samples the distribution will be
pretty smooth.  However, a poor RNG may be biased and be significantly
less fair, even in the long run.

A more deterministic algorithm would be to simply iterate through your
list and call them in order.  You can shuffle the list or not, it
shouldn't make a difference in the long run.  (Any ordering could have
resulted from a random shuffle, including the original order of the
objects in the list!)  This approach ensures that all functions are
called before any is ever called again.


Posted on the users mailing list.