UNIVERSITY OF ATHENS
DEPARTMENT OF INFORMATICS & TELECOMMUNICATIONS
Lectures (Fall 2009): Wednesdays 13:00-16:00 in Aithousa E.
|
Name |
|
Office |
Office Hours |
|
mema -at* di *dot- uoa -dot* gr |
A 38 |
By appt |
Announcements
1) Please make sure you subscribe to the class mailing list. We will use this list to make important announcements as the semester proceeds. See directions below for how to subscribe.
2) Your (SOSP/OSDI) choices for the final paper are due by email at 13:00 on December 16. See details below for the logistics of the final paper.
3) The final paper is due in class on January 13. Please bring a hardcopy to class to turn in to instructor.
4) During the last class, students will present VERY briefly their final paper. The challenge here is to be able to present the MOST important points of each paper and provide your comparison in a MAXIMUM of 8 minutes.
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).
The course has no textbook.
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 due before each class by email. Send these as a single email to the Instructor with "Review for Day/Month" in the subject line, where Day/Month is the current lecture date. Please send reviews in plain ASCII text.
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 send any questions about the paper to the staff before class if you feel shy asking about a particular detail in the paper. There are no dumb questions!!
In addition to reviews and class participation, there will be a final paper. You must select three related papers from any of the SOSP or OSDI Conferences of the last 15 years. SOSP (ACM Symposium on Operating Systems Principles) and OSDI (USENIX Symposium on Operating Systems Design and Implementation) are the premier systems research conferences and occur in alternate years.
The papers you choose should be on the same topic (e.g., virtualization). (Note, if papers are on the same topic, the later papers will most certainly cite the earlier ones). Your paper will be a critical analysis of the three papers. You will summarize each paper and then compare and contrast the design, experimental methodology, and performance presented by the systems described in the three papers. Your paper should conclude with a summary opinion on the three papers, which you must justify. The opinion could be “The system described by Paper 1 clearly outperforms Paper 2’s system in aspects ABC for reasons XYZ.” Or, another opinion might be “Paper 3’s approach shows that Papers 1 and 2 approaches are inherently flawed because…”
Likely your opinion will NOT be a blanket statement (such as “Paper 2’s system is best overall.”) because nearly every system has limitations and design tradeoffs. More likely, your analysis and opinion will show that each system approach/implementation works well in certain circumstances (applications used, workloads, hardware configuration, etc.) and not as well in others. The papers you choose should NOT be any of the papers discussed in class, although you may certainly compare against a relevant paper discussed in class, if this helps frame your analysis. Length: a maximum of 5-6 pages, one page to summarize each paper plus 2-3 pages analysis.
Class Mailing List
Class mailing list: mde-518-class -at* di *dot- uoa -dot* gr. We will use this list to
send out any important announcements, so please be sure to subscribe. You can
subscribe to the mailing list by clicking
here
and filling out the form provided.
Grading
Reviews: 30%
Class Participation: 20%
Final Paper: 50%
Syllabus & Schedule (tentative)
(bibliography)
|
Date
|
Topic
|
|
Presenter
|
|
7/10 |
Course Overview |
-- No reading -- |
Roussopoulou |
|
14/10 |
Virtual Memory |
Roussopoulou |
|
|
21/10 |
Virtual Memory / OS Structure |
Roussopoulou |
|
|
28/10 |
-- No class (holiday) -- |
-- |
-- |
|
4/11 |
File
Systems |
- |
|
|
11/11 |
(Distributed) File Systems |
Roussopoulou |
|
|
18/11 |
Threads |
Roussopoulou |
|
|
25/11 |
Threads versus Events |
Roussopoulou |
|
|
2/12 |
Data Sharing, Race Detection |
Roussopoulou |
|
|
9/12 |
Scheduling |
Roussopoulou |
|
|
16/12 |
Virtual Machines |
Are VMMs
microkernels done right? |
Roussopoulou |
|
6/1 |
-- No class
(holiday)-- |
-- |
-- |
|
13/1 |
Experience Papers -- Systems Design |
Observations on the Development of an Operating System Hints for Computer Systems Design Final Paper Due. Brief presentations by each student. |
|
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,
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,
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.