CS 6210: Advanced Operating Systems
Fall 2007, Section B

• Time/Location: TTH 12:05-1:15pm, KACB 1447
  
• Instructor: Dr. Ada Gavrilovska (ada@cc)
• Office Hours: Tue. 1:30-2:30pm or by appointment, KACB 3228.
• TA: Girish Saini (gsaini@cc), TBA (Wednesday 1:30PM- 2:30PM CoC Commons)
• newsgroup: git.cc.class.cs6210
• Please report dead links to gsaini@cc

Course Description

CS 6210 (Advanced Operating Systems) is a graduate level course that covers in detail many advanced topics in operating system design and implementation. It starts with topics such as operating systems structuring, multithreading and synchronization and then moves on to systems issues in parallel and distributed computing systems. There is no textbook for this course. Rather, we will read and discuss a number of important research papers that have been published. For each paper that is covered in class, students are expected to gain a solid understanding of the problem that is addressed by the paper, and the solution proposed by the authors. While this syllabus only lists the papers covered in class, additional materials including background readings and optional readings can be found here.

Prerequisites

• CS4210 or equivalent undergraduate OS course. It should have covered much of Operating Systems Concepts, Silberschatz and Galvin. (Or equivalent).
• Good knowledge of Unix and C programming.
• CS4210's prerequisites or equivalents.

Grading

10% class participation
35% projects
25% midterm
30% final

Note that a passing grade is required in each of the above components in order to pass the class.

Projects

This course is project intensive and will have a sequence of four or five projects. Strong programming skills are absolutely essential for completing these projects. Students can either do the assigned projects or they can choose to define a project that fits more closely with their individual research goals.

Each student in the class will get access to Clusters and Warp machines. You will turn in your projects via email to the TA. If you have no COC account, please apply soon so you can have the class directory.

Project One - due 9/12 at midnight

Special Project list. Initial Project description due by Sep. 17

Project 2 - due 10/14 at midnight

Project 3 - due 11/12 at midnight

Project 4 - due 11/30 at midnight (reference paper)

Syllabus

Optional supplementary reference texts include the following:

• Operating Systems Concepts , Silberschatz and Galvin.
• OS: Advanced Concepts, Maekawa, Oldehoeft. Addison-Wesley.
• Distributed Systems, Sape Mullender, Addison-Wesley.
• Distributed Operating Systems , Andrew S. Tanenbaum, Prentice Hall.
• An Introduction to Programming with Threads , Andrew Burrell.
• Multithreaded Programming with Pthreads , Chapter 4, Bil Lewis, Daniel J. Berg.

Note: the following paper list is tentative and subject to change in the next week or so. Please consider this before printing a large number of papers, especially those from later in this schedule. Also a list including all necessary background readings and optional readings can be found here.

Basics

1. Course overview and assumptions, which include basics of operating system structure, micro-kernels, user- and kernel-level threads, synchronization, deadlock detection and avoidance. Refer to Operating System Concepts, Silberschatz and Galvin, and Multithreaded Programming with Pthreads, Chapter 4.

OS Structures

1. Aug. 21.       Dawson R. Engler, Frans Kaashoek and James O'Toole, "Exokernel: An Operating System Architecture for Application-Level Resource Management ", Proceedings of the 15th ACM Symposium on Operating System Principles, ACM, December 1995.

2. Aug. 23      Brian Bershad et al., " Extensibility, Safety and Performance in the SPIN Operating System ", Proceedings of the 15th ACM Symposium on Operating System Principles, December 1995.

3. Aug. 30      J. Liedtke, " On Micro-Kernel Construction ", Proceedings of the 15th ACM Symposium on Operating System Principles, ACM, December 1995. (slides)

4. Aug. 27      Paul Barham, Boris Dragovic, Keir Fraser, Steven Hand, Tim Harris, Alex Ho, Rolf Neugebauer, Ian Pratt, Andrew Warfield, "Xen and the Art of Virtualization ", SOSP 2003. (slides)

