Schedule for Witchel's Spring 2010 CS380L: Advanced Operating Systems (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 1/20 Review syllabus and HW1. notes
How (and How Not) to Write a Good Systems Paper (Levin and Redell, SIGOPS OSR, 1983)
2 1/25
1) Medical Devices: The Therac-25 (Levinson, Safeware: System Safety and Computers, 1995
2) The Wrong Patient (Chassin and Becher, American College of Physicians - American Society of Internal Medicine, 2002)
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 Rise of "Worse is Better" (Richard Gabriel, Lisp: Good News, Bad News, How to Win Big, 1989)
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
Historical perspective & OS Design
1) The UNIX Timesharing System (Ritchie and Thompson, SOSP, 1974)    notes 2up
2) The Linux Edge (Linus Torvalds, Open Sources: Voices from the Open Source Revolutionm 1999)
3) Singularity: Rethinking the Software Stack (Hunt and Larus, SIGOPS OSR, 2007)
Review the UNIX paper.  For the singularity paper, identify 2 or 3 design decisions in Singularity that differ from UNIX and comment on whether you think the Singularity approach is a real improvement.  Also indentify what you believe to be the biggest potential problem with Singularity.
THE (Dijkstra, 1968)   notes
3 2/1
OS Design  
1) Application performance and Flexibility on Exokernel Systems (Kaashoek, Engler, Ganger, Briceno, Hunt, Mazieres, Pinckney, Grimm, Jannotti, and Mackenzie, SOSP, 1997) notes 2up
2) End-to-end Arguments in System Design (Saltzer, Reed, and Clark, TOCS, 1984) notes 2up
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.
Exokernel: An Operating System Architecture for Appliation-Level Resource Management (Engler, Kaashoek, and O'Toole Jr., SIGOPS, 1995)
2/3 OS Design, Synchronization
1) Synthesis kernel (Massalin and Pu, SOSP, 1989) notes 2up
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
4 2/8 Virtual Machines
1) Memory Resource Management in VMware ESX Server (Waldspurger, OSDI, 2002) notes 2up
2) Compatibility is not transparency: VMM detection myths and realities (Garfinkel, Adams, Warfield, and Franklin, HOTOS, 2007)
Programming Assignment 0 DUE
Disco: Running Commodity Operating Systems on Scalable Multiprocessors (Bugnion, Devine, and Rosenblum, SOSP, 1997)  notes 2up
List of 5 papers you can present (chosen from papers that we have not read) due Monday 2/8.  Email prioritized list to Witchel.
2/10 Virtual Machines
A comparison of software and hardware techniques for x86 virtualization (Adams and Agesen, ASPLOS, 2006)
On Micro-Kernel Construction (Liedtke, SOSP, 1995) notes
Unix as an Application Process (Golub, USENIX, 1990)
5 2/15 Threads and concurrency 
1) Experiences with Processes and Monitors in Mesa (Lampson and Redell, Communications of the ACM 23, 2, 1980) notes Snotes
2) Event-driven Programming for Robust Software (Dabek, Zeldovich, Kaashoek, Mazieres, and Morris, SIGOPS, 2002)
3) Why Events Are A Bad Idea (for high-concurrency servers) (von Behren, Condit, and Brewer, HOTOS, 2003)
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)
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
6 2/22
Database transactions
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 Art of Multiprocessor Programming (Maurice Herlihy and Nir Shavit, 2008)
notes Snotes
The Transaction Concept (Gray, 1981)
Linearizability: A Correctness Condition for Concurrent Objects (Herlihy and Wing, TOPLS, 1990)
2/24 OS tranactions/multicore programming
1) Operating System Transactions (Porter, Hofmann, Rossbach, Benn, and Witchel, SOSP, 2009)
2) Transactional memory: The great nerd equalizer (Dziuba, The Register, 2008)
Experiences with transactions in QuickSilver (Shmuck and Wyllie, SOSP 1991)
7 3/1
File Systems
1) Design and Implementation of the SUN Network Filesystem (Sandberg, Goldberg, Kleiman, Walsh, and Lyon, USENIX, 1985) notes Snotes  
2) LBFS: A Low-bandwidth Network File System (Muthitacharoen, Chen, and Mezieres, SOSP, 2001)
A Fast File System for UNIX (McKusick, Joy, Leffler, and Fabry, TOCS, 1984)notes 2up
A toolkit for user-level file systems (Mazieres, USENIX, 2001)
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
File Systems
The Design and Implementation of a Log-Structured File System (Rosenblum and Ousterhout, TOCS, 1992)  LFS notes 2up
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
Programming Assignment 1 DUE (3/3)
8 3/8
Distributed File Systems
Scale and Performance in a Distributed File System (Howard, Kazar, Menees, Nichols, Satyanarayanan, Sidebothiam, and West,TOCS, 1988)  notes 2up Snotes

