TA:  Dong Song (dsong@cc )
Office: 226B CoC Bldg.
Office hours:  MW 12-1pm, or by appointment
Newsgroup: git.cc.class.cs6210

CS6210 (Operating Systems) is a graduate level course that covers indetail 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 anddistributed computing systems. There is no textbook for this course. Rather,we will read and discuss a number of important research papers which havebeen published. For each paper that is covered in class, students are expectedto gain a solid understanding of the problem that is addressed by the paper,and  the solution proposed by the authors.  Some papers willbe assigned for self study.  You must carefully read the self studypapers because the understanding of their content may be essential forthe papers that will be covered in class. Reading only papers will covertopics that extend  or supplement the material in papers that arecovered in class.  The students will be expected to have some understandingof the results  in these papers but they will not be tested on thesepapers.

This course is project intensive and will have a sequence of  four 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 fitwith their research goals. See the last section of the handout for information about projects that can be defined by students.

 Project 1: Multithreaded Traffic Information Server (Due Date: January 30, 2001)

• An Introduction to Programming with Threads, Birrell, DEC Systems Research Center
• Solaris 7 "Multithreaded Programming Guide"
• Debugging Solaris Pthreads using dbx
• Pthreads Tutorial by Phillip Ward Hutto

Project 2: Distributed Traffic Information Server(Due Date: February 27, 2001)

 Project 3: Building a Distributed Shared Memory (DSM) System

 Homework 2 - Due Date: April 12, 2001

 Project 4: Recoverable Memory

Old Examinations

 Midterm exam, Spring 2000
 

Course Outline

Basics(1/9/01)

1. Course overview and assumptions, which include basics of operating systemstructure, micro-kernels, user- and kernel-level threads, synchronization, deadlock detection and avoidance - see Silberschatz/Galvin, OperatingSystem Concepts. Also see GNU threads (class project).

1. Brian Bershad et al., " Extensibility,Safety and Performance in the SPIN Operating System", Proceedings ofthe 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. Anderson, T.E., ``The Performance Implications of Spin-Waiting Alternatives for Shared-Memory Multiprocessors", IEEE Transactions on Parallel and Distributed Systems, 1, 1, pgs. 6-16, January 1990. (mostly self-study)
2. Mellor-Crummey, J. M. and Scott, M., " Algorithmsfor Scalable Synchronization on Shared-Memory Multiprocessors ", ACMTransactions on Computer Systems, Feb. 1991.
3. Bershad, B.N. Anderson, A.E., Lazowska, E.D., and Levy, H.M., " UserLevel Interprocess Communication for Shared Memory Multiprocessor" ,ACM Transactions on Computer Systems, 9, 2, pgs. 175-198, May 1991.
4. T.E. Anderson, B.D. Bershad, E. Lazowska, and H. Levy, " SchedulerActivations: Effective Kernel Support for the User-Level Management ofParallelism", Proceedings of the Thirteenth ACM Symposium on Operating System Principles, pgs. 95-109, December 1991.
5. Draves, R.P., Bershad, B.N., Rashid, R.F. and Dean, R.W., ``Using Continuations to Implement Thread Management and Communication in OperatingSystems", Proceedings of the Thirteenth ACM Symposium on Operating System Principles, pgs. 122-136, December 1991. (reference only)
6. M.S. Squillante and E.D. Lazowska, " UsingProcessor-Cache Affinity Information in Shared Memory Multiprocessor Scheduling",IEEE Transactions on Parallel and Distributed Systems, Feb. 1993, pgs.131-143.

1. Basics on message passing and communication protocols (refer to networking courses and to Peterson/Galvin).
2. 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).
3. Birrell, A.D., "Secure Communication Using Remote Procedure Calls", ACMTransactions on Computer Systems, 3,1, pgs. 1-14, February 1985. (reference only).
4. 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)
5. Wallach, D.A., Hsieh, W.C., Johnson, K.K., Kaashoek, M.F., and Weihl, W.E.,"Optimistic Active Messages: A Mechanism for SchedulingCommunication with Computation", Proceedings of ACM SIGPLAN Symposiumon Principles & Practice of Parallel Programming (PPOPP), pgs. 217-225,July 1995.

