CSE221: Graduate Operating Systems
Fall 2019
| Week 0 | Week 1 | Week 2 | Week 3 | Week 4 | Week 5 | Week 6 | Week 7 | Week 8 | Week 9 | Week 10 |
|
9/26 |
10/1 10/3 |
10/8 10/10 |
10/15 10/17 |
10/22 10/24 |
10/29 10/31 |
11/5 11/7 |
11/12 11/14 |
11/19 11/21 |
11/26 11/28 |
12/3 12/5 |
All papers are accessible online from the UCSD network. To access the papers from a non-UCSD computer, you can use the campus VPN with your computer.
Course Introduction
- Course Overview
Historical Perspective
- E. W. Dijkstra, The Structure of the 'THE'-Multiprogramming System, Communications of the ACM, Vol. 11, No. 5, May 1968, pp. 341-346.
- P. B. Hansen, The Nucleus of a Multiprogramming System, Communications of the ACM, Vol. 13, No. 4, April 1970, pp. 238-241, 250.
(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?
- 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.
- 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.
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
- B. Lampson, Protection, Operating Systems Review, Vol. 8, No. 1, January 1974, pp. 18-24.
- J. H. Saltzer, Protection and the Control of Information Sharing in Multics, Communications of the ACM, Vol. 17, No. 7, July 1974, pp. 388-402.
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.
- D. M. Ritchie and K. Thompson, The UNIX Time-Sharing System, Communications of the ACM, Vol. 17, No. 7, July 1974, pp. 365-375.
- R. Pike, D. Presotto, S. Dorward, B. Flandrena, K. Thompson, H. Trickey, and P. Winterbottom, Plan 9 From Bell Labs, USENIX Computing Systems, Vol. 8, No. 3, Summer 1995, pp. 221-254.
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"?
- J. K. Ousterhout, D. A. Scelza, and P. S. Sindhu, Medusa: An Experiment in Distributed Operating Systems Structure, Communications of the ACM, Vol. 23, No. 2, February 1980, pp. 92-105.
- 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.
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?
Synchronization
- C. A. R. Hoare, Monitors: An Operating System Structuring Concept, Communications of the ACM, Vol. 17, No. 10, October, 1974, pp. 549-557.
- 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.
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.
Distribution
- D. R. Cheriton and W. Zwaenepoel, The Distributed V Kernel and its Performance for Diskless Workstations, Proceedings of the 9th Symposium on Operating Systems Principles, pp. 129-140, November 1983.
- J. K. Ousterhout, A. R. Cerenson, F. Douglis, M. N. Nelson, and B. B. Welch, The Sprite Network Operating System, IEEE Computer, Vol. 21, No. 2, February 1988, pp. 23-36.
Q: What is the argument for diskless workstations, and do you agree/disagree with the argument?
Q: How do the caching policies in Sprite differ from those in the V Kernel?
- M. D. Schroeder, A. D. Birrell, and R. M. Needham, Experience with Grapevine: The Growth of a Distributed System, ACM Transactions on Computer Systems, Vol. 2, No. 1, February 1984.
- 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.
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?
- (Class cancelled)
OS/Architecture Interaction
- H. Haertig, M. Hohmuth, J. Liedtke, S. Schoenberg, J. Wolter, "The Performance of Micro-Kernel- Based Systems," Proceedings of the 16th Symposium on Operating Systems Principles, October 1997, pp. 66-77.
- D. R. Engler, M. F. Kaashoek, and J. O'Toole Jr., Exokernel: An Operating System Architecture for Application-Level Resource Management, In Proceedings of the Fifteenth ACM Symposium on Operating Systems Principles, December 1995, Copper Mountain Resort, Colorado, pp. 251-266.
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.
- R. J. Creasy, The Origin of the VM/370 Time-Sharing System, In IBM Journal of Research and Development, 25(5):483-490, September 1981.
- P. Barham, B. Dragovic, K. Fraser, S. Hand, T. Harris, A. Ho, R. Neugebauer, I. Pratt, and A. Warfield, Xen and the Art of Virtualization, In Proceedings of the 19th Symposium on Operating System Principles, October, 2003.
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?
Virtual Memory
- H. M. Levy and P. Lipman, "Virtual Memory Management in VAX/VMS", IEEE Computer, Vol. 15, No. 3, March 1982, pp.35-41.
- Richard Rashid, Avadis Tevanian, Michael Young, David Golub, Robert Baronn, 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.
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?
I/O and File System
- 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.
- 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.
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?
- Gregory R. Ganger, Marshall Kirk McKusick, Craig A.N. Soules, and Yale N. Patt. "Soft Updates: A Solution to the Metadata Update Problem in File Systems," ACM Transactions on Computer Systems, Vol. 18, No. 2, May 2000, Pages 127-153.
- 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.
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?
Scheduling
- Thomas E. Anderson, Brian N. Bershad, Edward D. Lazowska, Henry M. Levy, Scheduler Activations: Effective Kernel Support for the User-level Management of Parallelism, Proceedings of the 13th ACM Symposium on Operating Systems Principles, Sept. 1991, pp. 95-109.
- Carl A. Waldspurger and William E. Weihl, Lottery Scheduling: Flexible Proportional-Share Resource Management. Proceedings of the First USENIX Symposium on Operating System Design and Implementation, November, 1994.
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?
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.
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?
Smartphones
- Jeremy Andrus, Christoffer Dall, Alexander Van.t Hof, Oren Laadan, and Jason Nieh, Cells: A Virtual Mobile Smartphone Architecture, SOSP'11, October 2011.
- W. Enck, P. Gilbert, B.G. Chun, L. P. Cox, J. Jung, P. McDaniel, A. N. Sheth, TaintDroid: An Information-Flow Tracking System for Realtime Privacy Monitoring on Smartphones , OSDI'10, October 2010
Big Data I
- Sanjay Ghemawat, Howard Gobioff, Shun-Tak Leung, The Google File System, Proceedings of the Nineteenth ACM Symposium on Operating Systems Principles (SOSP), pp. 29-43, October 2003.
Optional GFS retrospective:
Marshall Kirk McKusick and Sean Quinlan, GFS: Evolution on Fast-forward, ACM Queue, August 2009.
- Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes, and Robert E. Gruber, "Bigtable: A Distributed Storage System for Structured Data", Proceedings of the 7th USENIX Symposium on Operating System Design and Implementation (OSDI), Seattle, WA, Nov 2006
Big Data II
- (Class cancelled for Thanksgiving)
- Jeffrey Dean and Sanjay Ghemawat, MapReduce: simplified data processing on large clusters, Proceedings of the 6th USENIX Symposium on Operating System Design and Implementation (OSDI), 2004
- Doug Beaver, Sanjeev Kumar, Harry C. Li, Jason Sobel, and Peter Vajgel, Finding a needle in Haystack: Facebook’s photo storage, Proceedings of the 9th USENIX Symposium on Operating System Design and Implementation (OSDI), 2010
- Martin Abadi, Paul Barham, et. al. TensorFlow: A system for large-scale machine learning Proceedings of the 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16), 2016.