CS 519: Operating Systems Theory

Instructor: Thu D. Nguyen
Time & Location: W 6:40-9:30pm, CoRE A

Logistics

Announcements

• Final exam: W 12/21, 6:40-9:30, CoRE A.
• Some additional instructions from Kien for Assignment 2.
• In the future, I will make all announcements through the Main discussion topic in webct just to have all announcements appear in a consistent place.
• Please make sure all emails sent to me for this class has the following in the subject: [cs519].  You can of course have other words in the subject as well but just make sure the [cs519] is in there somewhere so that I can filter all class-related emails to a separate mailbox.

Programming Assignments and Projects:

• You have 3 options:
  1. Standard: threads package, single-node file system, distributed file system
  2. Advance: threads package, single-node file system, independent project
  3. Been-there-done-that: distributed file system, independent project
• Assignments are "do-at-your-own pace."  Most students should choose the Standard option.  Students wishing to eventually do research in OS/distributed systems may choose the Advance option.  To do so, however, you must complete the first 2 assignments by the 6th week (10/12) and successfully define a project with us by 11/2.  Finally, some students may have taken 416 with me (or the equivalent somewhere else) so that they thoroughly understand how to build a threads package.  If you can convince us that you thoroughly understand threads, then you can choose the "Been-there-done-that" option.  Note that we will expect you to complete a larger than normal independent project since you will have more time than the students choosing the Advance option.
• Resources for programming assignments:
  • Cereal cluster (for non-kernel work)
    • Note that, for now, the page is somewhat out of date.  The Soup and Pasta machines are now 3.2 GHz P4 boxes running Linux.  So, any of the cereal machines are now quite fast and can be used for our assignments.
  • vOS Lab
    • User Mode Linux

Acknowledgement: The single-node file system assignments is based on John Zahorjan's Linux Projects for Undergraduate Operating System Courses.

Syllabus: (This is preliminary.  The dates and specific papers may still change substantially.)

Please remember that I want 1-2 scribes for each lecture.

9/07 Introduction

• Background: SGG Chapters 1-3.
• D. M. Ritchie and K. Thompson. The UNIX Timesharing System. Communications of the ACM 17(7), July 1974.
• V. A. Vyssotsky, F. J. Corbato, and R. M. Graham.  Structure of the Multics Supervisor.  1965 Fall Joint Computer Conference.

9/14 & 21 Processes, Threads & Synchronization

• Background: SGG Chapters 4, 5 & 7.
• A. D. Birrell. An Introduction to Programming with Threads. SRC Research Report 35, 1989.
• M. Herlihy. A Methodology for Implementing Highly Concurrent Data Objects. ACM Transactions on Programming Languages, 15(5), 1993.

9/28 & 10/05 Virtual Memory

• Background: SGG Chapters 9 & 10.
• J. Chase, H. Levy, M. Feeley, and E. Lazowska. Sharing and Protection in a Single Address Space Operating System. ACM Trans. on Computer Systems, November 1994.

10/12 I/O and File Systems

• Background: SGG Chapters 11-14.
• M. K. McKusick, W. N. Joy, S.J. Leffler, and R. S. Fabry. A Fast File System for UNIX. ACM Trans. on Computer Systems 2(3), August 1984.
• M. Rosenblum and J. K. Ousterhout. The Design and Implementation of a Log-Structured File System. ACM Trans. on Computer Systems 10(1), February 1992, pp. 26-52.

10/19 Processor Scheduling

• Background: SGG Chapter 6.
• C. Waldspurger and W. Weihl. Lottery Scheduling: Flexible Proportional-Share Resource Management. Proceedings of the First USENIX Symposium on Operating System Design and Implementation , November 1994.

10/26 Midterm (Thu is gone to conference)

11/02 Communication

• A. Basu, V. Buch, W. Vogels, and T. von Eicken. U-Net: A User-Level Network Interface for Parallel and Distributed Computing. Proceedings of the 15th ACM Symposium on Operating Systems Principles (SOSP), December 1995.
• Andrew D. Birrell and Bruce Jay Nelson. Implementing Remote Procedure Calls . ACM Trans. on Computer Systems 2(1), February 1984, pp. 39-59.

11/09 Distributed Systems Fundamentals

• Leslie Lamport. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, Volume 21 , Issue 7 (July 1978).
• M. Fischer, N. A. Lynch, and M. S. Patterson. Impossibility of distributed consensus with one faulty processor. Journal of the ACM, 32(2):374-382, April 1985.
• J. Gray. The transaction concept: virtues and limitation. Proceedings of the 7th VLDB Conference, 1981

11/16 Distributed File Systems

• M. N. Nelson, B. B. Welch, and J. K. Ousterhout. Caching in the Sprite Network File System. ACM Trans. on Computer Systems 6(1), February 1988, pp. 134-154.
  • Here are two NFS RFCs for comparison. You should skim the first one. The second one is really long so you should just briefly look at it for interesting changes.
    • RFC 1094: NFS: Network File System Protocol Specification.
    • RFC 3010 (rfc3010) - NFS version 4 Protocol.

11/22 Distributed File Systems (cnt'd) & Cluster (ALERT: This is a Tuesday because of Rutgers class shifting for Thanksgiving week!)

• Edward K. Lee and Chandramohan A. Thekkath. Petal: distributed virtual disks. In Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, 1996.
• C. A. Thekkath, T. Mann, and E. K. Lee. Frangipani: A Scalable Distributed File System. In Proceedings of the 16th ACM Symposium on Operating Systems Principles, October 1997.
• Kenneth P. Birman, The Process Group Approach to Reliable Distributed Computing. Communications of the ACM (CACM), 36(12):37-53, December 1993.

11/30 Cluster (cnt'd) & Structure and Organization

• Y. Saito, B. Bershad, and H. Levy. Manageability, Availability and Performance in Porcupine: A Highly Scalable Internet Mail Service . Proc. of the 17th ACM Symp. on Operating Systems Principles, Dec. 1999.
• M. Welsh, D. Culler, E. Brewer. SEDA: An Architecture for Well-Conditioned, Scalable Internet Services. Proc. of the 18th ACM. Symp. on Operating Systems Principles, Oct. 2001.

12/07 OS Structure

• J. Liedtke. On micro-kernel construction. Proceedings of the fifteenth ACM symposium on Operating systems principles. Dec, 1995.
• B. Bershad, S. Savage, P. Pardyak, E. Sirer, M. Fiuczynski, D. Becker, C. Chambers, and S. Eggers. Extensibility, Safety and Performance in the SPIN Operating System. Proc. of the 15th ACM. Symp. on Operating Systems Principles, December 1995.