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

Papers

For each week 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. 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)

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

• Questions from past OS exams (pdf)
• Self Assessment (pdf)

Week 2 - January 18: System Evaluation and Benchmarking

Read and provide summaries for the following papers:

• 1. lmbench: an extensible micro-benchmark suite
  C. Staelin, Software--Practice and Experience, vol. 35, no. 11, May 2005, pp. 1079-1105.
  
• 2. 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.
  

Week 3 - January 25: System Design: Microkernels and Performance

Read and provide summaries (due at the beginning of class on Jan. 25th) for the following papers:

• 1. The impact of operating system structure on memory system performance
  J. B. Chen and B.N. Bershad, Proceedings of the 14th SOSP, 1994, pp. 120--133.
• 2. The performance of microkernel-based systems
  H. Hartig, M. Hohmuth, J. Liedtke, and S. Schonberg, Proceedings of the 16th SOSP, 1997, pp. 66-77.

Week 4 - February 1: Communication Models

Read and provide summaries (due at the beginning of class on Feb. 1) for the following papers:

• 1. Implementing Remote Procedure Call
  A.D. Birrell and B.J. Nelson, ACM Transactions on Computer Systems, vol. 2, no. 1, February 1984, pp. 39-59.
• 2. TreadMarks: Shared Memory Computing on Networks of Workstations
  C. Amza, A.L. Cox, S. Dwarkadas, P. Keleher, H. Lu, R. Rajamony, W. Yu, and W. Zwaenepoel, IEEE Computer, vol. 29, no. 2, February 1996, pp. 18-28.

Week 5 - February 8: Threads and Concurrency

No summaries required for this week. Read and be prepared to discuss the following papers:

• 1. Using threads in interactive systems: a case study
  C. Hauser, C. Jacobi, M. Theimer, B. Welch, M. Weiser, Proceedings of the 14th SOSP, 1994, pp. 94-105.
• 1. Capriccio: scalable threads for internet services
  R. von Behren, J. Condit, F. Zhou, G. C. Necula, E. Brewer, Proceedings of the 19th SOSP, 2003, pp. 268-281.

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

• Birrell's Introduction to Programming with Threads, referred to frequently in the Hauser et al. paper lays out key challenges and paradigms for using threads.
• 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 - February 15: File System Integrity

Read and provide summaries (due at the beginning of class on Feb. 15) 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.
• 2. Soft updates: a solution to the metadata update problem in file systems
  G.R. Ganger, M.K. McKusick, C.A.N. Soules, Y.N. Patt, ACM Transactions on Computer Systems, vol. 18, no. 2, May 2000, pp. 127-153.

The papers above describe two file system implementation techniques that offer alternate views on the problem of ensuring file systems are in a recoverable state following a crash. Both assume that a small window of vulnerability for new data is acceptible to users. The first assumes that large caches will capture all reads and thus optimizes for writes. The second eliminates the historical expense of synchronous I/O operations by enabling integrity-maintaining write caching for metadata.

Additional readings that compare the performance of these approaches to other file systems are:

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

Week 7 - March 1: Scalable distributed file systems

Read and provide summaries (due at the beginning of class on Mar. 1) for the following papers:

• 1. Serverless Network File Systems
  T. E. Anderson, M. D. Dahlin, J. M. Neefe, D. A. Patterson, D. S. Roselli, R. Y. Wang, in Proceedings of the 15th SOSP, 1995, pp. 109-126.
• 2. The Google File System
  S. Ghemawat, H. Gobioff, S.-T. Leung, in Proceedings of the 19th SOSP, 2003, pp. 29-43.

The papers above represent two points in a large space of work on distributed file and storage systems. The first paper discusses xFS, which attempts to improve scalability and reliability by removing the centralized file server from the system architecture. The second paper takes a different approach, borrowing concepts from Network-Attached Secure Disks (NASD) to implement a large scale, high performance storage system.

Week 8 - March 8: Virtual Memory Management

Read and provide summaries (due at the beginning of class on Mar. 8) for the following papers:

• 1. A new page table for 64-bit address spaces
  M. Talluri, M. D. Hill, Y. A. Khalidi, in Proceedings of the 15th SOSP, 1995, pp. 184-200.
• 2. Transparent Operating System Support for Superpages
  J. Navarro, S. Iyer, P. Druschel, A. Cox, in Proceedings of the 5th OSDI, 2002, pp. 89-104.

Week 9 - March 15: I/O Prefetching

Read and provide summaries (due at the beginning of class on Mar. 15) for the following papers:

• 1.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.
• 2.Operating System I/O Speculation: How Two Invocations Are Faster Than One
  K. Fraser, F. Chang, in Proceedings of the USENIX Annual Technical Conference, 2003, pp. 325-338.

Week 10 - March 22: Scheduling and Resource Accounting

Read and provide summaries (due at the beginning of class on Mar. 22) for the following papers:

• 1.Making Paths Explicit in the Scout Operating System
  D. Mosberger and L. L. Peterson, in Proceedings of the 2nd OSDI, 1996, pp. 153-167.
• 2.Resource Containers: A New Facility for Resource Management in Server Systems
  G. Banga, P. Druschel, J. C. Mogul, in Proceedings of the 3rd OSDI, 1999, 14 pages.

Week 11 - March 29: Virtual Machines

Read and provide summaries (due at the beginning of class on Mar. 29) for the following papers:

• 1.Disco: running commodity operating systems on scalable multiprocessors
  E. Bugnion, S. Devine, K. Govil, M. Rosenblum, in Proceedings of the 16th SOSP, 1997, pp. 143-156. (Also published in ACM Transactions on Computer Systems (TOCS), vol. 15, no. 4, November 1997, pp. 412-447.)
• 2. 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.

Week 12 - April 5: Using Virtual Machines

Read and provide summaries (due at the beginning of class on Apr. 5) for the following papers:

• 1.Terra: a virtual machine-based platform for trusted computing
  T. Garfinkel, B. Pfaff, J. Chow, M. Rosenblum, D. Boneh, in Proceedings of the 19th SOSP, 2003, pp. 193-206.
• 2.Debugging Operating Systems with Time-Traveling Virtual Machines
  S. T. King, G. W. Dunlap, P. M. Chen, in Proceedings of the 2005 Usenix Annual Technical Conference, 2005, pp. 1-15. (General Track best paper)

Week 13 - April 12: Fault Tolerance

Read and provide summaries (due at the beginning of class on Apr. 12) for the following papers:

• 1.The Byzantine Generals Problem
  L. Lamport, R. Shostak, M. Pease, in ACM Transactions on Computer Systems, vol. 4, no. 3, July 1982, pp. 382-401.
• 2. Practical Byzantine fault tolerance
  M. Castro, B. Liskov, Proceedings of the 3rd Symposium on Operating Systems Design and Implementation (OSDI'99), February 1999, pp. 173 - 186.