CSE 221: Reading List and Schedule

Fall 2024

Week 0 Week 1 Week 2 Week 3 Week 4 Week 5 Week 6 Week 7 Week 8 Week 9 Week 10   Exam
9/26 10/1
10/3
10/8
10/10
10/15
10/17
10/22
10/24
10/29
10/31
11/5
11/7
11/12
11/14
11/19
11/21
11/26
11/28
12/3
12/5
  12/9
All papers are accessible online from the UCSD network. To access the papers off campus, you can use the campus VPN. As a last resort, if you still encounter problems accessing papers, you can always search for the paper by title.

In this quarter we will cover a few historical papers, as well as papers about protection, synchronization, virtual memory, distributed OSes, virtualization, file systems, scheduling, networking, and more.

Course Introduction

Thu
9/26
  • Course Overview

Historical Perspective

Tue
10/1
  • E. W. Dijkstra, The Structure of the 'THE'-Multiprogramming System, Communications of the ACM, May 1968.

    (Additional historical background on semaphores in Wikipedia.)

    Q: Dijkstra explicitly states their goals for the THE operating system. How do these goals compare to, say, Microsoft's goals for the Windows operating system? Why do we no longer build operating systems with the same goals as THE?

  • P. B. Hansen, The Nucleus of a Multiprogramming System, Communications of the ACM, April 1970.

    Q: How does synchronization in the RC 4000 system compare with synchronization in the THE system?

