|Week 1||Week 2||Week 3||Week 4||Week 5||Week 6||Week 7||Week 8||Week 9||Week 10||Exam|
|1/8 1/10||1/15 1/17||1/22 1/24||1/29 1/31||2/5 2/7||2/12 2/14||2/19 2/21||2/26 2/28||3/5 3/7||3/12 3/14||3/21|
All papers are accessible online from the UCSD network. To access the papers from a non-UCSD computer, use the campus web proxy with your web browser or campus VPN with your computer.
(Additional historical background on semaphores in Wikipedia.)
Q: Dijkstra explicitly states their goals for the THE operating system. How do these goals compare to, say, Microsoft's goals for the Windows operating system? Why do we no longer build operating systems with the same goals as THE?
Optional related paper on a deployment experience of RC 4000:
P. B. Hansen, The RC 4000 Real-Time Control System at Pulway, BIT 7, pp. 279-288, 1967.
Q: How does synchronization in the RC 4000 system compare with synchronization in the THE system?
Q: What features in TENEX are reminiscent of features in Unix (a later system)?
Q: How is a Hydra procedure different from the procedures we are familiar with in a typical language and runtime environment?
Q: What are the concepts in HYDRA that correspond to Lampson's definitions of "Domain", "Object", and "Access Matrix"? What about Multics?
Optional Multics paper:
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.
Q: Compare and contrast protected subsystems in Multics with procedures in Hydra.
Q: What aspects of Unix as described in the 1974 paper do not survive today, or have been considerably changed?
Q: What does it mean, "9P is really the core of the system; it is fair to say that the Plan 9 kernel is primarily a 9P multiplexer"?
Q: What are the three distributed OS structures outlined in the paper, which structure does Medusa use, and why?
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?
Q: What are "monitor invariant" I and "condition" B, and why are they important in the discussion of monitors?
Q: Compare and contrast synchronization in Java with Hoare monitors and Mesa monitors.
Q: The paper states, "VAX/VMS, then, is a collection of procedures that exist in the address space of each process." Explain in your own words what this statement means.
Q: Why does Mach support copy-on-write, and how does it implement it?
Q: What is the argument for diskless workstations, and do you agree/disagree with the argument?
Optional historical retrospective:
J. K. Ousterhout, Sprite Retrospective
Q: How do the caching policies in Sprite differ from those in the V Kernel?
Q: In what ways was Grapevine explicitly designed to handle scalability?
Q: How does the implementation of the GMS page replacement algorithm approximate the ideal algorithm?
Optional related papers on hierarchical address spaces and formally verifying a microkernel:
J. Liedtke, On Micro-kernel Construction, In Proceedings of the Fifteenth ACM Symposium on Operating Systems Principles, December 1995, Copper Mountain Resort, Colorado, pp. 237-250.
G. Klein, K. Elphinstone, G. Heiser, J. Andronick, D. Cock, P. Derrin, D. Elkaduwe, K. Engelhardt, M. Norrish, R. Kolanski, T. Sewell, H. Tuch, S. Winwood, seL4: Formal Verification of an OS Kernel, In Proceedings of the 22nd ACM Symposium on Operating Systems Principles, October 2009, Big Sky Resort, MT, pp. 207-220.
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.
Optional — the other Exokernel paper:
M. F. Kaashoek, D. R. Engler, G. R. Ganger, H. M. Briceno, R. Hunt, D. Mazieres, T. Pinckney, R. Grimm, J. Jannotti and K. Mackenzie, Application Performance and Flexibility on Exokernel Systems, In Proceedings of the Sixteenth ACM Symposium on Operating Systems Principles, October 1997, St. Malo, France, pp. 52-65.
Q: Compare and contrast an exokernel with a microkernel.
Optional related paper describing VMware virtualization performance (2006-era):
Keith Adams and Ole Agesen, A Comparison of Software and Hardware Techniques for x86 Virtualization, In Proceedings of the 12th International Conference on Architectural Support for Programming Languages and Operating Systems, October 2006, pp. 2–13.
Q: Microkernels and virtual machine monitors are two different ways to support the execution of multiple operating systems on modern hardware. How does the microkernel approach in L4 compare and constrast with the VMM approach in Xen?
Q: The goal of scheduler activations is to have the benefits of both user and kernel threads without their limitations. What are the limitations of user and kernel threads, and what are the benefits that scheduler activations provide?
Q: At a high level, as a mechanism how does lottery scheduling provide modular resource management? Why can't the Unix scheduler provide a similar kind of management?
Optional related papers on lottery scheduling:
David Petrou, John W. Milford, Garth A. Gibson, Implementing Lottery Scheduling: Matching the Specializations in Traditional Schedulers, In Proceedings of the USENIX Annual Technical Conference, 1999.
Carl A. Waldspurger and William E. Weihl, Stride Scheduling: Deterministic Proportional-Share Resource Management, Technical Report: TM-528, MIT, Cambridge, MA, 1995.
|Communication and Bugs|
Q: In what ways do the authors optimize connection management?
Optional fun retrospective:
Al Bessey, Ken Block, Ben Chelf, Andy Chou, Bryan Fulton, Seth Hallem, Charles Henri-Gros, Asya Kamsky, Scott McPeak, and Dawson Engler, A Few Billion Lines of Code Later: Using Static Analysis to Find Bugs in the Real World, Communications of the ACM, Vol. 53, No. 2, February 2010, pp. 66-75.
|I/O and File Systems|
Q: In FFS, reading is always at least as fast as writing. In old UFS, writing was 50% faster. Why is this?
Q: When we want to read a block in LFS on disk, how do we figure out where it is?
Optional further readings on Rio:
David E. Lowell and Peter M. Chen, Free Transactions with Rio Vista, In Proceedings of the Sixteenth ACM Symposium on Operating Systems Principles October 1997, St. Malo, France, pp. 92–101.
Q: Do you believe the underlying argument in Rio? Why or why not? Would you use a system that recovered data using Rio?
Optional GFS retrospective:
Marshall Kirk McKusick and Sean Quinlan, GFS: Evolution on Fast-forward, ACM Queue, August 2009.
Michael Vrable, Justin Ma, Jay Chen, David Moore, Erik VandeKieft, Alex C. Snoeren, Geoffrey M. Voelker, and Stefan Savage, Scalability, Fidelity and Containment in the Potemkin Virtual Honeyfarm, Proceedings of the 20th ACM Symposium on Operating Systems Principles (SOSP), Brighton, UK, October 2005, pages 148-162.
Diwaker Gupta, Kenneth Yocum, Marvin McNett, Alex C. Snoeren, Amin Vahdat, and Geoffrey M. Voelker, To Infinity and Beyond: Time-Warped Network Emulation, Proceedings of the 3rd ACM/USENIX Symposium on Networked Systems Design and Implementation (NSDI), San Jose, CA, May 2006, pages 87-100.
Diwaker Gupta, Kashi Vishwanath, and Amin Vahdat, DieCast: Testing Distributed Systems with an Accurate Scale Model, Proceedings of the 5th ACM/USENIX Symposium on Networked Systems Design and Implementation (NSDI), San Francisco, CA, April 2008.
Diwaker Gupta, Sangmin Lee, Michael Vrable, Stefan Savage, Alex C. Snoeren, George Varghese, Geoffrey M. Voelker, and Amin Vahdat, Difference Engine: Harnessing Memory Redundancy in Virtual Machines, Proceedings of the 8th ACM/USENIX Symposium on Operating System Design and Implementation (OSDI), San Diego, CA, December 2008.