CS240: Advanced Topics in Operating Systems

Autumn 2005 -- Dawson Engler


Announcements

Quiz 3 (Final) Statistics

17 exams were graded. Mean = 25, average = 25.0588235294118, std = 4.6296677558343

Local students can pick up your finals outside Prof. Engler's office (Gates 314)

Final Exam

(1) The Final is on Friday, Dec 9th. It's cumulative, open book/notes.

(2) The last homework is due Wed, Dec7th before class. Read the hints paper, and find five examples where the hints are obeyed or disobeyed from the papers we read this quarter. Local students bring the papers to class. SCPD students post your homework to cs240-aut0506-staff@lists.stanford.edu

Quiz Solutions

quiz1 solution (ps pdf)

quiz2 solution (ps pdf)

Quiz 2 (Midterm) Statistics

20 exams were graded. Mean = 28, average = 28.2, std = 5.66243391967949

Quiz 2 (Midterm)

(1) Quiz 2 will be on Friday, Nov 18th

(2) Post your quiz questions, one for each paper since Quiz 1 (excluding the network normalizer paper), to the class newsgroup(su.class.cs240) by Wed, Nov 16, 11:59PM.

(3) Here are some sample exams: questions and answers. Note that you are responsible for figuring out which answers correspond to which questions. Quiz 2 with answers from Winter 2005. More samples can be found through previous years' websites.

Quiz 2 and Final Dates

Quiz 2 will be on Friday, Nov 18th. The final exam will be on Friday, Dec 9th

Quiz 1 (Midterm) Statistics

So far, 18 exams were graded. Here are some statistics: mean = 32, average = 32.1111111111111, std = 9.29192495024824

Due to unknown delays, SCPD exams just came in today (Thu, 11/3). We are going to grade them ASAP.

Quiz 1 (Midterm)

(1) The first Quiz (Midterm) will be on Monday, Oct. 24th, in class, open book but close laptop. SCPD students do not need to come to campus to take the exam.

(2) Post your quiz questions, one for each paper, up to and including the two failure oblivious papers to the newsgroup (su.class.cs240) by Thursday, Oct. 20 11:59PM.

(3) Friday, Oct.21 will be a review session. Bring your quiz questions to the review session.

(4) Here are some sample questions and answers culled from the previous quarters' quizzes. Note that you are responsible for figuring out which answers correspond to which questions. Also check out Quiz 1 with answers from last Spring.


Class Abstract

Students will study advanced operating system topics and be exposed to recent developments in operating systems research. This course involves readings and lectures on classic and new papers. Topics: virtual memory management, synchronization and communication, file systems, protection and security, operating system structure and extension techniques, fault tolerance, and history and experience of systems programming.

Class Times

MWF 1:15PM - 2:05PM in Gates B03

Course Staff

Instructor

Dawson Engler
Office: 314 Gates
Telephone: (650) 723-0762
E-mail: engler@cs.stanford.edu
Office hours: By appointment

Teaching Assistant

Junfeng Yang
E-mail: yjf@stanford.edu
Office hours: Monday and Wednesday 2:15PM - 3:10PM
Location: Gates 324
Extra office hours before exams and by appointment.

Course Secretary

Jane Klickman
Office: 303 Gates
Phone: (650) 725-3726
E-mail: klickman@stanford.edu

Email

To contact the staff, please send email to cs240-aut0506-staff@lists.stanford.edu and prefix the subject line with "CS240" for a prompt response. Announcements from the staff will be sent via the cs240-aut0506-students@lists.stanford.edu mailing list to which any registered student will automatically be added.

Prerequisites

The prerequisite for this class is CS 140 (previously CS 240A) or the equivalent. It is necessary to have this background before taking the class, as we'll read a lot papers quickly without much time for catching up on the basics. The course assumes an understanding of topics in operating systems such as synchronization, virtual memory management, scheduling, and file systems.

The other requirement is that students be able to send and receive email, access the class newsgroup, access the class web page, and download and print postscript from the class web page. There will be very few handouts in the course, since most of the notes and other materials will be available only on the class web page.

Course Organization and Workload

The course consists of lectures, readings, and three exams. As the quarter progresses there may be ways to get extra credit. The two most important things to know about the class: (1) the main goal is to have interesting in-class discussions and (2) we recommend you read each paper at least twice, preferably more than a day in advance so that it sinks in.

Most of the work in this course consists of reading journal and conference papers. We will cover one paper for each class meeting. This class will be primarily discussion based (rather than organized around lectures). Active discussion will (hopefully) give you a non-trivial understanding of the material. The only way this approach can work is if you read the papers carefully. To encourage this, 40% of your class grade will come from class participation: this includes talking in class, as well as how you do on pop quizzes and (possibly) pop presentations. Class time will not be used to rehash the material in the papers. Instead, it will be used to highlight the important points and discuss some of the more interesting features. There will be as much as 10-15 hours of reading per week. Do not take this course unless you are willing and able to do a lot of reading.

Readings

There is no textbook for this course. The course is based on a collection of journal and conference papers that describe the history and state of the art in operating systems. Papers will be discussed in class in approximately the order that they appear on the reading list. You must read the papers before class. At a minimum we recommend two close readings. We will provide most papers online; those that are only available in hardcopy will be provided about a week before they are needed.

