CMPS 221: Advanced Operating Systems
Fall 2011

Reading List

This is the reading list for the Fall 2003 section of CMPS 221 at UC Santa Cruz. We will cover the papers in this order during the quarter. The papers are available for download in Adobe PDF by students in the class.

There are two types of papers: required and optional. Required papers must be read before the class in which they will be covered. You should try to read as many optional papers as you can, particularly in topics that interest you. You are encouraged to go beyond this reading list as well and find more papers on these topics. You will have to do this for your projects as well as throughout your graduate career—taking the initiative to find and read papers on your research is essential for success in graduate school.

You will need to write a summary for each (required) paper that you read. The summary must answer eight questions (briefly!); a sample summary is available online.

Early systems / history

Required

1. J. Fotheringham, "Dynamic Storage Allocation in the Atlas Computer, Including an Automatic Use of a Backing Store," Communications of the ACM, Vol. 4, No.10, Oct. 1961, pp. 435–436.
2. F. J. Corbató, M. M. Daggett, and R. C. Daley, "An Experimental Time-Sharing System," Proceedings of the AFIPS 1962 Spring Joint Computer Conference (SJCC), May 1962, pages 335–344.
3. F. J. Corbató and V. A. Vyssotsky, "Introduction and Overview of the Multics System," Proceedings of the AFIPS 1965 Fall Joint Computer Conference (FJCC), 1965, Spartan Books: New York, pp. 185–196.
4. E. W. Dijkstra, "The Structure of the THE Multiprogramming System," Communications of the ACM, Vol. 11, No. 5, May 1968, pp. 341–346.
5. D. M. Ritchie and K. Thompson, "The UNIX Time-sharing System," Bell System Technical Journal, Vol. 57, No. 6, 1978, pp. 1905–1929.

Optional

• R. C. Daley and J. B. Dennis, "Virtual Memory, Processes, and Sharing in MULTICS," Communications of the ACM, Vol. 11, No. 5, May 1968, pp. 306–312.
• F. J. Corbató, J. H. Saltzer and C. T. Clingen, "Multics - The first seven years," Proceedings AFIPS 1972 Fall Joint Computer Conference (FJCC), vol. 27, no. 1, 1965, Spartan Books: New York, pp. 185–196.
• D. M. Ritchie, "The Evolution of the Unix Time-sharing System," Bell System Technical Journal, Vol. 63, No. 6, Part 2, October 1984, pp. 1577–1593.
• K. Thompson, "UNIX Implementation," Bell System Technical Journal, Vol. 57, No. 6, 1978, pp. 1931–1946.

Kernel structures

Required

1. M. Accetta, R. Baron, W. Bolosky, D. Golub, R. Rashid, A. Tevanian, and M. Young, "Mach: A New Kernel Foundation for Unix Development," Proceedings of the USENIX Summer Conference, July 1986.
2. B. Bershad, S. Savage, P. Pardyak, E. G. Sirer, D. Becker, M. Fiuczynski, C. Chambers and S. Eggers, "Extensibility, Safety and Performance in the SPIN Operating System," Proceedings of the 15th Symposium on Operating System Principles (SOSP), Dec. 1995, pp. 267-284.
3. M. F. Kaashoek, D. R. Engler, G. R. Ganger, H. M. Briceño, R. Hunt, D. Mazières, T. Pinckney, R. Grimm, J. Jannotti, and K. MacKenzie, "Application Performance and Flexibility on Exokernel Systems," Proceedings of the 16th Symposium on Operating Systems Principles (SOSP), Oct. 1997, pp. 52–65.
4. M. Seltzer, Y. Endo, C. Small and K. Smith, "Dealing with Disaster: Surviving Misbehaved Kernel Extensions," Proceedings of the Second Symposium on Operating System Design and Implementation (OSDI) , October 1996.

Optional

• G. Hamilton and P. Kougiouris, "The Spring Nucleus: A Microkernel for Objects," Proceedings of the 1993 Summer USENIX Technical Conference, 1993.
• A. Alexandrov, M. Ibel, K. E. Schauser, and C. J. Scheiman, "Ufo: A Personal Global File System Based on User-Level Extensions to the Operating System," ACM Transactions on Computer Systems, Volume 16, Number 3, Aug. 1998, pp. 207–233.

Memory management

Required

