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

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:

• The team members.
• A brief (one or two paragraph) description of the topic and why it is interesting.
• Your plan of attack.

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

• There have been some influential papers written on some aspect of system performance that have affected the way we design systems. Two examples are:

"Measurements of a Distributed File System" by Mary G. Baker et. al in SOSP 13.

Jim Gray, ``A Census of Tandem System Availability between 1985 and 1990,'' IEEE Transactions on Reliability, vol. 39, Oct 1990.


We'll see more cited in the papers we cover this quarter. Are the observations in these papers still valid? If so, why have they remained valid considering the huge changes that have taken place since? If not, then how have they changed, and what does this imply about operating system structure?

• More generally, the design of an operating system depends on the underlying hardware and its performance. If you don't know these values, then a system you design may not be useful. Come up with a set of metrics and measure them for a real system. The metrics should include: memory access times, page fault penalty (ratio of page fault service time to memory access time), min, average and maximum disk access time, page fault rate, the effects of changing file cache size, the access time to read a page from a remote file server, procedure invocation time, context switch overhead as a function of the instruction cycle time.
• In the same vein, there have been architectural changes that operating systems haven't fully caught up with. For example, 64-bit words allows for a huge physical memory space; how should it be managed? For such a topic, you could survey the current work in the area and add your own thoughts about the different approaches.
• Some of the systems (notably, some appearing in the ACM Symposium on Operating System Principles) are available for interested researchers. This is done so that the experimental results can be independently verified. Try to verify the results. Be suspicious; try changing the parameters to see if agree or disagree with their conclusions.

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.

11. 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.
12. 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.
13. 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.

14. 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.
15. Ö. 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.
16. 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.
17. 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.

18. 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.
19. J. H. Saltzer, Protection and the control of information sharing in Multics. Communications of the ACM, July 1974, 17(7):388-402. February 18.
20. B. Lampson, Protection. Operating Systems Review, January 1974, 8(1):18-24. February 18.

21. D. M. Ritchie, A stream input-output system. AT&T Bell Laboratories Technical Journal, 62(8):1897-1910, October 1984. February 20.
22. 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.

23. 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.
24. 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.
25. A. Birell and B. J. Nelson, Implementing RPC. ACM Transactions on Computer Systems 2(1):39-59, February 1984. February 27.
26. 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.
27. 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.
28. 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.
29. 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.

30. 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.
31. 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.
32. Butler W. Lampson, Hints for Computer System Design, ACM Operating Systems Review 15, 5 (October 1983), pp. 33-48. March 13.