Honors Operating Systems

(Also known as CSCI-GA.3250-001)

Spring 2012
Class: Mondays and Wednesdays, 3:30-4:45pm, WWH 312
Office hours: On request, 715 Broadway, room 711

Robert Grimm
rgrimm@cs.nyu.edu

• Overview
• Schedule
• Resources

Overview

Honors Operating Systems is a graduate course on operating and distributed systems. It covers a wide range of systems research, ranging from historical perspectives to internet-scale services and mobile/pervasive computing. The class has two major components: (1) reading, reviewing, and discussing research papers, and (2) performing a term-long class project. The goals are to expose students to a wide variety of systems research, to provide them with an opportunity to perform systems design and implementation of their own, and to develop their communication skills.

Readings

Readings cover a wide range of research papers and must be completed before the corresponding class. Students also need to write a review for each assigned paper (to make sure everyone keeps up with the readings). Each review should be about a paragraph long and discuss in the student's own words (1) the main idea(s) of each paper, (2) the student's main criticisms (regarding soundness, methodology, presentation, etc.), and (3) relevance to current systems or future research directions. David Wetherall at the University of Washington has written a great guide to reviewing papers.

Reviews are submitted by emailing them in plain-text format (with hard line breaks after each line) to csci_ga_3250_001_sp12@cs.nyu.edu. Please make sure the subject specifies the paper title. The archive of all reviews is here. Paper reviews are due at 8am on the day of the corresponding class!

Projects

The goal for the projects is to gain experience with designing, implementing, and evaluating real systems. Projects are term-long and performed in groups of two or three students. Each group produces a final report, structured like a conference paper, and presents their results at the end of the course. Projects can either explore a new systems challenge, focusing more on design and implementation, or try to replicate a previously published paper's results, focusing more on implementation and evaluation. Topics are picked by students in consultation with the instructor.

To guide project groups through the term, there are several milestones along the way:

• Project proposal. In about two pages, describe the problem you intend to address and your proposed solution. You should also identify non-goals and resources you need to completing the project.
• Literature search. In about a page, identify related work and compare it with your own work. This milestone should form the foundation of the related work section of your final paper.
• Mid-term report. In about five pages, describe what you have achieved so far and the work still left to do. You should also describe problems you encountered and surprising or unexpected issues.
• Final report. The final report is a full-length paper (of 10-14 pages) and structured like a conference paper. Motivate your work, review related work, describe the design and implementation of your system, and provide an evaluation of its effectiveness. You also need to give the corresponding talk, with 20 minutes for the presentation and 10 minutes for questions.

The final project presentations are TBA. Reports are due before the presentations.

Exams

There is an open book, take home mid-term, but no final exam.

Prerequisites

Undergraduate operating systems. Additionally, experience with building large software systems and the ability to digest and review research papers are highly helpful.

Grading Policy

Roughly: 50% for readings, class participation, and mid-term, and 50% for class project. Missed reviews, however, will have a disproportionate negative impact on the final grade.

Collaboration Policy

Students are encouraged to discuss class topics and readings with each other. However, each student must write his/her reading review individually. Students in different project groups may help each other with general programming questions. However, students in different groups must not exchange code or use code from outside sources (such as the Internet) without explicit permission by the instructor.

Schedule

1. Introduction

   • (Jan 23) Overview of the course. Slides.

2. Historical Perspective

   • (Jan 25)
     • Per Brinch Hansen. The Nucleus of a Multiprogramming System. Communications of the ACM, 13(4):238–241, April 1970.
     • Dennis M. Ritchie and Ken Thompson. The UNIX Time-Sharing System. Communications of the ACM, 17(7):365–375, July 1974.
   • (Jan 30)
     • Jerome H. Saltzer. Protection and Control of Information Sharing in Multics. Communications of the ACM, 17(7):388–402, July 1974.

   Further readings:

   • Edsger W. Dijkstra. The Structure of the "THE"-Multiprogramming System. Communications of the ACM, 11(5):341–346, May 1968.
   • Jack B. Dennis and Earl C. van Horn. Programming Semantics for Multiprogrammed Computations. Communications of the ACM, 9(3):143–155, March 1966.

