CSE 221: Reading List and Schedule

Winter 2021

Week 1 Week 2 Week 3 Week 4 Week 5 Week 6 Week 7 Week 8 Week 9 Week 10   Exam
1/5
1/7
1/12
1/14
1/19
1/21
1/26
1/28
2/2
2/4
2/9
2/11
2/16
2/18
2/23
2/25
3/2
3/4
3/9
3/11
  3/18
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.

Course Introduction

Tue
1/5
  • Course Overview

Historical Perspective

Thu
1/7
  • 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.

    Optional related paper on a deployment experience of RC 4000:

    P. B. Hansen, The RC 4000 Real-Time Control System at Pulway, BIT 7, pp. 279-288, 1967.

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

Tue
1/12
  • 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?

    Optional papers exploring operating system designs for the multiprocessor aspects of the Cm* machine (successor to the C.mmp machine briefly described in the Hydra paper):

    Anita K. Jones, Robert J. Chansler, Ivor Durham, Karsten Schwans, and Steven R. Vegdahl, StarOS, A Multiprocessor Operating System for the Support of Task Forces, Proceedings of the Seventh ACM Symposium on Operating Systems Principles (SOSP'79), December 1979, pp. 117–127.

    Q: One goal of StarOS is to support concurrent execution whenever and wherever possible. What are examples of support for this goal?

    John K. Ousterhout, Donald A. Scelza, and Pradeep S. Sindhu, Medusa: An Experiment in Distributed Operating Systems Structure, Communications of the ACM, Vol. 23, No. 2, February 1980, pp. 92–105.

    Q: Compare and contrast the abstraction of task forces in StarOS and Medusa?

Structure

Thu
1/14
  • 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.

    Optional Multics paper:

    A. Bensoussan, C. T. Clingen, and R. C. Daley, The Multics Virtual Memory: Concepts and Design, Communications of the ACM, Vol 15, No. 5, May 1972, pp. 308-318.

    Q: Compare and contrast protected subsystems in Multics with procedures in Hydra.

Tue
1/19
  • 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?

  • 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"?

Thu
1/21
  • D. D. Redell, Y. K. Dalal, T. R. Horsley, H. C. Lauer, W. C. Lynch, P. R. McJones, H. G. Murray, and S. C. Purcell, Pilot: An Operating System for a Personal Computer, Communications of the ACM, Vol. 23, No. 2, February 1980, pp. 81-92.

    Q: How do the requirements of the Pilot operating system differ from the systems we have read about so far, and how does the design of Pilot reflect those differences?

  • 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 Pilot?

    Optional recent paper implementing software-based protection domains in Rust, reminiscent of Singularity's SIPs:

    Vikram Narayanan, Tianjiao Huang, David Detweiler, Dan Appel, Zhaofeng Li, Gerd Zellweger and Anton Burtsev, RedLeaf: Isolation and Communication in a Safe Operating System, Proceedings of the 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI'20), November 2020, pp. 21–39.

    Q: How does RedLeaf's domains compare and contrast with Singularity's SIPs?

Synchronization

Tue
1/26
  • 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.

    Optional related papers on a completely different kind of synchronization known as wait-free or non-blocking synchronization:

    For a formal treatment of wait-free synchronization, see Herlihy's seminal paper:

    Maurice Herlihy, Wait-Free Synchronization, ACM Transactions on Programming Languages and Systems (TOPLAS), Vol. 13, No. 1, January 1991, pp. 124–149.

    Linux uses a particular version called read-copy-update (RCU):

    Paul E. McKenney, Dipankar Sarma, Andrea Arcangeli, Andi Kleen, Orran Krieger, and Rusty Russell. Read Copy Update. In Proceedings of the Ottawa Linux Symposium, June 2002, pp. 338–367.

    For an extensive bibliography on RCU through 2013, see this Linux RCU document. For a recent retrospective, see:

    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.

Virtual Memory

Thu
1/28
  • 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?

Distribution

Tue
2/2
  • 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?

    Optional reading on V later in its life:

    David R. Cheriton, The V Distributed System, Communications of the ACM, Vol. 31, No. 3, March 1988, pp. 314–333.

  • 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?

    Optional historical retrospective:

    J. K. Ousterhout, Sprite Retrospective

    In addition to V, Sprite, and Plan 9, optional related papers on other distributed operating systems of the era:

    Bruce Walker, Gerald Popek, Robert English, Charles Kline and Greg Thiel, The LOCUS Distributed Operating System, Operating Systems Review, Vol. 17, No. 5, October 1983, pp. 49–70.

    Paul J. Leach, Paul H. Levine, Bryan P. Douros, James A. Hamilton, David L. Nelson, and Bernard L. Stumpf, The Architecture of an Integrated Local Network, IEEE Journal on Selected Areas in Communication, Vol. SAC-1, No. 5, November 1983, pp. 842–857.

    M. Rozier, V. Abrossimov, F. Armand, I. Boule, M. Gien, M. Guillemont, F. Herrmann, C. Kaiser, S. Langlois, P. Léonard, W. Neuhauser, Overview of the CHORUS Distributed Operating Systems, USENIX Computing Systems, Vol. 1, No. 4, Fall 1988, pp. 305–370.

    Andrew S. Tanenbaum, Robbert van Renesse, Hans van Staveren, Gregory J. Sharp, Sape J. Mullender, Jack Jansen, and Guido van Rossum, Experiences with the Amoeba Distributed Operating System, Communications of the ACM, Vol. 33, No. 12, December 1990, pp. 46–63.

Thu
2/4
  • Michael J. Feeley, William E. Morgan, Frederic H. Pighin, Anna R. Karlin, and Henry M. Levy, Implementing Global Memory Management in a Workstation Cluster, Proceedings of the 15th ACM Symposium on Operating Systems Principles, Dec. 1995, 29(5): 201-212.

    Q: How does the implementation of the GMS page replacement algorithm approximate the ideal algorithm?

  • Luiz André Barroso, Jeffrey Dean, and Urs Hölzle, Web Search for a Planet: The Google Cluster Architecture, IEEE Micro, March 2003, 23(2): 22–28.

    Optional:

    Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati, Avinash Lakshman, Alex Pilchin, Swaminathan Sivasubramanian, Peter Vosshall, and Werner Vogels, Dynamo: Amazon's Highly Available Key-value Store, Proceedings of the 21st Symposium on Operating Systems Principles, December 2007, pp. 205–220.

OS/Architecture Interaction

Tue
2/9
  • H. Haertig, M. Hohmuth, J. Liedtke, S. Schoenberg, J. Wolter, The Performance of Micro-Kernel-Based Systems, Proceedings of the 16th Symposium on Operating Systems Principles, October 1997, pp. 66-77.

    Optional related papers on hierarchical address spaces and formally verifying a microkernel:

    J. Liedtke, On Micro-kernel Construction, In Proceedings of the Fifteenth ACM Symposium on Operating Systems Principles, December 1995, Copper Mountain Resort, Colorado, pp. 237-250.

    G. Klein, K. Elphinstone, G. Heiser, J. Andronick, D. Cock, P. Derrin, D. Elkaduwe, K. Engelhardt, M. Norrish, R. Kolanski, T. Sewell, H. Tuch, S. Winwood, seL4: Formal Verification of an OS Kernel, In Proceedings of the 22nd ACM Symposium on Operating Systems Principles, October 2009, Big Sky Resort, MT, pp. 207-220.

    Q: Compare and contrast the L4 microkernel with the RC4000 Nucleus and the HYDRA kernel 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.

    Optional — the other Exokernel paper:

    M. F. Kaashoek, D. R. Engler, G. R. Ganger, H. M. Briceno, R. Hunt, D. Mazieres, T. Pinckney, R. Grimm, J. Jannotti and K. Mackenzie, Application Performance and Flexibility on Exokernel Systems, In Proceedings of the Sixteenth ACM Symposium on Operating Systems Principles, October 1997, St. Malo, France, pp. 52-65.

    Unikernels are a contemporary take on library operating systems (also see Mirage OS):

    Anil Madhavapeddy, Richard Mortier, Charalampos Rotsos, David Scott, Balraj Singh, Thomas Gazagnaire, Steven Smith, Steven Hand and Jon Crowcroft, Unikernels: Library Operating Systems for the Cloud, In Proceedings of the 18th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), pp. 461–472, March 2013.
