Skip Navigation
Jack Baskin School of EngineeringUC Santa Cruz

CMPS 221 – Fall 2007

Links

General Class Information

Discussion forum
Lecture times:
MW, 5:00–6:45PM, Physical Sciences 114
Instructor:
Name: Darrell Long
Phone: 831-459-2616
Office: E2.371
Instructor Office Hours:
By appointment
 
 

Course Description

This course is a graduate level study of the issues in the design and implementation of computer operating systems. In terms of preparation, you are expected to have basic operating system knowledge, such as presented in a standard undergraduate course such as CS 111. Undergraduates will be admitted only with the permission of the instructor.

The readings will be taken from the current research literature and articles of historical significance. The topics include, but are not limited to: early systems, kernel structures, memory management, file systems, authentication, protection, security, synchronization, performance evaluation, fault tolerance, mobility and distributed systems. The course proceeds by topic, beginning with systems of historical significance. The focus will be on current research in the area, and so the time allocated to each topic will depend on the availability of articles.

In addition, we will be reading from the latest literature in the field, for example: the Symposium on Operating Systems Design and Implementation (OSDI), was held last November in Seattle and the Symposium on Operating Systems Principles (SOSP), will be held in October in the wilderness of southern Washington.

You will be required to write a report on a topic in the area of computer operating systems. This report should be the results of a project, original research (preferred), or a strong survey of prior art. A list of suggested projects is available, and will be handed out in class and posted to the web. Reporting work done for another course is not acceptable. You must choose a topic by second week of the quarter.

One or more articles will be assigned as reading prior to each class meeting. These should be read carefully, and a short summary of each article prepared for the following class meeting. You will use this in the discussion of the article, and your participation in the discussion is an important component of the course. In addition, each student will present one or more of the articles during the course of the class. You should prepare a short presentation and then lead a discussion of the article.

You will be required to complete a midterm and final examination. These are normally take-home, and may include experimentation with an operating system, or trying out an interesting idea. In more than one instance a question that appeared on the final examination led to a doctoral thesis, so the questions can be challenging.

Preparedness and class participation, both in your presentation and in the discussions, will be noted. Grading will be based on:

  • Final examination: 25%
  • Final project: 30%
  • Class participation and summaries: 25%
  • Paper presentations: 20%

Reading List

The reading list is in a state of flux. Check back frequently for updates.

History

  1. J. Fotheringham, "Dynamic Storage Allocation in the Atlas Computer, Including an Automatic Use of a Backing Store," Communications of the ACM, Vol. 4, No.10, October 1961, pp. 435–436.
  2. F. J. Corbató, M. M. Daggett, and R. C. Daley, "An Experimental Time-Sharing System," Proceedings of the AFIPS 1962 Spring Joint Computer Conference (SJCC), May 1962, pages 335–344.
  3. F. J. Corbató and V. A. Vyssotsky, "Introduction and Overview of the Multics System," Proceedings of the AFIPS 1965 Fall Joint Computer Conference (FJCC), 1965, Spartan Books: New York, pp. 185–196.
  4. E. W. Dijkstra, "The Structure of the THE Multiprogramming System," Communications of the ACM, Vol. 11, No. 5, May 1968, pp. 341–346.
  5. D. M. Ritchie and K. Thompson, "The UNIX Time-sharing System," Bell System Technical Journal, Vol. 57, No. 6, 1978, pp. 1905–1929.

Kernel Structures

  1. M. Accetta, R. Baron, W. Bolosky, D. Golub, R. Rashid, A. Tevanian, and M. Young, "Mach: A New Kernel Foundation for Unix Development," Proceedings of the Usenix Summer Technical Conference, July 1986.
  2. B. Bershad, S. Savage, P. Pardyak, E. G. Sirer, D. Becker, M. Fiuczynski, C. Chambers and S. Eggers, "Extensibility, Safety and Performance in the SPIN Operating System," Proceedings of the Fifteenth Symposium on Operating System Principles (SOSP), December 1995, pp. 267-284.
  3. M. F. Kaashoek, D. R. Engler, G. R. Ganger, H. M. Briceño, R. Hunt, D. Mazières, T. Pinckney, R. Grimm, J. Jannotti, and K. MacKenzie, "Application Performance and Flexibility on Exokernel Systems," Proceedings of the Sixteenth Symposium on Operating Systems Principles (SOSP), October 1997, pp. 52–65.
  4. M. Seltzer, Y. Endo, C. Small and K. Smith, "Dealing with Disaster: Surviving Misbehaved Kernel Extensions," Proceedings of the Second Symposium on Operating System Design and Implementation (OSDI) , October 1996.

