| 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) |
HW1 |
| 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). notes |
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) Communication 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) 3-3.6 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 7.1-7.6 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 |
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
