| Date |
Topic |
Assignments |
Reading |
Non-required Reading |
| Thu 08/28 |
Course Intro
|
HW 1 out
|
1) How (and How Not) to Write a Good Systems Paper (Levin and Redell, SIGOPS OSR, 1983)
|
You and Your Research(Hamming 1986)
|
| Tue 09/02 |
Software correctness
|
HW 2 due
|
1) Medical Devices, The Therac-25 (Levinson, Safeware: System Safety and Computers, 1995)
2) The Rise of Worse is Better (Richard Gabriel, Lisp: Good News, Bad News, How to Win Big, 1989)
3) On Being the Right Size (Haldane, 1928)
|
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 09/04 |
OS Design
|
|
1) The UNIX Timesharing System (Ritchie and Thompson, SOSP, 1974) notes
2) 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)
|
| Tue 09/09 |
OS Design
|
HW1 in-class quiz
HW3 due
|
1) Exokernel: An Operating System Architecture for Appliation-Level Resource Management (Engler, Kaashoek, and O'Toole Jr., SOSP, 1995) notes
2) End-to-end Arguments in System Design (Saltzer, Reed, and Clark, TOCS, 1984) notes
|
Application performance and Flexibility on Exokernel Systems (Kaashoek, Engler, Ganger, Briceno, Hunt, Mazieres, Pinckney, Grimm, Jannotti, and Mackenzie, SOSP, 1997)
Rethinking the Library OS from the Top Down (Porter, Boyd-Wickizer, Howell, Olinsky, and Hunt, ASPLOS 2011)
|
| Thu 09/11 |
OS Design
|
Lab 0 due
|
1) Threads and Input/Output in the Synthesis Kernel (Massalin and Pu, SOSP, 1989) notes
|
Chapter 6 from Massalin's Thesis (1992)
Protection and the Control of Information Sharing in Multics (Saltzer, 1974)
|
| Tue 09/16 |
mmap + page faults
|
|
Understanding the Linux Kernel (3rd Edition) Chapter 9, Process Address Space
|
Practical, transparent operating system support for superpages (Navarro, Iyer, Druschel, and Cox, OSDI, 2002)
Machine-Independent Virtual Memory Management for Paged Uniprocessor and Multiprocessor Architectures (Rashid, Tevanian, Young, Golub, Baron, Black, Bolosky, and Chew, 1987)
|
| Thu 09/18 |
Virtual machines
|
|
1) Xen and Art of Virtualization (Barham, Dragovic, Fraser, Hand, Harris, Ho, Neugebaur, Pratt and Warfield, SOSP 2003). notes
2) Are Virtual Machine Monitors Microkernels Done Right? (Hand, Warfield, Fraser, Kotsovinos, and Magenheimer, HotOS 2005)
3) Are Virtual Machine Monitors Microkernels Done Right? (Heiser, Uhlig, and LeVasseur, SIGOPS OSR, 2006)
|
Intel Virtualization Technology (Uhlig, Neiger, Rodgers, Santoni, Martins, Anderson, Bennett, Kagi, Leung, and Smith, IEEE Computer 2005)
The Turtles Project: Design and Implementation of Nested Virtualization (Ben-Yehuda, Day, Dubitzky, Factor, Har’El, Gordon, Liguoriz, Wasserman, Yassour, OSDI 2010)
On Micro-Kernel Construction (Liedtke, SOSP, 1995) notes
Unix as an Application Process (Golub, USENIX, 1990)
|
| Tue 09/23 |
Virtual Machines
|
Lab 1 due
|
1) Memory Resource Management in VMware ESX Server (Waldspurger, OSDI, 2002)
|
Compatibility is not transparency VMM detection myths and realities (Garfinkel, Adams, Warfield, and Franklin, HOTOS, 2007)
Disco: Running Commodity Operating Systems on Scalable Multiprocessors (Bugnion, Devine, and Rosenblum, SOSP, 1997) notes
Dune: Safe User-level Access to Privileged CPU Features (Belay, Bittau, Mashtizadeh, Terei, Mazieres, Kozyrakis, OSDI 2012)
|
| Thu 09/25 |
Catch up
|
|
Catch up
|
|
| Tue 09/30 |
File system
|
|
1) Improving the Performance of fsck in FreeBSD (Marshall Kirk McKusick 2013)
2) Crash Consistency: FSCK and Journaling (Chapter 42 in Operating Systems: Three Easy Pieces) (R. Arpaci-Dusseau, A. Arpaci-Dusseau)
|
Disks from the Perspective of a File System (Marshall Kirk McKusick, ACM Queue, 2012)
A Fast File System for UNIX (McKusick, Joy, Leffler, and Fabry, TOCS, 1984) notes
|
| Thu 10/02 |
File system
|
Lab 2 due
|
1) The Design and Implementation of a Log-Structured File System (Rosenblum and Ousterhout, TOCS, 1992) 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)
|
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)
Generalized File System Dependences (Frost, Mammarella, Kohler, de los Reyes, Hovsepian, Matsuoka, and Zhang, SOSP 2007)
|
| Tue 10/07 |
Exam 1 (OSDI)
|
|
Exam is on Tuesday evening. GDC 4.304 5-9pm
|
| Thu 10/09 |
Networked file systems
|
|
1) Design and Implementation of the SUN Network Filesystem (Sandberg, Goldberg, Kleiman, Walsh, and Lyon, USENIX, 1985) notes
|
XDR: External Data Representation Standard (M. Eisler, Ed., RFC 4506, 2006) pdf txt
Remote Procedure Calls (Birrell and Nelson, TOCS, 1984) notes
|
| Tue 10/14 |
Data center file systems
|
|
1) The Google File System (Ghemawat, Gobioff, and Leung, SOSP, 2003) notes
|
GFS: Evolution on Fast-forward (McKusick and Quinlan, ACM Queue, 2009)
|
| Thu 10/16 |
Race conditions
|
Project Plan DUE
|
1) RaceTrack: Efficient Detection of Data Race Conditions via Adaptive Tracking (Yu, Rodeheffer, and Chen, SOSP, 2005) notes
2) The "Double-Checked Locking is Broken" Declaration (Bacon, Bloch, Bogda, Click, Haahr, Lea, May, Maessen, Mitchell, Nilsen, Pugh, Sirer, 2004)
|
Eraser: A Dynamic Data Race Detector for Multithreaded Programs (Savage, Burrows, Nelson, Sobalvarro, Anderson, TOCS, 1997)
Experiences with Processes and Monitors in Mesa (Lampson and Redell, Communications of the ACM 23, 2, 1980) notes
JSR 133 (Java Memory Model FAQ by Manson and Goetz, 2004)
|
| Tue 10/21 |
Events and threads
|
|
1) Determinism Is Not Enough: Making Parallel Programs Reliable with Stable Multithreading (Yang, Cui, Wu, Tang, and Hu, CACM v57 no 3, 2014)
2) Introduction to Non-blocking IO (Kegel 1999)
3) Exchange between Linus Torvalds and David Patterson about parallelism Part 1
4) Part 2
5) Part 3
|
Scheduler Activations (Anderson, Bershad, Lazowska, and Levy, TOCS, 1992)
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)
|
| Thu 10/23 |
Transactions
|
Lab 3 due
|
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 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
Linearizability: A Correctness Condition for Concurrent Objects (Herlihy and Wing, TOPLAS, 1990)
|
| Tue 10/28 |
Transactions
|
Lab 3 due
|
1) Operating System Transactions (Porter, Hofmann, Rossbach, Benn, and Witchel, SOSP, 2009)
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/30 |
Paxos
|
Lab 4a due
Revised Project Plan DUE
|
1) Paxos Made Practical (Mazieres, 2007)
|
Paxos Made Simple (Lamport, 2001)
Paxos Made Moderately Complex (VanRenesse, 2011)
|
| Tue 11/04 |
Cloud computing
|
|
1) MapReduce: Simplified Data Processing on Large Clusters (Dean and Ghemawat, OSDI, 2004)
2) MapReduce: A Major Step Backwards (DeWitt and Stonebreaker, 2008)
|
Airavat: Security and Privacy for MapReduce (Roy, Ramadan, Setty, Kilzer, Shmatikov, and Witchel, NSDI 2010)
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
PNUTS: Yahoo!'s Hosted Data Serving Platform (Cooper, Ramakrishnan, Srivastava, Silberstein, Bohannon, Jacobsen, Puz, Weaver, Yereni, VLDB, 2008)
|
| Thu 11/06 |
Cloud computing
|
Lab 4 due
|
1) 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)
|
Large-scale Incremental Processing Using Distributed Transactions and Notifications (Peng and Dabek, OSDI 2010)
Dynamo: Amazon’s Highly Avaiable Key-value Store
|
| Tue 11/11 |
Security
|
|
1) 17 Mistakes Microsoft Made in the Xbox Security System (Steil, 2005) notes
2) The Many Faces of Systems Research - And How To Evaluate Them (Brown, Chanda, Farrow, Fedorova, Maniatis, Scott, HotOS 2005)
|
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)
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/13 |
Security
|
Lab 4b due
|
1) The Confused Deputy (Hardy, SIGOPS OSR, 1988)
2) Brewer's CAP Theorem (Browne 2009)
|
Information flow control for standard OS abstractions (Krohn, Yip, Brodsky, Cliffer, Kaashoek, Kohler, and Morris, SOSP, 2007)
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)
|
| Tue 11/18 |
Data analytics
|
|
1) Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing (Zaharia, Chowdhury, Das, Dave, Ma, McCauley, Franklin, Shenker, and Stoica, NSDI 2012)
|
| Thu 11/20 |
Protection and Capabilities
|
|
Catch up
|
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
|
| Tue 11/25 |
Exam 2
|
|
Exam is 5pm-9pm in GDC 4.304
|
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)
|
| Thu 11/27 |
Thanksgiving
|
|
|
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)
|
| Tue 12/02 |
Project presentation
|
Presentation group 1
Project DUE
|
|
|
| Thu 12/04 |
Project presentation
|
Presentation group 2
Presentation group 3 AT 5PM in GDC 4.304
|
|
|