CS 450: Operating Systems

Staff

Instructor: Kyle C. Hale
  Office Hours: Mon. 9AM-10:30AM, Thurs. 4:15PM-5:45PM (Zoom)
  E-mail: khale [at] cs [dot] iit [dot] edu

TAs:

Course Info

Course number: CS 450

Semester: Fall 2020

Lecture Time: Tues/Thurs 2PM - 3:15PM

Lecture Location: Hermann Hall 100 (currently virtual)

Overview

Operating systems run the world. Without an OS, you couldn't have hundreds of programs running at once, you'd have to have deep understanding of hardware, and you'd have to rewrite your code for each new machine on the market. You wouldn't have web servers, desktop machines, laptops, phones, or smart watches; no Siri, no Alexa, no TensorFlow or CUDA programs.

In this course, you will dive straight into the deepest and often most confounding component of a computer system's software stack. You will become familiar with both the high-level concepts underpinning modern operating systems and with low-level mechanisms, in addition to new and emerging techniques and programming models for computer systems. I am a strong believer in learning by doing, so the majority of your time for this course will be spent working on programming projects, both very low-level work and high-level (user-space) work. This course will be challenging! It will bring together a lot of concepts you've learned in your previous courses, from data structures and algorithms to assembly language, computer architecture, virtual memory, and advanced C programming.

For this course, I assume that you have basic familiarity with computer organization (as introduced in CS 350), data structures, C, and systems programming (as covered in CS 351). You will for sure need to be able to program in C and should be able to navigate around a UNIX environment.

Lectures and COVID

While we are online only, lectures and office hours will be held on zoom. If students have issues with this medium, we may switch (e.g. to Blackboard Collaborate). The link for these will be posted on the course Piazza. Recordings of the lectures will be posted afterwards on Blackboard.

Communication

We will be primarily using Piazza as a course communication mechanism. If you have an issue or question that is not strictly private (especially one that would benefit everyone were it answered), please use Piazza as your first resource. The instructor, the TA, and your fellow classmates will be there to help. Note that you can also post anonymously if you so choose.

Homeworks

While there will be no homework to turn it, it is a very good idea to do some of the homeworks associated with the readings as I post them. These are usually short coding tasks that use a simulator for the OS component in question. These homeworks will help solidify knowledge needed for the exams.

Readings

