Qualifying Exam in Operating Systems and Distributed Systems

This page contains information about the PhD Qualifying Exam in operating systems (and distributed systems), as of the last time I was the examiner for that topic (Spring 2018). This information is only valid for that quarter.

For this exam I expect you to be familiar with the material in the papers listed below. You do not need to memorize minute details, but you should be able to answer questions such as:

  • What are the key contributions of this paper? Why are these benefits important?
  • How does this system work (at a medium level of detail)?
  • What are the strengths and weaknesses of this system?
  • How does the system compare to X, where X is another system from the reading list?

The format of the exam will be a 30-minute oral exam. You are welcome to bring copies of the papers with you to the exam, either in paper or electronic form, and you may consult them during the exam (so you don't have to worry about memorizing information). However, there won't be enough time during the exam free to spend large amounts of time rereading papers to refresh yourself.

Readings

  1. R. Daley and J. Dennis, "Virtual Memory, Processes, and Sharing in MULTICS," Communications of the ACM, Vol. 11, No. 5, May 1968, pp. 306–312.
  2. D. Ritchie and K. Thompson, "The UNIX Time-Sharing System," Communications of the ACM, Vol. 17, No. 7, July 1974, pp. 365–375.
  3. B. Lampson and D. Redell, "Experience with Processes and Monitors in Mesa," Communications of the ACM, Vol. 23, No. 2, Feb 1980, pp. 105–117.
  4. K. Thompson, "Reflections on Trusting Trust," Communications of the ACM, Vol. 27, No. 8, Aug 1984, pp. 761–763.
  5. R. Sandberg, D. Goldberg, S. Kleiman, D. Walsh, and B. Lyon, "Design and Implementation of the Sun Network Filesystem," 1985 USENIX Conference and Exhibition, June 1985, pp. 119–130.
  6. C. Gray and D. Cheriton, "Leases: an Efficient Fault-Tolerant Mechanism for Distributed File Cash Consistency," Proc. 12th ACM Symposium on Operating Systems Principles, October 1989, pp. 202–210.
  7. M. Rosenblum and J. Ousterhout, "The Design and Implementation of a Log-Structured File System," ACM Transactions on Computer Systems, Vol. 10, No. 1, Feb. 1992, pp. 26–52.
  8. D. Engler, M.F. Kaashoek, and J. O'Toole Jr., "Exokernel: an Operating System Architecture for Application-Level Resource Management," Proc. 15th ACM Symposium on Operating Systems Principles, October 1995, pp. 251–266.
  9. S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. Anderson, "Eraser: a Dynamic Data Race Detector for Multithreaded Programs," ACM Transactions on Computer Systems, Vol. 15, No. 4, Nov. 1997, pp. 391–411.
  10. C. Waldspurger, "Memory Resource Management in VMware ESX Server," 5th USENIX Symposium on Operating Systems Design and Implementation (OSDI 2002), Dec 2002.
  11. G. DeCandia, D. Hastorun, M. Jampani, G. Kakulapati, A. Lakshman, A. Pilchin, S. Sivasubramanian, P. Vosshall, and W. Vogels, "Dynamo: Amazon's Highly Available Key-Value Store," Proc. 21st ACM Symposium on Operating Systems Principles, October 2007, pp. 205–220.
  12. F. Chang, J. Dean, S. Ghemawat, W. Hsieh, D. Wallach, M. Burrows, T. Chandra, A. Fikes, and R. Gruber, "Bigtable: A Distributed Storage System for Structured Data," ACM Transactions on Computer Systems, Vol. 26, No. 2, June 2008, Article 4.
  13. M. Zaharia, M. Chowdhury, T. Das, A. Dave, J. Ma, M. McCauley, M. Franklin, S. Shenker, and I. Stoica, "Resilient Distributed Datasets: a Fault-Tolerant Abstraction for In-Memory Cluster Computing," 9th USENIX Symposium on Networked Systems Design and Implementation (NSDI 2012), April 2012.
  14. E. Bugnion, S. Devine, M. Rosenblum, J. Sugerman, and E. Wang, "Bringing Virtualization to the x86 Architecture with the Original VMware Workstation," ACM Transactions on Computer Systems, Vol. 30, No. 4, Nov. 2012, Article 12.
  15. D. Ongaro and J. Ousterhout, "In Search of an Understandable Consensus Algorithm," 2014 USENIX Annual Technical Conference (USENIX ATC '14), June 2014, pp. 305–319.
  16. A. Belay, G. Prekas, A. Klimovic, S. Grossman, C. Kozyrakis, and E. Bugnion, "IX: a Protected Dataplane Operating System for High Throughput and Low Latency," 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI 2014), Oct 2014, pp. 49–65.
  17. A. Clements, M.F. Kaashoek, N. Zeldovich, R. Morris, and E. Kohler, "The Scalable Commutativity Rule: Designing Scalable Software for Multicore Processors," ACM Transactions on Computer Systems, Vol. 32, No. 4, January 2015, Article 10.
  18. J. Ousterhout, A. Gopalan, A. Gupta, A. Kejriwal, C. Lee, B. Montazeri, D. Ongaro, S. J. Park, H. Qin, M. Rosenblum, S. Rumble, R. Stutsman, and S. Yang, "The RAMCloud Storage System," ACM Transactions on Computer Systems, Vol. 33, No. 3, August 2015, pp. 7:1–7:55.
  19. S. Roghanchi, J. Eriksson, and N. Basu, "ffwd: Delegation is (Much) Faster Than You Think," Proc. 26th ACM Symposium on Operating Systems Principles, October 2017, pp. 342–358.
  20. H. Qin, Q. Li, J. Speiser, P. Kraft, and J. Ousterhout, "Arachne: Core-Aware Thread Management," paper in submission.