[Kernel, courtesy IowaFarmer.com CornCam]

CS 261 Research Topics in Operating Systems, Fall 2011

Tentative Schedule

Week 0 Thu 9/1 Course introduction, x86 assembly
Week 1 Tue 9/6
Part 1. OS Organization
“The UNIX Time-Sharing System”, D. M. Ritchie and K. Thompson, 1974, revised from Communications of the ACM 17(7), July 1974, pp.365-375
“The Evolution of the Unix Time-sharing System”, Dennis M. Ritchie, AT&T Bell Laboratories Technical Journal 63(6), Part 2, Oct. 1984, pp.1577-93
Thu 9/8 Class is moved to MD 323 for today
Using virtual memory
“Reducing Seek Overhead with Application-Directed Prefetching”, Steve VanDeBogart, Christopher Frost, and Eddie Kohler, Proc. 2009 USENIX Annual Technical Conf., June 2009
Week 2 Tue 9/13 Microkernels
“Improving IPC by Kernel Design”, Jochen Liedtke, Proc. 14th SOSP, Dec. 1993, pp.175-188

Optional further reading (Papers listed in dotted boxes like this are optional)

Liedtke was instrumental in developing the L3 and L4 microkernels, whose descendents are still among the most widely-used true microkernels. (The seL4 microkernel was recently proved correct!) Liedtke was a fascinating guy who loved tricks and cared a lot about performance. His take on microkernels in general is interesting, although less technically deep than the “Improving IPC” paper. Look for the controversial statements:

“On μ-Kernel Construction”, Jochen Liedtke, Proc. 15th SOSP, Dec. 1995

Liedtke seems to have known the x86 architecture inside and out. Two guesses which little-used virtual memory feature he took advantage of for improving address space switching performance!

