CSE 221: Graduate Operating Systems

Fall 2002

Instructor

P. Venkat Rangan venkat@cs.ucsd.edu
AP&M 5151 or AP&M 5337 (Try both locations always)
(858) 534-5419 or (858) 534-8173 or (858) 699-0300 (try all three numbers)

Office Hours Mon/Wed 1-1:45pm (by appointment – please send email in advance if you plan to come)

Lectures

Tu/Th 3:30 – 4:50pm in U413 (University Center, Building 413)

Teaching Assistant

Doug Brown d2brown@cs.ucsd.edu

Office Hours Mon 10-11am, AP&M 2331 - please email your question(s) in advance to indicate you are coming and to help plan the discussion

Announcements

• Exam #4 Statistics (100 possible points): Mean = 78.7, Median = 80, Standard Deviation = 11.7
• Exam #3 Statistics (100 possible points): Mean = 87.7, Median = 90, Standard Deviation = 9.4
• Exam #2 Statistics (20 possible points): Mean = 17.5, Median = 17.5, Standard Deviation = 1.7
• Exam #1 Statistics (100 possible points): Mean = 84.6, Median = 85, Standard Deviation = 8.0

Course Objectives

The purpose of this course is to teach fundamental advanced concepts about operating systems and distributed systems. The course is organized as a sequence of paper readings from the early seventies to the late nineties, with most of the papers from the seventies and eighties, when the fundamental advances in operating systems and distributed systems took place.  This course will give you a strong background and preparation for advanced research in operating systems, distributed sytems, and networks.

Grading

• Exam 1: Tuesday, October 15: 20 points
• Exam 2: Thursday, October 31: 20 points
• Exam 3: Thursday, November 21: 20 points
• Exam 4: Thursday, December 5: 20 points
• Class Notes: Each team of 2 students is to select a paper from the first set of 24 papers to write comprehensive class notes based on the class discussion. This will count for 5 points.
• Project: The same teams (of 2 students each) as above will select a paper from one of the last 11 papers, and present it in class. These presentations will be held from Thursday November 22 to Tuesday, December 3, 15 min per presentation: 15 points.

Reading List

We will be reading and discussing about 3-4 papers every week.  The list of papers is as follows (note: UCSD has a site license for the ACM digital library; in order to access these papers from off-campus, you will need to configure your web browser to use a web proxy according to these instructions).

EARLY OPERATING SYSTEMS (6 papers, Exam 1)

Sample Questions (exam 1, papers dijkstra to jones)

• E. Dijkstra, "The Structure of the 'THE'-Multiprogramming System," Communications of the ACM, Vol. 11, No. 5, May 1968, pp. 341-346.
  Class notes by Ajay Bharadwaj, Saurabh Panjwani
   
• P. B. Hansen, "The Nucleus of a Multiprogramming System," Communications of the ACM, Vol. 13, No. 4, April 1970, pp. 238-241, 250.
  Class notes by Weifeng Zhang, Dayou Zhou
   
• 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.
  Class notes by Scott O'Neil, Yekaterina Tsipenyuk
   
• 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.
  Class notes by Patricia Shanahan, Sunjeev Sikand
   
• Jones, Chansler, Durham, Schwans, and Vegdahl, "StarOS, a Multiprocessor Operating System for the Support of Task Forces."
  Class notes by Nuno Bandeira, Hrishikesh Gupta
   
• Jerome H. Saltzer, "Protection and the Control of Information Sharing in Multics," Communications of the ACM 17(7), July 1974.
  Class notes by Cyrus Jam, Cynthia Lee (Supplemental Notes)
   

OPERATING SYSTEM ABSTRACTIONS (6 papers, Exam 2)

• D. M. Ritchie and K. Thompson, "The UNIX Time-Sharing System," The Bell System Technical Journal, Vol. 57, No. 6, July-August 1978, pp. 1905-1929.
  Class notes by Nut Taesombut, Yang Yang (Supplemental Notes)
   
• B. Lampson, "Protection," Operating Systems Review, January 1974, 8(1):18-24.
  Class notes by William Frantz, Vadim Lyubashevsky (Supplemental Notes)
   
