CSE 221: Reading List and Schedule

Winter 2005

All papers are accessible online via a UCSD computer. To access the papers from a non-UCSD computer, use the campus web proxy with your web browser.

Course Introduction

(1/4)

• Overview of the course.

(1/6)

• E. W. Dijkstra, The Structure of the 'THE'-Multiprogramming System, Communications of the ACM, Vol. 11, No. 5, May 1968, pp. 341-346.

  Q: Dijkstra explicitly states their goals for the THE operating system. How do these goals compare to, say, Microsoft's goals for the NT 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?

(1/11)

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

(1/13)

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

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

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

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

(1/20)

• J. K. Ousterhout, D. A. Scelza, and P. S. Sindhu, Medusa: An Experiment in Distributed Operating Systems Structure, Communications of the ACM, Vol. 23, No. 2, February 1980, pp. 92-105.

  Q: What are the three distributed OS structures outlined in the paper, which structure does Medusa use, and why?

• D. D. Clark, The Structuring of Systems using Upcalls, Proceedings of the 10th Symposium on Operating Systems Principles. pp. 171-180, December 1985.

  Q: What are the benefits of using an upcall structure, and what are the potential drawbacks?

(1/25)

• No class.

(1/27)

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

  J. K. Ousterhout, Sprite Retrospective

  Q: How do the caching policies in Sprite differ from those in the V Kernel?

(2/1)

• G. J. Popek, B. Walker, J. Chow, D. Edwards, C. Kline, G. Rudisin, and G. Theil, "LOCUS: A Network Transparent, High Reliability Distributed System," Proceedings of the 8th Symposium on Operating Systems Principles, pp. 160-168, December 1981.

  Q: How do the replication semantics of Grapevine and LOCUS differ?

• M. D. Schroeder, A. D. Birrell, and R. M. Needham, "Experience with Grapevine: The Growth of a Distributed System," ACM Transactions on Computer Systems, Vol. 2, No. 1, February 1984.

  Q: In what ways was Grapevine explicitly designed to handle scalability?

(2/3)

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

(2/8)

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

  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.

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

(2/10)

• Thomas E. Anderson, Brian N. Bershad, Edward D. Lazowska, Hanry 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.

  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?

• Carl A. Waldspurger and William E. Weihl, "Lottery Scheduling: Flexible Proportional-Share Resource Management." In Proceedings of the First USENIX Symposium on Operating System Design and Implementation, November, 1994.

  Q: At a high level, as a mechanism how does lottery scheduling provide modular resource management? Why can't the Unix scheduler provide a similar kind of management?

(2/15)

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

• B. N. Bershad, T. E. Anderson, E. D. Lazowska, and H. M. Levy, "Lightweight Remote Procedure Call," Proceedings of the 12th Symposium on Operating Systems Principles, pp. 102-113, December 1989.

  Q: What is the argument that "local" remote procedure call performance is important? Does this argument still hold today?

(2/17)

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

(2/22)

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

(2/24)

• V. S. Pai, P. Druschel, and W. Zwaenepoel, "IO-Lite: A Unified Buffering and Caching System," In Proceedings of the Third Symposium on Operating Systems Design and Implementation (OSDI'99), New Orleans, LA, February 1999, pp. 15-28.

  Q: Which optimization in IO-Lite had the most significant performance impact? Does this optimization generalize to many applications?

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

(3/1)

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

• D. S. Santry, M. J. Feeley, N. C. Hutchinson, A. C. Veitch, R. W. Carton, and J. Or, "Deciding When to Forget in the Elephant File System." In Proceedings of the Seventeenth ACM Symposium on Operating Systems Principles, December 12-15, 1999, Charleston, SC, pp. 110-123.

  Q: Do you think versioning would be a useful feature in contemporary file systems? Both the VMS file system and the Andrew File System had versioning. Why do you think Unix FFS and NTFS do not?

(3/3)

• B. N. Bershad, S. Savage, P. Pardyak, E. G. Sirer, M. E. Fiuczynski, D. Becker, C. Chambers, S. Eggers, "Extensibility, Safety and Performance in the SPIN Operating System." In Proceedings of the Fifteenth ACM Symposium on Operating Systems Principles, December, 1995, Copper Mountain, CO, pp. 267-283.

  Q: What is the Spin protection model for extensions, and to which systems we have read about is it most similar?

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

  Q: How does customizability in Exokernel compare/contrast to extensibility in SPIN?

(3/8)

• Jeffrey S. Chase, Darrell Anderson, Prachi Thakar, Amin Vahdat, and Ronald Doyle, "Managing Energy and Server Resources in Hosting Centers." In Proceedings of the Eighteenth ACM Symposium on Operating Systems Principles (SOSP), October 2001.

• Alex C. Snoeren, Craig Partridge, Luis A. Sanchez, Christine E. Jones, Fabrice Tchakountio, Stephen T. Kent, and W. Timothy Strayer. "Single-Packet IP Traceback." In IEEE/ACM Transactions on Networking (ToN), Volume 10, Number 6, December 2002.

• Thursday 3/10, 9:30-10:50am, WLH 2204