CS 736 @ UW-Madison Fall 2020 Reading List

Imported from https://canvas.wisc.edu/courses/205576/pages/paper-list. The reading list was put together by Prof. Andrea Arpaci-Dusseau.

This semester, we are reading many of the paper that the OS community has placed into the SIGOPS Hall of Fame (Links to an external site.). The SIGOPS Hall of Fame Award was instituted in 2005 to recognize the most influential Operating Systems papers that were published at least ten years in the past. We've marked those papers on our reading list that are in the Hall of Fame.

Schedule

File and Storage Systems

1. Background: Traditional Local File Systems -- FFS and LFS

   1. FFS - Questions, Background: Disk Questions McKusick, M.K., Joy, W.N., Leffler, S.J., and Fabry, R.S. , A Fast File System for UNIXLinks to an external site. , ACM Transactions on Computer Systems, Vol. 2, No. 3, August 1984, pp. 181-197. SIGOPS Hall of Fame Award

   2. LFS - Questions Rosenblum, M. and Ousterhout, J. The Design and Implementation of a Log-Structured File SystemLinks to an external site. , ACM Transactions on Computer Systems, Vol. 10, No. 1, February 1992, pp. 26-52. SIGOPS Hall of Fame Award

2. Background: Storage Technology -- RAID

   1. RAID - Questions Patterson, D., Gibson, G., and Katz, R., A Case for Redundant Arrays of Inexpensive Disks (RAID)Links to an external site. Proceedings of the 1988 ACM SIGMOD Conference on Management of Data, Chicago IL, June 1988. SIGOPS Hall of Fame Award

   2. RDP (No questions yet) Row-Diagonal Parity for Double Disk Failure Correction (Links to an external site.), (Links to an external site.) Proceedings of USENIX File and Storage Technology (FAST), 2004, FAST Test of Time Award

3. Measurement

   1. iBench - Questions Tyler Harter, Chris Dragga, Michael Vaughn, Andrea C. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau A file is not a file: understanding the I/O behavior of Apple desktop applications Links to an external site.SOSP '11 Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles Pages 71-83 SOSP Best Paper, UW-Madison Authors

4. Archival Storage and Deduplication-Questions

   1. SnapMirror SnapMirror: File-System-Based Asynchronous Mirroring for Disaster Recovery,2002 FAST Test of Time Award

   2. Venti Venti: A New Approach to Archival Storage, 2002 FAST Test of Time Award

   3. Deduplication Avoiding the Disk Bottleneck in the Data Domain Deduplication File System,2008 FAST Test of Time Award

5. Caching

   1. ARC (No questions yet) ARC: A Self-Tuning, Low Overhead Replacement Cache, 2003 FAST Test of Time Award

