[plt-scheme] Scheduling fairness

"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.

-- 
Chris