In addition to the projects (and homeworks if you're studious), you'll be needing to do the readings I post (almost) every lecture. These will primarily come from the OSTEP book, but I will also post other required and optional readings from seminal research papers, articles, and books.

We will, when time allows, also be spending some time reading code! This will likely include code snippets from real OSes including the Linux kernel.


The following is a rough schedule of the class. Note that it is subject to change.

Lecture Schedule

Week Date Item Topic Notes Reading
1 Tues 8/25 Lec 1 Intro and Administrivia Lec. 1 slides Required Reading: OSTEP Preface, 1, 2
1 Thurs 8/27 Lec 2 Resource Virtualization and Processes Lec. 2 slides Required Reading: OSTEP 3, 4, 5, 6, System Calls
2 Tues 9/1 Lec 3 Scheduling Lec. 3 slides Required Reading: OSTEP 7, 8, Summary, Linux processes, Interrupts (gentle)
Optional Reading: A decade of wasted cores, OSTEP: Multi-processor Scheduling, Linux CFS
2 Thurs 9/3 Lec 4 Virtual Memory Lec. 4 slides Required Reading: OSTEP 13, 15, 16, Anatomy of a program in memory
Optional Reading: Kernel memory management, Closures, stacks, and the heap
3 Tues 9/8 Lec 5 Intro to Paging Lec. 5 slides Required Reading: OSTEP 18, 19, 20, Getting Physical with Memory
Optional Reading: Memory Translation and Segmentation
3 Thurs 9/10 Lec 6 Multi-level Paging and the TLB Lec. 6 slides Required Reading: OSTEP 21, 22, Summary
Optional Reading: OSTEP 23, The Page Cache
4 Tues 9/15 Lec 7 Virtual Memory and Paging Tricks Lec. 7 slides Required Reading: OSTEP 25, 26
4 Thurs 9/17 Lec 8 Concurrency I: Threads Lec. 8 slides Required Reading: OSTEP 28, 29
5 Tues 9/22 Lec 9 Concurrency II: Mutual Exclusion (locks) Lec. 9 slides Required Reading: OSTEP 30
5 Thurs 9/24 Lec 10 Concurrency III: Signaling and Condition Variables Lec. 10 slides Required Reading: OSTEP 31, 33, Signals, Linux kernel signals
6 Tues 9/29 Lec 11 Concurrency IV: Semaphores, Signals, Event-driven architecture Lec. 11 slides Required Reading: OSTEP 32, Sys V. Shared Memory, Sys V. Message Queues
6 Thurs 10/1 Lec 12 Concurrency V: Concurrency Bugs and IPC Lec. 12 slides Required Reading: OSTEP d, 36
Optional Reading: Therac-25, Mars Pathfinder
7 Tues 10/6 Lec 13 I/O I: Devices and Drivers Required Reading: Overview of PCIe, Chipsets and the Memory Map
Optional Reading: How PCI Express Works
7 Thurs 10/8 Lec 14 I/O II: PCI and dynamic MMIO Required Reading: OSTEP 37
Optional Reading: What your computer does while you wait
8 Tues 10/13 Lec 15 I/O III: Disks Lec. 15 slides Required Reading: OSTEP 38
Optional Reading: Original RAID paper
8 Thurs 10/15 Lec 16 I/O IV: RAID Lec. 16 slides Required Reading: OSTEP 38
9 Tues 10/20 Lec 17 File Systems I: File Abstractions Lec. 17 slides Required Reading: OSTEP 39
9 Thurs 10/22 Lec 18 File Systems II: Implementation Required Reading: OSTEP 40
10 Tues 10/27 Lec 19 File Systems III: FFS Required Reading: OSTEP 41
10 Thurs 10/29 Lec 20 File Systems IV: Journaling and LFS Required Reading: OSTEP 42, 43
11 Tues 11/3 Lec 21 SSD, Flash, and NVM Required Reading: OSTEP 44, NVDIMMs
11 Thurs 11/5 Lec 22 Distributed Systems I Required Reading: OSTEP 48
12 Tues 11/10 Lec 23 Distributed Systems II: RPC and NFS Required Reading: OSTEP 49, 50
12 Thurs 11/12 Lec 24 Programming Models I: MapReduce Required Reading:MapReduce
13 Tues 11/17 Lec 25 Case Study: GFS Required Reading:Google FS
13 Thurs 11/19 Lec 26 TBD
14 Tues 11/24 -- No lecture: Thanksgiving Break
14 Thurs 11/25 -- No lecture: Thanksgiving Break
15 Tues 12/1 Lec 27 TBD
15 Thurs 12/3 Lec 28 TBD

Exams

Week Date Item Length Covers Notes
8 Wed 10/14 (Not set in stone) Midterm TBD Lec 1-14 example
TBD TBD Final Exam TBD Apx 70% material after Lec 15, 30% first half of class

Projects

You'll notice that (almost) every project listed below for this class is split into two parts. In many cases these are really entirely separate projects, but are logically grouped together to stress some particular concept. The (a) parts are mostly concentrated on userspace components (part of the broader operating system) and the (b) parts are kernel components that will involve hacking on xv6. Unless otherwise noted, grades for these projects are going to be based on whether or not your code works. Partial solutions will not be given credit! With that in mind, you should always start early.

Project Topic Due Date Handout Notes (TBP = To Be Posted)
1a UNIX warmup Monday, 9/7/2020 Tuesday, 9/8/2020 11:59PM CST p1a description Posted Monday, 8/31 4:00PM CST
1b xv6 warmup Friday, 9/18/2020 11:59PM CST p1b description Posted Tuesday, 9/8 7:00PM CST
2a out of the depths of x86 Friday, 9/25/2020 11:59PM CST p2a description Posted Thursday, 9/17 5:45PM CST
2b xv6 scheduling Friday, 10/9/2020 11:59PM CST p2b description Posted Saturday, 9/26, 9:41AM CST
3a parallel zip Friday, 10/23/2020 11:59PM CST p3a description Posted Monday, 10/12/2020 11:29AM CST
3b null pointers and shared memory TBD TBP
4a kernel threads TBD TBP
4b TBD TBD TBP

Books

The following book is the only required textbook for this course. It is not only an excellent textbook, but is also freely availble online:

ostep-book
Operating Systems: Three Easy Pieces by Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau, 2015.

The below books are also great and often-used texts on Operating Systems. If you find a copy of one for a good price, snatch it. Keep in mind, however, that the best way to earn operating systems is by building!.

This is probably my favorite OS textbook after OSTEP. Full disclosure, I took undergrad OS with Dahlin many years ago.

anderson-os
Operating Systems: Principles and Practice (2nd Edition), by Thomas Anderson and Michael Dahlin, Recursive Books 2014.
silberschatz-os
Operating System Concepts (9th Edition), by Abraham Silberschatz, Peter Baer Galvin, and Greg Gagne, 2012 Wiley.
tanenbaum-os
Modern Operating Systems (4th Edition), by Andrew S. Tanenbaum and Herbert Bos, Pearson 2014.

For general systems design, a good one to have on the shelf:

system-design-kaashoek
Principles of Computer System Design: An Introduction (1st Edition), by Jerome H. Saltzer and M. Frans Kaashoek, Morgan Kaufmann 2009.

The following book, while outdated (uses a 2.6.10 kernel as a reference), still provides one of the best references for practical kernel hacking:

linux-kernel-book
Understanding the Linux Kernel (3rd Edition), by Daniel P. Bovet and Marco Cesati, O'Reilly Media 2005.

Good book on Linux kernel programming:

love-kernel-dev-book
Linux Kernel Development (3rd Edition), by Robert Love, Addison-Wesley Professional, 2010.

If you're interested in the macOS kernel, this one is not out yet, but will be soon:

osx-internals-book
OSX Internals, Volume II, 2nd Edition, by Jonathan Levin.

Similarly for Windows:

windows-internals-book
Windows Internals, Part 1: System Architecture... (7th Edition), by Pavel Yosifovich, Mark E. Russinovich, Alex Ionescu, and David A. Solomon, Microsoft Press 2017.

Development Environment

We will primarily be using Docker for development. You will need to have the Docker client installed on your machine.

Other Useful Links and Resources

This is a list of other resources that you might find useful for this class. Feel free to peruse them at your own convenience.

Links

Interesting, important, historical, and new OS Kernels