Readings in Operating Systems

A list of papers essential to computer software system design with my notes. It is based on the reading lists of CS 523 Advanced Operating Systems (Fall 2020) and CS 423 Operating System Design (Spring 2020) at UIUC.

Historical Perspectives

• The Structure of the “THE”-Multiprogramming System (1967). Paper | Note
  • Layered OS structure
• The Nucleus of a Multiprogramming System (1970). Paper | Note
  • OS kernel; Separation of policy and mechanism
• TENEX, a Paged Time Sharing System for the PDP-10 (1971). Paper
  • Paged virtual memory; Interactive terminal
• HYDRA: The Kernel of a Multiprocessor Operating System (1974). Paper
  • Capability-based kernel; Separation of policy and mechanism; Rejection of rigid layering

Unix and Plan 9 (and MINIX and Linux)

• The UNIX Time-Sharing System (1973). Paper | Note
  • Interactive terminal; Everything is a file
• Plan 9 From Bell Labs (1995). Paper | Note
  • Distributed OS that further pushes everything is a file; UTF-8
• Lessons Learned from 30 Years of MINIX (2016). Paper | Note
  • OS lesson? Microkernel!
• Linux’s Early History by Linus Torvalds (1992).
  • It’s a hobby project!

Microkernel

• Improving IPC by Kernel Design (1993). Paper | Note
  • Microkernel can be fast with a proper design
• The Performance of μ-Kernel-Based Systems (1997). Paper | Note
  • Add evidence to the previous one

Library OS

• Exokernel: An Operating System Architecture for Application-Level Resource Management (1995). Paper | Note
  • Separate protection from management → Exokernel + Libary OSes
• Unikernels: Library Operating Systems for the Cloud (2013). Paper | Note

Synchronization

• Experience with Processes and Monitors in Mesa (1980). Paper | Note
  • Background: Monitors: An Operating System Structuring Concept (1974). Paper
  • Hoare semantics → Mesa semantics (notify is just an hint and awakening may not happen immediately)

• Transactional Memory: Architectural Support for Lock-Free Data Structures (1993). Paper | Note

• Eraser: A Dynamic Data Race Detector for Multi-Threaded Programs (1997).
  • Finding and Reproducing Heisenbugs in Concurrent Programs (2008). Paper | Note
  • Ad Hoc Synchronization Considered Harmful (2010). Paper | Note
• Making Parallel Programs Reliable with Stable Multithreading (2014).

Scheduling

• Scheduler Activations: Effective Kernel Support for the User-level Management of Parallelism (1991). Paper | Note
  • Background: The Structuring of Systems Using Upcalls (1985). Paper | Note

• The Linux Scheduler: a Decade of Wasted Cores (2016). Paper | Note

• Lottery Scheduling: Flexible Proportional-Share Resource Management (1994). Paper | Note
  • Get scheduled = win lottery

Memory Management

• Virtual Memory Management in VAX/VMS Operating System (1982). Paper

• Machine-Independent Virtual Memory Management for Paged Uniprocessor and Multiprocessor Architectures (1987). Paper

• Translation Caching: Skip, Don’t Walk (the Page Table) (2010). Paper | Note
  • Radix-tree-based virtual memory translation made fast with proper cache design

• Elastic Cuckoo Page Tables: Rethinking Virtual Memory Translation for Parallelism (2020). Paper | Note

• Efficient Virtual Memory for Big Memory Servers (2013). Paper | Note
  • If troubled by paged VM, why not welcome back segmentation (partially)?
• Coordinated and Efficient Huge Page Management with Ingens (2016). Paper | Note
  • Memory contiguity as a resource

Virtual Machine and Container

• Xen and the Art of Virtualization (2003). Paper | Note
  • Paravirtualization
• A Comparison of Software and Hardware Techniques for x86 Virtualization (2006). Paper | Note
  • We need hardware support for MMU virtualization
• My VM is Lighter (and Safer) than your Container (2017). Paper | Note
  • Minimalist VM image (+ improved Xen control plane) = light VM
• X-Containers: Breaking Down Barriers to Improve Performance and Isolation of Cloud-Native Containers (2019). Paper | Note
  • Applying the exokernel approach to the container architecture
• Firecracker: Lightweight Virtualization for Serverless Applications (2020). Paper | Note
  • VMM specialized for serverless workloads

Storage and File Systems

• A Fast File System for Unix (1984). Paper | Note
  • Your FS runs on a disk, optimize for it!
• The Design and Implementation of a Log-Structured File System (1991). Paper | Note
  • Sequential write is fast? Then do it all the time!

• Soft Updates: A Solution to the Metadata Update Problem in File Systems (2000). Paper | Note

• The Rio File Cache: Surviving Operating System Crashes (1996). Paper | Note
  • What if my RAM survives OS crash?

• The Google File System (2003). Paper | Note

• Windows Azure Storage: A Highly Available Cloud Storage Service with Strong Consistency (2011). Paper | Note

Distributed Systems

• The Sprite Network Operating System (1988).

• The Distributed V Kernel and its Performance for Diskless Workstations (1983).

• Web Search for a Planet: The Google Cluster Architecture (2003).

• MapReduce: Simplified Data Processing on Large Clusters (2004).

Protection

Reliability

• Improving the Reliability of Commodity Operating Systems (2003). Paper | Note

• Bugs as Deviant Behavior: A General Approach to Inferring Errors in Systems Code (2001). Paper | Note