Lecture Notes on Operating Systems

Mythili Vutukuru
Department of Computer Science and Engineering, IIT Bombay


This page serves as a reference for courses on operating systems (OS) and related topics in computer systems. The material consists of video lectures, practice problems, and programming assignments.

The content is broadly divided into the following parts.

  • Parts A,B,C,D (lectures 1-20) cover basic concepts of operating systems that are taught in a regular UG OS course in a CS curriculum. This material is mostly based off the excellent online textbook Operating Systems: Three Easy Pieces (OSTEP), with pointers to the relevant chapters of the textbook provided against each lecture. A brief video lecture introduces the concepts from the textbook, and students are strongly encouraged to read the book chapters (that are freely available online) for a more in-depth understanding of the concepts.
  • Part X (lectures 21-24) covers the xv6 operating system in some detail. The xv6 teaching operating system comes with concise source code and a textbook/commentary, and is a great resource to understand fundamental concepts using a simple OS. While you are encouraged to get the latest version of xv6 from the link above, you may also refer to our local copy of xv6 textbook and local copy of xv6 code when reading our lecture notes.
  • Part N (lectures 25-26) covers the basics of the networking subsystem in Unix-like operating systems. This material is at the intersection of networking and OS, and can be part of a networking/OS UG/PG course.
  • Part Z (lectures 27-30) provides an overview of several topics at the intersection of OS and computer systems, including CPU caches, multicore scalability, performance measurement, and distributed systems. This material can be covered in an advanced UG/PG OS course, and can serve as a prelude to future courses on these topics.

Credits: Thanks to the OSTEP textbook authors for allowing me to use material from their book in my slides. Thanks also to the xv6 authors for making the xv6 OS available for teaching. Thanks to all my TAs who have helped me come up with the various labs and videos.



>
Lecture# Topics References Video & Annotated Slides Programming Exercises Problem Sets
PART A: Processes
1 Introduction to operating systems OSTEP Ch. 2 video / slides Lab: Introduction

Helper files: helper-files.tgz
questions / solutions
2 Process abstraction OSTEP Ch. 4 video / slides Lab: Shell

Skeleton code: my_shell.c, commands.txt

Testing scripts: autograder.tgz
3 System calls for process management OSTEP Ch. 5 video / slides
4 Process execution mechanisms OSTEP Ch. 6 video / slides
5 Scheduling policies OSTEP Ch. 7, OSTEP Ch. 8 video / slides
6 Inter-process communication Notes on IPC mechanisms

A sample tutorial on Linux IPC mechanisms.
video / slides
PART B: Memory
7 Introduction to virtual memory OSTEP Ch. 13 , OSTEP Ch. 14

A short note on the concept of address space
video / slides questions / solutions
8 Mechanism of address translation OSTEP Ch. 15, OSTEP Ch. 16 video / slides
9 Paging OSTEP Ch. 18 , OSTEP Ch. 19 , OSTEP Ch. 20 video / slides
10 Demand paging OSTEP Ch. 21 , OSTEP Ch. 22 video / slides
11 Memory allocation and free space management algorithms OSTEP Ch. 17 video / slides Lab: Dynamic memory management

Skeleton code: alloc.h and alloc.c

Code and scripts for testing: test-code.tgz
PART C: Concurrency
12 Introduction to threads and concurrency OSTEP Ch. 26 , OSTEP Ch. 27

A sample tutorial on pthreads.
video / slides questions / solutions
13 Locks OSTEP Ch. 28

A short note on software-based locks
video / slides Lab: Pthreads Synchronization

Skeleton code: master-worker-skeleton.c
rwlock.h, rwlock-reader-pref.cpp, rwlock-writer-pref.cpp

Code and scripts for testing: master-worker-autograder.tgz, rwlock-autograder.tgz
14 Condition variables OSTEP Ch. 30 video / slides
15 Semaphores OSTEP Ch. 31

Little Book of Semaphores has many interesting synchronization problems.
video / slides
16 Concurrency bugs OSTEP Ch. 32 video / slides
PART D: I/O and Filesystems
17 Communication with I/O devices OSTEP Ch. 36 video / slides questions / solutions
18 Files and directories OSTEP Ch. 39 video / slides
19 File system implementation OSTEP Ch. 40

Optional reading on crash consistency: OSTEP Ch. 42
video / slides Lab: A simple filesystem

Skeleton code: simplefs-disk.h,
simplefs-disk.c,
simplefs-ops.h,
simplefs-ops.c

Code and scripts for testing: test-code.tgz
20 Hard disk internals OSTEP Ch. 37 video / slides
PART X: The xv6 operating system
21 Process management in xv6 Notes on xv6 process management Lab: Processes and Scheduling in xv6

Skeleton code: original xv6 code and patched files for this lab

Code and scripts for testing: test-code.tgz
questions / solutions
22 Synchronization in xv6 Notes on xv6 synchronization Lab: Synchronization in xv6

Skeleton code: original xv6 code and patched files for this lab
23 Memory management in xv6 Notes on xv6 memory management Lab: Copy-on-Write Fork in xv6

Skeleton code: basic xv6 code and patched files

Code and scripts for testing: test-code.tgz



Lab: Lazy Memory Allocation in xv6

Skeleton code: basic xv6 code and patched files
24 The xv6 file system Notes on the xv6 file system Lab: Understanding the xv6 filesystem

Skeleton code: basic xv6 code and patched files
PART N: Networking
25 Socket programming (blocking, event-driven) Notes on network programming with sockets

A sample tutorial on socket programming.

A sample tutorial on event-driven I/O using epoll.

OSTEP Ch. 33
Lab: Key-value server (Part A)

Sample client and server socket programs
questions / solutions
26 Techniques to improve network I/O performance Notes on recent techniques to improve network I/O performance

[MICA] "MICA: A Holistic Approach to Fast In-Memory Key-Value Storage", Lim et al.
PART Z: Advanced topics in OS and systems
27 Performance evaluation of computer systems, load testing, Little's law Notes on performance Lab: Key-value server (Part B) questions / solutions
28 CPU caches, cache coherence, optimizing cache performance Notes on CPU caches

Sections 3.0-3.3, 6.2 of [Drepper] "What Every Programmer Should Know About Memory" by Ulrich Drepper
questions / solutions
29 Multicore scalability, scalable locking, lock-free synchronization Notes on multicore scalability

Section 8.1 of [Drepper] "What Every Programmer Should Know About Memory" by Ulrich Drepper.

[Mosbench] "An Analysis of Linux Scalability to Many Cores", Boyd-Wickizer et al.
questions / solutions
30 Distributed systems: fault tolerance, replication, consistency, distributed transactions Notes on distributed systems

[Raft] "In Search of an Understandable Consensus Algorithm", Ongaro and Ousterhout.

[Dynamo] "Dynamo: Amazon's Highly Available Key-value Store", DeCandia et al.
questions / solutions