Seminar week 5: Scheduling

Overview

For this week’s seminar we will learn more about scheduling algorithms. This is an important part of operating systems design, and still an open research problem today! We’ll start this seminar talking about the evolution of the scheduler in the Linux operating system, which changed algorithms several times in its 30 year history–we’ll talk about why, and some of the tradeoffs and considerations in modern scheduling algorithms.

Room assignments: This week, we will split into two rooms again. We will likely use the same room assignments as previous weeks, but please watch Edstem for an announcement (we’re planning to revisit the roster and may re-shuffle, now that shopping period has ended).

Assigned work: As in previous seminars, please complete the readings below and submit a brief response in the form below, along with any questions you have. Your responses are due Thursday, October 8 at 11:59pm.

Reading

Read this article about the evolution of the Linux scheduler. This article was written mainly for an audience of Linux kernel developers, so there will be references to Linux-specific code and terminology that won’t make sense–that’s okay! As with our previous articles, try to focus on the high-level points (i.e., what the scheduling algorithms do), and feel free to ignore the parts that you don’t recognize. In particular:

  • You can ignore all of the code: the article contains several snippets of actual Linux kernel code to implement the scheduler. Don’t worry about parsing this (though you may notice some similarities to your own OS!)
  • You may see references to a process’ “nice” level: this is a term from Linux, and older Unix-based operating systems, to refer to a user-specified process priority. The kernel uses this value to compute a process true priority, which is used by the scheduling algorithm. You can read more about nice levels here (though this isn’t required).

What you should turn in

By Thursday, October 8 at 11:59pm, fill out this form with brief responses to the following questions:

  • Describe, in your own words, the evolution of Linux’ scheduling algorithms. What are the key differences between each one, and what led to the switch each time? You don’t need to recite every detail–just explain the parts that you thought were most important about each phase of the evolution.

  • Please ask us a question about scheduling.

Once again, your goal is not to understand every detail, but to begin parsing some technical documents based on what we’ve seen so far. We’ll use this, and your questions, as a starting point for our discussion.