CSE 221: Graduate Operating Systems (Winter 2019)

Date and Time: Mondays and Wednesdays, 3:30-4:50, Room CSE 4140

Course Instructor: Prof. Joseph Pasquale
- Office hours: Mondays 2-3, in CSE 3112

Teaching Assistant: Erin McGinnis
- Office hours: 8:00-9:50am, Mon/Wed in EBU3B B250A, and by appt

Synopsis

This is a graduate 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 a number of classic papers in 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 quickly get accustomed (and it will serve you well outside of this class). You will learn how to think and respond in real time.

Prerequisite

The prerequisite for the class is CSE 120 (Principles of Computer Operating Systems), or the equivalent offered at other universities. This class ASSUMES you have this background; if you do not, I strongly recommend you reconsider taking this class and first take CSE 120, as it will be very difficult for you without this background.

Class Attendance

As will be discussed in our first meeting, class attendance is very important. If you have a conflict and can't make class, you'll need to drop, as this is not the kind of class where you can simply do the work outside of class. If you cannot make a particular class meeting, it will be your responsibility to find out what happened from other students.

Grading

30% Class attendance/participation
30% Final paper
40% Final exam (Wed 03/20/19, 3:00PM-5:59PM, CSE Bldg room 2154)

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. These will primarily be the "classics," i.e., papers that describe seminal ideas that have stood the test of time. Keep in mind that these papers are a small subset of the good 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.

Reading List (tentative)

Monday, January 7

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)

Wednesday, January 9

F. J. Corbato, M. M. Daggett, R. C. Daley, An Experimental Time-Sharing System, In Proc. AFIPS 1962 SJCC, Vol. 21, Spartan Books, New York, 335-344.

Monday, January 14

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.

Wednesday, January 16

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.
D. G. Bobrow, J. D. Burchfiel, D. L. Murphy, and R. S. Tomlinson, TENEX, a Paged Time Sharing System for the PDP-10, Communications of the ACM, Vol. 15, No. 3, March 1972, pp. 135-143.

Monday, January 21

University holiday - no class

Wednesday, January 23

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.
B. Lampson, Protection, Operating Systems Review, Vol. 8, No. 1, January 1974, pp. 18-24.

Monday, January 28

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.
A. N. Habermann , L. Flon , L. Cooprider, Modularization and hierarchy in a family of operating systems, Communications of the ACM, v.19 n.5, p.266-272, May 1976.

Wednesday, January 30

D. M. Ritchie and K. Thompson, The UNIX Time-sharing System, Communications of the ACM, Vol. 17, No. 7, July 1974, pp. 365-375.
K. Thompson Unix Implementation 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.

Monday, February 4

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.
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.

Wednesday, February 6

C. A. R. Hoare, Monitors: An Operating System Structuring Concept, Communications of the ACM, Vol 17, No 10,, October 1974, pp 549-557.
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).

Monday, February 11

D. D. Redell, Y. K. Dalal, T. R. Horsley, H. C. Lauer, W. C. Lynch, P. R. McJones, H. G. Murray, and S. C. Purcell, Pilot: An Operating System for a Personal Computer, Communications of the ACM, Vol. 23, No. 2, February 1980, pp. 81-92.
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.

Wednesday, February 13

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.

Monday, February 18

G. J. Popek, B. Walker, J. Chow, D. Edwards, C. Kline, G. Rudisin, and G. Theil, LOCUS: A Network Transparent, High Reliability Distributed System, Proc. Eighth Symposium on Operating Systems Principles, pp. 160-168, December 1981.
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.

Wednesday, February 20

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.
D. D. Clark, The Structuring of Systems using Upcalls, Proc. Tenth Symposium on Operating Systems Principles, Operating Systems Review, 19, 5, pp. 171-180, December 1985.

Monday, February 25

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.
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.

Wednesday, February 27

M. Accetta et al., Mach: A new kernel foundation for UNIX development, Proc. USENIX Summer Conference, Atlanta, GA, 1986, pp. 93-112.
D. Golub , R. Dean , A. Forin , A. Dean , R. Forin , R. Rashid, Unix as an Application Program. In USENIX 1990 Summer Conference, 1990, pp. 87-95.

Monday, March 4

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.

Wednesday, March 6

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.
R. Rosenblum and T. Garfinkel, Virtual Machine Monitors: Current Technology and Future Trends, Computer, Vol. 38 , Issue 5, May 2005, pp. 34-43.

Monday, March 11

Presentations I

Monday, March 13

Presentations II

Academic Integrity

You are expected to follow the UCSD Academic Integrity guidelines, which you can find here.