G22.3250-001 Honor Operating Systems

Fall 2008
Prof. Lakshminarayanan Subramanian
Tue-Thu 3:30-4:45, WWH 102
Office Hours:  Tue 5:00- 6:00, 715 Broadway, Room 706


Honors OS is a graduate course on operating systems. The goal of the course is to cover a broad array of research topics in computer systems, and to engage you in top-flight systems research. The class has two major components: (1) reading, reviewing, and discussing research papers, (2) a design paper and (3) performing a research project. 

This is a discussion-based class where each class would cover 1-2 important research papers on a specific aspects of operating systems design. Students are expected to read the papers before the class and submit reviews about the paper "before" the class.  Students in this class are expected to work on a systems research project that should lead to project paper of  publishable quality.  In addition, each project should get a working prototype of their system which will be displayed in a Fall Showcase demo session at the end of the term.

Prerequisites: Undergraduate operating systems background is a must. The course project would involve substantial programming; hence, programming experience is essential. 

Grading Policy

The main work of this class is to read papers frequently and deeply, while working toward a group research project of publishable quality.  Each student will be individually responsible for writing up a short summary of every paper. The summaries are due before 12 PM on the day of the corresponding class. There will be no exams in this class. Instead the class will have a "short" design paper on how you would go about designing an OS for programmable cellphones (Note: Symbian OS is going open source soon!). This design paper (maximum 5 pages in 10pt, two-column format excluding references) is due on the 15th of November. More details will be given in the class. 

Research projects are a critical aspect of the course.  Your goal is to do some quality systems research; that is, to add to our understanding of how to build systems.  Research projects must be written up in a term paper, and will be presented in a poster in a departmental mini-conference in the Fall Showcase.  Suggested project ideas will be provided by the instructor.  Potential projects include implementation or analysis of some piece of an OS, a DBMS, or an internet service; extending one of these systems with new functionality; or measurement and analysis of existing systems with the goal of better understanding issues in system design. 

Overall Grading:

Lectures and Readings

There is no textbook required. We will read and discuss 2-4 papers per week. All of the papers for the class will be available on-line (if paper is not on the class web-page, search for the paper online).

Paper Summaries

For every assigned paper, students must turn in a reading summary before 12 PM on the day of the corresponding lecture. Summaries should be e-mailed to "honorsosfall08@gmail.com" with the subject title "Paper Summary: Date of the Class". Summaries should not only summarize the ideas of the paper but also describe at least one aspect you liked and one criticism of the paper. (Just a simple summary based on abstract/intro/conclusion will NOT be accepted!). The goal is to learn how to review a research paper.

 Part 1:  OS structure and Information Protection

Tue 9/2 Introduction and Project Topics
OS Basics (Undergraduate concepts revisited)
Thu 9/4 Classics (Part I)

The UNIX Time-Sharing System 
Dennis M. Richie and Ken Thompson

Anatomy of the Linux OS.
Tue 9/9 Classics (part II)

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

Protection and Control of Information Sharing in Multics.
Jerome Saltzer
Communications of the ACM, 17(7):388-402, July 1974
Thu 9/11 OS Design and Structure

