Operating Systems
Timeline: 80 - 200+ hours, Credit goes to palladian
Introduction
For the subject of operating systems, we offer two options: a "base" approach which is suitable for most students, and an "extended" approach for those that want to specialize in systems-level programming.
The "base" approach covers all of our operating system curriculum requirements and should take about 80 hours of work.
The "extended" approach contains all of the work of the base approach and more. It involves learning very serious C and x86 assembly, and delving deep into kernel programming. It takes significantly more time (over 200 hours) and is much more challenging. For those students interested in this area of computing it is also highly rewarding.
Base Approach
- Read through the free online textbook Operating Systems: Three Easy Pieces
- Complete the homework questions at the end of each chapter. (There is an associated Github repository for the homeworks.)
This should take about 8 weeks, 10 hours/week. That's all you need to do!
You will need a Unix/Linux system, some basic command line tools, and a C compiler (such as GCC or Clang). On Windows, you can install Ubuntu in a virtual machine, or use WSL (Windows Subsystem for Linux). Mac OS is Unix-like, so it should be OK to use.
Course Links
C
Question: I see some C code in this book. How much C do I need to know?
Answer: You'll need to read and understand some C code in this book. You'll need basic understanding of arrays, pointers and print formatting. You can consult the free book Dive into Systems: Chapter 1 and 2. The CS50 Manual pages are also helpful to look up functions. You shouldn't spend too much time on learning C.
The code you'll read is fairly simple and presented in short fragments. The book helps you out quite a bit by manually introducing many C APIs such as the Process API, the Thread API, and so on. You can type, compile and run the code fragments, and read the corresponding explanations. The book explains them in great detail in a conversational style that's fun to read.
You will also write a little bit of C code. Only a minority of the chapters (about 10 out of 50) ask you to write some C code (while the other chapters require you to run provided simulation code and answer questions). These are usually simple, short C programs that imitate the code that was presented in that chapter, with small modifications.
When you're ready to start the homework, start with the reverse project this will be a good test to see if you're ready for the rest of the projects. For the rest of the hw projects use the link under course links.
If you are getting stuck on these, please don't spend too much time on them. There is a great solution set here. There is no honor code for this, so you are free to use the solutions. If you find yourself spending too much time, feel free to read and understand the solutions instead. Your main priority should be to gain understanding of operating systems concepts, not to master C coding.
Extended Approach
If you've chosen this option, it is a must that you complete both courses in Intro to Computer Systems or equivalent first.
That said, if you're able to commit the time required for the prerequisites, we believe the reward is well worth the effort: this course is exciting, interesting, and quite useful for other fields of computer science and programming. One big attraction of this course is the opportunity to see a simplified but fully-functional Unix-like operating system in action and understand the concepts and design decisions that went into it as well as the low-level implementation details.
You should either watch all the lecture videos or read chapters 1 through 47 in the textbook (don't worry, the chapters are usually just a few pages long) as well as finish the projects listed below. We also strongly encourage you to do the homework exercises as they're assigned on the course website or in the book chapters; think of these like the "check-your-understanding" questions that pop up in the middle of lecture videos on sites like Coursera or edX.
Course Links
- Course website
- Book
- Lecture videos
- Homework
- Homework Source Code Repo
- Homework Solutions
- Projects
- xv6
Roadmap
This course was originally taught as CS 537 at the University of Wisconsin by the author of the OSTEP textbook, so the projects are assigned in the course according to the best times to give UWisconsin students access to on-campus resources like recitation sections and office hours. That means they don't match up perfectly with the material being covered at that time in the lectures or textbook chapters. We recommend doing the course in the following order instead.
| Topic | Readings | Lectures | Projects |
|---|---|---|---|
| Intro | [pre] [1] [2] | [1.1] [1.2] | Unix Utilities |
| Virtualization | |||
| Dialogue | [3] | ||
| Processes | [4] [5] [6] | [1.3] [2.1] | Unix Shell |
| Scheduling | [7] [8] [9] [10] | [2.2] [2.3] [3.1] | Intro to xv6 STCF-scheduler |
| Summary | [11] | ||
| Dialogue | [12] | ||
| Virtual Memory | [13] [14] [15] [16] [17] | [3.2] [3.3] | |
| Paging | [18] [19] [20] | [4.1] [4.2] [4.3] [5.1] | |
| Beyond physical | [21] [22] [23] | [5.2] | Memory Mapping |
| Summary | [24] | ||
| Concurrency | |||
| Dialogue | [25] | ||
| Threads | [26] [27] | [6.1] | |
| Concurrency primitives | [28] [29] [30] [31] | [6.2] [6.3] [7.1] [7.2] [7.3] [8.1] [8.2] | |
| More topics in concurrency | [32] [33] | [9.1] [9.2] | Optional: Kernel Threads xv6 MapReduce |
| Summary | [34] | ||
| Midterm review | Review | ||
| Persistence | |||
| Dialogue | [35] | ||
| IO and Disks | [36] [37] | [10.1] [10.2] [10.3] | |
| RAID | [38] | [11.1] [11.2] [11.3] | |
| Filesystems | [39] [40] | [11.4] [12.1] [12.2] [12.3] | |
| Crash consistency, journaling, FFS | [41] [42] | [13.1] [13.2] [13.3] | |
| LFS and SSDs | [43] [44] | [14.1] [14.2] [14.3] [14.4] | |
| Data Integrity and Protection | [45] | Mini-WFS | |
| Summary | [46] | ||
| End of class review | Part 1, Part 2 |
Advanced Topics
| Topic | Readings |
|---|---|
| Distributed systems | [47] [48] [49] [50] [51] |
| Security | [52] [53] [54] [55] [56] [57] |
Running the Projects
This course was originally taught as CS 537 at the University of Wisconsin by the author of the OSTEP textbook, which means that the homework and projects were written with those students as a target audience and designed to be run on UWisconsin lab computers with specific software versions pre-installed for students. We hope this section fixes that so you can run them on other computers, but we haven't tested this on every computer, so if you run into other issues, let us know on the Discord channel and we'll try to help out.
In order to run the homework and projects on Linux or macOS, you'll need to have all of the following programs installed:
gccgasldgdbmakeobjcopyobjdumpddpythonperlgawkexpectgitqemu
On macOS, you'll need to install a cross-compiler gcc suite capable of producing x86 ELF binaries; see the link above for details as well.
On Windows, you can use a Linux virtual machine for the homework and projects. Some of these packages are not yet supported on Apple M1 computers, and virtual machine software has not yet been ported to the new processor architecture; some students have used a VPS to do the homework and projects instead.
In our experience, modern Linux systems may run into compatibility issues when trying to build and/or run the xv6 kernel. Ubuntu 18.04 has shown to be a known-good version of linux for both building, running, and debugging the last version of xv6. You can run this version of Ubuntu in either a virtual machine or a Docker image. This blog post contains instructions on how to run and debug xv6 in an Ubuntu Docker image. UW-Madison has also made a Docker image available here.
For the homeworks and most projects, we use the GitHub repositories authored by Remzi. You can get them by cloning the ostep-homework and ostep-projects repositories:
git clone https://github.com/remzi-arpacidusseau/ostep-homework/
git clone https://github.com/remzi-arpacidusseau/ostep-projects/
You'll have to clone the xv6-public repository into the directory for each xv6-related OSTEP project. You could use the same copy for all the projects, but we recommend using separate copies to avoid previous projects causing bugs for later ones. Run the following commands in each of the initial-xv6, scheduling-xv6-lottery, vm-xv6-intro, concurrency-xv6-threads, and filesystems-checker directories.
mkdir src
git clone https://github.com/mit-pdos/xv6-public src
In some cases, we have found that the projects are either lacking in tests or in compatibility with the publicly available revisions of xv6. In those cases, we have chosen to replace those projects with projects from the UW Madison GitLab. Any projects from here will have a dedicated git repository for you to clone, which includes any material you may need such as an appropriate version of the xv6-kernel. For these projects, make your changes in the solution-directory of the repository, and run tests/run-tests.sh from the root of the repository in order to check your work.
Hints and tips for Projects
Debugging
Debugging is an essential part of kernel hacking. The xv6-repository offers qemu-gdb and qemu-nox-gdb as build targets. If you are running xv6 inside a docker container or virtual machine, make sure to have port 25000 on your localhost mapped to port 25000 on the guest OS.
In order to debug xv6, do the following:
- make sure your present working directory is the root of the xv6 repository
- run
make qemu-nox-gdbormake qemu-gdb. Wait for your console to output*** Now run 'gdb'.. - in a second terminal, same working directory, run
gdb kernelto start gdb. - inside gdb, run
target remote localhost:25000and thenbreak mainto set a breakpoint at the kernel's main function. - run
continueto start executing. you are now running xv6 with a debugger attached.****
For more information on how to debug with gdb, see Beej's Quick Guide to GDB.
xv6
The xv6 authors provide a book that you can read alongside the source code. There's also a handy line-numbered PDF version of the code with an index to see exactly where each function or constant gets used.
However, that book glosses over a lot of the details in the code that you might find challenging, including the advanced C features used, the x86 architecture- specific instructions, and the concurrency aspects (if you haven't finished that section of OSTEP before starting the xv6 projects). To solve this problem, we provide an annotated guide to xv6 that goes over the entire xv6 code and analyzes it line-by-line with explanations of the C features, hardware specs, and x86 conventions used. That means it's longer than the official xv6 book, so you don't have to read all of it (and you can probably skip the optional sections unless you care about device drivers), but you can use it as a reference if you're scratching your head about some part of the code.
Here is another in-depth explanation of the xv6 code.
Also here is an excellent video series walking through much of the xv6 code.
Miscellaneous
You'll need a general sense of how Makefiles work in order to use the Makefile for xv6. This tutorial covers much more than you need; just read the "Getting Started" and "Targets" sections and come back to the rest later if you need to look something up (but you shouldn't have to).
Additional (optional) resources include:
- GCC Command Options: a guide to command-line flags for the GNU C compiler
gcc. - Linker Scripts: a guide to writing scripts for the GNU linker
ld. - OSDev Wiki: a great resource for all kinds of OS concepts and implementation details.
- Linux Kernel Development: if you want to apply your xv6 knowledge toward contributing to the Linux kernel, this is a great read after OSTEP.