Schedule for Witchel's Fall 2011 CS380L: Advanced Operating Systems NOTE: THIS SCHEDULE WILL CHANGE
(Syllabus, Programming assignments, Presentations, Reviews)

Papers (presentations and reviews) are only accssible to hosts in the domain. Almost all of these papers are available on the web.
Wk Date Discussion Topic Homework/
Extra Reading
1 8/24 Review syllabus and HW1. notes
How (and How Not) to Write a Good Systems Paper (Levin and Redell, SIGOPS OSR, 1983)
2 8/29 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) FAA: Boeing's New 787 May Be Vulnerable to Hacker Attack (Zetter, Wired, 2008)
4) On Being the Right Size (Haldane, 1928)
5) The Wrong Patient (Chassin and Becher, American College of Physicians - American Society of Internal Medicine, 2002)
Review the Therac-25.  For worse is better, choose two recent developments in computer technology that you think illustrate the worse is better principle and explain why.  As an alternate for a worse is better writeup, you can make an argument for the natural size of something computer related, like the size of a social networking site.  As another alternate, you can comment on The Wrong Patient by describing why some complex computer system failed for complex reasons.
Radiation Offers New Cures, and Ways to Do Harm (New York Times 2010) flash animation disturbing graphic
Federal Register Vol 73 #1 (details of the 787) (FAA 2008)
The Task of the Referee (Smith)
See Dahlin's Advice
8/31 Historical perspective & 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)
Review the UNIX paper. 
Singularity: Rethinking the Software Stack (Hunt and Larus, SIGOPS OSR, 2007)
THE (Dijkstra, 1968)   notes
3 9/5 Labor day, no class

