CSE 291: Reading List and Schedule

Fall 2001

Course Introduction

(9/20)

Overview of the course.

Historical Perspective

(9/25)

E. W. Dijkstra, "The Structure of the 'THE'-Multiprogramming System," Communications of the ACM, Vol. 11, No. 5, May 1968, pp. 341-346. [Evaluate!]
Q: Dijkstra explicitly states their goals for the THE operating system. How do these goals compare to, say, Microsoft's apparent goals for the NT operating system? Why don't we no longer build operating systems with the same goals as THE?
P. B. Hansen, "The Nucleus of a Multiprogramming System," Communications of the ACM, Vol. 13, No. 4, April 1970, pp. 238-241, 250. [Evaluate!]
Q: How does synchronization in the RC 4000 system compare with synchronization in the THE system?

(9/27)

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. [Evaluate!]
Q: What features in TENEX are reminiscent of features in Unix (a later system)?
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. [Evaluate!]
Q: How is a Hydra procedure different from the procedures we are familiar with in a typical language and runtime environment?

(10/2)

Jerome H. Saltzer, "Protection and the Control of Information Sharing in Multics," Communications of the ACM 17(7), July 1974. [Evaluate!]
Q: Compare and contrast protected subsystems in Multics with procedures in Hydra.
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. [Evaluate!]
Q: What aspects of Unix as described in the 1974 paper do not survive today, or have been considerably changed?

Structure

(10/4)

B. Lampson, "Protection," Operating Systems Review, January 1974, 8(1):18-24. (Also on Lampson's publication page.) [Evaluate!]
Q: What are the concepts in HYDRA that correspond to Lampson's definitions of "Domain", "Object", and "Access Matrix"? What about Multics?
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. [Evaluate!]
Q: How do the requirements of the Pilot operating system differ from the systems we have read about so far, and how does the design of Pilot reflect those differences?

(10/9)

Jones, Chansler, Durham, Schwans, and Vegdahl, "StarOS, a Multiprocessor Operating System for the Support of Task Forces". [Evaluate!]
Q: One goal of StarOS is to support concurrent execution whenever and wherever possible. What are examples of support for this goal?
John K. Ousterhout, Donald A. Scelza, and Pradeep S. Sindhu, "Medusa: An Experiment in Distributed Operating Systems Structure". [Evaluate!]
Q: Compare and contrast the abstraction of task forces in StarOS and Medusa.

(10/11)

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). [Evaluate!]
Q: Do you agree with the central argument of this paper that message-passing and procedure-oriented systems are equivalent?
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. [Evaluate!]
Q: What are the benefits of using an upcall structure, and what are the potential drawbacks?

Distribution

(10/16)

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. [Evaluate!]
Q: What are the design constraints/goals of Accent that we haven't seen before in an operating system?
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. [Evaluate!]
Q: How does the network transparency of LOCUS compare with the network transparency of Accent?

(10/18)

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. [Evaluate!]
Q: What is the argument for diskless workstations, and do you agree/disagree with the argument?
John K. Ousterhout, Andrew R. Cerenson, Frederick Douglis, Michael N. Nelson, and Brent B. Welch, "The Sprite Network Operating System." [Evaluate!]
Q: How do the caching policies in Sprite differ from those in the V Kernel?

(10/23)

No class, instructor AWOL.

(10/25)

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. [Evaluate!]
Q: In what ways was Grapevine explicitly designed to handle scalability?
Eric Jul, Henry Levy, Norman Hutchinson, and Andrew Black. "Fine-Grained Mobility in the Emerald System," ACM Transactions on Computer Systems, 6(1), February 1988, pp. 109-133. [Evaluate!]
Q: In what ways did the Emerald language support mobility?

OS/Architecture Interaction

(10/30)

John K. Ousterhout, "Why Aren't Operating Systems Getting Faster as Fast as Hardware?," Proc. USENIX Summer Conference, pp. 247-256, June 1990. [Evaluate!]
Q: Note that the remote penalty is high. Does this invalidate the V Kernel's claim that remote penalty for file access is acceptable?
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. [Evaluate!]
Q: Compare and contrast the L4 microkernel with the RC4000 Nucleus and the HYDRA kernel in terms of their goals to provide a basis on which higher level OS functionality can be implemented.

Synchronization

(11/1)

C. A. R. Hoare, "Monitors: An Operating System Structuring Concept," Communications of the ACM, Vol. 17, No. 10, October, 1974, pp. 549-557. [Evaluate!]
Q: What are "monitor invariant" I and "condition" B, and why are they important in the discussion of monitors?
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. [Evaluate!]
Q: Compare and contrast synchronization in Java with Hoare monitors and Mesa monitors.

Communication

(11/6)

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. [Evaluate!]
Q: Classify the following types of communication using Spector's taxonomy: message passing, sending mail, RPC, streaming video, remote fork.
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. [Evaluate!]
Q: In what ways do the authors optimize connection management?

(11/8)

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. [Evaluate!]
Q: What is the argument that "local" remote procedure call performance is important? Does this argument still hold today?
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. [Evaluate!]
Q: In your own words, describe what a Threaded Abstract Machine is, and why it can benefit from the use of Active Messages.

Virtual Memory

(11/13)

A. Bensoussan, C. T. Clingen, and R. C. Daley, "The Multics Virtual Memory: Concepts and Design," Communications of the ACM, Vol. 15, No. 5, May 1972, pp. 308-318. [Evaluate!]
Q: Why must segments be "Made Known", and how is it done?
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. [Evaluate!]
Q: Why does Mach support copy-on-write, and how does it implement it?

(11/15)

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. [Evaluate!]
Q: Why is it important to have a pool of free pages? How does their implementation of Unix VM maintain a free pool of pages?
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. [Evaluate!]
Q: How does the implementation of the GMS page replacement algorithm approximate the ideal algorithm?

I/O and File Systems

(11/20)

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. [Evaluate!]
Q: In FFS, reading is always at least as fast as writing. In old UFS, writing was 50% faster. Why is this?
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. [Evaluate!]
Q: When we want to read a block in LFS on disk, how do we figure out where it is?

(11/22)

Thanksgiving Holiday

(11/27)

D. M. Ritchie, "A Stream Input-Output System," AT&T Bell Laboratories Technical Journal, 62(8):1897-1910, October, 1984. [Evaluate!]
Q: In what way are coroutines used to implement the new version of stream I/O? Why are they useful?
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. [Evaluate!]
Q: Which optimization in IO-Lite had the most significant performance impact? Does this optimization generalize to many applications?

(11/29)

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. [Evaluate!]
Q: Do you believe the underlying argument in Rio? Why or why not? Would you use a system that recovered data using Rio?
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. [Evaluate!]
Q: Do you think versioning would be a useful feature in contemporary file systems? Both the VMS file system and the Andrew File System had versioning. Why do you think Unix FFS and NTFS do not?

Final Project Presentations

(12/4)

Final project presentations: 8-11am (location TDB)

voelker@cs.ucsd.edu