CSE 221: Reading List and Schedule

Winter 2024

Week 1	Week 2	Week 3	Week 4	Week 5	Week 6	Week 7	Week 8	Week 9	Week 10	Exam
1/9 1/11	1/16 1/18	1/23 1/25	1/30 2/1	2/6 2/8	2/13 2/15	2/20 2/22	2/27 2/29	3/5 3/7	3/12 3/14	3/19

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 OS structure, synchronization, virtual memory, distributed OSes, extensibility, scheduling, networking, I/O and file systems, and more. The readings for later weeks will be added as we progress through the quarter.

Course Introduction

Tue
1/9

Course Overview

Historical Perspective

Thu
1/11

E. W. Dijkstra, The Structure of the 'THE'-Multiprogramming System, Communications of the ACM, Vol. 11, No. 5, May 1968, pp. 341-346.
(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, Vol. 13, No. 4, April 1970, pp. 238-241, 250.
Q: How does synchronization in the RC 4000 system compare with synchronization in the THE system?

Tue
1/16

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, Vol. 15, No. 3, March 1972, pp. 135-143.
Q: What features in TENEX are reminiscent of features in Unix (a later system)?
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, Vol. 17, No. 6, June 1974, pp. 337-345.
Q: How is a Hydra procedure different from the procedures we are familiar with in a typical language and runtime environment?

Structure

Thu
1/18

B. Lampson, Protection, Operating Systems Review, Vol. 8, No. 1, January 1974, pp. 18-24.
Q: What are the concepts in HYDRA that correspond to Lampson's definitions of "Domain", "Object", and "Access Matrix"? What about Multics?
J. H. Saltzer, Protection and the Control of Information Sharing in Multics, Communications of the ACM, Vol. 17, No. 7, July 1974, pp. 388-402.
Q: Compare and contrast protected subsystems in Multics with procedures in Hydra.

Tue
1/23

D. M. Ritchie and K. Thompson, The UNIX Time-Sharing System, Communications of the ACM, Vol. 17, No. 7, July 1974, pp. 365-375.
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, Proceedings of the Workshop on Hot Topics in Operating Systems, pp. 14-22. 2019.
Galen C. Hunt and James R. Larus. Singularity: Rethinking the Software Stack, ACM SIGOPS Operating Systems Review, Vol. 41, No. 2, April 2007, pages 37–49.
Q: How does the language-based approach that Singularity takes compare and contrast with other approaches to protection we have discussed so far?

Synchronization

Thu
1/25

C. A. R. Hoare, Monitors: An Operating System Structuring Concept, Communications of the ACM, Vol. 17, No. 10, October, 1974, pp. 549-557.
Q: What are "monitor invariant" I and "condition" B, and why are they important in the discussion of monitors?
B. W. Lampson and D. D. Redell, Experience with Processes and Monitors in Mesa, Communications of the ACM, Vol. 23, No. 2, February 1980, pp. 105-117.
Q: Compare and contrast synchronization in Java with Hoare monitors and Mesa monitors.

Scalability

Tu
1/30

Paul E. McKenney, Joel Fernandes, and Silas Boyd-Wickizer. RCU Usage In the Linux Kernel: Eighteen Years Later. ACM SIGOPS Operating Systems Review Vol. 54, No. 1, August 2020, pp. 47–63.
Q: In what settings is RCU a particularly good choice, or a particularly bad choice?
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), October 2013, pp. 1–17.
Q: In the context of this paper, what does it mean for two operations to commute?

Virtual Memory

Thu
2/1

H. M. Levy and P. Lipman, Virtual Memory Management in VAX/VMS, IEEE Computer, Vol. 15, No. 3, March 1982, pp.35-41.
Q: The paper states, "VAX/VMS, then, is a collection of procedures that exist in the address space of each process." Explain in your own words what this statement means.
Richard Rashid, Avadis Tevanian, Michael Young, David Golub, Robert Baronn, David Black, William Bolosky, and Jonathan Chew, Machine-Independent Virtual Memory Management for Paged Uniprocessor and Multiprocessor Architectures, In Proceedings of the Second International Conference on Architectural Support for Programming Languages and Operating Systems, October 1987, pp. 31-39.
Q: Why does Mach support copy-on-write, and how does it implement it?

