Reading List

  • OS History and Architecture
    • [1] P. Brinch Hansen, "The Nucleus of a Multiprogramming System", Communications of the ACM, 238-242, April 1970. Direct Link
      • No questions
    • [2] Dennis M. Ritchie and Ken Thompson, "The UNIX Time-Sharing System", Communications of the ACM, volume 17, number 7, July 1974. Direct Link
      • Question 1: The paper mentions "i-nodes" that contain file descriptions; name three pieces of information you can find in an i-node.
    • [3] Dawson R. Engler, M. Frans Kaashoek, and James O'Toole Jr., "Exokernel: An Operating System Architecture for Application-Level Resource Management", Proc. of the 15th Symposium on Operating Systems Principles, December 1996. Direct Link
      • No questions
  • Storage and File Systems
    • [4] Marshal Kirk McKusick, William Koy, Samuel Leffler, and Robert Fabry, "A Fast File System for Unix", ACM Transactions on Computer Systems, volume 2, issue 3, August 1984. DOI
      • Question 1: In a file system, what is a "free list" used for?
      • Question 2: In some file systems, the "free list" is replaced by a "bit map"; what is the difference?
    • [5] Mendel Rosenblum and John Ousterhout, "The Design and Implementation of a Log Structured File System", Proceedings of the Symposium on Operating Systems Principles, 1991. DOI [Sections 1-3.4 only]
      • No questions
    • [6] Changman Lee, Dongho Sim, Joo-Young Hwang, and Sangyeun Cho "F2FS: A New File System for Flash Storage", Proceedings of the 13th USENIX Conference on File and Storage Technologies (FAST), 2015. Direct Link [Sections 1-2.6 only]
      • No questions
    • [7] B. Randell, P. Lee, and P. C. Treleaven. 1978. Reliability Issues in Computing System Design. ACM Comput. Surv. 10, 2 (June 1978), 123-165. Direct Link [Sections 1-4 only]
      • Question 1: Write your month of birth as integer (e.g., May = 5); then write your month of birth as a byte (e.g., 5 = 0000 0101). Then add a single even parity bit for this number (yielding a 9-digit number); clearly indicate the bit you've added.
      • Question 2: For a TMR system, where the three replicated components have outputs 5, 7, and 5, what will be the output of the voter?
    • [8] Peter Chen, Edward Lee, Garth Gibson, Randy Katz, and David Patterson, "RAID: High-Performance, Reliable Secondary Storage", ACM Computing Surveys, volume 26, number 2, June 1994. Direct Link [Sections 1-3.4 only]
      • Question 1: If write performance is your primary concern, would you choose RAID Level 0 or RAID Level 1? Explain!
      • Question 2: If you wanted to reduce your risk of data loss, would you choose RAID Level 0 or RAID Level 1? Explain!
    • [9] Mahesh Balakrishnan, Asim Kadav, Vijayan Prabhakaran, and Dahlia Malkhi, "Differential RAID: Rethinking RAID for SSD Reliability", ACM Transactions on Storage, volume 6, issue 2, July 2010. DOI [Skip 3.3 and 3.4]
      • No questions
    • [10] John Howard, Michael Kazarm Sherri Menees, David Nichols, M. Satyanarayanan, Robert Sidebotham, and Michael West, "Scale and Performance in a Distributed File System", ACM Transactions on Computer Systems, Volume 6, Number 1, February 1988. DOI
      • Question 1: What does RPC stand for?
      • Question 2: What is an advantage of "whole-file caching compared to more fine-grained caching?"
    • [11] Sage Weil, Scott Brandt, Ethan Miller, Darrell Long, and Carlos Maltzahn, "Ceph: A Scalable, High Performance Distributed File System", Proceedigns of USENIX Operating Systems Design and Implementation, 2006. Direct Link
      • No questions
    • [12] Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung, "The Google File System", Proceedings of the ACM Symposium on Operating Systems Principles (SOSP), 2003. Direct Link
      • No questions
  • Threads, Events, Concurrency
    • [13] D. Stein and D. Shah, "Implementing Lightweight Threads", Proc. of USENIX, San Antonio, TX, June 1992. Direct Link
      • Question 1: Explain briefly what "thread-local storage" is in comparison to "regular" variables used by threads?
      • Question 2: What is a "thread ID"?
    • [14] John Ousterhout, "Why Threads are a Bad Idea (for most purposes)", talk given at USENIX Annual Conference, September 1995. Direct Link
      • No questions
    • [15] Rob von Behren, Jeremy Condit, and Eric Brewer, "Why Events are a Bad Idea (for high-concurrency servers)", Workshop on Hot Topics in Operating Systems, 2003. Direct Link
      • No questions
    • [16] Matt Welsh, David Culler, and Eric Brewer, "SEDA: An Architecture for Well-Conditioned, Scalable Internet Services", ACM Symposium on Operating Systems Principles, 2001. Direct Link
      • Question 1: Apache uses a concept called "bounded thread pools". What does that mean?
    • [17] C. A. R. Hoare, "Monitors: An Operating Systems Structuring Concept", Communications of the ACM, 17, 10, October 1974. ACM
      • Question 1: What are the two operations used on condition variables?
    • [18] Thomas Anderson, Brian Bershad, Edward Lazowska, and Henry Levy, "Scheduler Activations: Effective Kernel Support for the User-Level Management of Parallelism", ACM Transactions on Computer Systems, vol. 10, no. 1, February 1992. ACM [Sections 1-3.2 only]
      • No questions
    • [19] Tongping Liu, Charlie Curtsinger, and Emery D. Berger, "Dthreads: Efficient Deterministic Multithreading", ACM Symposium on Operating Systems Principles, October 2011. ACM [Sections 1-4 only]
      • No questions
  • Memory Management
    • [20] Peter Denning, "The Working Set Model for Program Behavior", Communications of the ACM, 1968. Direct Link
      • No questions
    • [21] Richard Carr and John Hennessy, "WSClock -- A Simple and Effective Algorithm for Virtual Memory Management", Proceedings of the Symposium on Operating Systems Principles, 1981. ACM
      • No questions
    • [22] A. Bensoussan and R. Daley, "The Multics Virtual Memory: Concepts and Design", Proceedings of the Symposium on Operating Systems Principles, 1969. ACM
      • Question 1: Explain the concept of a "page" in memory. What problem does the use of pages eliminate (similar to what blocks achieve on disks)?
      • Question 2: What is the purpose of a "page table"? What exactly is stored in such a table?
    • [23] Juan Navarro, Sitaram Iyer, Peter Druschel, and Alan Cox, "Practical, Transparent Operating System Support for Superpages", Proceedings of USENIX Operating Systems Design and Implementation, 2002. Direct Link
      • Question 1: What does TLB stand for and what exactly is being cached by the TLB?
    • [24] Michael Young, Avadis Tevanian, Richard Rashid, David Golub, Jeffrey Eppinger, Johnathan Chew, William Bolosky, David Black, and Robert Baron, "The Duality of Memory and Communication in the Implementation of a Multiprocessor Operating System", Proceedings of the Symposium on Operating Systems Principles, 1987. Direct Link
      • No questions
  • Virtual Machines
    • [25] Robert P. Goldberg, "Survey of Virtual Machine Research", Computer, 1974. IEEE
      • Question 1: What is the "release trauma" mentioned in the paper?
    • [26] Mendel Rosenblum and Tal Garfinkel, "Virtual Machine Monitors: Current Technology and Future Trends", Computer, 2005. Direct Link
      • Question 1: What is paravirtualization?
    • [27] James E. Smith and Ravi Nair, "The Architecture of Virtual Machines", Computer, 2005. Direct Link
      • No questions
    • [28] P. Barham, D. Dragovic, K. Fraser, S. Hand, T. Harris, A. Ho, R. Neugebauer, I. Pratt, and A. Warfield, "Xen and the Art of Virtualization", 2003. Direct Link
      • Question 1: What is a "hypercall"?
  • Scheduling
    • [29] J. Andrus, C. Dall, A. Van't Hof, O. Laadan, and J. Nieh, "Cells: A Virtual Mobile Smartphone Architecture", 2011. Direct Link
      • No questions
    • [30] G. C. Buttazzo, "Rate Monotonic vs. EDF: Judgment Day", 2005. Direct Link
      • Question 1: How would you define "jitter"?
      • Question 2: How does Rate Monotonic Scheduling determine task priorities?
    • [31] P. Pillai and K. G. Shin, "Real-Time Dynamic Voltage Scaling for Low-Power Embedded Operating Systems", 2001. Direct Link
      • No questions
  • Surviving and Thriving in Grad School
    • [A] Lucia Dettori, "Research Talk 101", DePaul University, June 2007. Direct Link
    • [B] Roy Levin and David D. Redell, "An Evaluation of the Ninth SOSP Submissions or How (and How Not) to Write a Good Systems Paper", ACM SIGOPS Operating Systems Review, 1983. Direct Link
    • [C] "How to Write a Research paper", Presentation Slides. Direct Link
    • [D] "Writing Reviews for Systems Conferences", Timothy Roscoe, ETH Zuerich, March 2007. Direct Link
    • [E] "Giving a Research Talk", Prof. Aaron Striegel (Notre Dame). Direct Link
    • [F] "The Task of the Referee", Alan Jay Smith, University of California. Direct Link