
Introduction
Operating System forms the backbone of any coding interview. Thus it's very important to have a good grasp of this topic. But don't you worry about any of it. Ninjas are here for you, and today we will be going to discuss ‘Lottery Process Scheduling.’
Also see: Multiprogramming vs Multitasking and Open Source Operating System.
CPU Scheduling
CPU Scheduling is the process of choosing which process will have exclusive use of the CPU while another is waiting. When the CPU is idle, the OS selects at least one of the programs in the ready queue to run.
Lottery Process Scheduling
Lottery Process Scheduling is a sort of process scheduling that is distinct from the rest. The scheduling of processes is done at random. Preemptive or non-preemptive lottery scheduling is possible. It also addresses the issue of hunger. Giving each process at least one lottery ticket ensures that it will be chosen at some point during the scheduling process.
Every process in this scheduling has several tickets, and the scheduler selects one at random. The process with that ticket is the winner, and it is executed for a time slice, before the scheduler selects another ticket. The share of processes is represented by these tickets. A process with a higher number of tickets has a better chance of being selected for execution. Now lets see an example of Lottery Process Scheduling.
Example
If we have two processes A and B, each with 60 and 40 tickets out of a total of 100, A has a 60% CPU share, while B has a 40% CPU share. These percentages are calculated in a probabilistic rather than deterministic manner.
Explanation
- A and B are the two processes we have. A has 60 tickets (from 1 to 60), while B has 40 tickets (ticket no. 61 to 100).
- The scheduler chooses a number between 1 and 100 at random. If the chosen number is between 1 and 60, A is executed; otherwise, B is executed.
- The table will look like
Ticket number - 73 82 23 45 32 87 49 39 12 09. |
Resulting Schedule - B B A A A B A A A A. |
- A is performed seven times, while B is performed three times. As you can see, A consumes 70% of the CPU while B consumes 30%, which is not the same as what we require: A should consume 60% of the CPU while B should consume 40%. This occurs because shares are calculated probabilistically, but over time (i.e., when the number of tickets chosen exceeds 100 or 1000), we can attain a share percentage of roughly 60 and 40 for A and B, respectively.
Ways to manipulate tickets
Ticket Currency - The scheduler assigns a set number of tickets in one currency to each user, who can then deliver them to their processes in another currency. For example, two users A and B are each granted 100 and 200 tickets. User A is running two processes and handing out 50 tickets in A's own currency to each. B is running a single process and is giving out 200 tickets in his own currency. The tickets for each process are now translated into global currency at the time of scheduling, i.e., A's process will have 50 tickets, and B's process will have 200 tickets, and scheduling is done on this basis.
Ticket Transfer - A process can transfer its tickets to another process.
Inflation of tickets
A process can use this technique to temporarily increase or decrease the amount of tickets it owns.
Drawback
The lottery process scheduling algorithm has the disadvantage of being fundamentally unexpected. Due to the random nature of the scheduler, OS designers have no way of knowing what will happen in lottery scheduling, which could result in unpleasant outcomes.