Memory Management

  1. H. M. Levy and P. H. Lipman, "Virtual Memory Management in the VAX/VMS Operating System," IEEE Computer, March 1982, pp. 35–41.
  2. Ö. Babaoğlu and W. Joy, "Converting a Swap-Based System to do Paging in an Architecture Lacking Page Reference Bits," Proceedings of the Eighth Symposium on Operating Systems Principles (SOSP), 1981, pp. 78-85.
  3. J. S. Chase, H. M. Levy, M. J. Feeley, and E. D. Lazowska, "Sharing and Protection in a Single-Address-Space Operating System," ACM Transactions on Computer Systems, volume 12, number 4, November 1994, pp. 271–307.
  4. J. Bonwick, "The Slab Allocator: An Object-Caching Kernel Memory Allocator," Proceeding of the Usenix Summer Technical Conference, 1994.

Virtual Machines

  1. T. Garfinkel, B. Pfaff, J. Chow, M. Rosenblum and D. Boneh, "Terra: a virtual machine-based platform for trusted computing," Proceedings of the Nineteenth Symposium on Operating Systems Principles (SOSP), 2003, pp. 193–206.
  2. P. Barham, B. Dragovic and K. Fraser and S. Hand and T. Harris and A. Ho and I. Pratt and A. Warfield, and R. Neugebauer, "Xen and the Art of Virtualization," Proceedings of the Nineteenth Symposium on Operating Systems Principles (SOSP), 2003, pp. 164–177.

File Systems

  1. M. K. McKusick, W. N. Joy, S. J. Leffler and R. S. Fabry, "A Fast File System for UNIX," ACM Transactions on Computer Systems, Vol. 2, No. 3, August 1984, pp. 181–197.
  2. M. N. Nelson, B. B. Welch and J. K. Ousterhout, "Caching in the Sprite Network File System," ACM Transactions on Computer Systems, Vol. 6, No. 1, February 1988, pp. 134–154.
  3. M. Rosenblum and J. K. Ousterhout, "The Design and Implementation of a Log-Structured File System," ACM Transactions on Computer Systems, Vol. 10, No. 1, February 1992, pp. 26-52.
  4. D. Hitz, J. Lau, and M. Malcolm, "File System Design for an NFS File Server Appliance," Proceedings of the Usenix Winter Technical Conference, January 1994, pp. 235–246.
  5. A. Muthitacharoen, B. Chen, and D. Mazières, "A Low-Bandwidth Network File System," Proceedings of the Eighteenth ACM Symposium on Operating Systems Principles (SOSP), October 2001, pp. 174–187.
  6. S. Quinlan and S. Dorward, "Venti: A New Approach to Archival Storage," Proceedings of the Conference on File and Storage Technologies (FAST), January 2002, pp. 89–102.

Authentication, Protection, and Security

  1. B. W. Lampson, "A Note on the Confinement Problem," Communications of the ACM, Vol. 16, No. 10, October 1973, pp. 613–615.
  2. R. L. Rivest, A. Shamir and L. Adleman, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems," Communications of the ACM, Vol. 21, No. 2, February 1978, pp. 120–126.
  3. R. Needham and M. Schroeder, "Using Encryption for Authentication in Large Networks of Computers," Communications of the ACM, Vol. 21, No. 12, December 1978, pp. 993-999.
  4. J. G. Steiner, C. Neuman and J. I. Schiller, "Kerberos: An Authentication Service for Open Network Systems," Proceedings of the Usenix Winter Technical Conference, 1988, pp. 205–211.
  5. J. D. Strunk, G. R. Goodson, M. L. Scheinholtz, C. A. N. Soules, and G. R. Ganger, "Self-Securing Storage: Protecting Data in Compromised Systems," Proceedings of the Symposium on Operating Systems Design and Implementation (OSDI), October 2000, pp. 165–180.
  6. D. Mazières, M. Kaminsky, M. F. Kaashoek, and E. Witchel, "Separating Key Management from File System Security," Proceedings of the Seventeenth Symposium on Operating Systems Principles (SOSP), 1999, pp.124–139.
  7. E. L. Miller, D. D. E. Long, W. E. Freeman, and B. C. Reed, "Strong Security for Network-Attached Storage," Proceedings of the Conference on File and Storage Technologies (FAST), January 2002, pp. 1–13.