Midterm 5-8pm, ENS 116
Programming Assignment 3 Plan DUE (3/10)
Spring break
3/22 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)


System scale
1) BigTable: A system for Distributed Structured Storage (Chang, Dean, Ghemawat, Hsieh, Wallach, Burrows, Chandra, Fikes, and Gruber, OSDI, 2006)
webnotes video
2) ZFS: The last word in file systems (Moore, 2004)
PNUTS: Yahoo!'s Hosted Data Serving Platform (Cooper, Ramakrishnan, Srivastava, Silberstein, Bohannon, Jacobsen, Puz, Weaver, Yereni, VLDB, 2008)
Cloud computing
MapReduce: Simplified Data Processing on Large Clusters (Dean and Ghemawat, OSDI, 2004)
MapReduce: A Major Step Backwards (DeWitt and Stonebreaker, 2008)
Guest lecture: Vitaly Shmatikov/Chris Rossbach
Programming Assignment 2 DUE (3/29)
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)
Finding bugs
1) Klee: Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs (Cadar, Dunbar, and Engler, OSDI, 2008)
2) Weird things that surprise academics trying to commercialize a static checking tool (Chou, Chelf, Hallem, Hanri-Gros, Fulton, Unangst, Zak, and Engler, SPIN, 2005)

12 4/5
File Systems & Communication
1) Eliminating Receive Livelock in an Interrupt-driven Kernel (Mogul and Ramakrishnan, USENIX, 1996) Snotes
2) Brewer's CAP Theorem (Browne 2009)
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
Virtual memory
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) notes  Snotes(ppt)  Snotes(pdf)
13 4/12
File system dependences
Generalized File System Dependences (Frost, Mammarella, Kohler, de los Reyes, Hovsepian, Matsuoka, and Zhang, SOSP 2007)
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
Programming Assignment 3 Revised Plan DUE (4/12)
Browser is the OS
Leveraging Legacy Code to Deploy Desktop Applications on the Web (Douceur, Elson, Howell, Lorch, OSDI, 2008)

14 4/19
1) Authentication in Distributed Systems : Theory and Practice (Lampson, Abadi, Burrows, and Wobber, TOCS, 1992) TAOS notes  Snotes
2) 17 Mistakes Microsoft Made in the Xbox Security System (Steil, 2005)
A Logic of Authentication(Burrorws, Abadi, and Needham, TOCS, 1990) BAN notes
Why Cryptosystems Fail (Anderson, 1994) Security notes
Separating key management from file system security (Mazieres, Kaminsky, Kaashoek, and Witchel, SOSP, 1999)
Fast and secure distributed read-only file system (Fu, Kaashoek, and Mazieres, OSDI, 2002) notes Snotes
Understanding Data Lifetime via Whole System Simulation (Chow, Pfaff, Garfinkel, Christopher, and Rosenblum, USENIX, 2004)
Shredding Your Garbage: Reducing Data Lifetime Through Secure Deallocation (Chow, Pfaff, Garfinkel, and Rosenblum, USENIX, 2005)
Non-Control-Data Attacks Are Realistic Threats (Chen, Xu, Sezer, Gauriar, and Iyer, USENIX, 2006)
Protection, security, access control
1) Information flow control for standard OS abstractions (Krohn, Yip, Brodsky, Cliffer, Kaashoek, Kohler, and Morris, SOSP, 2007)
2) Crisis and Aftermath (Spafford, Communications of ACM, 1989)
A Decentralized Model for Information Flow Control (Myers and Liskov, SOSP, 1997)
A VMM Security Kernel for the VAX Architecture (Karger, Zurko, Bonin, Mason, Kahn, IEEE Oakland Security, 1990)
Improving Reliability of Modern OSes (Swift, Bershad, and Levy, SOSP, 2003)
Mondrix: Memory Isolation for Linux Using Mondriaan Memory Protection (Witchel, Rhee, and Asanovic, SOSP, 2005) notes
15 4/26
Protection, security, access control
1) Improving Application Security with Data Flow Assertions (Yip, Wang, Zeldovich, and Kaashoek, SOSP, 2009)
2) The Confused Deputy (Hardy, SIGOPS OSR, 1988) Snotes
Laminar: Practical Fine-Grained Decentralized Information Flow Control (Roy, Setty, Kilzer, Shmatikov, Witchel, PLDI 2009)
EROS: A Fast Capability System (Shapiro, Smith, and Farber, SOSP, 1999)
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) Snotes (ppt, sxi)
Guest Lecture: Vitaly Shmatikov/Owen Hofmann
Instead of a review for Hints paper, give your own hints based on your project experience.
16 5/3

Project Presentations

Career and general advice

Project Presentations
Midterm 5-8pm ENS 116
Programming Assingment 3 DUE (5/5)

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