1. H. M. Levy and P. H. Lipman, "Virtual Memory Management in the VAX/VMS Operating System," IEEE Computer, March 1982, pp. 35–41.
2. O. Babaoglu and W. Joy, "Converting a Swap-Based System to do Paging in an Architecture Lacking Page Reference Bits," Proceedings of the 8th Symposium on Operating Systems Principles (SOSP), 1981, pp. 78-85.
3. M. Talluri, M. D. Hill and Y. A. Khalidi, "A New Page Table for 64-bit Address Spaces," Proceedings of the 15th Symposium on Operating Systems Principles (SOSP), 1995, pp. 184–199.
4. J. S. Chase, H. M. Levy, M. J. Feeley, and E. D. Lazowska, "Sharing and Protection in a Single-Address-Space Operating System," ACM Transactions on Computer Systems, volume 12, number 4, Nov. 1994, pp. 271–307.

Optional

• R. Rashid, A. Tevanian, M. Young, D. Golub, R. Baron, D. Black, W. Bolsky and J. Chew, "Machine-independent Virtual Memory Management for Paged Uniprocessor and Multi-processor Architectures," IEEE Transactions on Computers, Vol. 37, No. 8 (1988), pp. 896–905.
• M. D. Dahlin, R. Y. Wang, T. E. Anderson, D. A. Patterson, "Cooperative Caching: Using Remote Client Memory to Improve File System Performance," Proceedings of the Symposium on Operating System Design and Implementation (OSDI), Nov. 1994.
• J. B. Carter, J. K. Bennett and W. Zwaenepoel, "Techniques for Reducing Consistency-related Communication in Distributed Shared-memory Systems," ACM Transactions on Computer Systems, Vol. 13, No. 3, August 1995, pp. 205–243.

File systems

Required

1. M. K. McKusick, W. N. Joy, S. J. Leffler and R. S. Fabry, "A Fast File System for UNIX," ACM Transactions on Computer Systems, Vol. 2, No. 3, August 1984, pp. 181–197.
2. M. Rosenblum and J. K. Ousterhout, "The Design and Implementation of a Log-Structured File System," ACM Transactions on Computer Systems, Vol. 10, No. 1, February 1992, pp. 26-52.
3. D. Hitz, J. Lau, and M. Malcolm, "File System Design for an NFS File Server Appliance," Proceedings of the USENIX Winter 1994 Technical Conference, Jan. 1994, pp. 235–246.
4. A. Sweeney, D. Doucette, W. Hu, C. Anderson, M. Nishimoto, G. Peck, "Scalability in the XFS File System," Proceedings of the 1996 USENIX Technical Conference, Jan. 1996.
5. A. Muthitacharoen, B. Chen, and D. Mazières, "A Low-Bandwidth Network File System," Proceedings of the 18th ACM Symposium on Operating Systems Principles (SOSP), Oct. 2001, pp. 174–187.
6. S. A. Weil, S. A. Brandt, E. L. Miller, D. D. E. Long, and C. Maltzahn, “Ceph: A
   Scalable, High-Performance, Distributed Object-based Storage System,” Symposium on Operating Systems Design and Implementation (OSDI ’06), Seattle, Washington, November 6–8. 2006, to appear.

Optional

• M. N. Nelson, B. B. Welch and J. K. Ousterhout, "Caching in the Sprite Network File System," ACM Transactions on Computer Systems, Vol. 6, No. 1, February 1988, pp. 134–154.
• M. Seltzer, K. Bostic, M. K. McKusick, C. Staelin, "An Implementation of a Log-Structured File System for UNIX," In Proceedings of the 1993 Winter Usenix Conference, January 1993, pp. 307–326.
• C. A. Thekkath, T. Mann, E. K. Lee, "Frangipani: A Scalable Distributed File System," Proceedings of the ACM Symposium on Operating Systems Principles (SOSP), Oct. 1997, pp. 224–237.
• D. S. Santry , M. J. Feeley, N. C. Hutchinson, A. C. Veitch, R. W. Carton, and J. Ofir, "Deciding When to Forget in the Elephant File System," Proceedings of the 17th ACM Symposium on Operating Systems Principles (SOSP), Dec. 1999, pp. 110–123.
• S. Quinlan and S. Dorward, "Venti: A New Approach to Archival Storage," In Proceedings of the 2002 Conference on File and Storage Technologies (FAST), January 2002, pp. 89–102.