6. Crash Consistency

   1. Alice - Questions Thanumalayan Sankaranarayana Pillai, Vijay Chidambaram, Ramnatthan Alagappan, Samer Al-Kiswany, Andrea C. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau, All File Systems Are Not Created Equal: On the Complexity of Crafting Crash-Consistent Applications Links to an external site.Proceedings of the 11th Symposium on Operating Systems Design and Implementation (OSDI '14) Broomfield, CO, October 2014. UW-Madison Authors

   2. OptFS - Questions Vijay Chidambaram, Thanumalayan Sanakaranarayana Pillai, Andrea C. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau Optimistic Crash Consistency Links to an external site.Symposium on Operating System Principles, SOSP 2013 , UW-Madison Authors

7. SSDs and Key-Value Stores

   1. Unwritten SSD Contract Jun HeLinks to an external site., Sudarsun KannanLinks to an external site., Andrea C. Arpaci-DusseauLinks to an external site., Remzi H. Arpaci-DusseauLinks to an external site. The Unwritten Contract of Solid State Drives Links to an external site.Proceedings of the 20th European Conference on Computer Systems (EuroSys '17) Belgrade, Serbia, April 2017. UW-Madison Authors

   2. Bourbon (preprint in hotcrp) Yifan Dai, Yien Xu, Aishwarya Ganesan, Ramnatthan Alagappan, Brian Kroth, Andrea Arpaci-Dusseau, and Remzi Arpaci-Dusseau. From WiscKey to Bourbon: A Learned Index for Log-Structured Merge Trees. In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI’20), October 2020. UW-Madison Authors

      1. Optional Background: WiscKey - Questions Lanyue LuLinks to an external site., Thanumalayan Sankaranarayana PillaiLinks to an external site., Andrea C. Arpaci-DusseauLinks to an external site.,Remzi H. Arpaci-DusseauLinks to an external site. WiscKey: Separating Keys from Values in SSD-conscious Storage Links to an external site.Proceedings of the 14th USENIX Conference on File and Storage Technologies (FAST '16) UW-Madison Authors

8. Persistent Memory

   1. Mnemosyne Haris Volos, Andres Jaan Tack, Michael M. Swift. Mnemosyne: Lightweight Persistent MemoryLinks to an external site., ASPLOS '11: Proceedings of the 16th International Conference on Architectural, UW-Madison Authors

   2. Level Hash - Questions Pengfei Zuo, Yu Hua, and Jie Wu, Write-Optimized and High-Performance Hashing Index Scheme for Persistent Memory (Links to an external site.)Huazhong University of Science and Technology, OSDI'18

9. Graph Processing - Don't read

   1. Links to an external site.GraphChi - Questions for all 3 papers Aapo Kyrola and Guy Blelloch and Carlos Guestrin GraphChi: Large-Scale Graph Computation on Just a PC. (Links to an external site.)USENIX Symposium on Operating Systems Design and Implementation (OSDI'12).

   2. Xstream Amitabha Roy, Ivo Mihailovic, Willy Zwaenepoel Xstream: Edge-centric graph processing using streaming partitions. (Links to an external site.)Symposium on Operating Systems Principles (2013).

   3. FlashGraph Da Zheng and Disa Mhembere and Randal Burns and Joshua Vogelstein and Carey E. Priebe and Alexander S. Szalay, FlashGraph: Processing Billion-Node Graphs on an Array of Commodity SSDs, (Links to an external site.)Conference on File and Storage Technologies (FAST 2015)

Process Synchronization and Scalability

1. Background: Monitors, Theory and Practice- Questions: Monitors

   1. Monitors C.A.R. Hoare Monitors: An Operating System Structuring Concept Links to an external site.Communications of the ACM 17, 10, October 1974, pp. 549-557
   2. Mesa Butler W. Lampson, David D. Redell Experiences with Processes and Monitors in Mesa Links to an external site.Communications of the ACM, 23 2, February 1980, pp. 105-117. SIGOPS Hall of Fame Award
2. OS Scalability: Measurement and Redesign

   1. (Links to an external site.)Measurement - Questions Silas Boyd-Wickizer, Austin T. Clements, Yandong Mao, Aleksey Pesterev, M. Frans Kaashoek, Robert Morris, and Nickolai Zeldovich An Analysis of Linux Scalability to Many Cores (Links to an external site.) In Proceedings of the 9th Symposium on Operating Systems Design and Implementation (OSDI), Vancouver, Canada, October 2010
   2. Scalable Commutativity - Questions Austin T. Clements, M. Frans Kaashoek, Nickolai Zeldovich, Robert T. Morris, and Eddie Kohler The Scalable Commutativity Rule: Designing Scalable Software for Multicore Processors. (Links to an external site.) In Proceedings of the 24th ACM Symposium on Operating Systems Principles (SOSP), Farmington, PA, November 2013.
3. Alternate Locking Primitives

   1. Delegation - Questions: Delegation Jean-Pierre Lozi and Florian David and Gael Thomas and Julia Lawall and Gilles Muller, Remote Core Locking: Migrating Critical-Section Execution to Improve the Performance of Multithreaded Applications, (Links to an external site.)USENIX Annual Technical Conference (ATC'12), 2012.
   2. Shuffle Locks Sanidhya Kashyap, Irina Calciu, Xiaohe Cheng, Changwoo Min, Taesoo Kim, Scalable and Practical Locking with Shufflin (Links to an external site.)g, SOSP'19

Scheduling

1. Background: Threads and Events

   1. Scheduler Activations - Questions Anderson, T., Bershad, B., Lazowska, E., and Levy, H. Scheduler Activations: Effective Kernel Support for the User-Level Management of ParallelismLinks to an external site. ACM Transactions on Computer Systems, Vol. 10, No. 1, February 1992, pp. 53-79.
   2. SEDA Matt Welsh, David Culler, Eric Brewer (UC Berkeley) SEDA: An Architecture for Well-Conditioned, Scalable Internet Services (Links to an external site.) SOSP'01
2. Background: Local CPU Schedulers and Resource Tracking

   1. Lottery Scheduling - Questions Waldspurger, C.A. and Weihl, W.E. Lottery Scheduling: Flexible Proportional-Share Resource Mangement Links to an external site.Proceedings of the First Symposium on Operating Systems Design and Implementation, Monterey CA, November 1994, pp. 1-11.
   2. Resource Containers - Questions Banga, G., Druschel, P,. Mogul, J. Resource Containers: A New Facility for Resource Management in Server SystemsLinks to an external site. Proceedings of the Third Symposium on Operating System Design and Implementation (OSDI-III), New Orleans, LA, February, 1999, 45-58.
3. Measurement: Linux and System Services

   1. Linux Scheduler Jean-Pierre Lozi (Université de Nice Sophia-Antipolis), Baptiste Lepers (Ecole Polytechnique Fédérale de Lausanne), Justin Funston (University of British Columbia), Fabien Gaud (Coho Data), Vivien Quéma (Grenoble INP / ENSIMAG), Alexandra Fedorova The Linux Scheduler: A Decade of Wasted Cores. (Links to an external site.)Eurosys 2016
   2. TAM - Questions Suli Yang, Jing Liu, Andrea C. Arpaci-Dusseau, and Remzi H. Arpaci-Dusseau Principled Schedulability Analysis for Distributed Storage Systems using Thread Architecture Models (Links to an external site.)(OSDI'18) UW-Madison Authors

      1. Optional Background Split-Level I/O Scheduling Links to an external site.Suli Yang, Tyler Harter, Nishant Agrawal, Salini Selvaraj Kowsalya, Anand Krishnamurthy, Samer Al-Kiswany, Andrea C. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau Split-Level I/O Scheduling Links to an external site.Proceedings of the 25th ACM Symposium on Operating Systems Principles (SOSP '15) UW-Madison Authors
4. Current System Scheduling

   1. Monotasks - Questions Kay Ousterhout (UC Berkeley); Christopher Canel (Carnegie Mellon University); Sylvia Ratnasamy (UC Berkeley); Scott Shenker Monotasks: Architecting for Performance Clarity in Data Analytics Frameworks (Links to an external site.), SOSP'17
   2. Arachne - Questions: Arachne Henry Qin, Qian Li, Jacqueline Speiser, Peter Kraft, and John Ousterhout,Stanford University, (Links to an external site.)Arachne: Core-Aware Thread Management (Links to an external site.)OSDI'18 (Links to an external site.)
5. Current System Scheduling 2

   1. Themis (Links to an external site.) (Links to an external site.)Kshiteej Mahajan, Arjun Balasubramanian, Arjun Singhvi, Shivaram Venkataraman, and Aditya Akella, University of Wisconsin-Madison;Amar Phanishayee,Microsoft Research;Shuchi Chawla,University of Wisconsin-Madison, Themis: Fair and Efficient GPU Cluster Scheduling (Links to an external site.)- NSDI 2020, UW-Madison Authors

OS Structure and Virtual Machines

1. Background: Layered vs. Extensible Kernels

   1. THE - Questions Edsger W. DijkstraThe Structure of the "THE" Multiprogramming SystemLinks to an external site. Communications of the ACM 11(5), May 1968. SIGOPS Hall of Fame Award
   2. Nucleus - Questions Per Brinch Hansen, The Nucleus of a Multiprogramming SystemLinks to an external site. Communications of the ACM 13(4), April 1970
2. Microkernels: Concepts and Measurements

   1. Exokernel - Questions Dawson R. Engler, M. Frans Kaashoek, and James O’Toole Jr Exokernel: An Operating System Architecture for Application-Level Resource Management (Links to an external site.) SOSP '95 Proceedings of the fifteenth ACM symposium on Operating systems principles
   2. Arrakis Simon Peter, Jialin Li, Irene Zhang, Dan R. K. Ports, Doug Woos, Arvind Krishnamurthy, and Thomas Anderson, University of Washington; Timothy Roscoe, ETH Zürich Arrakis: The Operating System is the Control Plane, (Links to an external site.) OSDI'14

      1. Optional Background - Barrelfish Andrew Baumann, Paul Barham, Pierre-Evariste Dagand, Tim Harris, Rebecca Isaacs, Simon Peter, Timothy Roscoe, Adrian Schüpbach, and Akhilesh Singhania. The Multikernel: A new OS architecture for scalable multicore systems (Links to an external site.). (Links to an external site.) In Proceedings of the 22nd ACM Symposium on OS Principles, Big Sky, MT, USA, October 2009
3. Monolithic, Disaggregation, and HLLs

   1. UNIX Ritchie, D.M. and Thompson, K. The UNIX Time-Sharing SystemLinks to an external site. Communications of the ACM, Vol. 17, No. 7, July 1974, pp. 365-375. SIGOPS Hall of Fame Award
   2. Disaggregation Yizhou Shan, Yutong Huang, Yilun Chen, and Yiying Zhang, LegoOS: A Disseminated, Distributed OS for Hardware Resource Disaggregation, (Links to an external site.)OSDI 2018
   3. HLLs - Questions Cody Cutler, M. Frans Kaashoek, and Robert T. Morris, MIT CSAIL, The benefits and costs of writing a POSIX kernel in a high-level language, (Links to an external site.)OSDI 2018
4. Virtual Machines

   1. Disco - Questions Edouard Bugnion, Scott Devine, Mendel Rosenblum. Disco: Running Commodity Operating Systems on Scalable MultiprocessorsLinks to an external site. Proceedings of The Sixteenth Symposium on Operating Systems Principles (October 1997). SIGOPS Hall of Fame Award
   2. (Links to an external site.)ESX - Questions Carl A. Waldspurger Memory Resource Management in VMware ESX Server Links to an external site.In Proc. Fifth Symposium on Operating Systems Design and Implementation (OSDI ’02), Dec. 2002 SIGOPS Hall of Fame Award
   3. Revirt George W. Dunlap, Samuel T. King, Sukru Cinar, Murtaza A. Basrai, and Peter M. Chen. ReVirt: Enabling intrusion analysis through virtual-machine logging and replay (Links to an external site.). In Proceedings of the 5th Symposium on Operating Systems Design and Implementation (OSDI '02), 2002, 211-224. SIGOPS Hall of Fame Award

      1. Optional Overview Bugnion, Nief, Tsafir, Hardware and Software Support for Virtualization Synthesis Lectures on Computer Architecture

Testing, Debugging, and Design

1. Profiling and Binary Code

   1. KernInst Ariel Tamches and Barton P. Miller, "Fine-Grained Dynamic Instrumentation of Commodity Operating System Kernels",3rd Symposium on Operating Systems Design and Implementation (OSDI),New Orleans, Louisiana, February 1999. UW-Madison Authors

      1. Optional

         1. Nathan E. Rosenblum, Xiaojin (Jerry) Zhu and Barton P. Miller, "Who Wrote This Code? Identifying the Authors of Program Binaries", 2011 European Symposium on Research in Computer Security (ESORICS), Leuven, Belgium, September 2011. UW-Madison Authors

         2. Xiaozhu Meng (Links to an external site.) and Barton P. Miller, Binary Code is Not Easy, International Symposium on Software Testing and Analysis, 2016 UW-Madison Authors
2. Symbolic Execution and Debugging Experience

   1. KLEE Cristian Cadar, Daniel Dunbar, and Dawson Engler. KLEE: Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs. In OSDI’08, SIGOPS Hall of Fame Award

   2. Debug Kirk Glerum, Kinshuman Kinshumann, Steve Greenberg, Gabriel Aul, Vince Orgovan, Greg Nichols, David Grant, Gretchen Loihle, and Galen Hunt.Debugging in the (Very) Large: Ten Years of Implementation and Experience. In SOSP ’09, SIGOPS Hall of Fame Award

3. Summary of System Design

   1. Hints Butler Lampson Hints for Computer System Design (Links to an external site.), Proceedings of the Ninth ACM Symposium on Operating Systems Principles, pp. 33-48, October 1983, Bretton Woods, NH, USA. SIGOPS Hall of Fame Award

Other Relevant SIGOPS Hall of Fame Papers (not covered)

1. Daniel G. Bobrow, Jerry D. Burchfiel, Daniel L. Murphy and Raymond S. Tomlinson. Tenex, A Paged Time Sharing System for the PDP-10 (Links to an external site.) Communications of the ACM 15(3), March 1972. SIGOPS Hall of Fame Award (Links to an external site.)
2. Daley, R.C., and Dennis, J.B. Virtual Memory, Processes, and Sharing in MULTICSLinks to an external site. Communications of the ACM, Vol. 11, No. 5, May 1968, pp. 306-312. (Multics paper in SIGOPS Hall of Fame (Links to an external site.))
3. R. Rashid and A. Tevanian and M. Young and D. Golub and R. Baron and D. Black and W. Bolosky and J. Chew, Machine-Independent Virtual Memory Management for Paged Uniprocessor and Multiprocessor ArchitecturesLinks to an external site. SIGOPS Hall of Fame Award (Links to an external site.) Proceedings of the 2nd International Conference on Architectural Support for Programming Languages and Operating System (ASPLOS), 1987. (Mach in SIGOPS Hall of Fame (Links to an external site.))
4. J. Liedtke. On micro-kernel construction (Links to an external site.). In Proceedings of the 15th ACM symposium on Operating Systems Principles (SOSP '95), December 1995, 237-250. SIGOPS Hall of Fame Award (Links to an external site.)