CSE 221 Winter 2003
Graduate Operating Systems
Last edited 22 January 2003.

Keith Marzullo, marzullo@cs, x4-3729, APM 4824. Office hours Tu/Th 10-12 or by appointment.

Class meets on Tuesdays and Thursdays 5-6:20 in Peterson 103



The purpose of this course is to teach computer software system structures from a design point of view. We will look at different structuring techniques, and we will examine their usage in both important historical systems and in modern systems.

There is no textbook for this class. You will instead read a set of papers that I'll make available to you as the class progresses. I'll try to make all of the papers available via the web, but there may be some that I'll need to pass out.

Your grade will be computed as follows:
 
Class participation 25%
Project 35%
Final 40%

Class participation

You're expected to critically read all of the papers. Part of your grade will be based on class participation, which I'll force (as gracefully as possible) by calling on you. I'll introduce each paper and start the discussion, but at some point I'll turn to you for details and insight. In doing so, my goal is to have a more active discussion than one normally has in a classroom setting.

Project

You will do a project for the class, and it will be due on Friday, March 14 at midnight. You can work by yourself or in teams of up to four students, but I will expect an amount of work commensurate with the size of the team.

I would like to receive by no later than February 6 a project proposal  from each team. The proposal should include:

Send them to me via e-mail. I'll review the proposal, and meet with you if necessary to discuss your ideas. I won't accept a project whose proposal I didn't first accept. You can send in your proposals before the due date, of course.

I would like your project to address a concrete and quantifiable aspect of computer systems. Here are some project suggestions.


Final

There will be a written final on Monday, March 17, from 7 to 10 PM, in Peterson 103. It will contain approximately six questions based on the papers in the reading list. It will be a "closed book" final; you won't be allowed to bring in the papers nor any notes.

Here is a copy of the final I gave last Spring quarter.

Reading List

Here are the papers that we'll be discussing in class. The date at the end of each entry is the earliest date that the paper will be discussed.

Note that this is an incomplete list; I'll be completing it as quickly as possible.

Kernel Design and Concurrency

  1. Edsger W. Dijkstra, The Structure of the THE Multiprogramming System. Communications of the ACM, 11(5):341-346, May 1968. January 9.
  2. P. B. Hansen, The Nucleus of a Multiprogramming System. Communications of the ACM, 13(4): 238-241, April 1970, pp. 238-241. January 9.
  3. 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, 15(3): 135-143, March 1972. January 14.
  4. Review of concurrency principles. January 14.
  5. C. A. R. Hoare, Monitors: An Operating System Structuring Concept, Communications of the ACM, (17)10:549-557, October, 1974. January 16.
  6. B. W. Lampson and D. D. Redell, Experience with processes and monitors in Mesa. Communications of the ACM, February 1980, 23(2):105-117. January 21.
  7. 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, 23(2):81-92, February 1980. January 23.
  8. H. C. Lauer and R. M. Needham. On the Duality of Operating System Structures. In Proceedings of the Second International Symposium on Operating Systems, IRIA, Oct. 1978 (reprinted in Operating Systems Review 13(2):3-19, April 1979. January 23.
  9. J. K. Ousterhout, Why Aren't Operating Systems Getting Faster as Fast as Hardware? In Proceedings of the  USENIX Summer Conference, pp. 247-256, June 1990. January 28.
  10. 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, 5-8 October 1997, pages 66-77. January 30.
File Systems
  1. M. K. McKusick, W. N. Joy, S. J. Leffler, and R. S. Fabry, A Fast File System for UNIX. ACM Transactions on Computer Systems 2(3):181-197, August 1984. January 30.
  2. M. Rosenblum and J. Ousterhout, The Design and Implementation of a Log-Structured File System. ACM Transactions on Computer Systems, February 1992, 10(1):26-52. February 4.
  3. Peter M. Chen, Wee Teck Ng, Subhachandra Chandra, Christopher Aycock, Gurushankar Rajamani, and David 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. February 6.
Virtual Memory
  1. A. Bensoussan, C. T Clingen, and R. C. Daley. The Multics virtual memory: Concepts and design. Communications of the ACM, May 1972, 15(5):308-318. February 6.
  2. Ö. Babaoglu and W. Joy. Converting a swap-based system to do paging in an architecture lacking page-referenced bits. In Proceedings of the Eighth Symposium on Operating Systems Principles, Pacific Grove, CA, USA, 14-16 December 1981, pages 78-86. February 11.
  3. R. Rashid et. al, Machine-independent virtual memory management for paged uniprocessor and multiprocessor architectures. IEEE Transactions on Computers, August 1988, 37(8): 896-908. February 11.
  4. 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. February 13.
Protection and Security
  1. W. Wulf, E. Cohen, W. Corwin, A. Jones, R. Levin, C. Pierson, and F. Pollack, HYDRA: The Kernel of a Multiprocessor System. Communications of the ACM 17(6):337-345, June 1974. February 13.
  2. J. H. Saltzer, Protection and the control of information sharing in Multics. Communications of the ACM, July 1974, 17(7):388-402. February 18.
  3. B. Lampson, Protection. Operating Systems Review, January 1974, 8(1):18-24. February 18.
I/O
  1. D. M. Ritchie, A stream input-output system. AT&T Bell Laboratories Technical Journal, 62(8):1897-1910, October 1984. February 20.
  2. 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. February 20.
Communications and Distributed Systems
  1. 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): 64-75, December 1981. February 25.
  2. 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): 129-140, November 1983. February 25.
  3. A. Birell and B. J. Nelson, Implementing RPC. ACM Transactions on Computer Systems 2(1):39-59, February 1984. February 27.
  4. M. D. Schroeder, A. D. Birrell, and R. M. Needham. Experience with Grapevine: the growth of a distributed system. ACM Transactions on Computer Systems, February 1984, 2(1):3-23. March 4.
  5. 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. March 4.
  6. J. H. Saltzer, D. P. Reed, and D. D. Clark, End-to-end arguments in system design. ACM Transactions on Computer Systems, November 1984, 2(4):277-288. March 6.
  7. D. D. Clark, The structuring of systems using upcalls. In Proceedings of the Tenth ACM Symposium on Operating Systems Principles, Orcas Island, WA, USA, 1-4 December 1985, pp. 171-180. March 6.
System Engineering
  1. Andrea Arpaci-Dusseau and Remzi Arpaci-Dusseau, Information and Control in Gray-Box Systems, Proc. Eighteenth ACM Symposium on Operating Systems Principles, pp. 43-56, October 2001. March 11.
  2. Dawson Engler et. al., Bugs as Deviant Behavior: A General Approach to Inferring Errors in Systems Code, Proc. Eighteenth ACM Symposium on Operating Systems Principles, pp. 57-72, October 2001. March 11.
  3. Butler W. Lampson, Hints for Computer System Design, ACM Operating Systems Review 15, 5 (October 1983), pp. 33-48. March 13.

  4.