CSC 2227S: Topics in the Design and Implementation of Operating Systems

Papers

For each meeting, readings are assigned. Usually, the readings will consist of two or three computer systems papers. The papers selected for this course are either classic papers or papers from recent top conferences. You are expected to read these papers thoroughly and summarize them BEFORE arriving at class on Wednesdays.

Each paper will be briefly presented by a student in the class, who will also lead the discussion of that paper. For each class meeting, we identify the topic and papers below; for each, we also try to identify good sources for background reading and for further investigation.

Electronic versions are linked where available (access will be denied for IP addresses outside of UofT). When electronic versions are not available, paper copies will be provided in class at least a week in advance.

(NOTE: This schedule is not set in stone. Some changes may be made to this schedule during the term)

Week 1 - January 12: Welcome to CSC 2227

This first meeting will be largely organizational in nature. In it, we will discuss how the class is going to work and what will be covered. In addition, we will very rapidly recap stuff you should already know, discussing what defines operating systems and distributed systems and what makes them continue to be interesting after all these years, and overviewing how the various topics in the course fit together.

There are no readings for this week, but the following items are intended to help you refresh your memory of operating systems. These are to help you prepare for the course and assess your own knowledge of the pre-requisite material. Sample solutions to the OS exam questions will be posted next week.

• First Lecture notes
• Questions from past OS exams (pdf)
• Self Assessment (pdf)

Week 2 - Early Systems

presented by Angela Demke Brown

Jan. 17

Read and provide summaries for the following papers:

• 1. The Structure of the "THE"-Multiprogramming System
  Edsger. W. Dijkstra, Communications of the ACM, vol. 11, no. 5, May 1968, pp. 341-346.
• 2. The Nucleus of a Multiprogramming System
  Per Brinch Hansen, Communications of the ACM, vol. 13, no. 4, April 1970, pp. 238-241,250.

Jan. 19

Read and summarize the following paper:

• 3. HYDRA: The Kernel of a Multiprocessor Operating System
  W. Wulf, E. Cohen, W. Corwin, A. Jones, R.Levin, C. Pierson, F. Pollack, Communications of the ACM, vol. 17, no. 6, June 1974, pp. 337-345.

Additional suggested reading (to be added)

Week 3 - Operating System Structure

Jan. 24

Read and provide summaries for the following papers:

• 4. On the Duality of Operating System Structures
  Hugh C. Lauer, Roger M. Needham, Proc. Second International Symposium on Operating Systems, IRIA, Oct. 1978, reprinted in Operating Systems Review, vol. 13, no. 2, April 1979, pp. 3-19.
  presented by Shvetank Jain
• 5. Medusa: an experiment in distributed operating system structure
  John K. Ousterhout, Donald A. Scelza, Pradeep S. Sindhu, Communications of the ACM, vol. 23, no. 2, Feb. 1980, pp. 92-105.
  presented by Adin Scannell

Jan. 26

Read and summarize the following paper:

• 6. The structuring of systems using upcalls
  David D. Clark, Proc. of the Tenth ACM Symposium on Operating Systems Principles, December, 1985, pp. 171-180.
  presented by Stephen Rumble

Additional suggested reading (to be added)

Week 4 - Flexibility and Performance

Jan. 31

Read and provide summaries for the following papers:

• 7. The Duality of Memory and Communication in the Implementation of a Multiprocessor Operating System
  Michael Young, Avadis Tevanian, Richard Rashid, David Golub, Jeffrey Eppinger, Jonathan Chew, William Bolosky, David Black,Robert Baron, in Proc. of the 11th ACM Symposium on Operating Systems Principles, 1987, pp. 63-76.
  presented by Tom Walsh
• 8. The Performance of Micro-kernel-based Systems
  Hermann Härtig, Michael Hohmuth, Jochen Liedtke, Sebastian Schönberg, Jean Wolter, in Proc. of the 16th ACM Symposium on Operating Systems Principles, Oct. 1997, pp. 66-77.
  presented by Vladan Djeric

Feb. 2

Read and summarize the following paper:

• 9. Application performance and flexibility on exokernel systems
  M. Frans Kaashoek, Dawson R. Engler, Gregory R. Ganger, Hector M. Briceño, Russell Hunt, David Mazières, Thomas Pinckney, Robert Grimm, John Jannotti, Kenneth Mackenzie, in Proc. of the 16th ACM Symposium on Operating Systems Principles, Oct. 1997, pp. 52-65.
  presented by Kiran Gollu