9/7 OS Design  
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
HW1 in-class quiz
Review exokernel paper.  Don't review end-to-end paper, instead apply end-to-end argument to 3 Exokernel design decisions.
Application performance and Flexibility on Exokernel Systems (Kaashoek, Engler, Ganger, Briceno, Hunt, Mazieres, Pinckney, Grimm, Jannotti, and Mackenzie, SOSP, 1997)
4 9/12 OS Design, Synchronization
1) Threads and Input/Output in the Synthesis Kernel (Massalin and Pu, SOSP, 1989) notes
2) Chapter 6 from Massalin's Thesis (1992) (remainder of thesis is optional)
Protection and the Control of Information Sharing in Multics (Saltzer, 1974)
Multics (Daley and Dennis, 1968) notes
Hamming's Advice on Research
List of 5 required, unread papers you can present due Monday 9/12 (see in-class presentation in sillybus).  Email prioritized list to Witchel.
9/14 Virtual memory
Practical, transparent operating system support for superpages (Navarro, Iyer, Druschel, and Cox, OSDI, 2002)
Guest lecture: Owen Hofmann/Vitaly Shmatikov
Programming Assignment 0 DUE
Machine-Independent Virtual Memory Management for Paged Uniprocessor and Multiprocessor Architectures (Rashid, Tevanian, Young, Golub, Baron, Black, Bolosky, and Chew, 1987) notes  Snotes(ppt)  Snotes(pdf)
5 9/19 Virtual Machines
1) Xen and Art of Virtualization (Barham, Dragovic, Fraser, Hand, Harris, Ho, Neugebaur, Pratt and Warfield, SOSP 2003).
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).
On Micro-Kernel Construction (Liedtke, SOSP, 1995) notes
Unix as an Application Process (Golub, USENIX, 1990)
A comparison of software and hardware techniques for x86 virtualization (Adams and Agesen, ASPLOS, 2006)
9/21 Virtual Machines
1) Memory Resource Management in VMware ESX Server (Waldspurger, OSDI, 2002) notes
2) 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
6 9/26 Threads and concurrency 
Experiences with Processes and Monitors in Mesa (Lampson and Redell, Communications of the ACM 23, 2, 1980) notes Snotes
Concurrent programming overview ppt pdf
Programming Assignment 1 DUE
Why Threads Are a Bad Idea (for most purposes) (Ousterhout, USENIX, 1996)  notes  Snotes
Programming with Threads (Birrell 1996)
Why Aren't Operating Systems Getting Faster As Fast As Hardware? (Ousterhout, USENIX, 1990)
9/28 Threads vs. events
1) Comparing the Performance of Web Server Architectures (David Pariag, Tim Brecht, Ashif Harji, Peter Buhr, and Amol Shukla, Eurosys 2007) notes
Code examples for non-blocking I/O here
2) Brewer's CAP Theorem (Browne 2009)
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)
7 10/03 Multithreading
RaceTrack: Efficient Detection of Data Race Conditions via Adaptive Tracking (Yu, Rodeheffer, and Chen, SOSP, 2005) notes Snote
JSR 133 (Java Memory Model FAQ by Manson and Goetz, 2004)
Double checked locking is broken (Bacon)
Virtual Time and Global States of Distributed Systems (Mattern, Parallel and Distributed Algorithms, 1988)
Scheduler Activations (Anderson, Bershad, Lazowska, and Levy, TOCS, 1992 )  notes Snotes
10/05 Interrupt vs. polling
1) Eliminating Receive Livelock in an Interrupt-driven Kernel (Mogul and Ramakrishnan, USENIX, 1996) notes Snotes
2) Warehouse-Scale Computers (Urs Hölzle and Luiz André Barroso, Internet Computing 2010)
Programming Assignment 2 DUE
From Dahlin's Advice:
The Emperor's Old Clothes(Hoare, Turing Award Lecture, 1981)
Active Messages: a Mechanism for Integrated Communication and Computation (von Eicken, Culler, Goldstein, and Schauser, International Symposium on Computer Architecture, 1992)  notes
8 10/10 File Systems
1) Design and Implementation of the SUN Network Filesystem (Sandberg, Goldberg, Kleiman, Walsh, and Lyon, USENIX, 1985) notes Snotes  
A Fast File System for UNIX (McKusick, Joy, Leffler, and Fabry, TOCS, 1984)notes
An Introduction to Disk Drive Modeling (Ruemmler and Wilkes, 1994) Snotes
Remote Procedure Calls (Birrell and Nelson, TOCS, 1984)  notes   Snotes
Lessons Learned Tuning 4.3BSD Reno Implementation of the NFS Protocol (Macklem, USENIX, 1991)
From Dahlin's Advice: Coping with complexity
10/12 File Systems
Scale and Performance in a Distributed File System (Howard, Kazar, Menees, Nichols, Satyanarayanan, Sidebothiam, and West,TOCS, 1988)  notes Snotes
Programming Assignment 2 DUE
Fast and secure distributed read-only file system (Fu, Kaashoek, and Mazieres, OSDI, 2002) notes Snotes
A toolkit for user-level file systems (Mazieres, USENIX, 2001)
Separating key management from file system security (Mazieres, Kaminsky, Kaashoek, and Witchel, SOSP, 1999)
9 10/17 The Design and Implementation of a Log-Structured File System (Rosenblum and Ousterhout, TOCS, 1992)  notes
Ousterhout's critique of Seltzer's 1993 paper
Ousterhout's critique of Seltzer's 1995 paper
Seltzer's response to Ousterhout's critiques
Ousterhout's response to Seltzer  Snotes
Log structured file systems: There's one in every SSD (Valerie Aurora (formerly Henson)) LWN 2009)

10/19 System scale
The Google File System (Ghemawat, Gobioff, and Leung, SOSP, 2003) notes
Google App Engine Event (Beckman 2009)
GFS: Evolution on Fast-forward (McKusick and Quinlan, ACM Queue, 2009)
10 10/24 Midterm 5-8pm, RLM 7.124
Programming Assignment 3 Plan DUE
10/26 Guest lecture by Vitaly Shmatikov/Sangman Kim to discuss superpages. Programming Assignment 3 Plan DUE