• C. A. R. Hoare, "Monitors: An Operating System Structuring Concept," Communications of the ACM, Vol. 17, No. 10, October, 1974, pp. 549-557.
  Class notes by Neil Alldrin, Nguyendo Ngo (Supplemental Notes)
   
• 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.
  Class notes by Ari Frank, Diem Vu (Supplemental Notes)
   
• H. C. Lauer and R. M. Needham, "On the Duality of Operating System Structures," Proc. Second International Symposium on Operating Systems, IRIA, Oct. 1978 (reprinted in Operating Systems Review, Vol. 13, No. 2, April 1979, pp. 3-19).
  Class notes by Xinran Wu, Xu Xu (Supplemental Notes)
   
• Loretta Guarino Reid and Philip L. Karlton, "A file system supporting cooperation between programs," ACM Symposium on Operating Systems Principles, 1983, pp. 20-29.
  Class notes by Tony Chen, Janice Ng (Supplemental Notes)
   

II Generation Operating Systems (6 papers, Exam 3)

• 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.
  Class notes by James Mata, Jake Sorensen (Supplemental Notes)
   
• John K. Ousterhout, Donald A. Scelza, and Pradeep S. Sindhu, "Medusa: An Experiment in Distributed Operating Systems Structure".
  Class notes by Michael Van Biesbrouck, Swammy Muddu (Supplemental Notes)
   
• 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.
  Class notes by Jin-Su Kim, Seungjoo Lee (Supplemental Notes)
   
• R. F. Rashid and G. G. Robertson, "Accent: A communication oriented network operating system kernel," Proc. Eighth Symposium on Operating Systems Principles, Operating Systems Review, 15, 5, pp. 64-75, December 1981.
  Class notes by Anjum Gupta, Vinu Somayaji (Supplemental Notes)
   
• 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, Operating Systems Review, 15(5), pp. 160-168, December 1981.
  Class notes by Tulika Agrawal, Peter Schwer (Supplemental Notes)
   
• D. R. Cheriton and W. Zwaenepoel, "The Distributed V Kernel and its Performance for Diskless Workstations," Proc. Ninth Symposium on Operating Systems Principles, Operating Systems Review, 17(5), pp. 129-140, November 1983.
  Class notes by Naveen Gattu, John Lynn (Supplemental Notes 1, Supplemental Notes 2)
   

III Generation Operating Systems (UNIX, Early Abstractions for Distributed Systems: 6 papers, Exam 4)

•  Alfred Z. Spector, "Performing Remote Operations Efficiently on a Local Computer Network," Communications of the ACM, Vol. 25, No. 4, April 1982, pp. 246-260.
  Class notes by Sandy Hung, Vitaliy Zavesov (Supplemental Notes)
   
•  O. Babaoglu and W. Joy, "Converting a swap-based system to do paging in an architecture lacking page-referenced bits." In Proceedings of the Eight Symposium on Operating Systems Principles, Pacific Grove, CA, December 14-16, 1981, pages 78-86.
  Class notes by Dan Liu, Jeff Hardy (Supplemental Notes)
   
•  Marshall K. McKusick, William N. Joy, Samuel J. Leffler, and Robert S. Fabry, "A Fast File System for Unix," ACM Transactions on Computer Systems, 2(3), August 1984, pp. 181-197.
  Class notes by John Rapp, Andrew Smith (Supplemental Notes)
   
• D. M. Ritchie, "A Stream Input-Output System," AT&T Bell Laboratories Technical Journal, 62(8):1897-1910, October, 1984.
  Class notes by Manny Hunjan, Phil Moy (Supplemental Notes)
   
• Andrew D. Birrell and Bruce J. Nelson, "Implementing Remote Procedure Calls", ACM Transactions on Computer Systems, Vol. 2, No. 1, pp. 39-59, February 1984.
  Class notes by Jonathan Wang, Class notes by Oleg Tanchuk (Supplemental Notes)
   
• Richard Rashid, Avadis Tevanian, Michael Young, David Golub, Robert Baron, David Black, William Bolosky, and Jonathan Chew, "Machine-Independent Virtual Memory Management for Paged Uniprocessor and Multiprocessor Architectures," In Proceedings of the Second International Conference on Architectural Support for Programming Languages and Operating Systems, October 1987, pp. 31-39.
  Class notes by Ryan Szypowski (Supplemental Notes)
   

