FOR FREE YEAR SOLVED

Lottery Scheduling

Mode: Preemptive or Non-preemptive

Lottery scheduling is a novel technique proposed for sharing a resource in a probabilistically fair manner. This scheduling policy used in the Unix and Solaris operating systems.

The main idea about lottery scheduling is, give lottery tickets to every process for CPU time (or other resources). At the time of CPU scheduling, a lottery ticket is chosen at random, and process having that ticket (is the winner), get CPU (or other resources) for execution. 

Sometimes more important processes can be given extra tickets; to increase their odds of winning because a process having a higher number of tickets, then obviously it can get more chance to (win) get the CPU for execution. 

For example, a process would be given 30 tickets out of a total of 100 tickets, and then it will get a 30% chance of winning in each lottery. 

It also solves the problem of starvation because a process has at least one lottery ticket.

Example1:

Consider we have three processes P1, P2 and P3 have 30%, 30%, and 40% tickets accordingly. Now we can also assume Total Tickets is 100 and P1 contains ticket number (1-30), P2 contains ticket number (31-60), P3 contains ticket number (61-100).

Now as per lottery scheduling, the scheduler picks the 1 to 100 ticket randomly. 

Here scheduler picks the tick randomly as below:

As per the diagram, we can calculate that among 10 tickets chosen by the scheduler P1 gets chance 2 times (20%), P2 gets chance 4 times (40%) and P3 gets chance 4 times (40%).

But it is also true when the scheduler will choose 100 tickets i.e. for the long term, P1, P2, and P3 will get a chance of 30%, 30%, and 40% accordingly.

Lottery scheduling can be used for Fair share CPU scheduling as follows: 

Tickets can be issued to applications (or users) on the basis of their fair share of CPU time.

Some interesting properties of the Lottery Schedule as below:

1) Ticket Transfer: Cooperating processes may exchange tickets between two of them if they wish.

2) When the scheduler gives certain numbers of tickets to different users where the user may have one or more processes.

Then the user can distribute different numbers of tickets to different processes.

Example: 

There are two groups/User A and B has 2(P1, P2) and 1 process accordingly. 

Let scheduler gives 60 tickets to A and 40 tickets to B. Now at the time of the scheduling user A gives 40 tickets to P1 

and 20 tickets to P2. Whereas user B gives a total of 40 tickets to one process.

3) Ticket inflation: Using this technique process or user can increase or decrease their tickets for a temporary situation. 

Application of Lottery Scheduling

Lottery scheduling can be used to solve problems that are difficult to handle with other methods. One example is a video server in which several processes are feeding video streams to their clients but at different frame rates. 

Suppose that the processes need frames at 10, 20, and 25 frames/sec. By allocating these processes 10, 20, and 25 tickets, respectively, they will automatically divide the CPU in approximately the correct proportion, that is, 10: 20: 25.