Thu
2/11
  • 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?

    Optional related paper describing VMware virtualization performance and comparing software versus hardware virtualization approaches (2006-era):

    Keith Adams and Ole Agesen, A Comparison of Software and Hardware Techniques for x86 Virtualization, In Proceedings of the 12th International Conference on Architectural Support for Programming Languages and Operating Systems, October 2006, pp. 2–13.

    Disco is the precursor to VMware, a company the authors later founded:

    Edouard Bugnion, Scott Devine, Kinshuk Govil, Mendel Rosenblum, Disco: Running Commodity Operating Systems on Scalable Multiprocessors. ACM Transactions on Computer Systems, 15(4), November 1997, pp. 412–447.
Tue
2/16

Scheduling

Thu
2/18

Communication

Tue
2/23
  • 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?

    Optional reading on highly-optimized RPC for data center communication:

    Anuj Kalia, Michael Kaminsky and David Andersen, Datacenter RPCs can be General and Fast, In Proceedings of the 16th USENIX Symposium on Networked Systems Design and Implementation (NSDI), Boston, MA, Feb 2019.

    and pointers to contemporary RPC and data wrangling packages:

    Google RPC & Protocol Buffers, Facebook Thrift, JSON-RPC/XML-RPC, SOAP.

  • Adam Belay, George Prekas, Ana Klimovic, Samuel Grossman, Christos Kozyrakis, Edouard 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, October 2014, 49–65.

    Optional reading on a microkernel architecture for user-level networking functionality:

    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.