Thu
10/3
  • D. G. Bobrow, J. D. Burchfiel, D. L. Murphy, and R. S. Tomlinson, TENEX, a Paged Time Sharing System for the PDP-10, Communications of the ACM, March 1972.

    Q: What features in TENEX are reminiscent of features in Unix?

  • D. M. Ritchie and K. Thompson, The UNIX Time-Sharing System, Communications of the ACM, July 1974.

    Q: What aspects of Unix as described in the 1974 paper do not survive today, or have been considerably changed?

    Optional paper that questions whether fork() is good abstraction for modern programmers:

    Andrew Baumann, Jonathan Appavoo, Orran Krieger, and Timothy Roscoe, A fork() in the Road, In Proceedings of the Workshop on Hot Topics in Operating Systems (HotOS'19), May 2019.

Protection

Tue
10/8
  • W. Wulf, E. Cohen, W. Corwin, A. Jones, R. Levin, C. Pierson, and F. Pollack, HYDRA: The Kernel of a Multiprocessor Operating System, Communications of the ACM, June 1974.

    Q: How is a Hydra procedure different from the procedures we are familiar with in a typical language and runtime environment?

  • B. Lampson, Protection, Operating Systems Review, January 1974.

    Q: What are the concepts in Hydra that correspond to Lampson's definitions of "Domain", "Object", and "Access Matrix"?

Thu
10/10

Synchronization

Tue
10/15

Virtual Memory

Thu
10/17

Distributed OSes

Tue
10/22
Thu
10/24
  • R. Pike, D. Presotto, S. Dorward, B. Flandrena, K. Thompson, H. Trickey, and P. Winterbottom, Plan 9 From Bell Labs, USENIX Computing Systems, July 1995.

    Q: What does it mean, "9P is really the core of the system; it is fair to say that the Plan 9 kernel is primarily a 9P multiplexer"?

  • Y. Shan, Y. Huang, Y. Chen, Y. Zhang, LegoOS: A Disseminated, Distributed OS for Hardware Resource Disaggregation, In Proceedings of the 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI'18), October 2018.

    Q: Which resources in LegoOS are partially diaggregated vs. fully disaggregated? Why?

Extending the OS

Tue
10/29
  • H. Haertig, M. Hohmuth, J. Liedtke, S. Schoenberg, J. Wolter, The Performance of Micro-Kernel-Based Systems, In Proceedings of the 16th Symposium on Operating Systems Principles (SOSP'97), October 1997.

    Q: Compare and contrast the L4 microkernel with Nucleus and Hydra in terms of their goals to provide a basis on which higher-level OS functionality can be implemented.

  • D. R. Engler, M. F. Kaashoek, and J. O'Toole Jr., Exokernel: An Operating System Architecture for Application-Level Resource Management, In Proceedings of the Fifteenth ACM Symposium on Operating Systems Principles (SOSP'95), December 1995.

    Q: Compare and contrast an exokernel with a microkernel.

Virtualization

Thu
10/31
  • R. J. Creasy, The Origin of the VM/370 Time-Sharing System, In IBM Journal of Research and Development, September 1981.

    Q: What was VM/370's motivation for virtualizing the hardware?

  • P. Barham, B. Dragovic, K. Fraser, S. Hand, T. Harris, A. Ho, R. Neugebauer, I. Pratt, and A. Warfield, Xen and the Art of Virtualization, In Proceedings of the 19th Symposium on Operating System Principles (SOSP'03), October, 2003.

    Q: Microkernels and virtual machine monitors are two different ways to support the execution of multiple operating systems on modern hardware. How does the microkernel approach in L4 compare and constrast with the VMM approach in Xen?

Tue
11/5

File Systems

Thu
11/7
  • M. K. McKusick, W. N. Joy, S. J. Leffler, and R. S. Fabry, A Fast File System for Unix, ACM Transactions on Computer Systems, August 1984.

    Q: In FFS, reading is always at least as fast as writing. In old UFS, writing was 50% faster. Why is this?

  • M. Rosenblum and J. K. Ousterhout, The Design and Implementation of a Log-Structured File System, Proceedings of the 13th ACM Symposium on Operating Systems Principles (SOSP'91), December 1991.

    Q: When we want to read a block in LFS on disk, how do we figure out where it is?

Tue
11/12

Scheduling

Thu
11/14
  • T. E. Anderson, B. N. Bershad, E. D. Lazowska, H. M. Levy, Scheduler Activations: Effective Kernel Support for the User-level Management of Parallelism, In Proceedings of the 13th ACM Symposium on Operating Systems Principles (SOSP'91), Sept. 1991.

    Q: The goal of scheduler activations is to have the benefits of both user and kernel threads without their limitations. What are the limitations of user and kernel threads, and what are the benefits that scheduler activations provide?

    Optional recent paper that tackles the same problem:

    H. Qin, Q. Li, J. Speiser, P. Kraft and J. Ousterhout, Arachne: Core-Aware Thread Management, In Proceedings of the Thirteenth USENIX Symposium on Operating System Design and Implementation (OSDI'18), October 2018.
  • J. Lozi, B. Lepers, J. Funston, F. Gaud, V. Quéma, and A. Fedorova, The Linux Scheduler: a Decade of Wasted Cores. In Proceedings of the Eleventh European Conference on Computer Systems (Eurosys'16), 2016.

    Q: What makes multicore scheduling more challenging than single-core scheduling?

Scalability

Tue
11/19
  • P. E. McKenney, J. Fernandes, and S. Boyd-Wickizer, RCU Usage In the Linux Kernel: Eighteen Years Later. ACM SIGOPS Operating Systems Review, August 2020.

    Q: In what settings is RCU a particularly good choice, or a particularly bad choice?

  • S. Boyd-Wickizer, A. T. Clements, Y. Mao, A. Pesterev, M. F. Kaashoek, R. Morris, and N. Zeldovich, An Analysis of Linux Scalability to Many Cores, In Proceedings of the 9th USENIX Symposium on Operating Systems Design and Implementation (OSDI'10), October 2010.

    Q: What kinds of application behavior can cause an application to scale poorly?

    Optional paper that proposes a rule for determining if an interface is scalable:

    Austin T. Clements, M. Frans Kaashoek, Nickolai Zeldovich, Robert Morris, Eddie Kohler, The Scalable Commutativity Rule: Designing Scalable Software for Multicore Processors, In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles (SOSP'13), October 2013.

Networking

Thu
11/21
Tue
11/26
  • A. Belay, G. Prekas, A. Klimovic, S. Grossman, C. Kozyrakis, and E. Bugnion IX: A Protected Dataplane Operating System for High Throughput and Low Latency, In Proceedings of the 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI'14), October 2014.

    Q: What is the difference between the control plane and the data plane and why does IX separate them?

  • M. Marty, M. de Kruijf, J. Adriaens, C. Alfeld, S. Bauer, C. Contavalli, M. Dalton, N. Dukkipati, W. C. Evans, S. Gribble, N. Kidd, R. Kononov, G. Kumar, C. Mauer, E. Musick, L. Olson, E. Rubow, M. Ryan, K. Springborn, P. Turner, V. Valancius, X. Wang and A. Vahdat, Snap: a Microkernel Approach to Host Networking, In Proceedings of the 27th ACM Symposium on Operating Systems Principles (SOSP'19), October 2019.

    Q: What are the tradeoffs between the monolithic, libOS, and microkernel-based approaches to structuring a network stack?

Thanksgiving Holiday

Thu
11/28
  • No class

File Systems, continued

Tue
12/3

  • S. Ghemawat, H. Gobioff, and S. Leung, The Google File System, In Proceedings of the Nineteenth ACM Symposium on Operating Systems Principles (SOSP'03), October 2003.

    Q: From an application's perspective, how is using GFS different from using a local file system?

  • H. Sigurbjarnarson, J. Bornholt, E. Torlak, and X. Wang, Push-Button Verification of File Systems via Crash Refinement, In Proceedings of the 12th Symposium on Operating Systems Design and Implementation (OSDI'16), November 2016.

    Q: What steps should a developer take in order to implement and verify a new file system using Yggdrasil?

Review

Thu
12/5
  • Review Session

Exam

Mon
12/9
  • Monday, December 9, 3–6pm