3. Structure and Organization

   • (Feb 1)
     • W. Wulf, E. Cohen, W. Corwin, A. Jones, R. Levin, C. Pierson, and F. Pollack. HYDRA: The Kernel of a Multiprocessor Operating System. Communications of the ACM, 17(6):337–345, June 1974.
     • R. Levin, E. Cohen, W. Corwin, F. Pollack, and W. Wulf. Policy/Mechanism Separation in Hydra. In Proceedings of the 5th ACM Symposium on Operating Systems Principles, pages 132–140, November 1975.
   • (Feb 6)
     • Jeffrey S. Chase, Henry M. Levy, Michael J. Feeley, and Edward D. Lazowska. Sharing and Protection in a Single-Address-Space Operating System. ACM Transactions on Computer Systems, 12(4):271–307, November 1994.
   • (Feb 8)
     • M. Frans Kaashoek, Dawson R. Engler, Gregory R. Ganger, Héctor Briceño, Russel Hunt, David Mazières, Tom Pinckney, Robert Grimm, and Ken Mackenzie. Application Performance and Flexibility on Exokernel Systems. In Proceedings of the 16th ACM Symposium on Operating Systems Principles, pages 52–65, October 1997.
     • Brian N. Bershad, Stefan Savage, Przemyslaw Pardyak, Emin Gün Sirer, Marc E. Fiuczynski, David Becker, Craig Chamgers, and Susan Eggers. Extensibility, Safety and Performance in the SPIN Operating System. In Proceedings of the 15th ACM Symposium on Operating Systems Principles, pages 267–283, December 1995.
   • (Feb 13)
     • Edouard Bugnion, Scott Devine, and Mendel Rosenblum. Disco: Running Commodity Operating Systems on Scalable Multiprocessors. In Proceedings of the 16th ACM Symposium on Operating Systems Principles, pages 143–156, October 1997.
     • Paul Barham, Boris Dragovic, Keir Fraser, Steven Hand, Tim Harris, Alex Ho, Rolf Neugebauer, Ian Pratt, and Andrew Warfield. Xen and the Art of Virtualization. In Proceedings of the 19th ACM Symposium on Operating Systems Principles, pages 164–177, October 2003.
   • (Feb 15)
     • 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. Corey: An Operating System for Many Cores. In Proceedings of the 8th USENIX Symposium on Operating Systems Design and Implementation, pages 43–57, December 2008.
     • Andrew Baumann, Paul Barham, Pierre-Evariste Dagand, Tim Harris, Rebecca Isaacs, Simon Peter, Timothy Roscoe, Adrian Schüpbach, and Akhilesh Singhania. The Multikernel: A New OS Architecture for Scalable Multicore Systems. In Proceedings of the 22nd ACM Symposium on Operating Systems Principles, pages 29–44, October 2009.

   Further readings:

   • Ellis Cohen and David Jefferson. Protection in the Hydra Operating System. In Proceedings of the 5th ACM Symposium on Operating Systems Principles, pages 141–160, November 1975.
   • Dawson R. Engler, M. Frans Kaashoek, and James O'Toole Jr. Exokernel: An Operating System Architecture for Application-Level Resource Management. In Proceedings of the 15th ACM Symposium on Operating Systems Principles, pages 251–266, December 1995.
   • Michael M. Swift, Brian N. Bershad, and Henry M. Levy. Improving the Reliability of Commodity Operating Systems. In Proceedings of the 19th ACM Symposium on Operating Systems Principles, pages 207–222, October 2003.
   • Michael M. Swift, Muthukaruppan Annamalai, Brian N. Bershad, and Henry M. Levy. Recovering Device Drivers. In Proceedings of the 6th USENIX Symposium on Operating Systems Design and Implementation, page 1–16, December 2004.
   • Silas Boyd-Wickizer, Austin T. Clements, Yandong Mao, Aleksey Pesterev, M. Frans Kaashoek, Robert Morris, and Nickolai Zeldovich. An Analysis of Linux Scalability to Many Cores. In Proceedings of the 9th USENIX Symposium on Operating Systems Design and Implementation, pages 1–16, October 2010.

