Adding Stride Scheduling to Xv6

Summary

The xv6 kernel uses a basic round robin scheduler. To understand scheduling more deeply, I replaced it with a stride scheduler. This post compares round robin and stride scheduling, explains how I added it to xv6, and what I learned along the way. xv6 uses a simple round robin scheduler that treats all runnable processes equally. I replaced it with a stride scheduler to explore proportional-share scheduling. Stride scheduling assigns each process a “stride” value that determines how often it runs; smaller strides mean higher priority. In a few lines of code, I was able to achieve stride scheduling effectiveness on par with the theoretical expectations. Along the way, I uncovered an interesting startup lockup in init worth looking into further. One of the most important responsibilities of an operating system is to select which processes (think: running programs) to run and when. If there were, say, one process running and one CPU on the system, then there’s no problem - just let that process run. But, on real systems, there are many processes running at a time and relatively few processors on which to run. To provide the illusion of letting every process run, the OS allows these processes to run for very short bursts of time, then allowing another one to run for a short time, and so on. Choosing which process to run is the role of the OS scheduler. An aside on terminology: Scheduling theory comes not just from the world of computers, but from the world of manufacturing. So, there are some terms that can sometimes be used interchangeably or which can be a bit confusing. For instance, processes are sometimes called “jobs.” Scheduling policies aren’t just called algorithms: they’re also called “disciplines.” And, a set of jobs is a “workload.” OK, let’s get back to the post. How many ways could there be to schedule jobs? Well, a lot, it turns out - different scheduling disciplines work better or worse for different workloads. We’re just going to talk about two, though:...