UNIVERSITY OF ATHENS
DEPARTMENT OF INFORMATICS & TELECOMMUNICATIONS

M 122. Advanced Operating Systems

Lectures (Fall 2017): Wednesdays 10:00-13:00 in Room G.

 

Name

E-mail

Office

Office Hours

Instructor: Mema Roussopoulou

mema -at* di *dot- uoa -dot* gr

A 38

By appt

 


Announcements

 

1) Please sign up on the Piazza class forum here. We will use the class forum to make important announcements as the semester proceeds regarding lectures, assignments, etc. You are thus, required to sign up and follow the class forum regularly.

2) A Note on Reviews : You are expected to turn in reviews on time -- that is, turn in a hardcopy in class on the day the reviwes are due. The review portion of your final grade will be based on a total of 19 reviews. The class schedule below contains a total of 23 papers, so this gives you some slack for weeks when it is difficult for you to submit a review on time.

3) For the final paper, each student should claim the paper session (three papers) from SOSP 2017 that he/she wants to read and present to the class. You should claim your paper session by editing the google doc found here. See below for details on final paper and presentation formats.

4) Final presentations are due in class on December 20, 2017.


Course Description

This is an advanced class on operating systems where we critically review some of the more influential operating systems research literature.   The goal of the course is to teach students the major principles of operating system design as presented in their original sources (papers).  We will be reviewing both “classic/historic” papers as well as modern papers on operating systems.  For many students, this is a first experience in reading research papers where key ideas were first presented.  This is in contrast to the typical undergraduate experience, where such ideas might be encountered as cursory descriptions in a textbook.  

 

Students will learn how to critically analyze a paper, pinpointing both strengths and weaknesses, and to identify open problems in systems research.  This involves careful critical reading.  Students should be prepared to read (and re-read) papers carefully and formulate questions and opinions on the paper prior to class.

 

Topics covered in this course include: virtual memory management, synchronization and communication, file systems, protection and security, operating systems structure, scheduling, fault tolerance, and history and experience programming systems.

This class is geared toward graduate students at all levels as well as advanced undergraduates. (Prerequisites include: Undergraduate Operating Systems and Undergraduate Systems Programming). If you have not taken the prerequisite courses, you cannot take this class.

 


Readings

The course has no textbook.  Readings will be research papers.  Links to papers are included in the class schedule below.


Assignments

This course will involve reading papers, writing reviews for papers, participating in class discussions, and a final paper.

Students will be required to write reviews for papers they read. Look here to get information on how to write a review. Reviews are to be turned in class in hardcopy form on the day the affiliated papers are discussed. Sample reviews will be posted on the class forum.

Students will actively participate in class discussions. For each paper, we will study the contribution of the paper, place this contribution in context of previous literature, critique the methodology used and the evaluation presented. Be prepared to come to class having read the paper carefully and ready to discuss questions or comments you have in detail.  Class participation is a portion of the overall grade, and an easy way for you to gain points in the class.

Note: You must have access to a printer so you may download, print copies of the papers (available below), and bring them to class for the discussions.  We recommend you scribble directly on a paper any notes or questions that arise as you are reading. In fact, taking detailed notes on the paper and then reading through them before writing your review and before coming to class is a good idea. You are also welcome to post any questions about the paper to the class forum if you like. Such posts can help start discussion in class and will certainly contribute to your class participation grade.

In addition to reviews and class participation, there will be a final paper and presentation. You will be reading, analyzing, and comparing a subset of papers from recent SOSP, Eurosys, and/or OSDI conferences. (These are top-tier systems research conferences.) A few higly-driven students may choose to do a project instead. Details on the format of the final paper and presentation are posted here.


Class Piazza Forum

Please sign up on the Piazza class forum here. I will use the class forum to make important announcements as the semester proceeds. Students can also use this forum to discuss concepts covered in class and post questions about class material. Students are required to follow the class forum regularly.

 


Grading

Reviews: 30%
Class Participation: 20%
Final Paper: 50%



Syllabus & Schedule (tentative)
(bibliography)

 

Date

Topic

Readings

Presenter

4/10

Course Overview

-- No reading --

Roussopoulou

11/10

Virtual Memory

Virtual Memory, Processes, and Sharing in MULTICS

Application-Controlled Physical Memory

Roussopoulou

18/10

OS Structure

On ì-kernel Construction

Unix Time-Sharing System

Roussopoulou

25/10

File Systems

UNIX FFS

LFS

Roussopoulou

1/11

(Distributed) File Systems

NFS

AFS

Roussopoulou

8/11

Threads versus Events

Intro to Programming with Threads

On the Duality of Operating System Structures

SEDA: An Architecture for Well-Conditioned, Scalable Internet Services (Read Sections 1 and 2)

Roussopoulou

22/11  

Threads versus Events

Why Threads are a Bad Idea

Why Events are a Bad Idea

Mesa


Roussopoulou

29/11

Data Sharing,

Race Detection

Capriccio

Eraser

Roussopoulou

6/12

Scheduling,

Reliability

Lottery Scheduling

Bugs as Deviant Behavior

Roussopoulou

13/12

Virtual Machines

Disco

Are VMMs microkernels done right?

Are VMMs microkernel done right?  (take 2)

Hype and Virtue

Roussopoulou

20/12

Presentations by students

Final presentations due in class for all students. Half of class will present one of their chosen SOSP 2017 papers.

Roussopoulou

10/1

Presentations by students


Experience Papers --

Systems Design

Observations on the Development of an Operating System (optional, will not be discussed in class)

Hints for Computer Systems Design (optional, will not be discussed in class)

