CSC 2227S | Spring 2014 | Readings




General Links Home page Readings Summaries Projects Project Ideas

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

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.

To enter your paper reviews, go here.

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 13: 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. 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.

Week 2 - January 23: Early Systems (10am-12noon, BA5205)

presented by Angela Demke Brown

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

Week 3 - January 27: A Tour of OS Designs

Read and provide summaries for the following papers:

  1. An open operating system for a single-user machine
    Butler Lampson and Robert S. Sproull, in Proceedings of the 7th ACM Symposium on Operating Systems Principles, 1979, pp. 98--105.
  2. LOCUS: A Network Transparent, High Reliability Distributed System
    G. Popek, B. Walker, J. Chow, D. Edwards, C. Kline, G. Rudisin, and G. Thiel, in Proceedings of the 8th ACM Symposium on Operating Systems Principles, 1981, pp. 169--177.

Additional suggested reading

There are many classic papers on different operating systems designs. Here are just a few more that are worth reading.

Week 4 - Feb. 3: Performance and Flexibility

Read and provide summaries for the following papers:

  1. 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:
  2. 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.
    (It may be a good idea to go through the original exokernel paper on the additional reading list as well.)

Additional suggested reading

There are a wide range of papers that address OS performance and flexibility, many of them coming from the microkernel camp. A related line of work looks at extending OS functionality by downloading code into the kernel (we will be looking at one specific method for this later in the term).

Week 5 - Feb. 10: Concurrency

Read and provide summaries for the following papers:

  1. 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:
  2. MapReduce: Simplified Data Processing on Large Clusters
    Jeffrey Dean and Sanjay Ghemawat, in Proc. of the 6th USENIX Symposium on Operating System Design and Implementation, Dec. 2004.
    Presented by:

Additional suggested reading

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

Week 6 - Feb. 24: OS Specialization and Non-blocking Synchronization.

Read and provide summaries for the following papers:

  1. Threads and input/output in the synthesis kernel
    Henry Massalin and Calton Pu, in Proc. of the 12th ACM Symposium on Operating Systems Principles, Dec. 1989, pp. 191-201.
    Presented by:
  2. The synergy between non-blocking synchronization and operating system structure (ps)
    Michael Greenwald and David Cheriton, in Proc. of the 2nd Usenix Symposium on Operating System Design and Implementation, Oct. 1996, pp. 123-136.
    Presented by:

Additional suggested reading

Week 7 - Mar 3: Scheduling and Resource Accounting

Read and provide summaries for the following papers:

  1. 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:
  2. 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.
    Presented by:

Additional suggested reading

The currently fashionable solution to the problems posed in these papers is virtualization. Here are a few related papers that take a different approach.

Week 8 - Mar. 10: Local File Systems

Read and provide summaries for the following papers:

  1. 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:
  2. Rethink the sync
    Edmund B. Nightingale, Kaushik Veeraraghavan, Peter M. Chen and Jason Flinn, in Proc. of the 7th USENIX Symposium on Operating System Design and Implementation, Nov. 2006, pp. 1-14.
    Presented by:

Additional suggested reading

Many papers have been written on the subject of file system performance and integrity. These are just a small sample. The proceedings of the USENIX Conference on File and Storage Technology (FAST) are a great source for file systems readings.

Week 9 - Mar. 17: Distributed File Systems

Read and provide summaries for the following papers:

  1. 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:
  2. The Google file system
    Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung, in Proceedings of the nineteenth ACM Symposium on Operating Systems Principles, 2003, pp. 29--43.

Additional suggested reading

Week 10 - Mar. 24: Virtualization and Memory Management (in VMs)

Read and provide summaries for the following papers:

  1. 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:
  2. Memory Resource Management in VMware ESX Server
    Carl A. Waldspurger, in Proc. of the 5th Usenix Symposium on Operating System Design and Implementation, Dec. 2002, pp. 181-194.
    Presented by:

Additional suggested reading

Once again, whole courses could be offered on the subject of virtualization. Here are some papers that provide useful background, or alternate approaches.

Week 11 - Mar. 31: Multiprocessor / Multicore / Heterogeneous Operating Systems

Read and provide summaries for the following papers:

  1. Tornado: Maximizing Locality and Concurrency in a Shared Memory Multiprocessor Operating System
    Ben Gamsa, Orran Krieger, Jonathan Appavoo, and Michael Stumm, in Proc. of the 3rd Usenix Symposium on Operating System Design and Implementation, Feb. 1999, pp. 87-100.
    Presented by:
  2. Corey: An Operating System for Many Cores
    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. In Proc. of the 8th USENIX Symposium on Operating System Design and Implementation, Dec. 2008, pp. 43-57.
    Presented by:

Additional suggested reading

Week 12 - Apr. 7: Languages and Systems

Read and provide summaries for the following papers:

  1. Safe Kernel Extensions Without Run-Time Checking
    George C. Necula, Peter 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:
  2. 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:

Additional suggested reading

-->