IMPROVED DISTRIBUTED SYSTEMS (6 papers: STUDENT PRESENTATIONS)

• Michael D. Schroeder, Andrew D. Birrell, and Roger M. Needham, "Experience with Grapevine: The Growth of a Distributed System," ACM Transactions on Computer Systems, 2(1), February 1984.
  Student presentation by William Frantz, Vadim Lyubashevsky and Naveen Gattu, John Lynn
   
•  John K. Ousterhout, "Why Aren't Operating Systems Getting Faster as Fast as Hardware?," Proc. USENIX Summer Conference, pp. 247-256, June 1990.
  Student presentations by Nuno Bandeira, Hrishikesh Gupta and Cyrus Jam, Cynthia Lee
   
• Brian N. Bershad, Thomas E. Anderson, Edward D. Lazowska, and Henry M. Levy, "Lightweight Remote Procedure Call," Proc. Twelfth Symposium on Operating Systems Principles, pp. 102-113, December 1989.
  Student presentation by Sandy Hung, Vitaliy Zavesov and Anjum Gupta, Vinu Somayaji
   
• Thorsten von Eicken, David E. Culler, Seth C. Goldstein, and Klaus E. Schauser, "Active Messages: a Mechanism for Integrated Communication and Computation," Proceedings of the 19th International Symposium on Computer Architecture, May 1992, pp. 256-266.
  Student presentations by Ryan Wu, Xu Xu and Nut Taesombut, Yang Yang
   
•  Mendel Rosenblum and John K. Ousterhout, "The Design and Implementation of a Log-Structured File System," Proceedings of the 13th ACM Symposium on Operating Systems Principles, December 1991.
  Student presentations by Dan Liu, Ryan Szypowski and John Rapp, Andrew Smith
   
• John K. Ousterhout, Andrew R. Cerenson, Frederick Douglis, Michael N. Nelson, and Brent B. Welch, "The Sprite Network Operating System."
  Student presentations by Jin-Su Kim, Seungjoo Lee and Swammy Muddu, Michael Van Biesbrouck
   

ADVANCED TOPICS: (5 papers, Student Presentations)

• H. Haertig, M. Hohmuth, J. Liedtke, S. Schoenberg, J. Wolter, "The Performance of Micro-Kernel- Based Systems." In Proceedings of the 16th ACM Symposium on Operating Systems Principles, Saint Malo, France, October 5-8, 1997, pp. 66-77.
  Student presentation by Weifeng Zhang, Dayou Zhou and Nguyendo Ngo, Jonathan Wang
   
• Michael J. Feeley, William E. Morgan, Frederic H. Pighin, Anna R. Karlin, and Henry M. Levy, "Implementing Global Memory Management in a Workstation Cluster", Proceedings of the 15th ACM Symposium on Operating Systems Principles, Dec. 1995, 29(5): 201-212.
  Student presentation by Tulika Agrawal, Peter Schwer and James Mata, Jake Sorensen
   
• P. M. Chen, W. T. Ng, S. Chandra, C. Aycock, G. Rajamni, and D. Lowell, "The Rio File Cache: Surviving Operating System Crashes," In Proceedings of the Seventh International Conference on Architectural Support for Programming Languages and Operating Systems, SIGPLAN Notices 31(9):74-83, September 1996.
  Student presentations by Tony Chen, Janice Ng, Sunjeev Sikand and Ajay Bharadwaj, Saurabh Panjwani
   
• D. S. Santry, M. J. Feeley, N. C. Hutchinson, A. C. Veitch, R. W. Carton, and J. Or, "Deciding When to Forget in the Elephant File System." In Proceedings of the Seventeenth ACM Symposium on Operating Systems Principles, December 12-15, 1999, Charleston, SC, pp. 110-123.
  Student presentation by Scott O'Neil, Yekaterina Tsipenyuk and Manny Hunjan, Phil Moy
   
• V. S. Pai, P. Druschel, and W. Zwaenepoel, "IO-Lite: A Unified Buffering and Caching System," In Proceedings of the Third Symposium on Operating Systems Design and Implementation (OSDI'99), New Orleans, LA, February 1999, pp. 15-28.
  Student presentation by Ari Frank, Diem Vu and Oleg Tanchuk