CSC 2227S | Spring 2010 | Readings

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.

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 11: 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)
• OS Self Assessment (pdf)
• Concurrency Self Assessment (pdf) (Skip 8-25, 32-33, 36, 40, 43-48, 52)

Week 2 - January 18: Early Systems

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 25: A Tour of OS Designs

Read and provide summaries for the following papers:

4. 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.
5. StarOS, a Multiprocessor Operating System for the Support of Task Forces
   Anita K. Jones, Robert J. Chansler Jr., Ivor Durham, Karsten Schwans and Steven R. Vegdahl, in Proceedings of the 7th ACM Symposium on Operating Systems Principles, 1979, pp. 117--127.
6. 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.

• Medusa: an experiment in distributed operating system structure
  John K. Ousterhout, Donald A. Scelza, and Pradeep S. Sindhu, in Communications of the ACM, vol. 23, no. 2, February 1980, pp. 92--105.
• The structuring of systems using upcalls
  David D. Clark, in Proceedings of the 10th ACM Symposium on Operating Systems Principles, 1985, pp. 171--180.

Week 4 - Feb. 1

Read and provide summaries for the following papers:

7. The Impact of Operating. System Structure on Memory System Performance
   J. Bradley Chen and Brian N. Bershad, in Proc. of The 14th Symposium on Operating System Principles, pp. 120-133.
   Presented by: Tomasz Nykiel
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: Hyonho Lee

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

• One of many Mach papers: 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.
• MIT's exokernel (taking the microkernel idea to the limit) Exokernel: An Operating System Architecture for Application-Level Resource Management
  Dawson R. Engler, M. Frans Kaashoek and James W. O'Toole, in Proc. of the 15th ACM Symposium on Operating Systems Principles, Dec. 1995, pp. 251-266.
• 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.
  
• Flexibility in support of research: The Flux OSKit: a substrate for kernel and language research
  Bryan Ford, Godmar Back, Greg Benson, Jay Lepreau, Albert Lin, and Olin Shivers, in Proc. of the 16th ACM Symposium on Operating Systems Principles, Oct. 1997, pp. 38-51.
• Protecting against bad kernel extensions: Dealing With Disaster: Surviving Misbehaved Kernel Extensions(ps)
  Margo I. Seltzer, Yasuhiro Endo, Christopher Small, and Keith A. Smith, in Proc. of the 2nd Usenix Symposium on Operating System Design and Implementation, Oct. 1996, pp. 213-227.

Week 5 - Feb. 8: Concurrency

Read and provide summaries for the following papers:

9. 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: Svitlana Tumanova
10. 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: yaowei

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 - OS Specialization and Non-blocking Synchronization.

Read and provide summaries for the following papers:

11. Threads and input/output in the synthesis kernal
    Henry Massalin and Calton Pu, in Proc. of the 12th ACM Symposium on Operating Systems Principles, Dec. 1989, pp. 191-201.
    Presented by: yaowei
12. 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: Hyonho Lee

Additional suggested reading

• Optimistic incremental specialization: streamlining a commercial operating system
  Calton Pu, Tito Autrey, Andrew Black, Charles Consel, Jon Inouye, Lakshmi Kethana, Jonathan Walpole, and Ke Zhang, in Proceedings of the fifteenth ACM Symposium on Operating Systems Principles, 1995, pp. 314--321.
• Pragmatic Nonblocking Synchronization for Real-Time Systems
  Michael Hohmuth and Hermann Hartig, in Proceedings of the 2001 USENIX Annual Technical Conference, 2001, pp. 217--230.

Week 7 - Scheduling and Resource Accounting

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: Tomasz Nykiel
14. 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: Svitlana Tumanova

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.

