W1 |
Tue 08/27 |
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/29 |
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/03 |
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/05 |
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"?
|
|
|
W3 |
Tue 09/10 |
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 RC4000 Nucleus in terms of their goals to provide a basis on which higher level OS functionality can be implemented.
|
|
|
|
Thu 09/12 |
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/17 |
Virtual Machine |
- Disco: Running Commodity Operating Systems on Scalable Multiprocessors, Bugnion, Devine, and Rosenblum, SOSP, 1997
Additional Reading
Questions
Disco
- Q: Compare and contrast Disco with Exokernel
|
|
Lab 1 due |
|
Thu 09/19 |
Project hack day |
|
|
|
|
Fri 09/20 |
|
|
|
Finalized proposal due |
W5 |
Tue 09/24 |
Virtual Machine |
- Xen and the Art of Virtualization, Barham, Dragovic, Fraser, Hand, Harris, Ho, Neugebauer, Pratt, and Warfield, SOSP, 2003
- 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
Additional Reading
Questions
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?
VMM v. Microkernels
- Are you convinced that VMMs are microkernels done right? Why?
|
1. Jake Block, Wynn Kaza, Jiarui Li 2, 3. Ivris Raymond, Robert Stanley, Mohammadali Kodeih |
|
|
Thu 09/26 |
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
|
1. Yogi Sahu, Liam Mulcahy 2. Jake Block, Wynn Kaza, Jiarui Li |
|
W6 |
Tue 10/01 |
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
|
1. Paul Aldea, Pranav Bangarbale, Rishi Patel 2. Gabe Lounsbury, Ann Stone |
|
|
Thu 10/03 |
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?
|
1. Paul Aldea, Pranav Bangarbale, Rishi Patel 2. Jiawei He, Jirong Yang, Fangyi Dai |
|
W7 |
Tue 10/08 |
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?
|
1. Adarsh Ponaka, Nolan Kuza, Gabe Lounsbury 2. Archit Bhatnagar, Mushtari Sadia |
|
|
Thu 10/10 |
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?
|
1. Ziming Zhou, Ivris Raymond 2. Mohammadali Kodeih, Ryan Kim |
|
W8 |
Tue 10/15 |
Fall Break |
|
|
|
|
Thu 10/17 |
Distribution |
- The Sprite Network Operating System, Ousterhout, Cerenson, Douglis, Nelson, and Welch, IEEE Computer, 1988
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
- LegoOS: A Disseminated, Distributed OS for Hardware Resource Disaggregation, Shan, Huang, Chen, and Zhang, OSDI, 2018
Questions
Sprite
- Q: How does Sprite achieve transparency for its process migration?
|
1. Liam Mulcahy, Jayanaka Dantanarayana |
Checkpoint #1 report due |
W9 |
Tue 10/22 |
Mid-semester Presentations |
|
|
|
|
Thu 10/24 |
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?
|
|
|
W10 |
Tue 10/29 |
Kernel Bypass |
- Arrakis: The Operating System is the Control Plane, Peter, Li, Zhang, Ports, Woos, Krishnamurthy, Anderson, and Roscoe, OSDI, 2014
Additional Reading
- IX: A Protected Dataplane Operating System for High Throughput and Low Latency, Belay, Prekas, Klimovic, Grossman, Kozyrakis, and Bugnion, OSDI, 2014
- 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?
|
|
|
|
Thu 10/31 |
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
|
|
|
W11 |
Tue 11/05 |
Project hack day |
|
|
|
|
Thu 11/07 |
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/12 |
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/14 |
Emerging Memory |
- TPP: Transparent Page Placement for CXL-Enabled Tiered-Memory, Maruf, Wang, Dhanotia, Weiner, Agarwal, Bhattacharya, Petersen, Chowdhury, Kanaujia, and Chauhan, ASPLOS, 2023
Additional Reading
- 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
- AIFM: high-performance, application-integrated far memory, Ruan, Schwarzkopf, Aguilera, and Belay, OSDI, 2020
- Partial Failure Resilient Memory Management System for (CXL-based) Distributed Shared Memory, Zhang, Ma, Hua, Liu, Chen, Ding, Du, Jiang, Ma, and Wu, SOSP, 2023
|
|
|
W13 |
Tue 11/19 |
Project hack day |
|
|
Checkpoint #2 report due |
|
Thu 11/21 |
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/26 |
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/28 |
Thanksgiving break |
|
|
|
W15 |
Tue 12/03 |
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/05 |
Final Presentations |
|
|
|