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!
  • Threads, Events, Concurrency
    • [4] 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"?
    • [5] John Ousterhout, "Why Threads are a Bad Idea (for most purposes)", talk given at USENIX Annual Conference, September 1995. Direct Link
      • No questions!
    • [6] 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!
    • [7] 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 this mean?
    • [8] 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?
    • [9] 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!
    • [10] 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!
  • Storage and File Systems
    • [11] 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?
    • [12] 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!
    • [13] 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 only]
      • No questions!
    • [14] 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 and 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?
    • [15] 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 was 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.
    • [16] 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!
    • [17] 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?
    • [18] 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!
    • [19] 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!
  • Memory Management
    • [20] Peter Denning, "The Working Set Model for Program Behavior", Communications of the ACM, 1968. Direct Link
    • [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
    • [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: What is a "page"?
      • Question 2: What is the purpose of a "page 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: A TLB is a cache. What exactly is being cached in a 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

Facilities

Several facilities are available for carrying out your project:
  • College of Engineering Cluster. The Engineering workstation cluster on the first floor of Fitzpatrick Hall can be used for this course. Note that a person sitting at the console of such a machine has priority over those who log in remotely.
  • Virtual Machines.
  • Computing Research Center (CRC). The CRC is a university-wide facility that provides access to a large high performance computing cluster as well as an assortment of large-memory and many-core machines. See the CRC web site to obtain an account.

Old Exams


Resources and References