CSE 221: Graduate Operating Systems

Section A: Tuesdays and Thursdays, 2:00-3:20, Room HSS 1128A
Section B: Tuesdays and Thursdays, 3:30-4:50, Room HSS 1128A

Course Instructor: Prof. Joseph Pasquale
- Office hours: by appointment (send email), in 3112 EBU3B (CSE Building).

Teaching Assistant: Ming Kawaguchi (please include CSE221 in subject of e-mails)
- Office hours: Mon/Wed, 5-6, in B240A EBU3B (CSE basement), or by appointment.

CSE221 webboard

Message of the Day

The course is over. Congratulations on completing, and good luck with your future studies.

Synopsis

This is an advanced class on operating systems where we critically review some of the more influential operating systems research literature. As a result of taking this class, you will learn the following:

Major principles of operating system design from original sources. We will be reviewing both older ("classic") and modern papers on operating systems. For many of you, this is your introduction to reading papers where key ideas were first presented, as opposed to textbooks which generally contain distilled summaries of these ideas.
How to analyze a technical paper. This involves critical reading, driven by questions you formulate prior to, during, and after reading (and rereading).
How to communicate effectively. The class format is question/answer, "Socratic" style. It may feel uncomfortable at first, but you will get the hang of it (and it will serve you well outside of this class). You will learn how to think and respond in real time.

Course Reading

Throughout your career, especially if you go into research, you will have to deal with the problem of staying current with an ever-growing body of research literature. As you progress, you will find that you have less and less time to spend reading papers. Consequently, it is important to learn how to get the most out of papers in the shortest amount of time.

The first problem is to determine what to read. Given the immense amount of written material that exists and continues to be generated, finding good papers by trial and error can be very inefficient. Fortunately, there are forums where the filtering is done for you; conferences such as SOSP and journals such as TOCS have developed a reputation for the level of scrutiny they use for accepting papers. These and other good forums are the sources of the papers that form our reading list. The papers form a good mix of the old and the new. These include classics -- papers that describe seminal ideas that have stood the test of time -- and modern papers that are a sampling of trends in current research. Keep in mind that these papers are a small subset of the good (even great) papers out there that could not be included due to space.

The second problem is getting the most out of a paper in the shortest amount of time. You must learn how to quickly identify what a paper is about, always seeking to identify the point -- the "big idea" -- of the paper. By developing a familiarity with the OS literature, you will then be able to compare a paper to other works, noting improvements, mistakes, and trends. Hopefully, this process will help you develop a taste for what is and isn't worth working on, an important quality for being a successful researcher.

Finally, this class involves A LOT of reading. Do your best to keep up. Do not be discouraged if, especially at first, you need to read a paper many times before you begin to understand it; this is normal. Make sure you allot enough time to do so.

Schedule (tentative)

Thursday, January 10

J. Fotheringham, Dynamic Storage Allocation in the Atlas Computer, Including an Automatic Use of a Backing Store, Communications of the ACM, Vol. 4, Issue 10, Oct 1961, pp. 435-436. (in class)

Tuesday, January 15

E. W. Dijkstra, The Structure of the "THE"-Multiprogramming System, Communications of the ACM, Vol. 11, No. 5, May 1968, pp. 341-346.
P. B. Hansen, The Nucleus of a Multiprogramming System, Communications of the ACM, Vol. 13, No. 4, April 1970, pp. 238-241, 250.

Thursday, January 17

B. Lampson, Protection, Operating Systems Review, Vol. 8, No. 1, January 1974, pp. 18-24.
J. H. Saltzer, Protection and the Control of Information Sharing in Multics, Communications of the ACM, Vol. 17, No. 7, July 1974, pp. 388-402.

Tuesday, January 22

A. Bensoussan, C. T. Clingen and R. C. Daley, The Multics Virtual Memory: Concepts and Design, Communications of the ACM 15, 5 (May 1972), 308-318.
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, Vol. 17, No. 6, June 1974, pp. 337-345.

Thursday, January 24

D. M. Ritchie, The UNIX Time-sharing System - A Retrospective, Bell System Technical Journal, Vol. 57, No. 6 (part 2), July-Aug. 1978.
B. W. Lampson and H. E. Sturgis, Reflections on an Operating System Design, Communications of the ACM, Vol. 19, No. 5, May 1976, pp. 251-265.

Tuesday, January 29

H. C. Lauer and R. M. Needham, On the Duality of Operating System Structures, Proc. Second International Symposium on Operating Systems, IR1A, Oct. 1978 (reprinted in Operating Systems Review, Vol. 13, No. 2, April 1979, pp. 3-19).
B. W. Lampson and D. D. Redell, Experience with Processes and Monitors in Mesa, Communications of the ACM, Vol. 23, No. 2, February 1980, pp. 105-117.

Thursday, January 31

