| Date |
Topic |
b |
Assignments |
Reading |
Non-required Reading |
| Tue 08/22 |
Course Intro
| |
HW 1 out
|
1) How (and How Not) to Write a Good Systems Paper (Levin and Redell, SIGOPS OSR, 1983)
2) On Being the Right Size (Haldane, 1928) lecture slides
|
You and Your Research(Hamming 1986)
|
| Thu 08/24 |
OS Design
| |
|
1) The UNIX Timesharing System (Ritchie and Thompson, SOSP, 1974) lecture slides prose notes
2) End-to-end Arguments in System Design -- (through page 4) -- (Saltzer, Reed, and Clark, TOCS, 1984) prose notes
|
1) The Linux Edge (Linus Torvalds, Open Sources: Voices from the Open Source Revolution 1999)
Singularity: Rethinking the Software Stack (Hunt and Larus, SIGOPS OSR, 2007)
THE (Dijkstra, 1968)
Application performance and Flexibility on Exokernel Systems (Kaashoek, Engler, Ganger, Briceno, Hunt, Mazieres, Pinckney, Grimm, Jannotti, and Mackenzie, SOSP, 1997)
On Micro-Kernel Construction (Liedtke, SOSP, 1995) notes
|
| Tue 08/29 |
OS design
| |
|
1) Exokernel: An Operating System Architecture for Application-Level Resource Management (Engler, Kaashoek, and O'Toole Jr., SOSP, 1995) lecture slides prose notes
2) A fork() in the road (Andrew Baumann, Jonathan Appavoo, Orran Krieger, Timothy Roscoe, HotOS, 2019)
|
The Wrong Patient (Chassin and Becher, American College of Physicians - American Society of Internal Medicine, 2002)
Radiation Offers New Cures, and Ways to Do Harm (New York Times 2010 flash animation)
The Task of the Referee (Smith)
|
| Thu 08/31 |
OS Design
| |
In-class debate on fork
|
1) The Rise of Worse is Better (Richard Gabriel, Lisp: Good News, Bad News, How to Win Big, 1989) lecture slides
2) Medical Devices, The Therac-25 (Levinson, Safeware: System Safety and Computers, 1995) SKIM! lecture slides
|
Threads and Input/Output in the Synthesis Kernel (Massalin and Pu, SOSP, 1989) lecture slides prose notes
Chapter 6 from Massalin's Thesis (1992)
Protection and the Control of Information Sharing in Multics (Saltzer, 1974)
|
| Tue 09/05 |
Virtual machines
| |
HW1 in-class quiz
Lab 0 due
|
Hardware and Software Support for Virtualization (Chapter 1, 3.3, 3.4, Chapter 4, Chapter 5) (Bugnion, Nieh, Tsafrir, Synthesis Lectures on Computer Architecture) lecture notes
|
Xen and Art of Virtualization (Barham, Dragovic, Fraser, Hand, Harris, Ho, Neugebaur, Pratt and Warfield, SOSP 2003). lecture notes prose notes
Are Virtual Machine Monitors Microkernels Done Right? (Hand, Warfield, Fraser, Kotsovinos, and Magenheimer, HotOS 2005) lecture notes
Are Virtual Machine Monitors Microkernels Done Right? (Heiser, Uhlig, and LeVasseur, SIGOPS OSR, 2006)
Disco: Running Commodity Operating Systems on Scalable Multiprocessors (Bugnion, Devine, and Rosenblum, SOSP, 1997) notes
The Turtles Project: Design and Implementation of Nested Virtualization (Ben-Yehuda, Day, Dubitzky, Factor, Har’El, Gordon, Liguoriz, Wasserman, Yassour, OSDI 2010)
Hardware and Software Support for Virtualization (Bugnion Nieh, Tsafrir, Synthesis Lectures on Computer Architecture 2017)
|
| Thu 09/07 |
Memory management
| |
|
1) Memory Resource Management in VMware ESX Server (Waldspurger, OSDI, 2002) lecture slides prose notes
|
Unix as an Application Process (Golub, USENIX, 1990)
Compatibility is not transparency VMM detection myths and realities (Garfinkel, Adams, Warfield, and Franklin, HOTOS, 2007)
|
| Tue 09/12 |
Lightweight Virtualization
| |
|
1) My VM is Lighter (and Safer) than your Container (Manco, Lupu, Schmidt, Mendes, Kuenzer, Sati, Yasukata, Raiciu, Huici, SOSP 2017) Skip section 5 and 7. lecture slides
2) LCE: The failure of operating systems and how we can fix it (Kerrisk, LWN.net, 2012) link
3) Namespaces in operation, part 1: namespaces overview (Kerrisk, LWN.net, 2013) link
|
X-Containers: Breaking Down Barriers to Improve Performance and Isolation of Cloud-Native Containers (Shen, Sun, Sela, Bagdasaryan, Delimitrou, Van Renesse, Weatherspoon, ASPLOS, 2019) Read up to and including Section 3.
Cells: A Virtual Mobile Smartphone Architecture (Andrus, Dall, Van’t Hof, Laadan, Nieh, SOSP 2011)
|
| Thu 09/14 |
Catch Up
| |
|
| Tue 09/19 |
Virtual memory
| |
|
1) Practical, transparent operating system support for superpages (Navarro, Iyer, Druschel, and Cox, OSDI 2002) lecture slides
2) Understanding the Linux Kernel (3rd Edition) Chapter 9, Process Address Space (skim)
|
Coordinated and Efficient Huge Page Management with Ingens
Machine-Independent Virtual Memory Management for Paged Uniprocessor and Multiprocessor Architectures (Rashid, Tevanian, Young, Golub, Baron, Black, Bolosky, and Chew, 1987)
|
| Thu 09/21 |
Emerging memory technologies
| |
|
1) Pond: CXL-Based Memory Pooling Systems for Cloud Platforms (Li, Berger, Novakovic, Hsu, Ernst, Zardoshti, Shah, Rajadnya, Lee, Agarwal, Hill, Fontoura, Bianchini, ASPLOS 2023) talk slides
|
|
| Tue 09/26 |
Kernel Bypass
| |
Lab 1 due
|
1) Arrakis: The Operating System is the Control Plane (Peter, Li, Zhang, Ports, Woos, Krishnamurthy, Anderson, Roscoe. OSDI, 2014) lecture slides, prose notes
|
Rethinking the Library OS from the Top Down (Porter, Boyd-Wickizer, Howell, Olinsky, and Hunt, ASPLOS 2011)
Containers
Dune: Safe User-level Access to Privileged CPU Features (Belay, Bittau, Mashtizadeh, Terei, Mazieres, Kozyrakis, OSDI 2012)
|
| Thu 09/28 |
File systems
| |
|
1) Crash Consistency: FSCK and Journaling (Chapter 42 in Operating Systems: Three Easy Pieces) (R. Arpaci-Dusseau, A. Arpaci-Dusseau)
2) A File is Not a File: Understanding the I/O Behavior of Apple Desktop Applications (Harter, Dragga, Vaughn, A. Arpaci-Dusseau, R. Arpaci-Dusseau, SOSP 2011) lecture slides
|
A Fast File System for UNIX (McKusick, Joy, Leffler, and Fabry, TOCS, 1984) prose notes
Disks from the Perspective of a File System (Marshall Kirk McKusick, ACM Queue, 2012)
Improving the Performance of fsck in FreeBSD (Marshall Kirk McKusick 2013)
|
| Tue 10/03 |
File systems
| |
|
1) The Design and Implementation of a Log-Structured File System (Rosenblum and Ousterhout, TOCS, 1992) prose notes
2) Ousterhout's critique of Seltzer's 1993 paper
3) Ousterhout's critique of Seltzer's 1995 paper
4) Seltzer's response to Ousterhout's critiques
5) Ousterhout's response to Seltzer
6) Log structured file systems: There's one in every SSD (Valerie Aurora (formerly Henson)) LWN 2009)
|
Design and Implementation of the SUN Network Filesystem (Sandberg, Goldberg, Kleiman, Walsh, and Lyon, USENIX, 1985) lecture slides prose notes
XDR: External Data Representation Standard (M. Eisler, Ed., RFC 4506, 2006) pdf txt
Remote Procedure Calls (Birrell and Nelson, TOCS, 1984) notes
An Introduction to Disk Drive Modeling (Ruemmler and Wilkes, 1994)
Soft Updates: A Technique for Eliminating Most Synchronous Writes in the Fast Filesystem (McKusick and Ganger, USENIX, 1999)
|
| Thu 10/05 |
Catch up
| |
|
| Tue 10/10 |
Data center file systems
| |
Lab 2 due
|
1) The Google File System (Ghemawat, Gobioff, and Leung, SOSP, 2003) lecture slides prose notes
|
1) GFS: Evolution on Fast-forward (McKusick and Quinlan, ACM Queue, 2009)
|
| Thu 10/12 |
Exam
| |
|
Exam in class. faux-quiz compilation
|
|
| Tue 10/17 |
Data center
| |
Project Plan DUE
|
1) MapReduce: Simplified Data Processing on Large Clusters (Dean and Ghemawat, OSDI, 2004) lecture slides
2) MapReduce: A Major Step Backwards (DeWitt and Stonebreaker, 2008)
|
A Comparison of Approaches to Large-Scale Data Analysis (Pavlo, Paulson, Rasin, Abadi, DeWitt, Madden, Stonebreaker, SIGMOD 2009)
BigTable: A system for Distributed Structured Storage (Chang, Dean, Ghemawat, Hsieh, Wallach, Burrows, Chandra, Fikes, and Gruber, OSDI, 2006) webnotes video
Large-scale Incremental Processing Using Distributed Transactions and Notifications (Peng and Dabek, OSDI 2010)
Brewer's CAP Theorem (Browne 2009)
Spanner: Google's Globally-Distributed Database (Corbett, Dean, Epstein, Fikes, Frost, Furman, Ghemawat, Gubarev, Heiser, Hochschild, Hsieh, Kanthak, Kogan, Li, Lloyd, Melnik, Mwaura, Nagle, Quinlan, Rao, Rolig, Saito, Szymaniak, Taylor, Wang and Woodford, OSDI, 2012)
Dynamo: Amazon’s Highly Avaiable Key-value Store
|
| Thu 10/19 |
Data races
| |
Lab 2 due
|
1) RaceTrack: Efficient Detection of Data Race Conditions via Adaptive Tracking (Yu, Rodeheffer, and Chen, SOSP, 2005) lecture slides notes
2) The "Double-Checked Locking is Broken" Declaration (Bacon, Bloch, Bogda, Click, Haahr, Lea, May, Maessen, Mitchell, Nilsen, Pugh, Sirer, 2004)
3) Exchange between Linus Torvalds and David Patterson about parallelism Part 1
4) Part 2
5) Part 3
|
Introduction to Non-blocking IO (Kegel 1999)
Event-driven Programming for Robust Software (Dabek, Zeldovich, Kaashoek, Mazieres, and Morris, SIGOPS, 2002)
Why Events Are A Bad Idea (for high-concurrency servers) (von Behren, Condit, and Brewer, HOTOS, 2003)
Cooperative Task Management without Manual Stack Management Adya, Howell, Theimer, Bolosky, Douceur, USENIX 2002)
|
| Tue 10/24 |
Concurrency and Transactions
| |
|
1) Operating System Transactions (Porter, Hofmann, Rossbach, Benn, and Witchel, SOSP, 2009) lecture slides
2) TxOS OSDI 2008 rejected intro
3) TxOS ASPLOS 2009 rejected intro
4) TxOS HotOS 2009 intro
|
Experiences with transactions in QuickSilver (Shmuck and Wyllie, SOSP 1991)
|
| Thu 10/26 |
Concurrency and Transactions
| |
|
1) Ordering concurrent events and transactions in Principles of Transaction Processing (second edition by Philip A. Bernstein and Eric Newcomer 2009) book notes
2) The Art of Multiprocessor Programming (Maurice Herlihy and Nir Shavit, 2008) 3-3.6 book notes lecture slides notes
|
Transaction Processing: Concepts and Techniques (Jim Gray and Andreas Reuter 1993) 1.1 - 1.2.5
4.2, 4.7 and 4.7.1, 4.9 and 4.9.1
7.1-7.6
The Transaction Concept (Gray, 1981) notes
|
| Tue 10/31 |
Security
| |
|
1) 17 Mistakes Microsoft Made in the Xbox Security System (Steil, 2005) lecture slides
2) The Confused Deputy (Hardy, SIGOPS OSR, 1988) lecture notes
|
A VMM Security Kernel for the VAX Architecture (Karger, Zurko, Bonin, Mason, Kahn, IEEE Oakland Security, 1990)
Authentication in Distributed Systems : Theory and Practice (Lampson, Abadi, Burrows, and Wobber, TOCS, 1992) notes
A Logic of Authentication (Burrorws, Abadi, and Needham, TOCS, 1990) notes
|
| Thu 11/02 |
Security
| |
|
1) Ryoan: A Distributed Sandbox for Untrusted Computation on Secret Data (Hunt, Zhu, Xu, Peter, Witchel) lecture slides
|
Overshadow: a virtualization-based approach to retrofitting protection in commodity operating systems (Chen, Garfinkel, Lewis, Subrahmanyam, Waldspurger, Boneh, Dwoskin, Ports, ASPLOS 2008)
InkTag: Secure Applications on an Untrusted Operating System (Hofmann, Dunn, Kim, Lee, Witchel, ASPLOS 2013)
Information flow control for standard OS abstractions (Krohn, Yip, Brodsky, Cliffer, Kaashoek, Kohler, and Morris, SOSP, 2007)
|
| Tue 11/07 |
Distributed data structures
| |
|
1) Tango: distributed data structures over a shared log (Balakrishnan, Malkhi, Wobber, Wu, Prabhakaran, Wei, Davis, Rao, Zou, Zuck, SOSP 2013) lecture slides
|
Naiad: a timely dataflow system (Murray, McSherry, Isaacs, Isard, Barham, Abadi, SOSP 2013)
DryadLINQ: a system for general-purpose distributed data-parallel computing using a high-level language (Yu, Isard, Fetterly, Budiu, Erlingsson, Gunda, Currey, OSDI 2008)
|
| Wed 11/08 |
| |
Lab 3 due 10pm
|
| Thu 11/09 |
GPUs (guest lecture Chris Rossbach)
| |
|
1) PTask: operating system abstractions to manage GPUs as compute devices (Rossbach, Currey, Silberstein, Ray, Witchel, SOSP 2011) lecture slides
|
TensorFlow: A system for Large-scale Machine Learning (Abadi et al., OSDI 2016)
|
| Tue 11/14 |
Distributed computing
| |
|
Catch up
|
Ownership: A Distributed Futures System for Fine-Grained Tasks (Wang, Liang, Oakes, Hindman, Luan, Cheng, Stoica, NSDI 2021)
Scaling AI with Ray (Luhui, Medium 2023)
Ray: A Distributed Framework for Emerging AI Applications (Moritz, Nishihara, Wang, Tumanov, Liaw, Liang, Elibol, Yang, Paul, Jordan, Stoica, OSDI 2018)
Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing (Zaharia, Chowdhury, Das, Dave, Ma, McCauley, Franklin, Shenker, and Stoica, NSDI 2012) lecture slides
|
| Thu 11/16 |
Exam 2
| |
|
Exam in class. faux-quiz compilation
|
Hints for Computer System Design (Lampson, SIGOPS OSR, 1983)
A Note on the Confinement Problem (Lampson, Communications of ACM, 1973)
Reflections on Trusting Trust <(Thompson, Turing Award Lecture, 1984)
|
| Tue 11/21 |
Thanksgiving
| |
|
| Thu 11/23 |
Thanksgiving
| |
|
| Tue 11/28 |
Project due
| |
Presentations
Project DUE
|
|
|
| Thu 11/30 |
Project due
| |
Presentations
|
|
|
| Fri 12/01 |
Additional reading
| |
|
|
The Many Faces of Systems Research - And How To Evaluate Them (Brown, Chanda, Farrow, Fedorova, Maniatis, Scott, HotOS 2005)
A Decentralized Model for Information Flow Control (Myers and Liskov, SOSP, 1997)
Laminar: Practical Fine-Grained Decentralized Information Flow Control (Roy, Setty, Kilzer, Shmatikov, Witchel, PLDI 2009)
Improving Application Security with Data Flow Assertions (Yip, Wang, Zeldovich, and Kaashoek, SOSP, 2009)
Why Cryptosystems Fail (Anderson, 1994)
Linearizability: A Correctness Condition for Concurrent Objects (Herlihy and Wing, TOPLAS, 1990)
Klee: Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs (Cadar, Dunbar, and Engler, OSDI, 2008)
A few billion lines of code later: using static analysis to find bugs in the real world (Bessey, Block, Chelf, Chou, Fulton, Hallem, Henri-Gros, Kamsky, McPeak, Engler, CACM v53 no 2, 2010)
Weird things that surprise academics trying to commercialize a static checking tool (Chou, Chelf, Hallem, Hanri-Gros, Fulton, Unangst, Zak, and Engler, SPIN, 2005)
EROS: A Fast Capability System (Shapiro, Smith, and Farber, SOSP, 1999)
Capsicum: practical capabilities for UNIX (Watson, Anderson, Laurie, Kennaway, USENIX security 2010) < a href=lectures/capsicum.pdf>notes
|