1. Clark, D.D., "The Structuring of Systems Using Upcalls", Proceedings ofTenth ACM Symposium on Operating Systems Principles, pgs. 171-180, Dec. 1985. (self-study, to understand implications of layering)
2. 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.
3. Liu, Kreitz, van Renesse, Hickey, Hayden, Birman, Constable, `` BuildingReliable High Performance Communication Systems from Components '',17th ACM Symposium on Operating System Principles, OS Review, Volume 33, Number 5, Dec. 1999.
4. C.A. Thekkath and H.M. Levy, "Limits toLow-Latency Communications on High-Speed Networks", ACM Transactions on Computer Systems, May 1993.
5. Marcel-Catalin Rosu, Karsten Schwan, and Richard Fujimoto," SupportingParallel Applications on Clusters of Workstations", Cluster Computing,Baltzer Science Publishers, May 1998.
6. 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)
7. David Wetherall, `` ActiveNetworks: Vision and Reality: Lessons from a Capsule-based System' ',17th ACM Symposium on Operating System Principles, OS Review, Volume 33, Number 5, Dec. 1999.
8. "CCL: A portable and tunable Collective Communication Library for scalable parallel computers", V. Bala, et.al, in IEEE Transactions on Parallel and Distributed Systems, Vol 6, No 2, Feb 1995.  (reference only)

1. 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.
2. Lamport, L., "Time, Clocks, and the Ordering of Events in a Distributed System", Communications of the ACM, 21, 7, pgs. 558-565, July 1978.

Midtermexam in class: (3/1)

DistributedSystems: File Systems and  Distributed Shared Memory (3/13-3/22)