Additional suggested reading (to be added)

Week 5 - Concurrency

Feb. 7

Read and provide summaries for the following papers:

• 10. The performance implications of thread management alternatives for shared-memory multiprocessors
  Thomas E. Anderson, Edward D. Lazowska, Henry M. Levy, in IEEE Transactions on Computers, vol. 38, no. 12, Dec. 1989, pp. 1631-1644.
  presented by Angela Demke Brown
• 11. Scheduler activations: effective kernel support for the user-level management of parallelism
  Thomas E. Anderson, Brian N. Bershad, Edward D. Lazowska, Henry M. Levy, in Proc. of the 13th ACM Symposium on Operating Systems Principles, Sept. 1991, pp. 95-109.
  presented by Gennady Pekhimenko

Feb. 9

Read and summarize the following paper:

• 12. Capriccio: scalable threads for internet services
  Rob von Behren, Jeremy Condit, Feng Zhou, George C. Necula, Eric Brewer, in Proc. of the 19th ACM Symposium on Operating Systems Principles, Oct. 2003, pp. 268-281.
  presented by Adin Scannell

Additional suggested reading

The following items provide some additional background and perspectives on the challenges of programming with threads:

• Birrell's Introduction to Programming with Threads lays out key challenges and paradigms for using threads.
• Hauser et al's Using threads in interactive systems: a case study examines ways that threads are used in practice.
• Ousterhout's 1996 invited talk for the Usenix Technical Conference, Why threads are a bad idea (for most purposes)
• Boehm's 2005 PLDI paper on why Threads Cannot be Implemented as a Library

Week 6 - Scheduling and Resource Accounting

Feb. 14

Read and provide summaries for the following papers:

• 13. Lottery Scheduling: Flexible Proportional-Share Resource Management
  Carl A. Waldspurger, William E. Weihl, in Proc. of the 1st USENIX Symposium on Operating System Design and Implementation, Nov. 1994, 11 pages.
  presented by Waqas ur Rehman
• 14.Making Paths Explicit in the Scout Operating System
  David Mosberger and Larry L. Peterson, in Proc. of the 2nd USENIX Symposium on Operating System Design and Implementation, Oct. 1996, pp. 153-167.

Feb. 16

Read and summarize the following paper:

• 15.Resource Containers: A New Facility for Resource Management in Server Systems
  Gaurav Banga, Peter Druschel, Jeffrey C. Mogul, in Proc. of the 3rd USENIX Symposium on Operating System Design and Implementation, Feb. 1999, 14 pages.

Additional suggested reading (to be added)

Feb. 19-23: Reading Week, No Classes

Week 7 - Distributed Systems

Feb. 28

Read and provide summaries for the following papers:

• 16. A Comparison of Two Distributed Systems: Amoeba and Sprite
  F. Douglis, M. F. Kaashoek, A. S. Tanenbaum, J.K. Ousterhout, Computing Systems, vol. 4, no. 3, December 1991, pp. 353-384.
  presented by Angela Demke Brown
• 17. Cluster-Based Scalable Network Services
  A. Fox, S. D. Gribble, Y. Chawathe, E. A. Brewer, P. Gauthier, in Proc. of the 16th ACM Symposium on Operating System Principles, October 1997, pp. 78-91.
  presented by Tom Walsh

Mar. 2

Read and summarize the following paper:

• 18. Scale and Performance in a Distributed File System
  J. Howard, M. Kazar, et. al, ACM Transactions on Computer Systems, vol. 6, no. 1, February 1988, pp. 51-81.
  presented by Michael Jurka

Week 8 - File Systems and I/O

Mar. 7

Read and provide summaries for the following papers:

• 19. The Design and Implementation of a Log-Structured File System
  M. Rosenblum, J. Ousterhout, ACM Transactions on Computer Systems, vol. 10, no. 1, February 1992, pp. 26-52.
  presented by Gennady Pekhimenko
• 20. The Rio file cache: surviving operating system crashes
  P. M. Chen, W. T. Ng, S. Chandra, C. Aycock, G. Rajamani, D. Lowell, in Proc. of the 7th Intl. Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS-VII), Oct. 1996, pp. 74-83
  presented by Michael Jurka