Shared Memory/Server Platforms:

1. Sep. 4      Mellor-Crummey, J. M. and Scott, M., "Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors ", ACM Transactions on Computer Systems, Feb. 1991. (slides)

2. Sep 6      Paul E. Mckenney and John D. Slingwine. Read-Copy Update: Using Execution History to Solve Concurrency Problems, Parallel and Distributed Computing and Systems, Oct 1998 (useful slides)

3. Sep. 18      Ben Gamsa, Orran Krieger, Jonathan Appavoo, and Michael Stumm, Tornado: Maximizing Locality and Concurrency in a Shared Memory Multiprocessor Operating System , 1999 Symposium on Operating System  Design and Implementation. (slides)

4. Sep. 13      Kinshuk Govil, Dan Teodosiu, Yongqiang Huang, and Mendel Rosenblum. Cellular Disco: resource management using virtual clusters on shared-memory multiprocessors. In Proceedings of 17th Symposium on Operating Systems Principles, 1999 (slides)

5. Sep. 20      Alexandra Fedorova, Margo Seltzer, Christopher Small and Daniel Nussbaum. Performance of Multithreaded Chip Multiprocessors And Implications For Operating System Design. Usenix 05

6. Sep. 20      Partial reading: M.S. Squillante and E.D. Lazowska, " Using Processor-Cache Affinity Information in Shared Memory Multiprocessor Scheduling ", IEEE Transactions on Parallel and Distributed Systems, Feb. 1993, pgs. 131-143.

Communication Mechanisms, Interfaces, and Protocols

Partial reading : Schroeder, M., and Burrows, M., " Performance of the Firefly RPC ", Proceedings of the Twelfth ACM Symposium on Operating Systems Principles, pgs. 83-90, December 1989.

1. Sep. 25      B. N. Bershad, T. E. Anderson, E. D. Lazowska, and H. M. Levy. Lightweight Remote Procedure Call . ACM Transactions on Computer Systems, 8(1):37--55, Feb. 1990. (slides)

2. Sep. 27      C.A. Thekkath and H.M. Levy, " Limits to Low-Latency Communications on High-Speed Networks ", ACM Transactions on Computer Systems, May 1993. (slides)

3. Sep. 27      Hutchinson N.C., Peterson, L.L., " The x-Kernel: An Architecture for Implementing Network Protocols ", IEEE Transactions on Software Engineering, 17, 1, pgs. 64-76, January 1991. (slides)

4. Oct. 2      David Wetherall, " Active Networks: Vision and Reality: Lessons from a Capsule-based System ", 17th ACM Symposium on Operating System Principles, OS Review, Volume 33, Number 5, Dec. 1999. (slides)

5. Oct. 4      Liu, Kreitz, van Renesse, Hickey, Hayden, Birman, Constable, "Building Reliable High Performance Communication Systems from Components ", 17th ACM Symposium on Operating System Principles, OS Review, Volume 33, Number 5, Dec. 1999. (slides)

Midterm Exam

Date: October 11.

Here are some example midterms:

• Example Midterm 1
• Example Midterm 2
• Example Midterm 3

Distributed Platforms:

Concepts

1. Oct. 16      Lamport, L., " Time, Clocks, and the Ordering of Events in a Distributed System ", Communications of the ACM, 21, 7, pgs. 558-565, July 1978. (slides)

File Systems and Distributed Shared Memory

1. Oct. 16      Mahadev Satyanarayanan, "Coda: A Highly Available File System for a Distributed Workstation Environment", IEEE Trans. Computers, vol 39, no 4, Apr 1990 (slides)

2. Oct. 18      Anderson, T. et all., " Serverless Network File System ", ACM Transpaction on Computer Systems, February 1996. (slides)

3. Oct. 23      Feeley, Morgan, Pighin, Karlin, Levy, Thekkath,, "Implementing Global Memory Management in a Workstation Cluster ", Fifteenth ACM Symposium on Operating System Principles, Dec. 1995. (slides)

