CS 6210 Reading
Advanced Operating Systems
Spring 2007

Home

Logistics

Assignments

Reading

Lectures

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 the schedule.

Background Reading

Supplementary Reference

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 (4 lectures)

  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.
  4. 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.

Synchronization, Communication, and Scheduling in Parallel Systems (4 lectures)

  1. Mellor-Crummey, J. M. and Scott, M., "Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors ", ACM Transactions on Computer Systems, Feb. 1991.
  2. 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.
  3. 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.
  4. 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.

Communication Mechanisms in Distributed Systems (4 lectures)

  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. C.A. Thekkath and H.M. Levy, " Limits to Low-Latency Communications on High-Speed Networks ", ACM Transactions on Computer Systems, May 1993.
  3. 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.
  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.

Distributed Objects and Middleware (4 lectures)

  1. Mitchell, J. G., et al., " An Overview of the Spring System ", Proceedings of Compcon, Feb. 1994.
  2. 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. 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.
  4. 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.

Distributed Shared Memory and File Systems (3 lectures)

  1. Feeley, Morgan, Pighin, Karlin, Levy, Thekkath,, "Implementing Global Memory Management in a Workstation Cluster ", Fifteenth ACM Symposium on Operating System Principles, Dec. 1995.
  2. 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.
  3. Anderson, T. et all., " Serverless Network File System ", ACM Transpaction on Computer Systems, February 1996.

Multimedia (2 lectures)

  1. Bolosky, Fitzgerald, and Douceur. " Distributed Schedule Management in the Tiger Video Fileserver ", In Proceedings of the 16th ACM Symposium on Operating Systems Principles, Oct. 1997.
  2. 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.

Failures, Consistency, and Recovery (4 lectures)

  1. Satyanarayanan, M., et al., " Lightweight Recoverable Virtual Memory ", The Proceedings of Fourteenth ACM Symposium on Operating System Principles, pgs. 146-160, December 1993.
  2. David E. Lowell and Peter M. Chen, " Free Transactions With Rio Vista ", Proceedings of the Sixteenth ACM Symposium on Operating System Principles, October 1997.
  3. R. Haskin et. al., " Recovery Management in QuickSilver ", ACM Transactions on Computer Systems, February 1988.
  4. 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.

System Support for Internet Scale Computing (2 lectures)

  1. Web Technologies (2 short papers)
    1. 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.
    2. Curbera, F., Khalaf, R., Mukhi, N., Tai, S., Weerawarana, S., " The Next Step in Web Services ", Communications of the ACM, Volume 46 Issue 10 ,October 2003, pgs. 29-34.
  2. Content distribution networks (1 paper)
    1. Freedman, M., Freudenthal, E., Mazières, D., " Democratizing content publication with Coral ", In Proceedings of the 1st Symposium on Networked Systems Design and Implementation (NSDI 2004), San Francisco, CA, March 2004, pgs. 239-252.

Security (2 lectures)

  1. Saltzer, J.H. and Schroeder, M.D., " Protection and the Control of Information in Computer Systems ", Proceedings of the IEEE, 63(9):1278-1308, Sept. 1975.
  2. M. Satyanarayanan, " Integrating Security in Large Scale Distributed Systems ", ACM TOCS, Aug. 1989.

Background Papers

Required Background:

  1. Anderson, T.E., " The Performance of Spin Lock Alternatives for Shared-Memory Multiprocessors ", IEEE Transactions on Parallel and Distributed Systems, 1, 1, pgs. 6-16, January 1990.
  2. Birrell and Nelson, " Implementing Remote Procedure Calls ", ACM Transactions on Computer Systems, 2, 1, pgs. 39-59, February 1984. Also refer to Operating System Concepts , Silberschatz and Galvin.
  3. Basics on message passing and communication protocols. Refer to Operating System Concepts, Silberschatz and Galvin. Also refer to the web pages of the CoC networking courses.
  4. SUN NFS, Locus, and Sprite - from Operating System Concepts , Silberschatz and Galvin.
  5. Russel Sandberg et al., "Design and Implementation of the Sun Network Filesystem ", In Proceedings of Summer 1985 USENIX Conf., pgs. 119-130, 1985.
  6. Nelson, M.N., Welch, B.B., Ousterhout, J.K., "Caching in the Sprite Network File System ", ACM Transactions on Computer Systems, 6, 1, pgs. 134-154, February 1988.
  7. Walker et al., "The LOCUS Distributed Operating System ", Procedings of the Ninth ACM Symposium on Operaitng Systems Principles, pgs 49-70, December 1983

Optional Background/Supplemental

  1. Edsger W. Dijkstra, The Structure of the "THE" Multiprogramming System, Communications of the ACM, 11(5), May 1968.
  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. 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. Birrell, A.D., "Secure Communication Using Remote Procedure Calls", ACM Transactions on Computer Systems, 3, 1, pgs. 1-14, February 1985.
  6. 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.
  7. 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.
  8. 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.
  9. Jonathan Appavoo, Marc Auslander, Dilma Da Silva, Orran Krieger, et al., Enabling Scalable Performance for General Purpose Workloads on Shared Memory Multiprocessors , IBM Technical Report, 2003.
  10. 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.
  11. Fast Messages (FM): Efficient, Portable Communication for Workstation Clusters and Massively-Parallel Processors . IEEE Concurrency, vol. 5, no. 2, April-June 1997, pp. 60-73. (Pakin, Karamcheti & Chien).
  12. Marcel-Catalin Rosu, Karsten Schwan, and Richard Fujimoto," Supporting Parallel Applications on Clusters of Workstations ", Cluster Computing, Baltzer Science Publishers, May 1998.
  13. Aldrich, Dooley, et al., " Providing Easier Access to Remote Objects in Client-Server Systems ", 31th Hawaii International Conference on System Sciences in January, 1998.
  14. 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.
  15. Govindaraju, M., Slominski, A., Choppella, V., Bramley, R., Gannon, D., " Requirements for and evaluation of RMI protocols for scientific computing ", Conference on High Performance Networking and Computing, Proceedings of the 2000 Conference on Supercomputing, Dallas, Texas, USA.
  16. Linden, T.A., " Operating System Structures to Support Security and Reliable Software ", Computer Surveys, 8, 4, pgs. 409-445, 1976. Also refer to Operating System Concepts, Silberschatz and Galvin, the chapter on protection.
  17. Multics and the "computer utility" - F.J. Corbató and V. A. Vyssotsky, Introduction and Overview of the Multics System, In Proc. of the AFIPS Fall Joint Computer Conference 27, 1965.
  18. Saltzer, J.H., " Protection and the Control of Information Sharing in Multics ", Communications of the ACM, 17, 7, 1974.
  19. Priority inversion and what really happend on Mars? - Mike Jones' nicely written article on priority inversion and its part in the Mars Pathfinder mission What really happend on Mars?, December 1997.
  20. Shahabi, Zimmermann, Fu, and Yao. " Yima: A Second-Generation Continuous Media Server ", IEEE Computer Magazine, June 2002.
  21. 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.
  22. 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.
  23. Cohen, E., and Jefferson, D., " Protection in the HYDRA Operating System ", Proceedings of Fifth ACM Symposium on Operating System Principles, pgs. 141-160, 1975.
  24. 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.
  25. 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.

Supplementary Reference

Optional supplementary reference texts include the following: