Question

Q) Design a new Lottery CPU-scheduler. It must include details of any modifications you want to make to existing functions, methods, algorithms, formulae, and data structures. and where each addition will take place in. It must also include the same detailed description of any additional code. In the design document you should include how your algorithm distinguishes CPU-bound from I/O-bound, and user from system processes, how you designed it to prevent starvation, and how you think it will improve the responsiveness of the system.

Answer 1

Operating System | Lottery Process Scheduling

Prerequisite – CPU Scheduling, Process Management
Lottery Scheduling is type of process scheduling, somewhat different from other Scheduling. Processes are scheduled in a random manner. Lottery scheduling can be preemptive or non-preemptive. It also solves the problem of starvation. Giving each process at least one lottery ticket guarantees that it has non-zero probability of being selected at each scheduling operation.

In this scheduling every process have some tickets and scheduler picks a random ticket and process having that ticket is the winner and it is executed for a time slice and then another ticket is picked by the scheduler. These tickets represent the share of processes. A process having a higher number of tickets give it more chance to get chosen for execution.

Example – If we have two processes A and B having 60 and 40 tickets respectively out of total 100 tickets. CPU share of A is 60% and that of B is 40%.These shares are calculated probabilistically and not deterministically.

Explanation –

1. We have two processes A and B. A has 60 tickets (ticket number 1 to 60) and B have 40 tickets (ticket no. 61 to 100).
2. Scheduler picks a random number from 1 to 100. If the picked no. is from 1 to 60 then A is executed otherwise B is executed.
3. An example of 10 tickets picked by Scheduler may look like 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.
   

4. A is executed 7 times and B is executed 3 times. As you can see that A takes 70% of CPU and B takes 30% which is not the same as what we need as we need A to have 60% of CPU and B should have 40% of CPU.This happens because shares are calculated probabilistically but in a long run(i.e when no. of tickets picked is more than 100 or 1000) we can achieve a share percentage of approx. 60 and 40 for A and B respectively.

   Ways to manipulate tickets –

5. Ticket Currency –
   Scheduler give a certain number of tickets to different users in a currency and users can give it to there processes in a different currency. E.g. Two users A and B are given 100 and 200 tickets respectively. User A is running two process and give 50 tickets to each in A’s own currency. B is running 1 process and gives it all 200 tickets in B’s currency. Now at the time of scheduling tickets of each process are converted into global currency i.e A’s process will have 50 tickets each and B’s process will have 200 tickets and scheduling is done on this basis.
6. Transfer Tickets –
   A process can pass its tickets to another process.
7. Ticket inflation –
   With this technique a process can temporarily raise or lower the number of tickets it own.

References –
Lottery scheduling – Wikipedia
eecs.berkeley.edu