Welcome back to my hello-ebpf series. Last week, I showed you how to create a custom Linux scheduler with a simple web API to control the task scheduling using sched-ext. Just so you know: A talk based on this blog post got accepted in the Testing and Continuous Delivery dev room at FOSDEM 2025. But this is not what I’m going to talk about in this blog post; instead, this article is on a topic that I covered almost exactly eleven years ago on this very blog: Lottery scheduling. We’ll extend the taskcontrol project covered in last week’s post with a new scheduler.

Foundations and Retrospektive

Eleven years ago, I was a student in Professor Frank Bellosa‘s operating systems course, learning about different schedulers. I wrote a blog post on a scheduler that I found particularly interesting: the lottery scheduler. I could write a new introduction to lottery scheduling, but I can also delegate this task to my old self:

I currently have a course covering operating systems at university. We learn in this course several scheduling algorithms. An operating system needs these kind of algorithms to determine which process to run at which time to allow these process to be executed “simultaniously” (from the users view).

Good scheduling algorithms have normally some very nice features:

• They avoid the starving of one process (that one process can’t run at all and therefore makes no progress).
• That all processes run the approriate percentage (defined by it’s priority) of time in each bigger time interval.

But they are maybe not only useful for operating systems but also for people like me. Probably they could help me to improve the scheduling of my learning.

An algorithm that seems to be suited best for this purpose is called lottery scheduling (pdf). It’s an algorithm that gives a each process some lottery tickets (their number resembles the priority of the process). Every time the algorithm has to choose a new process to run, it simply picks a lottery ticket randomly and returns the process that owns the ticket. A useful addition is (in scenarios with only a few tickets) to remove the tickets that are picked temporarily from the lottery pot and put them back again, when the pot is empty.

Real life practice in lottery scheduling

We can visualize this similarly to the FIFO scheduler from last week’s blog post:

This is a truly random scheduler, making it great for testing applications with random scheduling orders. This is why it’s a great addition to the taskcontrol project.