Grading Policy

The class is graded on a rough curve with an average grade being a B+. 40% of your grade will come from class participation, the other 60% will be based on two midterm exam scores and the final exam score. All three exams count. SCPD students will be graded just on exams (and any homeworks).

Exams

Two midterm exams and a final exam will be given in class. They will be open book (but not open laptop). The midterm exams are not cumulative, but the final exam is cumulative. A sample exam will be available along with sample solutions. Review sessions will be held before each exam.

Newsgroup

There is a class newsgroup, su.class.cs240, that can be used by members of the class to converse with each other. All course announcements will be put on to the class web page. The news group is a good place to advertise for study groups, ask questions of other students, etc.

Course Outline

This course makes no attempt to cover all the interesting topics in operating systems. Instead, we will cover a few topics in depth. The course is divided into the following general topic areas:

Virtual memory management
Discussions of virtual memory management implementations and recent work in virtual memory for multiprocessors, NUMA machines, large virtual address spaces, and other topics.
Synchronization and communication
Discussions of synchronization with an emphasis on monitors. Communication using remote procedure call.
File systems
Discussions of file system interfaces and disk storage management techniques.
Protection and security
Discussions of data security and authentication.
Extensions and fault tolerance
Discussions of mechanisms for implementing OS services at user level, OS structure and performance, reliability and availability of OS services.
History and experience
Historically important papers and experience reports by senior researchers in the field.

Reading List

Category/Date Title Author(s)
(M 9/26) The Rise of "Worse is Better" Richard Gabriel
Conc. (W 9/28) An Investigation of the Therac-25 Accidents Leveson and Turner
Conc. (F 9/30) Eraser: A Dynamic Data Race Detector for Multithreaded Programs Stefan Savage
Conc. (M 10/3) Experience with Processes and Monitors in Mesa Butler Lampson
Conc. (W 10/5) Capriccio: Scalable Threads for Internet Services Rob von Behren, Jeremy Condit, Feng Zhou, George C. Necula, and Eric Brewer
Why Threads Are a Bad Idea (for most purposes) John Ousterhout
Cooperative Task Management without Manual Stack Management (up to and including Section 3) Atul Adya, Jon Howell, Marvin Theimer, William J. Bolosky, John R. Douceur
Conc. (F 10/7) Threads cannot be implemented as a library AHans-J. Boehm
Requirements for Programming Language Memory Models Jeremy Manson, William Pugh
VM (M 10/10) Virtual Memory Management in the VAX/VMS Operating System Levy and Lipman
VM (W 10/12) Practical, Transparent, Operating System Support for Superpages Navarro, Iyer, Druschel, and Cox
VM (F 10/14) Memory Resource Management in VMware ESX Server Waldspurger
(M 10/17) Improving the Reliability of Commodity Operating Systems Swift, Bershad, Levy
(W 10/19) A Dynamic Technique for Eliminating Buffer Overflow Vulnerabilities (and Other Memory Errors) Rinard, Cader, Dumitran, Roy, Leu
Enhancing Server Availability and Security Through Failure-Oblivious Computing Rinard, Cader, Dumitran, Roy, Leu, Beebee
(F 10/21) Quiz 1 Review
(M 10/24) Quiz 1 (Midterm)
N/W (W 10/26) Eliminating Receive Livelock in an Interrupt-Driven Kernel Mogul and Ramakrishnan
N/W (F 10/28) The End to End Argument in System Design Saltzer, Reed, Clark
N/W (M 10/31) Network Intrusion Detection: Evasion, Traffic Normalization, and End-to-End Protocol Semantics Mark Handley, Vern Paxson, Christian Kreibich
FS (W 11/2) Design and Implementation of the SUN Network Filesystem Sandberg et al.
FS (F 11/4) Leases: An Efficient Fault-Tolerant Mechanism for Distributed File Cache Consistency Gray and Cheriton
FS (M 11/7) A Low-Bandwidth Network File System Muthitacharoen, Chen, and Mazieres
(W 11/9) MapReduce: Simplified Data Processing on Large Clusters Dean and Ghemawat
FS (F 11/11) The Design and Implementation of a Log-Structured File System Rosenblum and Ousterhout
(M 11/14) A Case for Redundant Arrays of Inexpensive Disks (RAID) Patterson, Gibson, and Katz
FS (W 11/16) Using Model Checking to Find Serious File System Errors Yang, Twohey, Engler, Musuvathi
(F 11/18) Quiz 2 (Midterm)
(M 11/21) No class. University holidays
(W 11/23) No class. University holidays
(F 11/25) No class. University holidays
Exp. (M 11/28) Application Performance and Flexibility on Exokernel Systems Kaashoek et. al
(W 11/30) Xen and the Art of Virtualization Barham et. al
(F 12/2) Scalability, Fidelity and Containment in the Potemkin Virtual Honeyfarm Vrable et. al
FS (M 12/5) Speculative execution in a distributed file system Nightingale et. al
Exp. (W 12/7) Hints for Computer System Design Butler W. Lampson
(F 12/9) Quiz 3 (Final)

Class Websites from Previous Quarters


Webpage maintained by Junfeng Yang