Distributed OSes

Tue
2/6

D. R. Cheriton and W. Zwaenepoel, The Distributed V Kernel and its Performance for Diskless Workstations, Proceedings of the 9th Symposium on Operating Systems Principles, pp. 129-140, November 1983.
Q: What is the argument for diskless workstations, and do you agree/disagree with the argument?
J. K. Ousterhout, A. R. Cerenson, F. Douglis, M. N. Nelson, and B. B. Welch, The Sprite Network Operating System, IEEE Computer, Vol. 21, No. 2, February 1988, pp. 23-36.
Q: How do the caching policies in Sprite differ from those in the V Kernel?

Thu
2/8

R. Pike, D. Presotto, S. Dorward, B. Flandrena, K. Thompson, H. Trickey, and P. Winterbottom, Plan 9 From Bell Labs, USENIX Computing Systems, Vol. 8, No. 3, Summer 1995, pp. 221-254.
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"?
Yizhou Shan, Yutong Huang, Yilun Chen, Yiying Zhang, LegoOS: A Disseminated, Distributed OS for Hardware Resource Disaggregation, In Proceedings of the 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI), October 2018, pp. 69–87.
Q: Which resources in LegoOS are partially diaggregated vs. fully disaggregated? Why?

Extending the OS

Tue
2/13

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, October 1997, pp. 66-77.
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, December 1995, Copper Mountain Resort, Colorado, pp. 251-266.
Q: Compare and contrast an exokernel with a microkernel.

Virtualization

Thu
2/15

R. J. Creasy, The Origin of the VM/370 Time-Sharing System, In IBM Journal of Research and Development, 25(5):483-490, 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, 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
2/20

