| Week 1 | Week 2 | Week 3 | Week 4 | Week 5 | Week 6 | Week 7 | Week 8 | Week 9 | Week 10 | Exam |
| 1/6 1/8 | 1/13 1/15 | 1/20 1/22 | 1/27 1/29 | 2/3 2/5 | 2/10 2/12 | 2/17 2/19 | 2/24 2/26 | 3/3 3/5 | 3/10 3/12 | 3/19 |
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.
| Course Introduction |
| Historical Perspective |
(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?
| Structure |
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: 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: How does the language-based approach that Singularity takes compare and contrast with Pilot?
| Synchronization |
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.
| Virtual Memory |
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?
| Distribution |
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?
| OS/Architecture Interaction |
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: Why is virtualizing a smartphone different from virtualizing a server?
| Scheduling |
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 |
Q: In what ways do the authors optimize connection management?
| 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?
| Potpourri |
Optional GFS retrospective:
Marshall Kirk McKusick and Sean Quinlan, GFS: Evolution on Fast-forward, ACM Queue, August 2009.
Q: What are the distinguishing characteristics of "warm" data objects?
As optional further reading, this group's first work was exploring OS multicore scalability using an exokernel:
Silas Boyd-Wickizer, Haibo Chen, Rong Chen, Yandong Mao, Frans Kaashoek, Robert Morris, Aleksey Pesterev, Lex Stein, Ming Wu, Yuehua Dai, Yang Zhang, and Zheng Zhang. Corey: An Operating System for Many Cores. In Proceedings of the 8th Symposium on Operating System Design & Implementation (OSDI), October 2008, San Diego, California, pp. 43–57.
More recently, they framed OS multicore scalability in more fundamental aspects:
Austin T. Clements, M. Frans Kaashoek, Nickolai Zeldovich, Robert Morris, Eddie Kohler, The Scalable Commutativity Rule: Designing Scalable Software for Multicore Processors, In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles (SOSP), October 2013, pp. 1–17.
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.
Michael Vrable, Stefan Savage, and Geoffrey M. Voelker. Cumulus: Filesystem Backup to the Cloud, ACM Transaction on Storage 5(4):1-28, December 2009.
Michael Vrable, Stefan Savage, and Geoffrey M. Voelker, BlueSky: A Cloud-Backed File System for the Enterprise, Proceedings of the 7th USENIX Conference on File and Storage Technologies (FAST), San Jose, CA, February 2012, pages 19:1-19:14.
| Exam |