1. The SUN NFS, Locus, and Sprite - Silberschatz/Galvin, "Operating System Concepts". (self study).
2. Nelson, M.N., Wlech, B.B., Ousterhout, J.K., " Cachingin the Sprite Network File System", ACM Transactions on Computer Systems,6, 1, pgs. 134-154, February 1988. (self-study)
3. Anderson, T. etc. all., " ServerlessNetwork File System", ACM Transpaction on Computer Systems, February1996.
4. M. Satyanarayanan, ``Integrating Security inLarge Scale Distributed Systems'', ACM TOCS, Aug. 1989.
5. 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.
6. 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. Rangan, P.V. and Vin, H.M., "Designing FileSystems for Digital Video and Audio", Proceedings of the Thirteenth ACM Symposium on Operating System Principles, pgs. 81-94, December 1991(self-study).
2. D. James Gemmell, Harrick M. Vin, Dilip D. Kandlur, P. Venkat Rangan, andLawrence A. Rowe, " MultimediaStorage Servers: A Tutorial", IEEE Computer, May 1995.
3. Erik Riedel, Garth Gibson, Christos Faloutsos, "ActiveStorage For Large-Scale Data Mining and Multimedia," Proc. of the 24thInternational Conference on Very large Databases (VLDB '98), New York,New York, August 24-27, 1998.
4. Michael B. Jones, Daniela Rosu and Marcel Rosu " CPUReservations 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.
5. Clark and Zhang, "Supporting Real-time Applications in an Integrated Services Packet Network: Architecture andMechanism ", ACM SIGCOMM, 1992.
6. Armando Fox, Steven Gribble, Yatin Chawathe, Eric Brewer, and Paul Gauthier,"Cluster-basedScalable Network Services", Sixteenth ACM Symposium on Operating SystemPrinciples, Oct. 1997.
7. 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.
8. M. Frans Kaashoek, Dawson R. Engler, Gregory R. Ganger and Deborah A. Wallach,"Server OperatingSystems," 7th SIGOPS European workshop: Systems suppport for worldwideapplications, Connemara, Ireland, September 1996.
9. Henry Massalin and Calton Pu, "Threads andInput/Output in the Synthesis Kernel", ACM 12th Symposium on Operating Systems Principles, Dec. 1989.

1. Walker et all., "The LOCUS Distributed Operating System," Procedings ofthe Ninth ACM Symposium on Operating 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. David E. Lowell and Peter M. Chen, "Free TransactionsWith Rio Vista", Proceedings of the Sixteenth ACM Symposium on OperatingSystem Principles, October 1997.

Satyanarayanan, M., et al., "LightweightRecoverable Virtual Memory", The Proceedings of Fourteenth ACM Symposiumon Operating System Principles, pgs. 146-160, December 1993 (self-study).

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. (reference only)
3. Cohen, E., and Jefferson, D., "Protection in the HYDRA Operating System", Proceedings of Fifth ACM Symposium on Operating System Principles, pgs.141-160, 1975.
4. Shapiro, Smith, Farber, ``EROS: A Fast Capability System'', 17th ACM Symposium on Operating System Principles, OS Review, Volume 33, Number 5, Dec. 1999.
5. Mitchell, J. G., et al., "An Overview of the Spring System", Proceedings of Compcon, Feb. 1994.
6. Hamilton, G., Powell, M.L., and Mitchell, J.J., " Subcontract:A Flexible Base for Distributed Programming", Proceedings of the FourteenthACM SOSP, pgs. 69-79, December 1993.
7. Birrell, A., Nelson, G., Owicki, S., and Wobber, E., " NetworkObjects", Digital, SRC Research Report No. 115, Dec. 1995.
8. Wollrath, A., Riggs, R., and Waldo, J., "ADistributed Object Model for the Java System", Usenix Conference on Object Oriented Technologies and Systems, May 1996. (reading only)
9. 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.
10. Aldrich, Dooley, et al., "Providing Easier Access to Remote Objects in Client-Server Systems," 31th Hawaii International Conference on System Sciences in January, 1998. (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 3210/4210 and its prerequisites or equivalent.
4. Syllabus, homeworks (if any) and projects will be posted  on the classweb page. Information related to the course that is of general interest can also be posted in  the course newsgroup git.cc.class.6210.
5. Graduating students will be given the final examination in dead week. Consultthe instructor for details.

Grading

45% project/homework

25% midterm

25% final

5% class participation

To propose a special project for this class, I would like from you the following materials:

Brief Project Description

1. purpose of project
2. expected outcome/results
3. at least three different intermediate project steps, with delivery itemsand deadlines for each
4. final project deadline sometime during the week before finals

The second step, typically around midterm time, is having produced much of the software necessary, and having debugged it.

The third step must include not only software testing but alsoperformance evaluation, on whatever platform you choose to use.

The final deliverable not only includes the actual software but alsoa report, which is outlined next.

Final Report

You are asked to submit an on-line final report regarding your special project  that consists of the following parts:

1. A statement of your approach to the project and the technique used to solveit - two typewritten pages minimum, 8 pages maximum, including a list ofreferences to related work.
2. If applicable, a running program with sufficient documentation so that someone can understand your program without re-running it. Such documentation should consist of detailed comments within the program text and of explanations on a separate piece of paper. You should be prepared to handin your program electronically, if requested. Most likely, you will simplyschedule a demo with me. (please do so!)
3. A conclusion, stating the main results of your work. This conclusion mightcontain a performance evaluation of your program or a list of next steps concerning it (what might be interesting to do next). How it should beextended, what should be done to make it more useful. Maximum 4 pages,minimum 2 pages.
4. A one page evaluation of what you did: its usefulness in the context ofother work AND in the context of general research (namely, why did youdo this and why was or wasn't it worthwhile doing?)
5. A one page discussion relating the work you did to the topics we studied in  class. Comment on what papers in class relate to what you didor to extensions of what you did, if applicable.