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

J. H. Saltzer, Protection and the Control of Information Sharing in Multics, Communications of the ACM, July 1974.
Q: Compare and contrast protected subsystems in Multics with procedures in Hydra.
G. C. Hunt and J. R. Larus, Singularity: Rethinking the Software Stack, ACM SIGOPS Operating Systems Review, April 2007.
Q: How does the language-based approach that Singularity takes compare and contrast with other approaches to protection we have discussed so far?

Synchronization

Tue
10/15

C. A. R. Hoare, Monitors: An Operating System Structuring Concept, Communications of the ACM, October 1974.
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, February 1980.
Q: Compare and contrast synchronization in Java with Hoare monitors and Mesa monitors.

Virtual Memory

Thu
10/17

H. M. Levy and P. Lipman, Virtual Memory Management in VAX/VMS, IEEE Computer, March 1982.
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.
R. Rashid, A. Tevanian, M. Young, D. Golub, R. Baronn, D. Black, W. Bolosky, and J. 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.
Q: Why does Mach support copy-on-write, and how does it implement it?

Distributed OSes

Tue
10/22

D. R. Cheriton and W. Zwaenepoel, The Distributed V Kernel and its Performance for Diskless Workstations, In Proceedings of the 9th Symposium on Operating Systems Principles (SOSP'83), 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, February 1988.
Q: How do the caching policies in Sprite differ from those in the V Kernel?

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

No class

Thu
10/31

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

Tue
11/5

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?

Thu
11/7

S. Soltesz, H. Pötzl, M. E. Fiuczynski, A. 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), March 2007.
Q: What are the key tradeoffs between hardware virtualization and OS-level virtualization?
A. Agache, M. Brooker, A. Florescu, A. Iordache, A. Liguori, R. Neugebauer, P. Piwonka, and D. Popa, Firecracker: Lightweight Virtualization for Serverless Applications, In Proceedings of the 17th USENIX Symposium on Networked Systems Design and Implementation (NSDI'20), February 2020.
Q: What tradeoffs does Firecracker make compared to other virtualization approaches?

File Systems

Tue
11/12

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?

Thu
11/14

G. R. Ganger, M. McKusick, C. Soules, and Y. Patt. Soft Updates: A Solution to the Metadata Update Problem in File Systems, ACM Transactions on Computer Systems, May 2000.
Q: What is the metadata update problem?

Optional recent paper about a variant of Soft Updates that uses the Rust compiler:
H. LeBlanc, N. Taylor, J. Bornholt, and V. Chidambaram, SquirrelFS: Using the Rust Compiler to Check File-System Crash Consistency, In Proceedings of the Eighteenth USENIX Symposium on Operating System Design and Implementation (OSDI'24), July 2024.
R. Kadekodi, S. Lee, S. Kashyap, T. Kim, A. Kolli, V. Chidambaram, SplitFS: Reducing Software Overhead in File Systems for Persistent Memory, In Proceedings of the 27th ACM Symposium on Operating Systems Principles (SOSP'19), October 2019.
Q: Why does it make sense to design file systems for persistent memory differently?

Scheduling

Tue
11/19

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

Thu
11/21

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

Tue 11/26	A. D. Birrell and B. J. Nelson, Implementing Remote Procedure Calls, ACM Transactions on Computer Systems, 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 J. C. Mogul and K. K. Ramakrishnan, Eliminating Receive Livelock in an Interrupt-driven Kernel, ACM Transactions on Computer Systems, August 1997. Q: What are the tradeoffs between interrupts and polling?
Thu 11/28	Thanksgiving holiday - no class
Tue 12/3	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?

File Systems, continued and Review

Thu
12/5

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?

Optional paper that applies verification to file systems:
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.

Exam

Mon
12/9

Monday, December 9, 3–6pm