R. P. Goldberg, A Survey of Virtual Machine Research, IEEE Computer, Vol. 7, No. 4, June 1974, pp. 34-45.
L. H. Seawright and R. A. MacKinnon, VM/370: A study of multiplicity and usefulness, IBM Systems Journal, Vol 18, No 1, 1979, pp. 4-17.

Tuesday, February 5

D. R. Cheriton, M. A. Malcolm, L. S. Melen, G. R. Sager, Thoth, a portable real-time operating system Communications of the ACM, Vol. 22, Issue 2, Feb 1979, pp. 105-115.
R. F. Rashid and G. G. Robertson, Accent: A communication oriented network operating system kernel, Proc. Eighth ACM Symposium on Operating Systems Principles (SOSP), Pacific Grove, CA, 1981, pp. 64-75.

Thursday, February 7

D. R. Cheriton and W. Zwaenepoel, The Distributed V Kernel and its Performance for Diskless Workstations, Proc. Ninth Symposium on Operating Systems Principles (SOSP), November 1983, pp. 129-140.
M. Accetta et al., Mach: A new kernel foundation for UNIX development, Proc. USENIX Summer Conference, Atlanta, GA, 1986, pp. 93-112.

Tuesday, February 12

NO CLASSES

Thursday, February 14

O. Babaoglu and W. Joy, Converting a Swap-Based System to do Paging in an Architecture Lacking Page-Reference Bits, Proc. Eighth ACM Symposium on Operating System Principles (SOSP), December 1981, 78-86.
R. Carr and J. Hennessy, WSCLOCK-A Simple and Effective Algorithm for Virtual Memory Management, Proc. Eighth ACM Symposium on Operating System Principles (SOSP), December 1981, 87-95.

Tuesday, February 19

A D Birrell and B J Nelson, Implementing Remote Procedure Calls, ACM Transactions on Computer Systems (TOCS), Vol 2, No 1, February 1984, pp 39-59.
R Sandberg, D. Goldberg, S. Kleiman, D. Walsh, B. Lyon, Design and Implementation of the Sun Network Filesystem, Proc. Summer 1985 USENIX Conference, June 1985.

Thursday, February 21

Marshall K. McKusick, William N. Joy, Samuel J. Leffler, and Robert S. Fabry, A Fast File System for Unix, ACM Transactions on Computer Systems (TOCS), 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, Proc. 13th ACM Symposium on Operating Systems Principles (SOSP), December 1991, pp. 1-15.

Tuesday, February 26

C. A. Waldspurger and W. E. Weihl, Lottery Scheduling: Flexible Proportional-Share Resource Management, Proc. First USENIX Symposium on Operating System Design and Implementation, November, 1994, pp. 1-11.
G. Banga, P. Druschel, J. Mogul, Resource Containers: A New Facility for Resource Management in Server Systems, Proc. Third Symposium on Operating System Design and Implementation (OSDI-III), New Orleans, LA, February, 1999, pages 45-58.

Thursday, February 28

R. Wahbe, S. Lucco, T. E. Anderson, S. L. Graham, Efficient Software-based Fault Isolation, Proc. Fourteenth ACM symposium on Operating Systems Principles (SOSP), 1993, pp. 203-216.
G. C. Necula and P. Lee, Safe Kernel Extensions Without Run-Time Checking, Proc. 2nd Symposium on Operating Systems Design and Implementation (OSDI), Seattle, Washington, October 1996, pp. 229-243.

Tuesday, March 4

T. von Eicken, A. Basu, V. Buch, W. Vogels, U-Net: a user-level network interface for parallel and distributed computing, Proc. Fifteenth ACM Symposium on Operating Systems Principles (SOSP), 1995, pp. 40-53.
V. S. Pai, P. Druschel, W. Zwaenepoel, IO-lite: a unified I/O buffering and caching system, Proc. Third Symposium on Operating Systems Design and Implementation (OSDI), February 1999, pp. 15-28.

Thursday, March 6

C. Waldspurger, Memory Resource Management in VMware ESX Server, Proc. 5th Symposium on Operating Systems Design and Implementation (OSDI), December 2002, pp. 181-194.
P. Barham, B. Dragovic, K. Fraser, S. Hand, T. Harris, A. Ho, R. Neugebauer, I. Pratt, and A. Warfield, Xen and the Art of Virtualization, Proc. Nineteenth Symposium on Operating System Principles (SOSP), October 2003, pp. 164-177.

Tuesday, March 11

B. W. Lampson, Hints for Computer System Design, Proc. Ninth ACM Symposium on Operating System Principles (SOSP), October 1983, pp. 33-48.
Saltzer and Schroeder, End-to-End Arguments in System Design, ACM Transactions on Computer Systems (TOCS), Vol. 2, No. 4, November 1984, pp. 277-288.

Thursday, March 13

Final project presentations

Grading

20% Class participation
20% One optional written paper study
30-40% Final paper (in teams of 3)
30-40% Final exam