computer science

Lottery scheduling

Lottery scheduling is a computer science topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Lottery scheduling rather than just read about it. In short: Lottery scheduling is a probabilistic scheduling algorithm for processes in an operating system. Processes are each assigned some number of lottery tickets, and the scheduler draws a random ticket to select the next process.

Key takeaways

Lottery scheduling belongs to computer science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Lottery scheduling to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Lottery scheduling from memory before moving on to harder problems.

Reference excerpt

Lottery scheduling is a probabilistic scheduling algorithm for processes in an operating system. Processes are each assigned some number of lottery tickets, and the scheduler draws a random ticket to select the next process. The distribution of tickets need not be uniform; granting a process more tickets provides it a relative higher chance of selection. This technique can be used to approximate other scheduling algorithms, such as Shortest job next and Fair-share scheduling. Lottery scheduling 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.

Implementation Implementations of lottery scheduling should take into consideration that there could be billions of tickets distributed among a large pool of threads. To have an array where each index represents a ticket, and each location contains the thread corresponding to that ticket, may be highly inefficient. Lottery scheduling can be preemptive or non-preemptive.

External links Lottery Scheduling: Flexible Proportional-Share Resource Management by Carl A. Waldspurger and William E. Weihl. The 1994 Operating Systems Design and Implementation conference (OSDI '94). November, 1994. Monterey, California. Lottery and Stride Scheduling: Flexible Proportional-Share Resource Management by Carl A. Waldspurger. Ph.D. dissertation, Massachusetts Institute of Technology. September 1995. Operating Systems: Three Easy Pieces by Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau. Arpaci-Dusseau Books, 2014. Relevant chapter: Proportional-Share Scheduling. Implementing Lottery Scheduling - Matching the Specialization in Traditional Schedulers - Paper by David Petrou et al. Stochastic priority-based task Scheduler by Robert V. Welland and Walter R. Smith. United States Patent Number US 5247677 A

Worked examples

Example 1 — a first encounter with Lottery scheduling

Start with the simplest possible case. Write down what Lottery scheduling claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In computer science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Lottery scheduling before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Lottery scheduling ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Lottery scheduling

In research: Lottery scheduling appears in computer science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Lottery scheduling in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Lottery scheduling is common in secondary-school and first-year university syllabi. It links to neighbouring topics Processor scheduling algorithms, so understanding it makes those chapters shorter.
In everyday life: Look for Lottery scheduling outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Lottery scheduling in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Lottery scheduling means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Lottery scheduling out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Lottery scheduling in simple terms?

Why does Lottery scheduling matter?

Because it connects several computer science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Lottery scheduling?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Lottery scheduling.