Office: 220 CoC Bldg.
Office hrs.: MW 10-11 or by appointment.

TA:

Newsgroup: git.cc.class.cs6210

CS6210 (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. Some papers will be assigned for self-study. You must carefully read the self-study papers because the understanding of their content may be essential for the papers that will be covered in class. Reading only papers will cover topics that extend or supplement the material in papers that are covered in class. The students will be expected to have some understanding of the results in these papers but they will not be tested on these papers.

Prerequisites

Basic undergraduate OS course in which much of 'Silberschatz/Galvin, Operating System Concepts' (or equivalent) has been covered. Good knowledge of Unix and C programming.

Projects/Homeworks

This course is project intensive and will have a sequence of five projects. Strong programming skills are absolutely essential for completing these projects. Students can either do the projects that will be assigned by the instructor or they can choose to define one that has a better fit with their research goals. See the last section of the handout for information about projects that can be defined by students.

 Programming Project 1: Due Date January 22, 2002

 Homework 1, Due Date: February 8, 2002

 Programming Project II, Due Date: February 23, 2002

 Programming Project III, Due Date: April 9, 2002

 Programming Project IV, Due Date: April 30, 2002

=================================================
Some ppt notes from Fabián E. Bustamante

 PPT for microkernel paper

 PPT for OAM paper

 PPT for URPC paper

---------------------------------------------------
 Old Midterm Exam
 Old Final Exam
 

Course Outline

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 - see Silberschatz/Galvin, Operating System Concepts. Also see GNU threads (class project).

1. 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.
2. 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.
3. J. Liedtke, "On Micro-Kernel Construction", Proceedings of the 15th ACM Symposium on Operating System Principles, ACM, December 1995.

1. Mellor-Crummey, J. M. and Scott, M., "Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors", ACM Transactions on Computer Systems, Feb. 1991.
2. Bershad, B.N. Anderson, A.E., Lazowska, E.D., and Levy, H.M., "User Level Interprocess Communication for Shared Memory Multiprocessor", ACM Transactions on Computer Systems, 9, 2, pgs. 175-198, May 1991.
3. T.E. Anderson, B.D. Bershad, E. Lazowska, and H. Levy, "Scheduler Activations: Effective Kernel Support for the User-Level Management of Parallelism", Proceedings of the Thirteenth ACM Symposium on Operating System Principles, pgs. 95-109, December 1991.
4. 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.
5. Draves, R.P., Bershad, B.N., Rashid, R.F. and Dean, R.W., ``Using Continuations to Implement Thread Management and Communication in Operating Systems", Proceedings of the Thirteenth ACM Symposium on Operating System Principles, pgs. 122-136, December 1991. (reference only)

1. Birrell and Nelson, "Implementing Remote Procedure Calls", ACM Transactions on Computer Systems, 2, 1, pgs. 39-59, February 1984 (mostly self-study, a brief overview will be presented in class, also see Silberschatz/Galvin).
2. Birrell, A.D., "Secure Communication Using Remote Procedure Calls", ACM Transactions on Computer Systems, 3,1, pgs. 1-14, February 1985. (reference only).
3. 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. (mostly self-study)
4. C.A. Thekkath and H.M. Levy, "Limits to Low-Latency Communications on High-Speed Networks", ACM Transactions on Computer Systems, May 1993.

1. Wallach, D.A., Hsieh, W.C., Johnson, K.K., Kaashoek, M.F., and Weihl, W.E., "Optimistic Active Messages: A Mechanism for Scheduling Communication with Computation", Proceedings of ACM SIGPLAN Symposium on Principles & Practice of Parallel Programming (PPOPP), pgs. 217-225, July 1995
2. Marcel-Catalin Rosu, Karsten Schwan, and Richard Fujimoto,"Supporting Parallel Applications on Clusters of Workstations", Cluster Computing, Baltzer Science Publishers, May 1998.
3. Clark, D.D., "The Structuring of Systems Using Upcalls", Proceedings of Tenth ACM Symposium on Operating Systems Principles, pgs. 171-180, Dec. 1985. (self-study, to understand implications of layering)
4. 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.
5. John Hartman, Larry Peterson, Andy Bavier, Peter Bigot, Patrick Bridges, Brady Montz, Rob Piltz, Todd Proebsting, and Oliver Spatscheck "Joust: A Platform for Liquid Software". IEEE Computer (1999)
6. 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.

Midterm exam in class: TBA

Distributed Systems: Concepts

1. Lamport, L., " Time, Clocks, and the Ordering of Events in a Distributed System", Communications of the ACM, 21, 7, pgs. 558-565, July 1978.
2. Ricart, G. and Agrawala, A.K., " An Optimal Algorithm for Mutual Exclusion in Computer Networks", Communication of the ACM, 24, 1, pgs. 9-17, January 1981.

1. Nelson, M.N., Wlech, B.B., Ousterhout, J.K., "Caching in the Sprite Network File System", ACM Transactions on Computer Systems, 6, 1, pgs. 134-154, February 1988. (self-study)
2. Anderson, T. etc. all., "Serverless Network File System", ACM Transpaction on Computer Systems, February 1996.
3. M. Satyanarayanan, ``Integrating Security in Large Scale Distributed Systems'', ACM TOCS, Aug. 1989.
4. Karlin, A.R., Levy, H.M., and Thekkath, "Implementing Global Memory Management in a Workstation Cluster", Fifteenth ACM Symposium on Operating System Principles, Dec. 1995.
5. 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.

1. D. James Gemmell, Harrick M. Vin, Dilip D. Kandlur, P. Venkat Rangan, and Lawrence A. Rowe, "Multimedia Storage Servers: A Tutorial", IEEE Computer, May 1995.
2. Erik Riedel, Garth Gibson, Christos Faloutsos, "Active Storage For Large-Scale Data Mining and Multimedia," Proc. of the 24th International Conference on Very large Databases (VLDB '98), New York, New York, August 24-27, 1998.
3. Michael B. Jones, Daniela Rosu and Marcel Rosu " CPU Reservations and Time Constraints: Efficient, Predictable Scheduling of Independent Activities," Proceedings of the 16th ACM Symposium on Operating Systems Principles (SOSP '97), St. Malo, France, Oct., 1997.
4. 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.
5. 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.
6. Clark and Zhang, "Supporting Real-time Applications in an Integrated Services Packet Network: Architecture and Mechanism", ACM SIGCOMM, 1992.
7. Henry Massalin and Calton Pu, "Threads and Input/Output in the Synthesis Kernel", ACM 12th Symposium on Operating Systems Principles, Dec. 1989.

1. Walker et all., "The LOCUS Distributed Operating System," Procedings of the Ninth ACM Symposium on Operaitng Systems Principles, pgs 49-70, December 1983 (self study).
2. R. Haskin et. al., "Recovery Management in QuickSilver", ACM Transactions on Computer Systems, February 1988.
3. Satyanarayanan, M., et al., "Lightweight Recoverable Virtual Memory", The Proceedings of Fourteenth ACM Symposium on Operating System Principles, pgs. 146-160, December 1993.
4. David E. Lowell and Peter M. Chen, "Free Transactions With Rio Vista", Proceedings of the Sixteenth ACM Symposium on Operating System Principles, October 1997.

1. Linden, T.A., "Operating System Structures to Support Security and Reliable Software", Computer Surveys, 8, 4, pgs. 409-445, 1976. Also see chapter on protection in Silberschatz/Galvin, Operating System Concepts. (reference only).
2. Saltzer, J.H., ``Protection and the Control of Information Sharing in Multics'', Communications of the ACM, 17, 7, 1974.
3. Mitchell, J. G., et al., "An Overview of the Spring System", Proceedings of Compcon, Feb. 1994.
4. 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.
5. Birrell, A., Nelson, G., Owicki, S., and Wobber, E., "Network Objects", Digital, SRC Research Report No. 115, Dec. 1995.
6. 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.
7. 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. (reading only)

1. Christian Clemencon, Karsten Schwan, and Bodhi Mukherjee, "Distributed Shared Abstractions (DSA) on Large-Scale Multiprocessors", IEEE Transactions on Software Engineering, February 1996.
2. M. Ahamad and R. Kordale, "Scalable Consistency Protocols for Distributed Services" IEEE Transactions on Parallel and Distributed Systems, 1999.
3. Ahmed Gheith and Karsten Schwan, "CHAOS-Arc -- Kernel Support for Atomic Transactions in Real-Time Applications", ACM Transactions on Computer Systems, April 1993.

Other Information

1. Text: Papers available online (via the links above) or from instructor.
2. Supplementary Materials: Operating System Textbook used in GT OS undergraduate courses: Operating System Concepts, Silberschatz and Galvin; Advanced Operating Systems text: OS: Advanced Concepts, Maekawa, Oldehoeft. Addison-Wesley. "Distributed Systems", Sape Mullender, Addison-Wesley. "Distributed Operating Systems", Andrew S. Tanenbaum, Prentice Hall.
3. Prerequisites: CS 3431/4431 and its prerequisites or equivalent.
4. Syllabus, homeworks and projects will be posted on the class web page. Information related to the course that is of general interest can also be posted in the course newsgroup git.cc.class.6210.

Grading

Instructions for Special Projects
 

Information about special projects will be posted here soon.