Lottery Scheduling Example

Lottery Scheduling Example: Process scheduling of the lottery variety is slightly unique from normal scheduling. Random scheduling is used for scheduling processes. Preemptive or non-preemptive lottery scheduling are both options. Additionally, it addresses the issue of famine. Each method will have a non-zero probability of getting chosen at each scheduling operation if at least one lottery ticket is given to it. GeeksForGeeks has written a good post on Lottery Scheduling Example.

Lottery Scheduling Example
Lottery Scheduling Example

Every process in this scheduling has a number of tickets, and the scheduler chooses one at random. The process holding that ticket is the winner. It is run for a time slice before the scheduler chooses another ticket. These tickets stand in for the processes’ share. More tickets is directly proportional to being selected for execution.

Lottery Scheduling Example

If out of a total of 100 tickets, two processes, A and B, each have 60 and 40 tickets, respectively. A has a 60% CPU share, while B has a 40% CPU share. The calculation of these shares is probabilistic rather than deterministic.

Lotter Scheduling Explanation

  • A and B are the two methods we use. A has 60 tickets (numbered 1 through 60), while B has 40 tickets (ticket no. 61 to 100).
  • The scheduler chooses a random number between 1 and 100. A is executed if the selected number is between 1 and 60; else, B is executed.

An illustration of 10 tickets chosen by Scheduler would resemble this:
Ticket number – 73 82 23 45 32 87 49 39 12 09.
Resulting Schedule – B B A A A B A A A A.
B executes just once.A executes seven times. As you can see, A uses 70% of the CPU while B uses 30%, which is not what we require as A needs to use 60% of the CPU while B needs to use 40%. This occurs as a result of the probabilistic calculation of shares, but over the long term (i.e., when more than 100 or 1000 tickets are chosen), we may attain a share percentage of around 60 and 40 for A and B, respectively.

Lottery Scheduling Implementation

Let’s say we have 3 Processes A, B, C. Job A has 100 Tickets, Job B has 50 and Job C has 250

// 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;

 // loop until the sum of ticket values is > the winner
 while (current) {
 counter = counter + current->tickets;
 if (counter > winner)
 break; // found the winner
 current = current->next;
 }
 // ’current’ is the winner: schedule it...



READ MORE

Network Security related posts Visit HERE

Python-related posts Visit HERE

Data Structures related posts visit HERE

C/C++ related posts Visit HERE

Databases related posts Visit HERE

Algorithms related posts visit HERE

Data Science related posts visit HERE

Share the Knowledge

Leave a Comment