An Example

Unfairness metric

To make the dynamics of lottery scheduling more understandable, we now perform a brief study of the completion time of two jobs competing against one another, each with the same number of tickets (100) and the ​same run time ($R$, which we will vary).

In this scenario, we’d like for each job to finish at roughly the same time, but due to the randomness of lottery scheduling, sometimes one job finishes before the other. To quantify this difference, we define a simple unfairness metric, $U$ which is simply the time the first job completes divided by the time that the second job completes. For example, if $R = 10$, and the first job finishes at time 10 (and the second job at 20), $U = \frac {10}{20} =0.5$. When both jobs finish at nearly the same time, $U$ will be 20 quite close to 1. In this scenario, that is our goal: a perfectly fair scheduler would achieve $U = 1$.

The figure below plots the average unfairness as the length of the two jobs ($R$) is varied from 1 to 1000 over thirty trials (results are generated via the simulator provided at the end of the chapter).