If, like me, one operating system is just not enough for you, you probably got a Linux partition, like me. As a part of the open source community, the linux kernel has all its code online for the world to puzzle over. Over the past semester, some ambitious classmates and I decided to re-implement and visualize one of the central parts of any kernel, namely the scheduler.
Replacing the O(1) scheduler in 2007, the Linux Completely Fair Scheduler is based on the Red Black Tree data structure, where each node represents a running process in the computer. In action, it looks a little something like this
For each process, we keep track of the amount of time it’s been running. Since the tree is an ordered data structure, so if we were to color each process by how long it had been running (red -> less time) it would look something like this:
At every point, we remove the node that has been running the least amount of time and run that process. Ideally, this means each process should get the same amount of run time, although with all the additional complications such as priority, interrupts, and process blocking, I think it’s due for a rebranding.
You can find resources and more information at our github repo and report, and of curse reach out to me if you have any questions.
