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, communication, 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

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

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

Exam

Tue
3/19
  • Tuesday, March 19, 3–6pm