“Improved Address-Space Switching on Pentium Processors by Transparently Multiplexing User Address Spaces”, Jochen Liedtke, German National Research Center for Information Technology GMD Technical Report No. 933, Nov. 1995
Lab 1 due, 11:59pm
Thu 9/15 Exokernel
“Exokernel: An Operating System Architecture for Application-Level Resource Management”, Dawson R. Engler, M. Frans Kaashoek, and James O'Toole Jr., Proc. 15th SOSP, Dec. 1995, pp.251-266
“Application Performance and Flexibility on Exokernel Systems”, M. Frans Kaashoek, Dawson R. Engler, Gregory R. Ganger, Héctor M. Briceño, Russell Hunt, David Mazières, Thomas Pinckney, Robert Grimm, John Jannotti, and Kenneth Mackenzie, Proc. 17th SOSP, Oct. 1997, pp.52-65 ¡ONLY READ SECTION 4 IN DEPTH!
Further reading on exokernels:
“Fast and flexible application-level networking on exokernel systems”, Gregory R. Ganger, Dawson R. Engler, M. Frans Kaashoek, Héctor M. Briceño, Russell Hunt, and Thomas Pinckney, ACM Trans. on Computer Systems 20(1), Feb. 2002, pp.49-83
Week 3 Tue 9/20 Singularity
“Singularity: Rethinking the Software Stack”, Galen C. Hunt and James R. Larus, ACM SIGOPS Operating Systems Review 41(2), Apr. 2007, pp.37–49
Further reading on Singularity:
“Language Support for Fast and Reliable Message-based Communication in Singularity OS”, Manuel Fähndrich, Mark Aiken, Chris Hawblitzel, Orion Hodson, Galen Hunt, James R. Larus, and Steven Levi, Proc. EuroSys '06, Apr. 2006
Further reading on library OSes:
“Rethinking the Library OS from the Top Down”, Donald E. Porter, Silas Boyd-Wickizer, Jon Howell, Reuben Olinsky, and Galen C. Hunt, Proc. ASPLOS '11, Mar. 2011
Thu 9/22 Singularity (see 9/20) and virtual machines
“A comparison of software and hardware techniques for x86 virtualization”, Keith Adams and Ole Agesen, Proc. ASPLOS XII, Oct. 2006, pp.2-13
Week 4 Tue 9/27 Virtual machine optimization
“Virtual Memory Management in VMware ESX Server”, Carl A. Waldspurger, Proc. 5th OSDI, Dec. 2002
Further reading on VMM page sharing:
“Difference Engine: Harnessing Memory Redundancy in Virtual Machines”, Diwaker Gupta, Lee, Michael Vrable, Stefan Savage, Alex C. Snoeren, George Varghese, Geoffrey M. Voelker, and Amin Vahdat, Proc. 8th OSDI 2008, Dec. 2008
Further reading on Disco:
“Disco: Running Commodity Operating Systems on Scalable Multiprocessors”, Edouard Bugnion, Scott Devine, and Mendel Rosenblum, Proc. 16th SOSP, Oct. 1997, pp.143-156
Lab 2 due, 11:59pm
Thu 9/29 Virtual machines as tools
“DoublePlay: Parallelizing sequential logging and replay”, Kaushik Veeraraghavan, Dongyoon Lee, Benjamin Wester, Peter M. Chen, Jason Flinn, and Satish Narayanasamy, Proc. ASPLOS XVI, Mar. 2011
Further reading on virtual machines:
“Xen and the Art of Virtualization”, Paul Barham, Boris Dragovic, Keir Fraser, Steven Hand, Tim Harris, Alex Ho, Rolf Neugebauer, Ian Pratt, and Andrew Warfield, Proc. 19th SOSP, Oct. 2003, pp.164-177
Week 5 Tue 10/4 Debugging
“Bugs as Deviant Behavior: A General Approach to Inferring Errors in Systems Code”, Dawson Engler, David Yu Chen, Seth Hallem, Andy Chou, and Benjamin Chelf, Proc. 18th SOSP, Oct. 2001, pp.57-72
“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, and Dawson Engler, Communications of the ACM 53(2), pp66-75
Further reading on OS bug finding:
“Checking System Rules Using System-Specific, Programmer-Written Compiler Extensions”, Dawson Engler, Benjamin Chelf, Andy Chou, and Seth Hallem, Proc. 4th OSDI, Oct. 2000, pp.1-16
“An Empirical Study of Operating Systems Errors”, Andy Chou, Junfeng Yang, Benjamin Chelf, Seth Hallem, and Dawson Engler, Proc. 18th SOSP, Oct. 2001, pp.73-88
“Klee: Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs”, Cristian Cadar, Daniel Dunbar, and Dawson Engler, Proc. 8th OSDI, Dec. 2008
Fixing Device Drivers, a collection of research by Michael M. Swift's group
Thu 10/6 Performance debugging, high-performance debugging
“Debugging in the (Very) Large: Ten Years of Implementation and Experience”, Kirk Glerum, Kinshuman Kinshumann, Steve Greenberg, Gabriel Aul, Vince Orgovan, Greg Nichols, David Grant, Gretchen Loihle, and Galen Hunt, Proc. 22nd SOSP, Oct. 2009
Week 6 Tue 10/11 On system calls
“FlexSC: Flexible System Call Scheduling with Exception-Less System Calls”, Livio Soares and Michael Stumm, Proc. 9th OSDI, Oct. 2010
“Kqueue: A Generic and Scalable Event Notification Library”, Jonathan Lemon, Proc. 2001 USENIX ATC, FREENIX Track, June 2001
Further reading on event notification:
Libev documentation, by Marc Lehmann. Search for “epoll” and “kqueue”, and glance through the “Portability Notes”.
Lab 3 due, 11:59pm
Thu 10/13
Test 1
Week 7 Tue 10/18
Part 2. Multiprocessors
Multiprocessor concurrency fundament
“Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors”, John M. Mellor-Crummey and Michael L. Scott, ACM Trans. on Computer Systems 9(1), Feb. 1991, pp.21-65
“Threads Cannot Be Implemented as a Library”, Hans-J. Boehm, Proc. PLDI '05 June 2005
Further reading on memory models:
“Memory models: a case for rethinking parallel languages and hardware”, Sarita V. Adve and Hans-J. Boehm, Communications of the ACM 53(8), Aug. 2010 (Local link)
Thu 10/20 Multiprocessor concurrency and langauges
“TxLinux: Using and Managing Hardware Transactional Memory in an Operating System”, Christopher J. Rossbach, Owen S. Hofmann, Donald E. Porter, Hany E. Ramadan, Aditya Bhandari, and Emmett Witchel, Proc. 21st SOSP, 2007
You may also be interested in:
“Specifying and Checking Semantic Atomicity for Multithreaded Programs”, Jacob Burnim, George Necula, and Koushik Sen, Proc. ASPLOS XVI, Mar. 2011
Week 8 Tue 10/25
No class
Thu 10/27 High-performance multiprocessor concurrency: Read-Copy Update
“Read-Copy Update”, Paul E. McKenney, Jonathan Appavoo, Andi Kleen, Orran Krieger, Rusty Russell, Dipankar Sarma, and Maneesh Soni, Proc. Ottawa Linux Symposium 2001
“Resizable, Scalable, Concurrent Hash Tables via Relativistic Programming”, Josh Triplett, Paul E. McKenney, and Jonathan Walpole, Proc. USENIX 2011 ATC, June 2011