Authentication, protection, and security

Required

1. B. W. Lampson, "A Note on the Confinement Problem," Communications of the ACM, Vol. 16, No. 10, Oct. 1973, pp. 613–615.
2. 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.
3. R. Needham and M. Schroeder, "Using Encryption for Authentication in Large Networks of Computers," Communications of the ACM, Vol. 21, No. 12, Dec. 1978, pp. 993-999.
4. J. G. Steiner, C. Neuman and J. I. Schiller, "Kerberos: An Authentication Service for Open Network Systems," Proceedings of the Winter 1988 USENIX Conference, 1988, pp. 205–211.

Optional

• J. D. Strunk, G. R. Goodson, M. L. Scheinholtz, C. A. N. Soules, and G. R. Ganger, "Self-Securing Storage: Protecting Data in Compromised Systems," Proceedings of the 4th Symposium on Operating Systems Design and Implementation (OSDI 2000), Oct. 2000, pp. 165–180.
• D. Mazières, M. Kaminsky, M. F. Kaashoek, and E. Witchel, "Separating Key Management from File System Security," Proceedings of the 17th Symposium on Operating Systems Principles (SOSP), 1999, pp.124–139.
• E. L. Miller, D. D. E. Long, W. E. Freeman, and B. C. Reed, "Strong Security for Network-Attached Storage," Proceedings of the Conference on File and Storage Technologies (FAST), Jan. 2002, pp. 1–13.
• R. L. Rivest, A. Shamir and L. Adleman, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems," Communications of the ACM, Vol. 21, No. 2, February 1978, pp. 120–126.
• E. Wobber, M. Burrows, M. Abadi and B. Lampson, "Authentication in the Taos Operating System," ACM Transactions on Computer Systems, Vol. 12, No. 1, Feb. 1994, pp. 3-32.
• E. Reidel, M. Kallahalla, and R. Swaminathan, "A Framework for Evaluating Storage System Security," Proceedings of the Conference on File and Storage Technologies (FAST), Jan. 2002, pp. 15–30.
• B. Lampson, M. Abadi, M. Burrows, and E. Wobber, "Authentication in Distributed Systems: Theory and Practice," ACM Transactions on Computer Systems, Vol. 10, No. 4, Nov. 1992, pp. 265–310.

Synchronization

Required

1. C. A. R. Hoare, "Monitors: An Operating System Structuring Concept," Communications of the ACM, Vol. 17, No. 10, October 1974, pp. 549–557.
2. L. Lamport, "A Fast Mutual Exclusion Algorithm," ACM Transactions on Computer Systems, Vol. 5, No. 1, Feb. 1987, pp. 1–11

Optional

• D. Agrawal and A. E. Abbadi, "An Efficient and Fault-Tolerant Solution for Distributed Mutual Exclusion," ACM Transactions on Computer Systems, Vol. 9, No. 1, Feb. 1991, pp. 1–20.

Scheduling

Required

1. C. A. Waldspurger and W. E. Weihl, "Lottery Scheduling: Flexible Proportional-Share Resource Management," Proceedings of the Symposium on Operating System Design and Implementation (OSDI), Nov. 1994, pp. 1–11.
2. F. Douglis, "Transparent Process Migration: Design Alternatives and the Sprite Implementation," Software Practice & Experience, Vol. 21, No. 8, 1991, pp. 757–785.

Optional

• M. Harchol-Balter and A. B. Downey, "Exploiting Process Lifetime Distributions for Dynamic Load Balancing," ACM Transactions on Computer Systems, Vol. 15, No. 3, Aug. 1997, pages 253–285.
• M. Seltzer, P. Chen, and J. Ousterhout, "Disk Scheduling Revisited," Proceedings of the Winter 1990 USENIX Conference, June 1990.
• B. L. Worthington, G. R. Ganger, and Y. N. Patt, "Scheduling Algorithms for Modern Disk Drives," Proceedings of the 1994 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, May 1994, pp. 241–251.

Real-Time Systems

Required

