CS 519: Operating Systems Theory

Time: M 6-9pm
PLace: 1st lecture, SEC 220. After, CoRE A.

Instructor: Thu D. Nguyen
Email: tdnguyen@cs.rutgers.edu
Office Hours: Thursday 2:30-3:30pm
Office: CoRE 326

TA: Xiaoyan Li
Email: xili@paul.rutgers.edu
Office Hours: Th 8-10pm
Office: Hill 411

Mailing list: dcs_519@email.rutgers.edu
Newgroup: ru.nb.dcs.class.519 (news server: news-lcsr.rutgers.edu)

Acknowledgement: Lecture slides for this course were originally created by Liviu Iftode; the current version has been modified, extended, etc. by Ricardo Bianchini, Richard Martin, and me. Assignments 1, 2, & 3 were borrowed almost directly from John Zahorjan's OS course at the University of Washington. The final project was borrowed from Ricardo Bianchini.

Announcements

• Sample problems and answers: set1, set2, set3. These are from Silberschatz's book. You can find and practice on similar problems from Stallings. I don't have the answer key for Stallings.
• Midterm. Solution.
• Things always take longer than I think/want ... here's the final project. The description is a little sparse so read it and think about it. We will discuss it in class next Monday (as well as in office hours if you wish).
  

Pre-requisites:

• Undergraduate courses in operating systems and architecture
• Working knowledge of C/C++ (or the ability/willingness to pick up these languages rapidly)

Recommended Book: William Stallings. Operating Systems - Internals and Design Principles, 4th edition, Prentice Hall, 2001. There is no required book. If you have another undergraduate book that you are satisfied with, you don't have to buy the recommended text.

Programming Assignments:

• assignment 1
  • Handin instructions for assignment 1.
• assignment 2
• assignment 3

Schedule:

Introduction 1/28

• Lecture slides
• Stallings Chapters 1 & 2

Gone to conference - no lecture - 2/4

Processes, Threads, and Synchronization Mechanisms - 2/11

• Lecture slides
• Stallings Chapters 3-6
• D. M. Ritchie and K. Thompson. The Unix Time-Sharing System. Communications of the ACM, Vol. 17, No. 7, July 1974.
• Submit summary. View summaries.
• R. Pike, D. Presotto, S. Dorward, B. Flandrena, K. Thompson, H. Trickey, P. Winterbottom. Plan 9 from Bell Labs. Computing Systems, Vol 8 #3, Summer 1995, pp. 221-254.
• Submit summary. View summaries.
• M. Herlihy. A Methodology for Implementing Highly Concurrent Data Objects. ACM Transactions on Programming Languages, volume 15, number 5, 1993.
  
• Submit summary. View summaries.

Processor Scheduling - 2/18

• Lecture slides
• Stallings Chapter 9-10
• Kenneth J. Duda and David R. Cheriton. Borrowed-Virtual-Time (BVT) scheduling: supporting latency-sensitive threads in a general-purpose scheduler. In Proceedings of the 17th ACM Symposium on Operating Systems Principles (SOSP), Dec. 1999
  
  • Submit summary. View summaries.
  • This is not required but will be covered somewhat in lecture slides so I'm posting in case you are interested: Carl A. Waldspurger and William E. Weihl. Lottery Scheduling: Flexible Proportional-Share Resource Management. In Proceedings of the Operating Systems Design and Implementation Conference (OSDI). pages = 1-11, 1994.
    
• A. Gupta, A. Tucker, and S. Urushibara. The Impact of Operating System Scheduling Policies and Synchronization Methods on the Performance of Parallel Applications. In Proceedings of the 1991 ACM SIGMETRICS Conference, May 1991.
• Submit summary. View summaries.

Virtual Memory - 2/25 & 3/4

• Lecture slides
• Stallings Chapters 7-8
• 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, Vol. 12, No. 4, November 1994.
  
• Submit summary. View summaries.

I/O and File Management - 3/11

• Lecture slides
• Stallings Chapters 11-12
• 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.
• Submit summary. View summaries.
• Douglas S. Santry, Michael J. Feeley, Norman C. Hutchinson, Alistair C. Veitch, Ross W. Carton, and Jacob Ofir. Deciding when to forget in the Elephant file system. In Proceedings of the 17th ACM symposium on Operating systems principles (SOSP), 1999.
• Submit summary. View summaries.

Spring break - 3/18

Midterm - 3/25

I/O and File Management, continued - 4/1

Communication in Tightly Coupled Systems - 4/8

• Lecture slides
• T. von Eicken, D. E. Culler, S. C. Goldstein, and K. E. Schauser. Active Messages: A Mechanism for Integrated Communication and Computation. In Proceedings of the 19th Annual International Symposium on Computer Architecture, May 1992
• Submit summary. View summaries.
• A. Basu, V. Buch, W. Vogels, and T. von Eicken. U-Net: A User-Level Network Interface for Parallel and Distributed Computing. In Proceedings of the 15th ACM Symposium on Operating Systems Principles (SOSP), December 1995.
• Submit summary. View summaries.
• R. Santos, R. Bianchini, and C. L. Amorim. A Survey of Messaging Software Issues and Systems for Myrinet-Based Clusters. In Parallel and Distributed Computing Practices, special issue on High-Performance Computing on Clusters, volume 2, number 2, June 1999.
  
• Submit summary. View summaries.

 

Introduction to Distributed Systems - 4/15

• Lecture slides
• J. Gray. The transaction concept: virtues and limitation. Proceedings of the 7th VLDB Conference, 1981.
  
• Submit summary. View summaries.

Distributed File Systems

• Lecture slides
• 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.
  
• Submit summary. View summaries.
• 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.
• Submit summary. View summaries.

Protection and Security - 4/8

• Lecture slides
• Stallings Chapter 15