TA: Vernard Martin (vernard@cc)
Office: 226D CoC Bldg.
Office hours: Tu 1-2, Th 1-2 in CoC commons

CS6420 (Operating Systems) a graduate level course that covers in detail many advanced topics in operating system design and implementation. There is no textbook for this course. Rather, we will read and discuss a number of important research papers which have been published. For each paper, students are expected to understand the problem that is addressed by the paper, and what the solution is.

• Project 1
• Project 2
• Project 3
• Project 4
• Project 5

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 Cthreads paper (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. Engler, D.R., Andrews, G.R., Lowenthal, D.K., "Filaments: Efficient Support for Fine-Grain Parallelism", The Univ. of Arizona, Department of Computer Science, TR 93-13a, February 1994.
2. 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)
3. 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. (mostly self-study)
4. 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.
5. 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. (mostly self-study)
6. 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.
7. Mellor-Crummey, J. M. and Scott, M., "Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors", ACM Transactions on Computer Systems, Feb. 1991.

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, also see Silberschatz/Galvin).
3. Birrell, A.D., "Secure Communication Using Remote Procedure Calls", ACM Transactions on Computer Systems, 3,1, pgs. 1-14, February 1985 (self-study).
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.
5. 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.

Advanced Topics in Communications

1. Clark, D.D., "The Structuring of Systems Using Upcalls", Proceedings of Tenth ACM Symposium on Operating Systems Principles, pgs 171-180, Dec. 19885. (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. C.A. Thekkath and H.M. Levy, "Limits to Low-Latency Communications on High-Speed Networks", ACM Transactions on Computer Systems, May 1993.
4. Marcel-Catalin Rosu, Karsten Schwan, and Richard Fujimoto,"Supporting Parallel Applications on Clusters of Workstations", Cluster Computing, Baltzer Science Publishers, May 1998.
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. "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.

• Wednesday, September 29th. (IN CLASS)

  Distributed Systems: Concepts

  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.
  3. David K. Gifford, "Weighted Voting for Replicated Data," Proceedings of the Seventh ACM Symposium on Operating System Principles, Asilomar, Dec. 1979.
  Distributed Systems: Failures, Consistency and Recovery
  1. The SUN NFS, Locus, and Sprite - Silberschatz/Galvin, "Operating System Concepts". (self study).
  2. 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.
  3. Davcec and Burkhard, "Consistency and Recovery Control of Replicated Files", ACM Symposium on Operating System Principles, Dec. 1985.
  4. Anderson, T. etc. all., "Serverless Network File System", ACM Transpaction on Computer Systems, February 1996.
  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.
  %DSM:
  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.
  Multimedia, Real-Time, and Web Services
  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. Henry Massalin and Calton Pu, "Threads and Input/Output in the Synthesis Kernel", ACM 12th Symposium on Operating Systems Principles, Dec. 1989.
  3. Rangan, P.V. and Vin, H.M., "Designing File Systems for Digital Video and Audio", Proceedings of the Thirteenth ACM Symposium on Operating System Principles, pgs. 81-94, December 1991 (self-study).
  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. 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.
  6. Clark and Zhang, "Supporting Real-time Applications in an Integrated Services Packet Network: Architecture and Mechanism", ACM SIGCOMM, 1992.
  7. M. Frans Kaashoek, Dawson R. Engler, Gregory R. Ganger and Deborah A. Wallach, "Server Operating Systems," 7th SIGOPS European workshop: Systems suppport for worldwide applications, Connemara, Ireland, September 1996.
  Distributed Systems: Failures, Consistency and Recovery
  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.
  Protection, Object-based Systems and Object Technologies
  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. Cohen, E., and Jefferson, D., "Protection in the HYDRA Operating System", Proceedings of Fifth ACM Symposium on Operating System Principles, pgs. 141-160, 1975.
  3. Mitchell, J. G., et al., "An Overview of the Spring System".
  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. Aldrich, Dooley, et al., "Providing Easier Access to Remote Objects in Client-Server Systems," 31th Hawaii International Conference on System Sciences in January, 1998.
  Advanced Topics in Object Systems: Representations
  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.
  More on Object Technologies, Review, and Overflow

  ---

  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. Homeworks and projects will be posted in the newsgroup git.cc.class.6420. Information related to the course that is of general interest can also be posted in this newsgroup.
  5. Graduating students will be given the final examination in dead week. Consult the instructor for details.

  ---

  Grading

  40% project/homework (7% for project 1, 11% each for projects 2, 3, and 4)

  25% midterm

  30% final

  5% class participation

  ---

  
  Instructions for Special Projects
   

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

  Brief Project Description

  • purpose of project
  • expected outcome/results
  • at least three different intermediate project steps, with delivery iitems and deadlines for each
  • final project deadline sometime during the week before finals
  The first step is often background work, such as producing a bibliography of relevant papers and having read them and having designed suitable algorithms/approaches.

  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 also performance evaluation, on whatever platform you choose to use.

  The final deliverable not only includes the actual software but also a 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:

  • A statement of your approach to the project and the technique used to solve it - two typewritten pages minimum, 8 pages maximum, including a list of references to related work.
  • 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 hand in your program electronically, if requested. Most likely, you will simply schedule a demo with me. (please do so!)
  • A conclusion, stating the main results of your work. This conclusion might contain a performance evaluation of your program or a list of next st.ps concerning it (what might be interesting to do next). How it should be extended, what should be done to make it more useful. Maximum 4 pages, minimum 2 pages.
  • A one page evaluation of what you did: its usefulness in the context of other work AND in the context of general research (namely, why did you do this and why was or wasn't it worthwhile doing?)
  • 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 did or to extensions of what you did, if applicable.

  ---

  
  Pre-packaged Special Projects
  

  Below are some details on possible 6210 'Special Projects'. I can supply more information if any of you are interested in any of these topics. In each case, you will be working with some of my other PhD and MSc students and research scientists. The particular topic areas I am listing below are related to various research efforts undertaken by my group. I am also willing to entertain proposals from you that link your 6210 project to research you might be doing with other faculty, as long as the contents of your proposed projects address some significant portion of the technical matters taught in this course.

  For those who want to do a special project...I have given you indications as to projects I would find interesting...what I have given you is choices concerning areas in which you can do these projects. If you want to proceed, here is what I would like you to do:

  1. Send me email with whatever interests/vague ideas you have (schwan@cc)
  2. Let me look at it, then I can comment via email and/or we can meet to discuss it
  3. we work out a plan for the special project that covers the rest of the semester, typically consisting of several intermediate steps.
  It is my intent to have the special project you do, if you do it, replace the rest of ALL OF THE regular class projects . This way, you have time to do something interesting or relevant.
  1. Active System Area Networks (ASAN)

     This new project (funded by `just awarded' multi-year grants from NSF and DOE) is developing a software AND hardware architecture for scalable cluster computers. The large-scale cluster machines available to this work include both SMP-Intel-based nodes and SUN Sparc-based cluster machines, running the Solaris and Linux operating systems. In conjunction with collaborators in ECE, we are using and then enhancing communication coprocessors for such cluster nodes and also developing a software architecture as well as application-level code for these coprocessors, to enhance the scalability of the resulting cluster computing engines. Specific topics include:

     • Virtual Communication Machines - an extensible software architecture for Active System Area Networks (see Marcel Rosu's (Ph.D. student) web page for information on a previous, ATM-based prototype of the VCM). Build elements of a VCM on either Myrinet boards or on Intel's I2O-based communication co-processors.
     • Scalable Cluster Applications - develop web-based and media-based applications that exhibit improved scalability with the ASAN architecture
     • Quality Management - online quality management for cluster applications by development of innovative online resource management algorithms and methods (see Richard West's web page for information on packet scheduling methods, for instance. also see Daniela Rosu's web page for information on quality management algorithms and infrastructures at the application level).

  2. The Adaptive Systems Project

     More information can be found at the Adaptive Systems Home page and the Critical Systems Lab Home Page

     This project has been ongoing for some number of years, and its results have included the development of methods and algorithms for online adaptation of real-time systems and applications, the development of software infrastructures (at the kernel level and in middleware - CORBA and event-based, and using Linux at the kernel level) for online quality management, including online monitoring and program adaptation. NEW DIRECTIONS in this project for which we are actively seeking students and supported by recent, new funding from DARPA include:

     • Agile Quality Management Infrastructures help develop a software infrastructure that is capable of being instantiated at runtime in multiple ways; as middleware and with each application, in the OS kernel, or in the network infrastructure (ie., on communication coprocessors). Each instance of such an infrastructure is capable of managing the resources and resource usage of adaptable applications in just the way required by those applications.
     • Wireless and mobile systems work on applications and/or communication protocols and software that extends applications across wireless systems, with adaptations applied at the application, kernel, and network levels. Work with wireless communications, with media applications like a distributed version of the DOOM game being enhanced by our group, with media streaming applications (e.g., next generation virtual environments). This effort is funded in part by the new Yamacraw project at Georgia Tech.
     • Internet-based quality management, information flows work on Internet applications for which quality management must be performed for the flows of information between servers and clients. This effort links with the database-directed efforts of our new CoC faculty Calton Pu and Ling Liu.

  3. Computational and Information Spaces More information can be found at the Distriubted Labs Project Home Page and at the IHPCL Home Page

     This project, funded by the NSF, in partnership with the NCSA Alliance, and by large-scale industry funds (Intel Corp.) is developing middleware for high performance, parallel, and distributed applications. In contrast to previous work in HPC, our focus is on interactive high performance codes. Sample efforts for which students are needed include:

     • Develop distributed CORBA-compliant and/or JAVA-based software infrastructures with which high performance, interactive applications are easily assembled, employed, and controlled. (see web pages of Greg Eisenhauer and Dong Zhou for additional detail).
     • Build 'parallel workbenches' for applications like global atmospheric modeling, mechanical systems design, parallel optimization for applications like airline crew scheduling or others (based on students' interests). Or work on distributed object and event representations suitable for high performance usage.
     • Create sample applications requiring support like this, including working with the distributed version of DOOM and other such highly interactive high performance codes, including web-based applications.
     • Develop communication-level support for high performance computing, across SAN, LAN, and wireless media.
     • Develop compiler support for interactive high performance computing, including working with IDL compilers, with Java compilers/runtimes. Particular emphasis on development of online optimization methods for high performance interactive applications and systems, including online binary code generation.