I/O and File Systems

Thu
2/25
  • 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?

Tue
3/2
  • 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.

  • P. M. Chen, W. T. Ng, S. Chandra, C. Aycock, G. Rajamni, and D. Lowell, The Rio File Cache: Surviving Operating System Crashes, In Proceedings of the Seventh International Conference on Architectural Support for Programming Languages and Operating Systems, SIGPLAN Notices 31(9):74-83, September 1996.

    Q: Do you believe the underlying argument in Rio? Why or why not? Would you use a system that recovered data using Rio?

    Optional further readings on Rio:

    David E. Lowell and Peter M. Chen, Free Transactions with Rio Vista, In Proceedings of the Sixteenth ACM Symposium on Operating Systems Principles October 1997, St. Malo, France, pp. 92–101.

Potpourri

Thu
3/4
Tue
3/9
  • Silas Boyd-Wickizer, Austin T. Clements, Yandong Mao, Aleksey Pesterev, M. Frans Kaashoek, Robert Morris, and Nickolai Zeldovich. An Analysis of Linux Scalability to Many Cores In Proceedings of the 9th Symposium on Operating System Design & Implementation (OSDI), October 2010, Vancouver, BC, Canada, pp. 383–398.

    As optional further reading, this group's first work was exploring OS multicore scalability using an exokernel:

    Silas Boyd-Wickizer, Haibo Chen, Rong Chen, Yandong Mao, Frans Kaashoek, Robert Morris, Aleksey Pesterev, Lex Stein, Ming Wu, Yuehua Dai, Yang Zhang, and Zheng Zhang. Corey: An Operating System for Many Cores. In Proceedings of the 8th Symposium on Operating System Design & Implementation (OSDI), October 2008, San Diego, California, pp. 43–57.

    Then they framed OS multicore scalability in more fundamental aspects:

    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.

  • 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.
Thu
3/11
  • (Any of the following that strike your fancy)

Exam

Thu
3/18
  • Thursday, March 18