• Resource containers as implemented by Sun: Solaris Zones: Operating System Support for Consolidating Commercial Workloads
  Daniel Price and Andrew Tucker. In Proceedings of the 18th Large Installation Systems Administration Conference (USENIX LISA '04).
• Containers as a form of virtualization: Container-based operating system virtualization: a scalable, high-performance alternative to hypervisors
  Stephen Soltesz, Herbert Pötzl, Marc E. Fiuczynski, Andy Bavier and Larry Peterson. In Proc. of EuroSys 2007.
• Focusing on communication-oriented systems: Making Paths Explicit in the Scout Operating System
  David Mosberger and Larry L. Peterson. In Proc. of 2nd Symposiom on Operating System Design and Implementation, 1996.

Week 8 - Local File Systems

Read and provide summaries for the following papers:

15. 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: Andy Hwang
16. 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: Ryan Yang

Additional suggested reading

Many papers have been written on the subject of file system performance and integrity. These are just a small sample.

• File System Logging Versus Clustering: A Performance Comparison
  M. Seltzer, K. A. Smith, H. Balakrishnan, J. Chang, S. McMains, V. Padmanabhan, Usenix Annual Technical Conference, January, 1995.
• Journaling Versus Soft Updates: Asynchronous Meta-data Protection in File Systems
  M.I. Seltzer, G.R. Ganger, M.K. McKusick, K.A. Smith, C.A.N. Soules, C.A. Stein, Usenix Annual Technical Conference, June 2000.
• Generalized file system dependencies
  Christopher Frost, Mike Mammarella, Eddie Kohler, Andrew de los Reyes, Shant Hovsepian, Andrew Matsuoka and Lei Zhang, in Proc. of the 21st ACM Symposium on Operating Systems Principles, Oct. 2007, pp. 307-320.
  

Week 9 - Distributed File Systems

Read and provide summaries for the following papers:

17. 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: Philip Patchin
18. CA-NFS: A Congestion-Aware Network File System
    Alexandros Batsakis, Randal Burns, Arkady Kanevsky, James Lentini, and Thomas Talpey. In Proc. of the 7th USENIX Conference on File and Storage Technologies, Feb. 2009, pp. 99-110.(FAST'09 Best Paper award)
    Presented by: Ryan Yang

Additional suggested reading

Distributed file systems are a cornerstone of modern datacenters. Here is one representative example.

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

Week 10 - Virtualization

Read and provide summaries for the following papers:

19. 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: Michael Mior
20. Operating System Support for Virtual Machines
    Samuel T. King, George W. Dunlap, and Peter M. Chen. In Proc. of the 2003 USENIX Annual Technical Conference, June 2003, pp. 71-84.
    Presented by: suprio

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.

• Classic paper defining requirements for virtualization: Formal Requirements for Virtualizable Third Generation Architectures
  Gerald J. Popek and Robert P. Goldberg. Communications of the ACM, Vol. 17, No. 7, July 1974, pp. 412-421.
• SimOS, the precursor to VMWare: Complete Computer System Simulation: The SimOS Approach
  Mendel Rosenblum, Stephen A. Herrod, Emmett Witchel, Anoop Gupta. IEEE Parallel & Distributed Technology: Sytems & Technology, Vol. 3, No. 4, 1995, pp. 34-43.
• Server virtualization: Scale and performance in the Denali isolation kernel
  Andrew Whitaker, Marianne Shaw and Steven D. Gribble. In Proc. of the 5th USENIX Symposium on Operating systems design and implementation, Dec. 2002.

Week 11 - Memory Management (and Virtualization)

Read and provide summaries for the following papers:

21. 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: Philip Patchin
22. Difference Engine: Harnessing Memory Redundancy in Virtual Machines
    Diwaker Gupta, Sangmin Lee, Michael Vrable, Stefan Savage, Alex C. Snoeren, George Varghese, Geoffrey M. Voelker, and Amin Vahdat. In Proc. of the 8th USENIX Symposium on Operating System Design and Implementation, Dec. 2008, pp. 309-322. (OSDI'08 Jay Lepreau Best Paper Award)
    Presented by: Michael Mior

Additional suggested reading

• A recent paper from the Xen folks: Satori: Enlightened page sharing
  Grzegorz Milos, Derek G. Murray, Steven Hand and Michael A. Fetterman. In Proc. of the 2009 USENIX Annual Technical Conference.

Week 12 - Multiprocessor / Multicore Operating Systems

Read and provide summaries for the following papers:

23. 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: Andy Hwang
24. 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: suprio

Additional suggested reading

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

Week 13 - Languages and Systems

Read and provide summaries for the following papers:

25. 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: Peter Feiner
26. 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: Peter Feiner

Additional suggested reading

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