Operating System - Lottery Process Scheduling

---

---

In a multiprogramming environment, CPU scheduling algorithms are strategies that decide which process in the ready queue should execute next. Unlike the conventional scheduling algorithms that try to optimize the turnaround time or waiting time, lottery process scheduling aims to give each process a certain percentage of CPU time.

What is Lottery Process Scheduling?

Lottery process scheduling follows a probabilistic scheduling approach. The scheduler distributes tickets to the processes in the system which are allotted CPU time through lottery. The tickets may or may not be distributed uniformly. If a process possesses more tickets, it has a relatively higher probability of selection. Thus a process with more tickets has higher priority. In order to give equal priorities to all the processes, the scheduler distributes equal number of tickets to them.

This scheduling is also referred as a proportional-share scheduling and fair-share scheduling.

Working Principle of Lottery Process Scheduling

Lottery process scheduling has the following steps of implementation −

• Ticket Distribution − Initially, each process in the system is assigned some number of lottery tickets. Each ticket has a unique number and the total number of tickets distributed in the system is always the same.
• Lottery − The scheduler conducts lottery by drawing a random ticket. Generally, a random number generator is used that generates one ticket number among all the ticket numbers distributed in the system.
• Scheduling and Execution − The process having the winning ticket number is selected for execution in the next time slot. The selected process either runs to completion or to the end of the time slot whichever is smaller. If no process possesses the winning ticket, the lottery is done again.
• Ticket Adjustment − After all the processes which were allotted the tickets have run into completion, the scheduler wraps ups the present execution. If new processes arrive in the system, the scheduler restarts the procedure all over.

Manipulating tickets in Lottery Process Scheduling Algorithm

The lottery tickets are typically manipulated based on the priority of each process. Higher-priority processes are assigned more tickets than lower-priority processes, increasing their chances of being selected for execution. However, there are a few different ways to manipulate tickets in lottery scheduling −

Static Distribution

The number of tickets assigned to each process in this method is fixed and does not change over time. For instance, a process with a higher priority may be assigned 100 tickets. On the other hand, a process with a lower priority may be assigned only 10 tickets. This method is simple to implement, but it may not result in the most efficient or equitable resource distribution.

Dynamic Distribution

In this method, the total amount of tickets allocated to each process may fluctuate over time according to the system's behaviour. For example, if a strong-priority process is taking up materials and starving other operations, its ticket count may be minimized to give other procedures an increased likelihood of being selected. Although this technique has a greater computation overhead, it may result in more effective and equal resource allocation.

Weighted Distribution

In this method, the total amount of tickets designated to each process is determined by factors other than its priority. Other factors, which include the quantity of processing power it has already consumed, also play a role. Despite having the same priority, an operation that consumed a lot of processing power may be allocated a lesser number of tickets than a procedure that has employed very little CPU time. This approach can be difficult to put in place, but it can help prevent processes from monopolizing resources.

Example of Lottery Process Scheduling

Let us consider a situation where there are three processes, P0, P1 and P2 and the scheduler have distributed a total of 100 lottery tickets to them, as shown in the first two columns of the following table −

In the third column, we have calculated the proportion of tickets allotted to each process.

Consider that the lottery scheduler generates the following ticket numbers for the first 25 draws −

12, 34, 78, 55, 01, 23, 44, 54, 64, 94, 29, 89, 05, 36, 76, 62, 22, 32, 42, 51, 73, 85, 18, 81, 25

The resulting schedule will be −

P0, P1, P2, P2, P0, P1, P0, P2, P2, P2, P1, P2, P0, P1, P2, P2, P1, P1, P0, P2, P2, P2, P1, P2, P1

The percentage share of a process is calculated as −

$$\mathrm{ProportionalShare_{PX} \: = \: \frac{No. \: of \: Winning \: Draws \: by \: PX}{Total \: Number \: of \: Draws} \: \times \: 100}$$

Using this formula, we get the proportional share of each process as −

$$\mathrm{ProportionalShare_{P0} \: = \: \frac{5}{25} \: \times \: 100 \: = \: 20 \%}$$

$$\mathrm{ProportionalShare_{P1} \: = \: \frac{8}{25} \: \times \: 100 \: = \: 32 \%}$$

$$\mathrm{ProportionalShare_{P2} \: = \: \frac{12}{25} \: \times \: 100 \: = \: 48 \%}$$

We can observe that the proportional shares of CPU time of the processes are quite near to the proportion of tickets allotted to them. The values reach near perfection as the number of draws increases.

Advantages of Lottery Process Scheduling

• Lottery process scheduling is a fair scheduling algorithm. Each process has a probability of getting CPU time.
• As each process has a possibility of being selected, starvation is effectively avoided by this approach.
• It is adaptive to different operating system environments. It works well in real-time systems multi-processor systems etc.
• By using various distribution mechanisms, the method can be adjusted dynamically for various system requirements like assigning priorities etc.
• It can be implemented easily since we dont need to go through elaborate procedure to predict the burst times of processes.

Disadvantages of Lottery Process Scheduling

• Lottery process scheduling has an additional overhead of assigning lottery tickets to processes and also drawing lottery.
• The performance depends upon the random number generator. If the generator is biased or generates repetitive numbers, the scheduling fails. On the other side, a good generator requires more CPU time and other resources.
• It is more complex than First Come First Serve or Round Robin Scheduling due to its dependency on random number generator.