4. Managing Concurrency

   • (Feb 22)
     • Thomas E. Anderson, Brian N. Bershad, Edward D. Lazowska, and Henry M. Levy. Scheduler Activations: Effective Kernel Support for the User-Level Management of Parallelism. ACM Transactions on Computer Systems, 10(1):53–79, February 1992.
   • (Feb 27)
     • Carl A Waldspurger and William E. Weihl. Stride Scheduling: Deterministic Proportional-Share Resource Management. MIT LCS Technical Report TM-528.
   • (Feb 29)
     • Jeffrey C. Mogul and K. K. Ramakrishnan. Eliminating Receive Livelock in an Interrupt-Driven Kernel. ACM Transactions on Computer Systems, 15(3):217–252, August 1997.

   Further readings:

   • Carl A. Waldspurger and William E. Weihl. Lottery Scheduling: Flexible Proportional-Share Resource Management. In Proceedings of the First USENIX Symposium on Operating Systems Design and Implementation, pages 1–11, November 1994.
   • Vivek S. Pai, Peter Druschel, and Willy Zwaenepoel. Flash: An Efficient and Portable Web Server. In Proceedings of the 1999 USENIX Annual Technical Conference, pages 199–212, June 1999.
   • Atul Adya, Jon Howell, Marvin Theimer, William J. Bolosky, and John R. Douceur. Cooperative Task Management Without Manual Stack Management. In Proceedings of the 2002 USENIX Annual Technical Conference, pages 289–302, June 2002.

5. Communication

   • (Mar 5)
     • Brian N. Bershad, Thomas E. Anderson, Edward D. Lazowska, and Henry M. Levy. Lightweight Remote Procedure Call. ACM Transactions on Computer Systems, 8(1):37–55, February 1990.
   • (Mar 7)
     • Michael D. Schroeder, Andrew D. Birrell, and Roger M. Needham. Experience with Grapevine: The Growth of a Distributed System. ACM Transactions on Computer Systems, 2(1):3–23, February 1984.
   • (Mar 19)
     • Miguel Castro and Barbara Liskov. Practical Byzantine Fault Tolerance and Proactive Recovery. ACM Transactions on Computer Systems, 20(4):398–461, November 2002. (Section 5 and the appendix are optional.)
   • (Mar 21)
     • Eric Jul, Henry Levy, Norman Hutchinson, and Andrew Black. Fine-Grained Mobility in the Emerald System. ACM Transactions on Computer Systems, 6(1):109–133, February 1988.

   Further readings:

   • Andrew D. Birrell and Bruce Jay Nelson. Implementing Remote Procedure Calls. ACM Transactions on Computer Systems, 2(1):39–59, February 1984.
   • J. H. Saltzer, D. P. Reed, and D. D. Clark. End-to-End Arguments in System Design. ACM Transactions on Computer Systems, 2(4):277–288, November 1984.
   • Amitanand S. Aiyer, Lorenzo Alvisi, Allen Clement, Mike Dahlin, Jean-Philippe Martin, and Carl Porth. BAR Fault Tolerance for Cooperative Services. In Proceedings of the 20th ACM Symposium on Operating Systems Principles, pages 45–58, October 2005.
   • Bjarne Steensgaard and Eric Jul. Object and Native Code Thread Mobility Among Heterogeneous Computers. In Proceedings of the 15th ACM Symposium on Operating Systems Principles, pages 68–77, December 1995.

