Linux Completely Fair Scheduler

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

rb0

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:

rb2

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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s