Synchronization & Scheduling

  1. C. A. R. Hoare, "Monitors: An Operating System Structuring Concept," Communications of the ACM, Vol. 17, No. 10, October 1974, pp. 549–557.
  2. L. Lamport, "A Fast Mutual Exclusion Algorithm," ACM Transactions on Computer Systems, Vol. 5, No. 1, February 1987, pp. 1–11.
  3. D. Agrawal and A. E. Abbadi, "An Efficient and Fault-Tolerant Solution for Distributed Mutual Exclusion," ACM Transactions on Computer Systems, Vol. 9, No. 1, February 1991, pp. 1–20.
  4. C. A. Waldspurger and W. E. Weihl, "Lottery Scheduling: Flexible Proportional-Share Resource Management," Proceedings of the Symposium on Operating System Design and Implementation (OSDI), November 1994, pp. 1–11.
  5. F. Douglis, "Transparent Process Migration: Design Alternatives and the Sprite Implementation," Software — Practice & Experience, Vol. 21, No. 8, 1991, pp. 757–785.

Performance Evaluation

  1. J. Ousterhout, "Why Aren't Operating Systems Getting Faster as Fast as Hardware?" Proceedings of the Usenix Summer Technical Conference, June 1990, pp. 247–256.
  2. M. Rosenblum, E. Bugnion, S. A. Herrod, E. Witchel, and A. Gupta, "The Impact of Architectural Trends on Operating System Performance," Proceedings of the Fifteenth ACM Symposium on Operating Systems Principles (SOSP), December 1995, pp. 285–298.
  3. J. B. Chen, Y. Endo, K. Chan, D. Mazières, A. Dias, M. Seltzer, and M. D. Smith, "The Measured Performance of Personal Computer Operating Systems," Proceedings of the Fifteenth ACM Symposium on Operating Systems Principles (SOSP), December 1995, pp. 299–313.
  4. M. G. Baker, J. H. Hartman, M. D. Kupfer, K. W. Shirriff, and J. K. Ousterhout, "Measurements of a Distributed File System," Proceedings of the Thirteenth Symposium on Operating Systems Principles (SOSP), October 1991, pp. 198–212.

Communication and Distributed systems

  1. J. F. Shoch and J. A. Hupp, "The 'Worm' Programs — Early Experience with a Distributed Computation," Communications of the ACM, Vol. 25, No. 3, March 1982, pp. 172–180.
  2. M. D. Schroeder, A. D. Birrell and R. M. Needham, "Experience with Grapevine: the Growth of a Distributed System," ACM Transactions on Computer Systems, Vol. 2, No. 1, February 1984, pp. 3–23.
  3. L. Lamport, "Time, Clocks, and the Ordering of Events in a Distributed System," Communications of the ACM, Vol. 21, No. 7, July 1978, pp. 558–565.
  4. P. Maniatis, M. Baker, "Secure History Preservation through Timeline Entanglement," Proceedings of the Usenix Security Symposium, August 2002.


Reliability & Fault Tolerance

  1. R. Rodrigues, M. Castro, and B. Liskov, "BASE: Using Abstraction to Improve Fault Tolerance," Proceedings of the Eighteenth ACM Symposium on Operating Systems Principles (SOSP), October 2001, pages 15–28.
  2. A. Chou, J. Yang, B. Chelf, S. Hallem, and D. Engler, "An Empirical Study of Operating Systems Errors," Proceedings of the Eighteenth ACM Symposium on Operating Systems Principles (SOSP), October 2001, pp. 73–88.
  3. B. Liskov, S. Ghemawat, R. Gruber, P. Johnson, L. Shrira, and M. Williams, "Replication in the Harp File System," Proceedings of the Thirteenth Symposium on Operating Systems Principles (SOSP), October 1991, pp. 226–238.
  4. J. R. Douceur and R. P. Wattenhofer "Optimizing File Availability in a Secure Serverless Distributed File System," Proceedings of the Twentieth Symposium on Reliable Distributed Systems, 2001, pp. 4–13.

Miscellanea

  1. R. Levin and D. D. Redell, "An Evaluation of the Ninth SOSP Submissions," Operating Systems Review, Vol. 17, No. 3, July 1983, pp. 35-40.

More to come...