6. Virtual Memory

   • (Mar 26)
     • Henry M. Levy and Peter H. Lipman. Virtual Memory Management in the VAX/VMS Operating System. IEEE Computer, 15(3):35–41, March 1982.
     • Richard Rashid, Avadis Tevanian, Michael Young, David Golub, Robert Baron, David Black, William Bolosky, and Jonathan Chew. Machine-Independent Virtual Memory Management for Paged Uniprocessor and Multiprocessor Architectures. In Proceedings of the Second International ACM Conference on Architectural Support for Programming Languages and Operating Systems, pages 31–39, October 1987.
   • (Mar 28)
     • Andrew W. Appel and Kai Li. Virtual Memory Primitives for User Programs. In Proceedings of the 4th International ACM Conference on Architectural Support for Programming Languages and Operating Systems, pages 96–107, April 1991.
   • (Apr 2)
     • M. Satyanarayanan, Henry H. Mashburn, Puneet Kumar, David C. Steere, and James J. Kistler. Lightweight Recoverable Virtual Memory. In Proceedings of the 14th ACM Symposium on Operating Systems Principles, pages 146–160, December 1993.

   Further readings:

   • Kai Li and Paul Hudak. Memory Coherence in Shared Virtual Memory Systems. ACM Transactions on Computer Systems, 7(4):321–359, November 1989.
   • Philip A. Bernstein. Introduction to Transaction Processing. Lecture slides for University of Washington's CSEP 545, Transaction Processing.

7. File Systems

   • (Apr 4)
     • Adam Sweeney, Doug Doucette, Wei Hu, Curtis Anderson, Mike Nishimoto, and Geoff Peck. Scalability in the XFS File System. In Proceedings of the USENIX 1996 Annual Technical Conference, pages 1–14, January 1996.
   • (Apr 9)
     • Mendel Rosenblum and John K. Ousterhout. The Design and Implementation of a Log-Structured File System. ACM Transactions on Computer Systems, 10(1):26–52, February 1992.
   • (Apr 11)
     • Michael N. Nelson, Brent B. Welch, and John K. Ousterhout. Caching in the Sprite Network File System. ACM Transactions on Computer Systems, 6(1):134–154, February 1988.
     • John H. Howard, Michael L. Kazar, Sherri G. Menees, David A. Nichols, M. Satyanarayanan, Robert N. Sidebotham, and Michael J. West. Scale and Performance in a Distributed File System. ACM Transactions on Computer Systems, 6(1):51–81, February 1988.
   • (Apr 16)
     • Atul Adya, William J. Bolosky, Miguel Castro, Gerald Cermak, Ronnie Chaiken, John R. Douceur, Jon Howell, Jacob R. Lorch, Marvin Theimer, and Roger P. Wattenhofer. FARSITE: Federated, Available, and Reliable Storage for an Incompletely Trusted Environment. In Proceedings of the 5th USENIX Symposium on Operating Systems Design and Implementation, pages 1–14, December 2002.

   Further readings:

   • Marshall K. McKusick, William N. Joy, Samuel J. Leffler, and Robert S. Fabry. A Fast File System for UNIX. ACM Transactions on Computer Systems, 2(3):181–197, August 1984.
   • Chandramohan A. Thekkath, Timothy Mann, and Edward K. Lee. Franigpani: A Scalable Distributed File System. In Proceedings of the 16th ACM Symposium on Operating System Principles, pages 224–237, October 1997.
   • Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung. The Google File System. In Proceedings of the 19th ACM Symposium on Operating System Principles, pages 29–43, October 2003.

