Implementation

This lesson describes​ the simple implementation of lottery scheduling.

Probably the most amazing thing about lottery scheduling is the simplicity of its implementation. All you need is a good random number generator to pick the winning ticket, a data structure to track the processes​ of the system (e.g., a list), and the total number of tickets.

Let’s assume we keep the processes in a list. Here is an example of three processes, A, B, and C, each with some number of tickets.

To make a scheduling decision, we first have to pick a random number (the winner) from the total number of tickets (400)Surprisingly, as pointed out by Bjo ̈ rn Lindberg, this can be challenging to do correctly; for more details, see http://stackoverflow.com/questions/2509679/ how-to-generate-a-random-number-from-within-a-range. Let’s say we pick the number 300. Then, we simply traverse the list, with a simple counter used to help us find the winner. Have a look at the code below:

Press + to interact
// counter: used to track if we’ve found the winner yet
int counter = 0;
// winner: use some call to a random number generator to
//         get a value, between 0 and the total # of tickets
int winner = getrandom(0, totaltickets);
// current: use this to walk through the list of jobs
node_t *current = head;
while (current) {
  counter = counter + current->tickets;
  if (counter > winner)
      break; // found the winner
  current = current->next;
}
// ’current’ is the winner: schedule it...
}

The code walks the list of processes, adding each ticket value to counter until the value exceeds winner. Once that is the case, the current list element is the winner. With our example of the winning ticket being 300, the following takes place. First, counter is incremented to 100 to account for A’s tickets; because 100 is less than 300, the loop continues. Then counter would be updated to 150 (B’s tickets), still less than 300 and thus again we continue. Finally, counter is updated to 400 (clearly greater than 300), and thus we break out of the loop with current pointing at C (the winner).

To make this process the most efficient, it might generally be best to organize the list in sorted order, from the highest number of tickets to the lowest. The ordering does not affect the correctness of the algorithm; however, it does ensure in general that the fewest number of list iterations are taken, especially if there are a few processes that possess most of the tickets.

Get hands-on with 1400+ tech skills courses.