W1 |
Tue 08/26 |
Course Intro |
- Rise of Worse Is Better, Gabriel, "Lisp: Good News, Bad News, How to Win Big", 1989
Additional Reading
- Example of Worse-Is-Better in Linux vs Unix, Ts'o, TUHS mailing list, 2017
- Worse is Better is Worse, Bourbaki[Gabriel], 2000
- End-to-End Arguments in System Design, Saltzer, Reed, and Clark, ACM TOCS, 1984
- Hints for Computer System Design, Lampson, SOSP, 1983
- The Emperor's Old Clothes, Hoare, CACM, 1981
- How (and How Not) to Write a Good Systems Paper, Levin and Redell, ACM SIGOPS OSR, 1983
|
|
Reviews not required; Lab 1 released |
|
Thu 08/28 |
Historical Perspective |
- The Structure of the 'THE'-Multiprogramming System, Dijkstra, SOSP, 1967
- The Nucleus of a Multiprogramming System, Hansen, CACM, 1970
Questions
THE
- 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?
Nucleus
- Q: How does synchronization in the RC 4000 system compare with synchronization in the THE system?
|
|
Reviews not required |
W2 |
Tue 09/02 |
Time-Sharing |
- Structure of the Multics Supervisor, Vyssotsky, Corbató, and Graham, Fall Joint Computer Conference, 1965
- The UNIX Time-Sharing System, Ritchie and Thompson, CACM, 1974
Additional Reading
- The Multics virtual memory: concepts and design, Bensoussan, Clingen, and Daley, CACM, 1972
- Protection and the control of information sharing in Multics, Saltzer, CACM, 1974
- The Evolution of the Unix Time-sharing System, Ritchie, Bell Labs Technical Journal, 1984
Questions
Multics
- Q: How does the virtual memory design of Multics compare to that of modern operating systems in terms of similarities and differences?
UNIX
- Q: What aspects of Unix as described in the 1974 paper do not survive today, or have been considerably changed?
|
|
|
|
Thu 09/04 |
OS Structure |
- Plan 9 From Bell Labs, Pike, Presotto, Dorward, Flandrena, Thompson, Trickey, and Winterbottom, USENIX Computing Systems, 1995
- Mach: A New Kernel Foundation For UNIX Development, Accetta, Baron, Bolosky, Golub, Rashid, Tevanian, and Young, USENIX, 1986
Questions
Plan 9
- 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"?
Mach
- Q: How do Mach's goals and its "port" abstractions compare with RC 4000's?
|
|
|
W3 |
Tue 09/09 |
OS Structure |
- On μ-Kernel Construction, Liedtke, SOSP, 1995
- The Performance of μ-Kernel-Based Systems, Härtig, Hohmuth, Liedtke, Schönberg, and Wolter, SOSP, 1997
Additional Reading
Questions
L4
- Q: Compare and contrast the L4 microkernel with the RC 4000 (Nucleus) in terms of their goals to provide a basis on which higher level OS functionality can be implemented.
|
|
|
|
Thu 09/11 |
OS Structure |
- Exokernel: An Operating System Architecture for Application-Level Resource Management, Engler, Kaashoek, and O'Toole, SOSP, 1995
- Rethinking the Library OS from the Top Down, Porter, Boyd-Wickizer, Howell, Olinsky, and Hunt, ASPLOS, 2011
Additional Reading
- Application Performance and Flexibility on Exokernel Systems, Kaashoek, Engler, Ganger, Briceño, Hunt, Mazières, Pinckney, Grimm, Jannotti, and Mackenzie, SOSP, 1997
- Extensibility safety and performance in the SPIN operating system, Bershad, Savage, Pardyak, Sirer, Fiuczynski, Becker, Chambers, and Eggers, SOSP, 1995
Questions
Exokernel
- Q: Compare and contrast an exokernel with a microkernel.
Drawbridge
- Q: How does Drawbridge differ with Exokernel in terms of their motivation and approaches?
|
|
Draft proposal due |
W4 |
Tue 09/16 |
Virtual Machine |
- Disco: Running Commodity Operating Systems on Scalable Multiprocessors, Bugnion, Devine, and Rosenblum, SOSP, 1997
- Xen and the Art of Virtualization, Barham, Dragovic, Fraser, Hand, Harris, Ho, Neugebauer, Pratt, and Warfield, SOSP, 2003
Additional Reading
Questions
Disco
- Q: Compare and contrast Disco with Exokernel
Xen
- 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 contrast with the VMM approach in Xen?
|
|
Lab 1 due |
|
Thu 09/18 |
Project hack day |
|
|
|
|
Fri 09/19 |
|
|
|
Finalized proposal due |
W5 |
Tue 09/23 |
Virtual Machine |
- A Comparison of Software and Hardware Techniques for x86 Virtualization, Adams and Agesen, ASPLOS, 2006
- The Turtles Project: Design and Implementation of Nested Virtualization, Ben-Yehuda, Day, Dubitzky, Factor, Har'El, Gordon, Liguori, Wasserman, Yassour, OSDI, 2010
Additional Reading
- Are Virtual Machine Monitors Microkernels Done Right?, Hand, Warfield, Fraser, Kotsovinos, and Magenheimer, HotOS, 2005
- Are Virtual Machine Monitors Microkernels Done Right?, Heiser, Uhlig, and LeVasseur, ACM SIGOPS OSR, 2006
Questions
x86 virt comparison
- Why a hardware VMM can be slower than a software VMM
|
|
|
|
Thu 09/25 |
Lightweight Virtualization |
- My VM is Lighter (and Safer) than your Container, Manco, Lupu, Schmidt, Mendes, Kuenzer, Sati, Yasukata, Raiciu, and Huici, SOSP, 2017
- Dune: Safe User-level Access to Privileged CPU Features, Belay, Bittau, Mashtizadeh, Terei, Mazieres, and Kozyrakis, OSDI, 2012
Additional Reading
Questions
Dune
- Q: Compare and contrast Dune with a VMM
|
|
|
W6 |
Tue 09/30 |
Memory Management |
- Practical, transparent operating system support for superpages, Navarro, Iyer, Druschel, and Cox, OSDI, 2002
- Memory Resource Management in VMware ESX Server, Waldspurger, OSDI, 2002
Additional Reading
- Coordinated and Efficient Huge Page Management with Ingens, Kwon, Yu, Peter, Rossbach, and Witchel, OSDI, 2016
- Machine-Independent Virtual Memory Management for Paged Uniprocessor and Multiprocessor Architectures, Rashid, Tevanian, Young, Golub, Baronn, Black, Bolosky, and Chew, ASPLOS, 1987
|
|
|
|
Thu 10/02 |
Scheduling |
- Scheduler Activations: Effective Kernel Support for the User-level Management of Parallelism, Anderson, Bershad, Lazowska, and Levy, SOSP, 1991
- Lottery Scheduling: Flexible Proportional-Share Resource Management, Waldspurger and Weihl, OSDI, 1994
Additional Reading
Questions
Scheduler Activations
- 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?
Lottery Scheduling
- 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?
|
|
|
W7 |
Tue 10/07 |
File System |
- The Design and Implementation of a Log-Structured File System, Rosenblum and Ousterhout, SOSP, 1991
- The Google File System, Ghemawat, Gobioff, and Leung, SOSP, 2003
Additional Reading
- An Implementation of a Log-Structured File System for UNIX, Seltzer, Bostic, McKusick, and Staelin, USENIX, 1993
- Ousterhout's critique of Seltzer's 1993 paper, Ousterhout
- Seltzer's response to Ousterhout's critique, Seltzer
- A Fast File System for Unix, McKusick, Joy, Leffler, and Fabry, ACM TOCS, 1984
- GFS: Evolution on Fast-forward, McKusick and Quinlan, ACM Queue, 2009
Questions
LFS
- Q: Why does LFS combine threading and copying in free space management?
|
|
|
|
Thu 10/09 |
File System |
- Soft Updates: A Solution to the Metadata Update Problem in File Systems, Ganger, K.McKusick, Soules, and Patt., ACM TOCS, 2000
- Rethink the sync, Nightingale, Veeraraghavan, Chen, and Flinn, OSDI, 2006
Additional Reading
Questions
Soft Updates
- Q: What are the advantages and disadvantages of soft updates compared to write-ahead logging?
|
|
|
W8 |
Tue 10/14 |
Fall Break |
|
|
|
|
Thu 10/16 |
Project hack day |
|
|
Checkpoint #1 report due |
W9 |
Tue 10/21 |
Mid-semester Presentations |
|
|
|
|
Thu 10/23 |
Distribution |
- The Sprite Network Operating System, Ousterhout, Cerenson, Douglis, Nelson, and Welch, IEEE Computer, 1988
- LegoOS: A Disseminated, Distributed OS for Hardware Resource Disaggregation, Shan, Huang, Chen, and Zhang, OSDI, 2018
Additional Reading
- A Brief Retrospective on the Sprite Network Operating System, Ousterhout, 1992
- The Distributed V Kernel and its Performance for Diskless Workstations, Cheriton and Zwaenepoel, SOSP, 1983
- Implementing global memory management in a workstation cluster, Feeley, Morgan, Pighin, Karlin, Levy, and Thekkath, SOSP, 1995
Questions
Sprite
- Q: How does Sprite achieve transparency for its process migration?
|
|
|
W10 |
Tue 10/28 |
Serverless |
- Firecracker: Lightweight Virtualization for Serverless Applications, Brooker, Florescu, Popa, Neugebauer, Agache, Iordache, Liguori, and Piwonka, NSDI, 2020
- No Provisioned Concurrency: Fast RDMA-codesigned Remote Fork for Serverless Computing, Wei, Lu, Wang, Gu, Yang, Chen, and Chen, OSDI, 2023
Additional Reading
- Cloud Programming Simplified: A Berkeley View on Serverless Computing, Jonas, Schleier-Smith, Sreekanti, Tsai, Khandelwal, Pu, Shankar, Carreira, Krauth, Yadwadkar, Gonzalez, Popa, Stoica, and Patterson, Technical Report No. UCB/EECS-2019-3, 2019
Questions
Firecracker
- Q: What motivates the development of Firecracker, and how does the microVM differ from Linux container?
|
|
|
|
Thu 10/30 |
Kernel Bypass |
- Arrakis: The Operating System is the Control Plane, Peter, Li, Zhang, Ports, Woos, Krishnamurthy, Anderson, and Roscoe, OSDI, 2014
- IX: A Protected Dataplane Operating System for High Throughput and Low Latency, Belay, Prekas, Klimovic, Grossman, Kozyrakis, and Bugnion, OSDI, 2014
Additional Reading
- Snap: a Microkernel Approach to Host Networking, Marty, Kruijf, Adriaens, Alfeld, Bauer, Contavalli, Dalton, Dukkipati, Evans, Gribble, Kidd, Kononov, Kumar, Mauer, Musick, Olson, Rubow, Ryan, Springborn, Turner, Valancius, Wang, and Vahdat, SOSP, 2019
Questions
Arrakis
- Q: How does Arrakis ensure isolation and security?
|
|
|
W11 |
Tue 11/04 |
Kernel Bypass |
- Shenango: Achieving High CPU Efficiency for Latency-sensitive Datacenter Workloads, Ousterhout, Fried, Behrens, Belay, and Balakrishnan, NSDI, 2019
- Shinjuku: Preemptive Scheduling for μsecond-scale Tail Latency, Kaffes, Chong, Humphries, Belay, Mazières, and Kozyrakis, NSDI, 2019
Additional Reading
- ZygOS: Achieving Low Tail Latency for Microsecond-scale Networked Tasks, Prekas, Kogias, and Bugnion, SOSP, 2017
- The Demikernel Datapath OS Architecture for Microsecond-scale Datacenter Systems, Zhang, Raybuck, Patel, Olynyk, Nelson, Leija, Martinez, Liu, Simpson, Jayakar, Penna, Demoulin, Choudhury, and Badam, SOSP, 2021
Questions
Shenango
- Q: Compare and contrast Shenango with Shinjuku
|
|
|
|
Thu 11/06 |
Multi-core |
- The Multikernel: A New OS Architecture for Scalable Multicore Systems, Baumann, Barham, Dagand, Harris, Isaacs, Peter, Roscoe, Schüpbach, and Singhania, SOSP, 2009
Additional Reading
- An Analysis of Linux Scalability to Many Cores, Boyd-Wickizer, Clements, Mao, Pesterev, Kaashoek, Morris, and Zeldovich, OSDI, 2010
- Corey: An Operating System for Many Cores, Boyd-Wickizer, Chen, Chen, Mao, Kaashoek, Morris, Pesterev, Stein, Wu, Dai, Zhang, and Zhang, OSDI, 2008
- The Scalable Commutativity Rule: Designing Scalable Software for Multicore Processors, Clements, Kaashoek, Zeldovich, Morris, and Kohler, SOSP, 2013
Questions
Barrelfish
- Q: Briefly compare and contrast multikernel with microkernel.
|
|
|
W12 |
Tue 11/11 |
Language |
- RedLeaf: Isolation and Communication in a Safe Operating System, Narayanan, Huang, Detweiler, Appel, Li, Zellweger, and Burtsev, OSDI, 2020
Additional Reading
- Language Support for Fast and Reliable Message-based Communication in Singularity OS, Fähndrich, Aiken, Hawblitzel, Hodson, Hunt, Larus, and Levi, EuroSys, 2006
- Singularity: Rethinking the Software Stack, Hunt and Larus, ACM SIGOPS OSR, 2007
- Theseus: an Experiment in Operating System Structure and State Management, Boos, Liyanage, Ijaz, and Zhong, OSDI, 2020
Questions
RedLeaf
- Q: Compare and contrast RedLeaf with SPIN or Singularity.
|
|
|
|
Thu 11/13 |
Emerging Memory |
- Pond: CXL-Based Memory Pooling Systems for Cloud Platforms, Li, Berger, Hsu, Ernst, Zardoshti, Novakovic, Shah, Rajadnya, Lee, Agarwal, Hill, Fontoura, and Bianchini, ASPLOS, 2023
- Managing Memory Tiers with CXL in Virtualized Environments, Zhong, Berger, Waldspurger, Wee, Agarwal, Agarwal, Hady, Kumar, Hill, Chowdhury, and Cidon, OSDI, 2024
Additional Reading
- TPP: Transparent Page Placement for CXL-Enabled Tiered-Memory, Maruf, Wang, Dhanotia, Weiner, Agarwal, Bhattacharya, Petersen, Chowdhury, Kanaujia, and Chauhan, ASPLOS, 2023
- AIFM: high-performance, application-integrated far memory, Ruan, Schwarzkopf, Aguilera, and Belay, OSDI, 2020
|
|
|
W13 |
Tue 11/18 |
Project hack day |
|
|
Checkpoint #2 report due |
|
Thu 11/20 |
Reliability |
- Bugs as Deviant Behavior: A General Approach to Inferring Errors in Systems Code, Engler, Chen, Hallem, Chou, and Chelf, SOSP, 2001
- Improving the Reliability of Commodity Operating Systems, Swift, Bershad, and Levy, SOSP, 2003
Additional Reading
- An empirical study of operating systems errors, Chou, Yang, Chelf, Hallem, and Engler, SOSP, 2001
- KLEE: Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs, Cadar, Dunbar, and Engler, OSDI, 2008
- Operating System Support for Safe and Efficient Auxiliary Execution, Jing and Huang, OSDI, 2022
Questions
Nooks
- Q: How does XPC differ from syscall or RPC?
|
|
|
W14 |
Tue 11/25 |
Reliability |
- seL4: Formal Verification of an OS Kernel, Klein, Elphinstone, Heiser, Andronick, Cock, Derrin, Elkaduwe, Engelhardt, Kolanski, Norrish, Sewell, Tuch, and Winwood, SOSP, 2009
- Using Crash Hoare Logic for Certifying the FSCQ File System, Chen, Ziegler, Chajed, Chlipala, Kaashoek, and Zeldovich, SOSP, 2015
Additional Reading
|
|
|
|
Thu 11/27 |
Thanksgiving break |
|
|
|
W15 |
Tue 12/02 |
Security |
- SCONE: Secure Linux Containers with Intel SGX, Arnautov, Trach, Gregor, Knauth, Martin, Priebe, Lind, Muthukumaran, O'Keeffe, Stillwell, Goltzsche, Eyers, Kapitza, Pietzuch, and Fetzer, OSDI, 2016
- Shielding Applications from an Untrusted Cloud with Haven, Baumann, Peinado, and Hunt, OSDI, 2014
Additional Reading
|
|
|
|
Thu 12/04 |
Final Presentation |
|
|
|
W16 |
Thu 12/09 |
Final Report |
|
|
|