8. Security

   • (Apr 18)
     • Jonathan S. Shapiro, Jonathan M. Smith, and David J. Farber. EROS: A Fast Capability System. In Proceedings of the 17th ACM Symposium on Operating Systems Principles, pages 170–185, December 1999.
   • (Apr 23)
     • Stephen Chong, Jed Liu, Andrew C. Myers, Xin Qi, K. Vikram, Lantian Zhen, and Xin Zheng. Secure Web Applications via Automatic Partitioning. In Proceedings of the 21st ACM Symposium on Operating Systems Principles, pages 31–44, October 2007.
   • (Apr 25)
     • Arvind Seshadri, Mark Luk, Elaine Shi, Adrian Perrig, Leendert van Doorn, and Pradeep Khosla. Pioneer: Verifying Code Integrity and Enforcing Untampered Code Execution on Legacy Systems. In Proceedings of the 20th ACM Symposium on Operating Systems Principles, pages 1–16, October 2005.

   Further readings:

   • Butler W. Lampson. Protection. In Proceedings of the 5th Princeton Symposium on Information Sciences and Systems, pages 437–443, Princeton, NJ, March 1971. Reprinted in ACM Operating Systems Review, 8(1):18–24, January 1974.
   • Andrew C. Myers and Barbara Liskov. Protecting Privacy Using the Decentralized Label Model. ACM Transactions on Software Engineering and Methodology, 9(4):410–442, October 2000.
   • Petros Efstathopoulos, Maxwell Krohn, Steve VanDeBogart, Cliff Frey, David Ziegler, Eddie Kohler, David Mazières, Frans Kaashoek, and Robert Morris. Labels and Event Processes in the Asbestos Operating Systems. In Proceedings of the 20th ACM Symposium on Operating Systems Principles, pages 17–30, October 2005.
   • Nickolai Zeldovich, Silas Boyd-Wickizer, Eddie Kohler, and David Mazières. Making Information Flow Explicit in HiStar. In Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation, pages 263–278, November 2006.
   • Maxwell Krohn, Alexander Yip, Micah Brodsky, Natan Cliffer, M. Frans Kaashoek, Eddie Kohler, and Robert Morris. Information Flow Control for Standard OS Abstractions. In Proceedings of the 21st ACM Symposium on Operating Systems Principles, pages 321–334, October 2007.

9. Mobile and Pervasive Computing

   • (Apr 30)
     • James J. Kistler and M. Satyanarayanan. Disconnected Operation in the Coda File System. ACM Transactions on Computer Systems, 10(1):3–25, February 1992.
   • (May 2)
     • Douglas B. Terry, Marvin M. Theimer, Karin Petersen, Alan J. Demers, Mike J. Spreitzer, and Carl H. Hauser. Managing Update Conflicts in Bayou, a Weakly Connected Replicated Storage System. In Proceedings of the 15th ACM Symposium on Operating Systems Principles, pages 172–182, December 1995.
     • Karin Petersen, Mike J. Spreitzer, Douglas B. Terry, Marvin M. Theimer, and Alan J. Demers. Flexible Update Propagation for Weakly Consistent Replicas. In Proceedings of the 16th ACM Symposium on Operating Systems Principles, pages 288–301, October 1997.
   • (May 7)
     • Robert Grimm, Janet Davis, Eric Lemar, Adam MacBeth, Steven Swanson, Thomas Anderson, Brian Bershad, Gaetano Borriello, Steven Gribble, and David Wetherall. System Support for Pervasive Applications. ACM Transactions on Computer Systems, 22(4):421–486, November 2004.

   Further readings:

   • Lily B. Mummert, Maria R. Ebling, M. Satyanarayanan. Exploiting Weak Connectivity for Mobile File Access. In Proceedings of the 15th ACM Symposium on Operating Systems Principles, pages 143–155, December 1995.
   • M. Satyanarayanan. The Evolution of Coda. ACM Transactions on Computer Systems, 20(2):85–124, May 2002.
   • Athicha Muthitacharoen, Benjie Chen, and David Mazières. A Low-Bandwidth Network File System. In Proceedings of the 18th ACM Symposium on Operating Systems Principles, pages 174–187, October 2001.

Resources

Mailing List

• csci_ga_3250_001_sp12@cs.nyu.edu

On Papers and Presentations

• David Wetherall's guide to reviewing papers
• Armando Fox's hints on paper writing and presentations