Extensibility, Safety and Performance in the SPIN Operating System,
Brian Bershard et al.
Proceedings of the 15th ACM Symposium on Operating System Principles, December 1995. 
Tue 9/16 Exokernel: an operating system architecture for application-level resource management. (PS)
Dawson R. Engler, M. Frans Kaashoek, and James O'Toole Jr.
In the Proceedings of the 15th ACM Symposium on Operating Systems Principles (SOSP '95),
Thu 9/18 Host Security and Firewalls: Guest Lecture (Jayanth Kannan, UC Berkeley)

Firewall Gateways, Chapter 3 of Firewalls and Internet Security
Repelling the Wily Hacker, Cheswick and Bellovin (1st ed).

Bro: A System for Detecting Network Intruders in Real-Time
Vern Paxson.

A secure environment for untrusted helper applications: confining the wily hacker
Goldberg, Wagner, Thomas, Brewer.
Tue 9/23

Secure Operating Systems

Making information flow explicit in HiStar.
Nickolai Zeldovich, Silas Boyd-Wickizer, Eddie Kohler, and David Mazières.
In Proceedings of the Seventh Symposium on Operating Systems Design and Implementation (OSDI 2006).

Labels and event processes in the Asbestos operating system.
Steve VanDeBogart, Petros Efstathopoulos, Eddie Kohler, Maxwell Krohn, Cliff Frey, David Ziegler, Frans Kaashoek, Robert Morris, and David Mazières. .
In ACM Transactions on Computer Systems, A version appeared in Proceedings of the 20th ACM Symposium on Operating System Principles, 2005.

Part 2: File Systems, Storage and Virtual Memory

Thu 9/25

File system Structure

A Fast File System for UNIX

McKusick, Joy, Leffler and Fabry

Analysis and Evolution of Journaling File Systems

Tue 9/30 File Sysem Organization

The Design and Implementation of a Log-Structured File System
Rosenblum and Ousterhout

The HP AutoRAID Hierarchical Storage System
Wilkes, Golding, Staelin and Sullivan 
Thu 10/2 Transactional Storage

ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-ahead Logging , 2-up version
C. Mohan et al.

Flexis: A Transactional Storage System
Rusty Sears and Eric Brewer
Tue 10/7 Virtual Memory

Virtual Memory Primitives for User Programs

Andrew W. Appel and Kai Li, Proc. ASPLOS IV, 1991, pp.96-107

Lightweight Recoverable Virtual Memory
M. Satyanarayanan, Henry H. Mashburn, Puneet Kumar, David C. Steere, and James J. Kistler
Thu 10/9

Scale and Performance in a Distributed File System

John H. Howard, et al.
Tue 10/14 No Class

Part 3: Concurrency and Scheduling

Thu 10/16 Locks and Concurrency

Granularity of Locks and Degrees of Consistency in a Shared Database
Gray et al.
Tue 10/21 Processes and Monitors

Experience with Processes and Monitors in Mesa
Butler Lampson and David Redell
Thu 10/23 Scheduling

Lottery Scheduling: Flexible Proportional-Share Resource Management
Waldspurger and Weihl

Borrowed-Virtual-Time (BVT) scheduling: supporting latency-sensitive threads in a general-purpose scheduler
Kenneth J. Duda and David R. Cheriton, Proc. 17th SOSP, Dec. 1999, pp.261-276
Tue 10/28 Scheduling (contd)

A Hierarchical Fair Service Curve Algorithm for Link-Sharing, Real-Time and Priority Service,
I. Stoica, H. Zhang and T. S. E. Ng, in Proceedings of SIGCOMM'97, Cannes, France, 1997, pp. 249-262.

Part 4: VM Design

Thu 10/30
VM Design

Xen and the Art of Virtualization

P. Barham, B. Dragovic, K Fraser, S. Hand, T. Harris, A. Ho, R. Neugebauer, I. Pratt and A. Warfield.
Tue 11/4 Sandboxing

Vx32: Lightweight User-level Sandboxing on the x86,
Bryan Ford and Russ Cox. USENIX 2008.

Scalability, Fidelity and Containment in the Potemkin Virtual Honeyfarm,
Michael Vrable, Justin Ma, Jay chen, David Moore, Erik Vandekieft, Alex C. Snoeren, Geoffrey M. Voelker and Stefan Savage,
Proceedings of the ACM Symposium on Operating System Principles (SOSP), Brighton, UK, October 2005.

Part 5: RPC + Networking basics

Thu 11/6 RPC

Lightweight Remote Procedure Call.
Brian N. Bershad, Thomas E. Anderson, Edward D. Lazowska, and Henry M. Levy.
ACM Transactions on Computer Systems, 8(1):37-55, February 1990.
Tue 11/11 Networking: Overview of basics

Part 6: Bugs, Reliability and Security

Thu 11/13 OS Bugs

Bugs as Deviant Behavior: A General Approach to Inferring Errors in Systems Code (postscript) (PDF). 
Dawson Engler, David Yu Chen, Seth Hallem, Andy Chou, and Benjamin Chelf.
Appeared in: Proceedings of the Eighteenth ACM Symposium on Operating Systems Principles, 2001.

Checking System Rules Using System-Specific, Programmer-Written Compiler Extensions (postscript) (PDF). 
Dawson Engler, Benjamin Chelf, Andy Chou, and Seth Hallem.
Appeared in: Proceedings of the 4th Symposium on Operating System Design and Implementation.
Tue 11/18 Code Checking and Software Protection

XFI: Software Guards for System Address Spaces.
Ulfar Erlingsson, Martin Abadi, Michael Vrable, Mihai Budiu, George Necula.
In Proceedings of Operating System Design and Implementation (OSDI'06), Seattle, 2006.

CCured: Type-Safe Retrofitting of Legacy Software,
George C. Necula, Jeremy Condit, Matthew Harren, Scott McPeak, Westley Weimer.
In ACM Transactions on Programming Languages and Systems (TOPLAS), Vol 27, No 3, May 2005.
Thu 11/20 OS Reliability

Improving the Reliability of Commodity Operating Systems.
Michael M. Swift, Brian N. Bershad, and Henry M. Levy.
In Proceedings of the 19th ACM Symposium on Operating Systems Principles, pages 207-222, Bolton Landing, New York, October 2003.

Recovering Device Drivers.
Michael M. Swift, Muthukaruppan Annamalai, Brian N. Bershad, and Henry M. Levy.
In Proceedings of the 6th USENIX Symposium on Operating Systems Design and Implementation, page 1-16, San Francisco, CA, December 2004.

Part 7: New Environments

Tue 11/25

Corey: An Operating System for Many Cores
Silas Boyd-Wickizer, Massachusetts Institute of Technology; Haibo Chen, Rong Chen, and Yandong Mao, Fudan University; Frans Kaashoek, Robert Morris, and Aleksey Pesterev, Massachusetts Institute of Technology; Lex Stein and Ming Wu, Microsoft Research Asia; Yuehua Dai, Xi'an Jiaotong University; Yang Zhang, Massachusetts Institute of Technology; Zheng Zhang, Microsoft Research Asia

Tue 12/2 Sensor Networks

mergence of Networking Abstractions and Techniques in TinyOS
Philip Levis, Sam Madden, David Gay,  Joseph Polastre, Robert Szewczyk, Alec Woo, Eric Brewer, and David Culler,
First Symposium on Network Systems Design and Implementation

TinyOS: An Operating System for Sensor Networks 
J. Hill, P. Levis, S. Madden, A. Woo, J. Polastre, C. Whitehouse, R. Szewczyk, C. Sharp, D. Gay,  M. Welsh, D. Culler and E. Brewer
Thu 12/4
Final Lecture: Energy Adaptation

Cooperative I/O
: a novel I/O semantics for energy-aware applications
Andreas Weissel, Bjorn Beutel and Frank Bellosa
OSDI 2002

Energy Aware Adaptation for Mobile Applications
Jason Flinn and M. Satyanarayanan
SOSP 1999
Tue 12/9
Project Presentations in Class
Thu 12/11
Project Demo in Fall Showcase
Mon 12/15 Project paper Submission