Mar. 9

Read and summarize the following paper:

• 21. Fbufs: a high-bandwidth cross-domain transfer facility
  P. Druschel, L. L. Peterson, in Proc. of the 14th ACM Symposium on Operating System Principles, Dec. 1993, pp. 189-202.
  presenter needed

Week 9 - Virtualization

Mar. 14

Read and provide summaries for the following papers:

• 22. Cellular disco: resource management using virtual clusters on shared-memory multiprocessors
  K. Govil, D. Teodosiu, Y. Huang, M. Rosenblum, ACM Transactions on Computer Systems, vol. 18, no. 3, August 2000, pp. 229-262.
  (Don't be intimidated by the length of this paper - its just the journal version of the 16-page SOSP paper, which has larger fonts and pictures. Feel free to read the SOSP version if you prefer to carry less paper.)
  presented by Kiran Gollu (on Friday)
• 23. Xen and the art of virtualization
  P. Barham, B. Dragovic, K. Fraser, S. Hand, T. Harris, A. Ho, R. Neugebauer, I. Pratt, A. Warfield, in Proceedings of the 19th SOSP, 2003, pp. 164-177.
  presented by Andrew Miklas

Mar. 16

Read and summarize the following paper:

• 24.A Comparison of Software and Hardware Techniques for x86 Virtualization
  K. Adams, O. Ageson, in Proc. of the 12th Intl. Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS-X11), Oct. 2006, pp. 2-13.
  presented by Waqas ur Rehman

Week 10 - Mar. 21/23 Project Work Week, No Classes

Week 11 - Virtual Memory

Mar. 28

• 25. Taming the Memory Hogs: Using Compiler-Inserted Releases to Manage Physical Memory Intelligently
  A. D. Brown, T. C. Mowry, in Proceedings of the 4th OSDI, 2000, pp. 31-44.
  presented by Joe Whitney
• 26. Dynamic Tracking of Page Miss Ratio Curve for Memory Management
  P. Zhou, V. Pandey, J. Sundaresan, A. Raghuraman, Y. Zhou, S. Kumar, in Proc. of the 11th Intl. Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS-XI), Oct. 2004, pp. 177-188.
  presented by Tom Walsh

Mar. 30

• 27. Memory Resource Management in VMware ESX Server
  C. Waldspurger, in Proc. of the 5th Usenix Symposium on Operating System Design and Implementation, Dec. 2002, pp. 181-194.
  presented by Shvetank Jain

Week 12 - Languages and Systems

Apr. 4

• 28. Bugs as deviant behavior: a general approach to inferring errors in systems code
  D. Engler, D. Y. Chen, S. Hallem, A. Chou, B. Chelf, in Proc. of the 19th ACM Symposium on Operating System Principles, Oct. 2001, pp. 57-72.
  Quoting Dawson Engler: "This paper has some of my favorite ideas, though unfortunately I can't say the same for the writing."
  presented by Vladan Djeric
• 29. Safe Kernel Extensions Without Run-Time Checking
  G. Necula, P. Lee, in Proc. of the 2nd Usenix Symposium on Operating System Design and Implementation, Oct. 1996, pp. 229-243.
  Winner of the 2006 ACM SIGOPS Hall of Fame Award for most influential paper appearing in OSDI at least 10 years in the past.
  presented by Joe Whitney

Apr. 6 - Good Friday, no class

Week 13 - More Languages and Systems

Apr. 11

• 30. Extensibility safety and performance in the SPIN operating system
  B. N. Bershad, S. Savage, P. Pardyak, E. G. Sirer, M. E. Fiuczynski, D. Becker, C. Chambers, S. Eggers, in Proc. of the 15th ACM Symposium on Operating System Principles, Dec. 1995, pp. 267-283.
  presented by Andrew Miklas
• 31. Language Support for Fast and Reliable Message-based Communication in Singularity OS
  M. Fahndrich, M. Aiken, C. Hawblitzel, O. Hodson, G. Hunt, J. R. Larus, S. Levi, in Proc. of the 2006 EuroSys Conference, April 2006, pp. 177-190.
  presented by Stephen Rumble

Apr. 13

• Wrap-up. No new papers.