11 10/31 OS tranactions/multicore programming
1) Operating System Transactions (Porter, Hofmann, Rossbach, Benn, and Witchel, SOSP, 2009)
2) TxOS OSDI 2008 rejected intro, TxOS ASPLOS 2009 rejected intro, TxOS HotOS 2009 intro
3) Transactional memory: The great nerd equalizer (Dziuba, The Register, 2008)
Experiences with transactions in QuickSilver (Shmuck and Wyllie, SOSP 1991)
11/2 Ordering concurrent events and transactions
Principles of Transaction Processing (second edition by Philip A. Bernstein and Eric Newcomer 2009) book notes
The Art of Multiprocessor Programming (Maurice Herlihy and Nir Shavit, 2008)
book notes notes
Programming Assignment 3 Revised Plan DUE
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
The Transaction Concept (Gray, 1981) notes, Snotes
Linearizability: A Correctness Condition for Concurrent Objects (Herlihy and Wing, TOPLS, 1990)
12 11/7 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)
11/9 File system dependences
1) Generalized File System Dependences (Frost, Mammarella, Kohler, de los Reyes, Hovsepian, Matsuoka, and Zhang, SOSP 2007)
2) The Many Faces of Systems Research - And How To Evaluate Them (Brown, Chanda, Farrow, Fedorova, Maniatis, Scott, HotOS 2005)
Soft Updates: A Technique for Eliminating Most Synchronous Writes in the Fast Filesystem (McKusick and Ganger, USENIX, 1999) Snotes
13 11/14 Finding bugs
1) Klee: Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs(Cadar, Dunbar, and Engler, OSDI, 2008)
2) A few billion lines of code later: using static analysis to find bugs in the real world (Al Bessey, Ken Block, Ben Chelf, Andy Chou, Bryan Fulton, Seth Hallem, Charles Henri-Gros, Asya Kamsky, Scott McPeak, Dawson Engler, Communications of the ACM archive Volume 53, Issue 2, February 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)
11/16 Protection, security, access control
1) Information flow control for standard OS abstractions (Krohn, Yip, Brodsky, Cliffer, Kaashoek, Kohler, and Morris, SOSP, 2007)
2) 17 Mistakes Microsoft Made in the Xbox Security System (Steil, 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)
EROS: A Fast Capability System (Shapiro, Smith, and Farber, SOSP, 1999)
Mondrix: Memory Isolation for Linux Using Mondriaan Memory Protection (Witchel, Rhee, and Asanovic, SOSP, 2005) notes
Improving Reliability of Modern OSes (Swift, Bershad, and Levy, SOSP, 2003)
14 11/21 Protection, security, access control
The Confused Deputy (Hardy, SIGOPS OSR, 1988)
Overshadow: a virtualization-based approach to retrofitting protection in commodity operating systems (Xiaoxin Chen, Tal Garfinkel, E. Christopher Lewis, Pratap Subrahmanyam, Carl A. Waldspurger, Dan Boneh, Jeffrey Dwoskin, Dan R.K. Ports, ASPLOS 2008)
Crisis and Aftermath (Spafford, Communications of ACM, 1989)
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) TAOS notes  Snotes
A Logic of Authentication(Burrorws, Abadi, and Needham, TOCS, 1990) BAN notes
Why Cryptosystems Fail (Anderson, 1994) Security notes
11/23 System building experience
1) Hints for Computer System Design (Lampson, SIGOPS OSR, 1983) Snotes
2) A Note on the Confinement Problem (Lampson, Communications of ACM, 1973) Snotes
3) Reflections on Trusting Trust (Thompson, Turing Award Lecture, 1984)
Instead of a review for Hints paper, give your own hints based on your project experience.
15 11/28 Project presentations Programming Assignment 3 DUE
Career and general advice
11/30 Project Presentations
Midterm 5-8pm RLM 7.124

To top of page

Copyright Notice: These lecture notes, homeworks, and lab assignments are part of a graduate course on operating systems. You must ask me permission to use these materials.  I do not grant to you the right to publish these materials for profit in any form.
Emmett Witchel, The University of Texas at Austin