1. A. Burns, "Scheduling Hard Real-Time Systems: A Review," Software Engineering Journal, May 1991, pp. 116-128.
2. S. Brandt, S. Banachowski, C. Lin, and T. Bisson, "Dynamic Integrated Scheduling of Hard Real-Time, Soft Real-Time, and Non-Real-Time Processes," The IEEE Real-Time Systems Symposium (RTSS 2003), December, 2003.

Optional

• Scott Banachowski and Scott Brandt, "The BEST Scheduler for Integrated Processing of Best-effort and Soft Real-time Processes," Multimedia Computing and Networking 2002 (MMCN '02), January 2002.

Communication and distributed systems

Required

1. J. F. Shoch and J. A. Hupp, "The 'Worm' Programs—Early Experience with a Distributed Computation," Communications of the ACM, Vol. 25, No. 3, March 1982, pp. 172–180.
2. 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, pp. 3–23.
3. L. Lamport, "Time, Clocks, and the Ordering of Events in a Distributed System," Communications of the ACM, Vol. 21, No. 7, July 1978, pp. 558–565.
4. D. R. Cheriton and D. Skeen, "Understanding the Limitations of Causally and Totally Ordered Communication," Proceedings of the 14th Symposium on Operating Systems Principles (SOSP), December 1993, pp. 44–57.
5. Sape J. Mullender, Guido van Rossum, Andrew S. Tanenbaum, Robbert van Renesse, Hans van Staveren, "Amoeba--A Distributed Operating System for the 1990s," IEEE Computer, May 1990.
6. Rob Pike, Dave Presotto, Ken Thompson, Howard Trickey, "Plan 9 From Bell Labs," Proceedings fo the Summer 1990 UKUUG Conference, 1990.
7. John K. Ousterhout, Andrew R. Cherenson, Frederick Douglis, Michael N. Nelson, Brent B. Welch, "The Sprite Network Operating System," IEEE Computer, Vol. 21 No. 2, February 1988.

Optional

• P. Maniatis, M. Baker, "Secure History Preservation through Timeline Entanglement," Proceedings of the 11th USENIX Security Symposium, August 2002.

Reliability & fault tolerance

Required

1. R. Rodrigues, M. Castro, and B. Liskov, "BASE: Using Abstraction to Improve Fault Tolerance," Proceedings of the 18th ACM Symposium on Operating Systems Principles (SOSP '01), October 2001, pages 15–28.
2. A. Chou, J. Yang, B. Chelf, S. Hallem, and D. Engler, "An Empirical Study of Operating Systems Errors," Proceedings of the 18th ACM Symposium on Operating Systems Principles (SOSP), Oct. 2001, pp. 73–88.

Optional

• B. Liskov, S. Ghemawat, R. Gruber, P. Johnson, L. Shrira, and M. Williams, "Replication in the Harp File System," Proceedings of the 13th Symposium on Operating Systems Principles (SOSP), October 1991, pp. 226–238.
• J. R. Douceur and R. P. Wattenhofer "Optimizing File Availability in a Secure Serverless Distributed File System," Proceedings of the 20th Symposium on Reliable Distributed Systems, 2001, pp. 4–13.

Performance evaluation

Required

1. J. Ousterhout, "Why Aren't Operating Systems Getting Faster as Fast as Hardware?", Proceedings of the Summer 1990 USENIX Conference, June 1990, pp. 247–256.
2. M. Rosenblum, E. Bugnion, S. A. Herrod, E. Witchel, and A. Gupta, "The Impact of Architectural Trends on Operating System Performance," Proceedings of the 15th ACM Symposium on Operating Systems Principles (SOSP), December 1995, pp. 285–298.

Optional

• J. B. Chen, Y. Endo, K. Chan, D. Mazières, A. Dias, M. Seltzer, and M. D. Smith, "The Measured Performance of Personal Computer Operating Systems," Proceedings of the 15th ACM Symposium on Operating Systems Principles (SOSP), Dec. 1995, pp. 299–313.
• M. G. Baker, J. H. Hartman, M. D. Kupfer, K. W. Shirriff, and J. K. Ousterhout, "Measurements of a Distributed File System," Proceedings of the 13th Symposium on Operating Systems Principles (SOSP), October 1991, pp. 198–212.

Miscellanea

Required

1. R. Levin and D. D. Redell, "An Evaluation of the Ninth SOSP Submissions," Operating Systems Review, Vol. 17, No. 3, July 1983, pp. 35-40. [distributed by USENIX with permission]