4. Oct. 25      C. Amza, A. Cox, S Dwarkadas, P Keleher, H Lu, R. Rajamony, W. Yu and W. Zwaenepoel, " TreadMarks: Shared Memory Computing on Networks of Workstations " IEEE Computer, February, 1996. (slides)

Failures, Consistency, and Recovery

1. Oct 30      R. Haskin et. al., " Recovery Management in QuickSilver ", ACM Transactions on Computer Systems, February 1988. (slides)

2. Nov 1      Satyanarayanan, M., et al., " Lightweight Recoverable Virtual Memory ", The Proceedings of Fourteenth ACM Symposium on Operating System Principles, pgs. 146-160, December 1993. (slides)

3. Nov 6      J. N. Gray, P. McJones, M. W. Blasgen, R. A. Lorie, T. G. Price, G. R. Putzolu, and I. L. Traiger. " The Recovery Manager of a Data Management System ", ACM Computing Surveys, Vol. 13, No. 2, June 1981, pp. 223-242. (slides)

Object-based Distributed Systems and Protection

1. Nov 13      Mitchell, J. G., et al., " An Overview of the Spring System ", Proceedings of Compcon, Feb. 1994. (slides)

2. Nov 13      Hamilton, G., Powell, M.L., and Mitchell, J.J., "Subcontract: A Flexible Base for Distributed Programming ", Proceedings of the Fourteenth ACM SOSP, pgs. 69-79, December 1993.

3. Nov 15      Wollrath, A., Riggs, R., and Waldo, J., "A Distributed Object Model for the Java System ", Usenix Conference on Object Oriented Technologies and Systems, May 1996. (slides)

4. Nov 15      Jason Maassen, Rob van Nieuwpoort, Ronald Veldema, Henri Bal, Thilo Kielmann, Ceriel Jacobs, Rutger Hofman, " Efficient Java RMI for Parallel Programming ", Vrije Universiteit Amsterdam, Faculty of Sciences, March 2000. (slides)

5. Nov 20      Emmanuel Cecchet, Julie Marguerite, Willy Zwaenepoel, "Performance and Scalability of EJB Applications", Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications. (slides)

6. Nov 20      Curbera, F., Duftler, M., Khalaf, R., Nagy, W., Mukhi, N., Weerawarana, S., " Unraveling the Web services web: an introduction to SOAP, WSDL, and UDDI ", IEEE Internet Computing, Volume: 6 Issue: 2, March-April 2002, pgs. 86 -93.

7. Nov 27      Cohen, E., and Jefferson, D., " Protection in the HYDRA Operating System ", Proceedings of Fifth ACM Symposium on Operating System Principles, pgs. 141-160, 1975. (slides)

Multimedia, Real-Time, and Web Services

1. Nov 29      Shahabi, Zimmermann, Fu, and Yao. " Yima: A Second-Generation Continuous Media Server ", IEEE Computer Magazine, June 2002.

2. Nov 29      Ashvin Goel, Luca Abeni, Charles Krasic, Jim Snow, Jonathan Walpole, Supporting Time-Sensitive Applications on a Commodity OS OSDI 2002 (slides)

3. Dec 4      Saito, Bershad, Levy, " Manageability, Availability, and Performance in Porcupine: A Highly Scalable Cluster-based Mail Service ", 17th ACM Symposium on Operating System Principles, OS Review, Volume 33, Number 5, Dec. 1999. (slides from SOSP presentation)

4. Dec 6      Armando Fox, Steven Gribble, Yatin Chawathe, Eric Brewer, and Paul Gauthier, " Cluster-based Scalable Network Services ", Sixteenth ACM Symposium on Operating System Principles, Oct. 1997.

Other Information

There will be a lab session. Date to be announced.

Final Exam

12/12 - 8:00-10:00am, Location KACB 1447

Example finals:

• Example Final 1
• Example Final 2