Further useful reading on RCU. You can also glance through the talk and/or the articles below to get a feeling for RCU's goals.

“Abstraction, Reality Checks, and RCU”, Paul E. McKenney, talk at U. of Toronto Cider Seminar, July 26, 2005
“What is RCU, Fundamentally?”, Paul E. McKenney and Jonathan Walpole, Linux Weekly News, Dec. 19, 2007
“Performance of memory reclamation for lockless synchronization”, Thomas E. Hart, Paul E. McKenney, Angela Demke Brown, and Jonathan Walpole, J. of Parallel and Distributed Computing 67(12), Dec. 2007, pp.1270-1285
Fri 10/28
Lab 4 due, 11:59pm
Week 9 Tue 11/1 Multiprocessor system architecture
“The Multikernel: A new OS architecture for scalable multicore systems”, Andrew Baumann, Paul Barham, Pierre-Evariste Dagand, Tim Harris, Rebecca Isaacs, Simon Peter, Timothy Roscoe, Adrian Schüpbach, and Akhilesh Singhania, Proc. 22nd SOSP, Oct. 2009
Thu 11/3 Multiprocessor system architecture II
“An Analysis of Linux Scalability to Many Cores”, Silas Boyd-Wickizer, Austin Clements, Yandong Mao, Aleksey Pesterev, M. Frans Kaashoek, Robert Morris, and Nickolai Zeldovich, Proc. 9th OSDI, 2010
Week 10 Tue 11/8
Part 3. Subsystems and whole systems
File systems and hashing
“Venti: a new approach to archival storage”, Sean Quinlan and Sean Dorward, Proc. 1st USENIX Conf. on File System And Storage Technologies (FAST), Jan. 2002, pp.89-101
Thu 11/10 Whole systems: Google infrastructure
“Bigtable: A Distributed Storage System for Structured Data”, Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes, and Robert E. Gruber, Proc. 7th OSDI, Nov. 2006
Background reading on the Google File System
“The Google File System”, Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung, Proc. 19th SOSP, 2003
Fri 11/11
Lab 5 due, 11:59pm
Week 11 Tue 11/15 Whole systems: Chord
“Chord: A Scalable Peer-to-peer Lookup Protocol for Internet Applications”, Ion Stoica, Robert Morris, David Liben-Nowell, David R. Karger, M. Frans Kaashoek, Frank Dabek, and Hari Balakrishnan, IEEE/ACM Transactions on Networking 11(1), Feb. 2003
Thu 11/17 Whole systems: CoralCDN
“Democratizing Content Publication with Coral”, Michael J. Freedman, Eric Freudenthal, and David Mazières, Proc. 1st NSDI, Mar. 2004
“Experiences with CoralCDN: A Five-Year Operational View”, Michael J. Freedman, Proc. 7th NSDI, Apr. 2010
Week 12 Tue 11/22 Security: Information flow systems
“Making information flow explicit in HiStar”, Nickolai Zeldovich, Silas Boyd-Wickizer, Eddie Kohler, and David Mazières, Proc. 7th OSDI, Nov. 2006
“Information Flow Control for Standard OS Abstractions”, Maxwell Krohn, Alexander Yip, Micah Brodsky, Natan Cliffer, M. Frans Kaashoek, Eddie Kohler, and Robert Morris, Proc. 21st SOSP, Oct. 2007
Thu 11/24 Thanksgiving holiday
Week 13 Tue 11/29 Whole systems: TritonSort
“TritonSort: A Balanced Large-Scale Sorting System”, Alexander Rasmussen, George Porter, Michael Conley, Harsha Madhyastha, Radhika Niranjan Mysore, Alexander Pucher, and Amin Vahdat, Proc. 8th NSDI, Apr. 2011
Thu 12/1
Test 2

Back to CS 261 Research Topics in Operating Systems