Stephen Soltesz, Herbert Pötzl, Marc E. Fiuczynski, Andy Bavier, Larry Peterson, Container-based Operating System Virtualization: A Scalable, High-performance Alternative to Hypervisors, In Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems (Eurosys'07), pp. 275–287, March 2007.
Q: What are the key tradeoffs between hardware virtualization and OS-level virtualization?
Alexandru Agache, Marc Brooker, Andreea Florescu, Alexandra Iordache, Anthony Liguori, Rolf Neugebauer, Phil Piwonka, and Diana-Maria Popa, Firecracker: Lightweight Virtualization for Serverless Applications, In Proceedings of the 17th USENIX Symposium on Networked Systems Design and Implementation (NSDI'20), pp. 419–434, February 2020.
Q: What tradeoffs does Firecracker make compared to other virtualization approaches?

Scheduling

Thu
2/22

Jean-Pierre Lozi, Baptiste Lepers, Justin Funston, Fabien Gaud, Vivien Quéma, and Alexandra Fedorova. The Linux Scheduler: a Decade of Wasted Cores. In Proceedings of the Eleventh European Conference on Computer Systems, pp. 1-16. 2016.
Q: What makes multicore scheduling more challenging than single-core scheduling?
Henry Qin, Qian Li, Jacqueline Speiser, Peter Kraft and John Ousterhout, Arachne: Core-Aware Thread Management, In Proceedings of the Thirteenth USENIX Symposium on Operating System Design and Implementation, pp. 145–160, October 2018.
Q: What are the limitations of user and kernel threads, and how does Arachne address them?

Optional paper on scheduler activations, an early approach to achieving the best of user and kernel threads:
Thomas E. Anderson, Brian N. Bershad, Edward D. Lazowska, Henry M. Levy, Scheduler Activations: Effective Kernel Support for the User-level Management of Parallelism, Proceedings of the 13th ACM Symposium on Operating Systems Principles, Sept. 1991, pp. 95-109.

Networking

Tue
2/27

A. D. Birrell and B. J. Nelson, Implementing Remote Procedure Calls, ACM Transactions on Computer Systems, Vol. 2, No. 1, pp. 39-59, February 1984.
Q: In what ways do the authors optimize connection management?

Pointers to contemporary RPC and serialization packages:
Google RPC & Protocol Buffers, Facebook Thrift
Jeffrey C. Mogul and Kadangode K. Ramakrishnan, Eliminating Receive Livelock in an Interrupt-driven Kernel, ACM Transactions on Computer Systems, Vol. 15, No. 3, pp. 217-252, August 1997.

Q: What are the tradeoffs between interrupts and polling?

Thu
2/29

Irene Zhang, Amanda Raybuck, Pratyush Patel, Kirk Olynyk, Jacob Nelson, Omar S. Navarro Leija, Ashlie Martinez, Jing Liu, Anna Kornfeld Simpson, Sujay Jayakar, Pedro Henrique Penna, Max Demoulin, Piali Choudhury, and Anirudh Badam, The Demikernel Datapath OS Architecture for Microsecond-scale Datacenter Systems, In Proceedings of the 28th ACM Symposium on Operating Systems Principles (SOSP), October 2021, pp. 195–211.
Q: What is the difference between the control path and the data path and why does Demikernel separate them?
Michael Marty, Marc de Kruijf, Jacob Adriaens, Christopher Alfeld, Sean Bauer, Carlo Contavalli, Michael Dalton, Nandita Dukkipati, William C. Evans, Steve Gribble, Nicholas Kidd, Roman Kononov, Gautam Kumar, Carl Mauer, Emily Musick, Lena Olson, Erik Rubow, Michael Ryan, Kevin Springborn, Paul Turner, Valas Valancius, Xi Wang and Amin Vahdat, Snap: a Microkernel Approach to Host Networking, In Proceedings of the 27th ACM Symposium on Operating Systems Principles (SOSP), Huntsville, ON, Canada, October 2019.
Q: What are the tradeoffs between the monolithic, libOS, and microkernel-based approaches to structuring a network stack?

I/O and File Systems

Tue 3/5	Marshall K. McKusick, William N. Joy, Samuel J. Leffler, and Robert S. Fabry, A Fast File System for Unix, ACM Transactions on Computer Systems, 2(3), August 1984, pp. 181-197. Q: In FFS, reading is always at least as fast as writing. In old UFS, writing was 50% faster. Why is this? Mendel Rosenblum and John K. Ousterhout, The Design and Implementation of a Log-Structured File System, Proceedings of the 13th ACM Symposium on Operating Systems Principles, December 1991. Q: When we want to read a block in LFS on disk, how do we figure out where it is?
Thu 3/7	Gregory R. Ganger, Marshall Kirk McKusick, Craig A.N. Soules, and Yale N. Patt. Soft Updates: A Solution to the Metadata Update Problem in File Systems, ACM Transactions on Computer Systems, Vol. 18, No. 2, May 2000, Pages 127–153. Q: What is the metadata update problem? Rohan Kadekodi, Se Kwon Lee, Sanidhya Kashyap, Taesoo Kim, Aasheesh Kolli, Vijay Chidambaram, SplitFS: Reducing Software Overhead in File Systems for Persistent Memory, In Proceedings of the 27th ACM Symposium on Operating Systems Principles (SOSP), October 2019, pp. 494–508. Q: Why does it make sense to design file systems for persistent memory differently?
Tue 3/12	Sanjay Ghemawat, Howard Gobioff, Shun-Tak Leung, The Google File System, In Proceedings of the Nineteenth ACM Symposium on Operating Systems Principles (SOSP), October 2003, pp. 29–43. Q: From an application's perspective, how is using GFS different from using a local file system? Helgi Sigurbjarnarson, James Bornholt, Emina Torlak, and Xi Wang, Push-Button Verification of File Systems via Crash Refinement, In Proceedings of the 12th Symposium on Operating Systems Design and Implementation (OSDI), pp. 1–16, November 2016. Q: What steps should a developer take in order to implement and verify a new file system using Yggdrasil?

Review

Thu
3/14

Review Session

Exam

Tue
3/19

Tuesday, March 19, 3–6pm