Table of contents
1.
Introduction
1.1.
CPU Scheduling
2.
Lottery Process Scheduling
2.1.
Ways to manipulate tickets
2.2.
Drawback
3.
Frequently Asked Questions
3.1.
What is an OS?
3.2.
What is an operating system's main purpose?
3.3.
What does a real-time system entail?
3.4.
What purpose does paging serve in an operating system?
3.5.
What is lottery process scheduling?
4.
Conclusion
Last Updated: Mar 27, 2024

Lottery Process Scheduling

Author Saksham Gupta
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?
Operating System

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.

Frequently Asked Questions

What is an OS?

The operating system is a piece of software that allows computer hardware and software to connect and work together. It is the most crucial component of a computer system; without it, the computer would be nothing more than a box.

What is an operating system's main purpose?

An operating system serves two primary functions:
Its goal is to keep a computer system running smoothly by monitoring and managing its computational activities.
It provides a setting for program development and implementation.

What does a real-time system entail?

When the operation of a processor is subjected to strict time constraints, a real-time system is utilized. It has well-defined and well-defined temporal limits.

What purpose does paging serve in an operating system?

In an operating system, paging is employed to solve the problem of external fragmentation. This method ensures that the information you require is provided as soon as feasible.

What is 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.

Conclusion

In this article, we have extensively discussed the ‘Lottery Process Scheduling  in Operating System.’ We hope that this blog has helped you enhance your knowledge of ‘Lottery Process Scheduling in Operating System.’

Recommended Readings: 


Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Live masterclass