Final Paper Due in class for all students. Remaining student presentations take place.

Students



Class Paper Bibliography

Robert C. Daley and Jack B. Dennis, “Virtual Memory, Processes, and Sharing in MULTICS.” Communications of  the ACM, Vol. 11, No. 5, May 1968, pp. 306-312.

Kieran Harty and David R. Cheriton, “Application-Controlled Physical Memory using External Page-Cache Management,” Proceedings of the Fifith International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), Boston, MA, October 1992, pp. 187-199.

J. Liedtke, “On Micro-Kernel Construction,” ACM SIGOPS Operating Systems Review, Vol 29, No 5, December 1995.

Dennis Ritchie and Ken Thompson, “The UNIX Time-Sharing System.” Communications of the ACM, Vol. 17, No. 7, July 1974, pp. 365-375.

Marshall Kirk McKusick, William N. Joy, Samuel J. Leffler and Robert S. Fabry, “A Fast File System for UNIX.”ACM Transactions on Computer Systems, Vol 2, No. 3, August 1984, pp. 181-197.

Mendel Rosenblum and John K. Ousterhout, “The Design and Implementation of a Log-Structured File System”, Proceedings of  the Thirteenth ACM Symposium on Operating Systems Principles, Operating Systems Review, Vol. 25, No. 5, Pacific Grove, California, October 1991, pp. 1-15.

R. Sandberg, D. Goldberg, S. Kleiman, D. Walsh, and B. Lyon, ``Design and Implementation of the Sun Network Filesystem'', Proc. USENIX Summer Conference, June 1985, pp. 119-130.

J. Howard, M. Kazar, S. Menees, D. Nichols, M. Satyanarayana, R. Sidebotham, M. West, “Scale and Performance in a Distributed File System”, ACM Trasactions on Computer Systems, Vol 6, No. 1, February 1988, p. 51-81.

A. Birrell. “An Introduction to Programming with Threads,” Research Report 35, DEC SRC, Jan 1989.

Hugh C. Lauer and Roger M. Needham, “On the Duality of Operating System Structures.” Proceedings of the Second International Symposium on Operating Systems, IRIA, Octover 1978, reprinted in Operating Systems Review, Vol. 13, No.2, April 1979, pp. 3-19.

John Ousterhout, “Why Threads are a Bad Idea (for most purposes),” Talk given at USENIX Technical Conference, January 25, 1996.

Rob von Behren, Jeremy Condit, and Eric Brewer, “Why Events are a Bad Idea (for high-concurrency servers),” Proceeding of the 10th Workshop on Hot Topics in Operating Systems”, May 2003.

Rob von Behren, Jeremy Condit, Feng Zhou, George C. Necula, and Eric Brewer, “Cappriccio: Scalable Threads for Internet Services”, Proceedings of the 19th Symposium on Operating Systems Principles, October 2003.

[NOT COVERED in CLASS, read and review on your own for Extra Credit] Atul Adya, Jon Howell, Marvin Theimer, William J. Bolosky, John Douceur,  “Cooperative Task Management without Manual Stack Management (or, Event-driven Programming is Not the Opposite of Threaded Programming).” PDF, Proceedings of the 2002 Usenix Annual Technical Conference, Monterey, CA 2002.

Butler W. Lampson and David D. Redell, “Experiences with Processes and Monitors in Mesa.” Communications of the ACM, Vol. 23, No. 2, February, 1980. pp. 105-117.

Stefan Savage, M. Burrows, G. Nelson, and Patrick Sobalvarro, and Tom Andersen, “Eraser: A Dynamic Data Race Detector for Multi-Threaded Programs,” ACM Symposium on Operating Systems Principles, October, 1997.

Tom Anderson, Brian Bershad, Ed Lazowska, and Hank Levy, “Scheduler Activations: Effective Kernel Support for the User-level Management of Parallelism,” ACM Transactions on Computer Systems, Vol. 10, pp. 53-79, February 1992.

Carl A. Waldspurger and William E. Weihl, “Lottery Scheduling: Flexible Proportional-Share Resource Management, Proceedings of the First Symposium on Operating System Design and Implementation, 1994, pp. 1-12.

Edouard Bugnion, Scott Devine, Mendel Rosenblum, “Disco: Running Commodity Operating Systems on Scalable Multiprocessors”. In Proceedings of 16th Symposium on Operating Systems Principles, 1997.

Steven Hand, Andrew Warfield, Keir Fraser, Evangelos Kotsovinos, and Dan Magenheimer, “Are Virtual Machine Monitors Microkernel done Right?”, Proceedings of the 10th Workshop on Hot Topics in Operating Systems, June 2005.

G Heiser, V Uhlig, and J LeVasseur, “Are Virtual Machine Monitors Microkernels done Right?”, SIGOPS Operating Systems Review, Vol 40, No 1, p. 95-99, 2006.

Timothy Roscoe, Kevin Elphinstone, Gernot Heiser, “Hype and Virtue”, Proceedings of the 11th Workshop on Hot Topics in Operating Systems (HotOS), May 2007.

Anita Borg, W. Blau, W. Graetsch, F. Herrmann, and W. Oberle, “Fault Tolerance under Unix”, Transactions on Computer Systems, Vol 7, No 1, p. 1-24, February 1989.

H. C. Lauer, “Observations on the Development of an Operating System”, ACM Symposium on Operating System Principles, also in Operating Systems Review vol. 15, no. 5, pp. 30-36, December 1981.

Butler Lampson, “Hints for Computer Systems Design”, 9th ACM Symposium on Operating Systems Principles, October 1983.