CS591 Operating Systems II Spring 2004

• Instructors: Wayne Snyder and Rich West
• Email: {snyder,richwest}@cs.bu.edu
• Office hours:
• Professor Snyder: MWF 10-11:00am
  
• Professor West: TR 2:30-4:00pm
  
• Office Locations:
• Professor Snyder: MCS 293
• Professor West: MCS 289
  
• Class location: MCS B29 (Officially)
• Note: we will meet in CAS B14 after the first class
  
• Lecture times: Monday 3-6pm
  
• Syllabus (Subject to change)

Prerequisites:

• CS552
• Proficiency with C and/or C++ (if in doubt, please see one of the instructors).

Overview:

• This is a research-oriented operating systems course.
• The internals of the Linux operating system will be discussed, along with some significant research papers.
• Class members are required to present some of the papers and/or topics in this course.
• There is one large project  in this course and possibly some smaller (primer) projects, so very good programming skills are essential.


• The semester project involves:
• writing a brief proposal describing the project and what you hope to achieve,
• implementing the details described in the proposal,
• writing a report, and
• presenting your project to the class at the end of the semester.

• The semester project will be based around (but not limited to) the advanced operating systems concepts discussed in class.
• Use of Linux to implement your project is encouraged but not required. Ultimately, the decision to approve your project will rest in the hands of the instructors. However, your project should involve a topic that is related to operating systems.
  
• Students should look at research papers outside the scope of the course for additional information and ideas for projects . Appropriate papers should come from quality conferences and journals, such as:
• ACM Symposium on Operating Systems Principles (SOSP)
• USENIX Operating Systems Design and Implementation (OSDI)
• IEEE International Conference on Distributed Computing Systems (ICDCS)
• USENIX Annual Technical Conference
• ACM SIGCOMM
• IEEE Real-Time Systems Symposium
• ACM Transactions on Computer Systems
• IEEE Transactions on Computers
• IEEE Transactions on Parallel and Distributed Systems
• ACM/IEEE Transactions on Networking
  

Grading

• class participation and quality of presentations during the course. You will be responsible for picking selected papers and/or topics of interest, presenting them in class, and discussing aspects of these papers/topics with other class members;
• class projects. This includes scope and complexity of the problem you propose in the semester project, the depth of results and/or interesting contributions, the final project presentation and the written report.
• The following is a tentative breakdown of the grades:

* The project milestone is a mid-semester report that will act as a skeleton for the final report. It should be similar to the final report with any preliminary results included, where appropriate. You should try to write your final report in the same format as the papers we will read and discuss in the course. The best papers will be selected as potential candidates for submission to conferences.

General Notes

• Everyone should read all the papers discussed in class, even if other people are presenting them.
• A good presentation involves a clear and accurate description of all the key points in the paper(s).
• You should take an appropriate amount of time to read papers and prepare your presentations before class.
• We strongly encourage you to consult with the class instructors before making a presentation to the class.
  
• There are no exams or written assignments outside the projects and class presentations, but there may be quizzes, so beware!

Project Ideas

• Ideas for projects can be found here.
  

Syllabus (subject to change)

• The syllabus may change depending on the time spent on different topics and whether or not new or alternative papers are discussed.
• All comments, paper suggestions and topics are welcome!

Reading List

Books and Documentation Sources

• Daniel P. Bovet and Marco Cesati, "Understanding the Linux Kernel", Second Edition, O'Reilly, ISBN: 0-596-00213-0, 2003.
• The above book has a useful bibliography section, covering many of the most relevant books and sources of documentation.
  
• If you have the firest edition, that will be good enough.
  
• A. Rubini, "Linux Device Drivers", O'Reilly, ISBN: 1-56592-292-1,  1998 or most recent edition.
• W. Richard Stevens, "Advanced Programming in the UNIX Environment", Addison-Wesley, ISBN: 0-201-56317-7, 1994.
• A. Tanenbaum, "Distributed Operating Systems", Prentice-Hall, 1995.
• Kip R. Irvine, "Assembly Language for Intel-Based Computers", Third Edition, Prentice-Hall, ISBN: 0-13-660390-4, 1999.
• Intel, "IA-32 Intel Architecture Software Developer's Manual", Volumes 1, 2 and 3.
  
• Linux websites:
• The Linux source code: http://www.kernel.org/
• Linux Online: http://www.linux.org/
• Linux Headquarters: http://www.linuxhq.com/
• The Linux Documentation Project: http://www.linuxdoc.org/
• Linux kernel traffic (summary of newsletters on kernel development): http://kt.zork.net/kernel-traffic/latest.html
• Linux cross reference (for finding your way through the source code): http://lxr.linux.no/
  
• ...and many more. Just use your favorite search engine...

OS Structures

[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] 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.

Threads

[5] S. Oikawa and H. Tokuda, " User-level Real-Time Threads ", Proceedings of the 11th IEEE Workshop on Real-Time Operating Systems and Software, Seattle, WA, May 1994.

[6] R. P. Draves, B.N. Bershad, R.F. Rashid, and R.W. Dean, " Using Continuations to Implement Thread Management and Communication in Operating Systems ", Proceedings of the Thirteenth ACM Symposium on Operating Systems Principles, pages 122--136, October 1991.

[7] R. Engelschall, "Portable Multithreading: the Signal Stack Trick for User-Space Thread Creation", in Proceedings of the USENIX Annual Technical Conference, 2000.

[8] Rob von Behren, Jeremy Condit, Feng Zhou, George C. Necula, and Eric Brewer,  "Capriccio: Scalable Threads for Internet Services", in Proceedings of the 19th Symposium on Operating System Principles (SOSP-19), Lake George, New York, October 2003.

• Related SOSP talk (ppt format) and general web page.
  

Scheduling and Synchronization

[10] C. Liu and J. Layland, " Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment ", Journal of the ACM, 1973.

[11] J. Lehoczky, L. Sha, , and Y. Ding, "The Rate Monotonic Scheduling algorithm: Exact Characterization and Average Case Behavior", in IEEE Real-Time Systems Symposium, 1989.

[12] A. Atlas and A. Bestavros, "Statistical Rate Monotonic Scheduling", in IEEE Real-Time Systems Symposium, 1998.

[13] L. Sha, R. Rajkumar, and J. Lehoczky, "Priority inheritance protocols: An approach to real-time synchronization",  in IEEE Transaction on Computers, September 1990.

[14] Pawan Goyal, Xingang Guo and Harrick M. Vin, " A Hierarchical CPU Scheduler for Multimedia Operating Systems ", 2nd Symposium on Operating Systems Design and Implementation, pp. 107-121, 1996.

[15] Carl A. Waldspurger and William E. Weihl, " Lottery Scheduling: Flexible Proportional-Share Resource Management ", First Symposium on Operating Systems Design
and Implementation (OSDI '94), Monterey, CA, November 1994.

[16] Richard West, Yuting Zhang, Karsten Schwan and Christian Poellabauer, "Dynamic Window-Constrained Scheduling of Real-Time Streams in Media Servers", to appear in IEEE Transactions on Computers, 2004.

[17] Aloysius K. Mok and Weirong Wang, "Window-Constrained Real-Time Periodic Task Scheduling", Proceedings of the 22nd IEEE Real-Time Systems Symposium, December 2001

[18] Kevin Jeffay and Gerardo Lamastra, "A Comparative Study of the Realization of Rate-Based Computing Services in General Purpose Operating Systems" .

• NOTE: Other papers on pinwheel, pfair and multiprocessor scheduling may be discussed.
  

QoS and Resource Management

[20] M. Jones, D. Rosu and M. Rosu, " CPU Reservations and Time Constraints: Efficient, Predictable Scheduling of Independent Activities ", Proc. of the 16th ACM symposium on Operating System Principles, St-Malo, France, pp. 198-211, Oct. 1997.

[22] J.A. Zinky, D.E. Bakken and R.E. Schantz, " Architectural Support for Quality of Service for CORBA Objects ", Theory and Practice of Object Systems, April, 1997. (See also: http://www.dist-systems.bbn.com/tech/QuO/ ).

[23] Tarek F. Abdelzaher and Kang G. Shin, `` End-host Architecture for QoS-Adaptive Communication '', IEEE Real-Time Technology and Applications Symposium, Denver, Colorado, June 1998.

[25] David C. Steere, Ashvin Goel, Joshua Gruenberg, Dylan McNamee, Calton Pu and Jonathan Walpole, " A Feedback-driven Proportion Allocator for Real-Rate Scheduling "  Operating Systems Design and Implementation (OSDI), Feb 1999.

[26] Chenyang Lu, Tarek F. Abdelzaher, John A. Stankovic, and Sang H. Son, "A Feedback Control Approach for Guaranteeing Relative Delays in Web Servers" .

• NOTE: Additional reading may include topics such as the "resource containers" work by Banga, Druschel and Mogul.
  

Extensible Systems

[27] Chris Small and Margo Seltzer, "A Comparison of OS Extension Technologies" .

[28] M. I. Seltzer, Y. Endo, C. Small and K. A. Smith, "Dealing with Disaster: Surviving Misbehaved Kernel Extensions",
in Proceedings of the 2nd Symposium on Operating Systems Design and Implementation (OSDI), 1996.

[30] M. Clarke and G. Coulson,  "An Architecture for Dynamically Extensible Operating Systems", in Proceedings of the 4th International Conference on Configurable Distributed Systems (ICCDS'98), Annapolis, MD, USA, May 1998.

[31] Tzi-cker Chiueh and Ganesh Venkitachalam and Prashant Pradhan, "Integrating Segmentation and Paging Protection for Safe, Efficient and Transparent Software Extensions", in Proceedings of the Symposium on Operating Systems Principles, 1999.

[32] Michael Jones, "Interposition Agents: Transparently Interposing User Code at the System Interface" .

[33] Richard West and Jason Gloudon, "User-Level Sandboxing: A Safe and Efficient Mechanism for Application-Specific Extensions", submitted for publication.

• Related paper (by Trevor Jim et al published in USENIX, 2002) and presentation on Cyclone. This is a type-safe language suitable for use in extensible systems. The BU User-Level Sandbox project leverages it for memory-safety of application code mapped into a shared virtual address space.
  

Virtual Machines

• A useful list of virtual machine topics by Peter Dinda of Northwestern University can be found here.
  

Communication Mechanisms and Abstractions

[42] D.A. Wallach, W.C. Hsieh, K.K. Johnson, M.F. Kaashoek and W.E. Weihl, " 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.

[44] N.C. Hutchinson and L.L. Peterson, " The x-Kernel: An Architecture for Implementing Network Protocols ", IEEE Transactions on Software Engineering, 17, 1, pgs. 64-76, January 1991.

[45] Deborah A. Wallach, Dawson R. Engler, and M. Frans Kaashoek, " ASHs: Application-specific Handlers for High-performance Messaging ", ACM Communication Architectures, Protocols, and Applications (SIGCOMM '96).

[46] Thorsten von Eicken, Anindya Basu, Vineet Buch, Werner Vogels: "U-Net: A User-Level Network Interface for Parallel and Distributed Computing", Symposium of Operating System Principles, 1995: 40-53

[47] E. Kohler, R. Morris, B. Chen, J. Jannotti  and  M. Frans Kaashoek, "The Click Modular Router", ACM Transactions on Computer Systems, 18(3), August 2000, pp 263-297.

Distributed System Concepts and Shared Memory

[49] Mustaque Ahamad, Gil Neiger, Prince Kohli, James Burns and Phil Hutto, " Causal Memory:  Definitions, Implementation and Programming ", Distributed Computing, 9(1):37-49, Aug 1995.

[50] P. Keleher, A. Cox and W. Zwaenepoel, " Lazy Release Consistency for Software Distributed Shared Memory ", Proc. of the Twentieth International Symposium on Computer Architecture, 1993.

[51] R. Haskin, Y. Malachi, W. Sawdon, and G. Chan, "Recovery Management in Quicksilver", ACM Transactions on Computer Systems, 6(1), Feb. 1998, pp 82-108.

[52] M. D. Schroeder and M. Burrows, "Performance of the Firefly RPC", in Proc. of the 12th Symposium on Operating System Principles, 1989.

[53] D. Mills, "Improved Algorithms for Synchronizing Computer Network Clocks", IEEE/ACM Transactions on Networks, 3(3), Jun. 1995, pp 245-254.

[54] M. Raynal and M. Singhal, "Logical Time: Capturing Causality in Distributed Systems", in IEEE Computer, 29(2), Feb. 1996, pp 49-56.

[55] M. Chandy and L. Lamport, "Distributed Snapshots: Determining Global States of Distributed Systems", ACM Transactions on Computer Systems, 3(1), Feb. 1985, pp 63-75.

[56] R. Schwarz and F. Mattern, "Detecting Causal Relationships in Distributed Computations: In Search of the Holy Grail", Distributed Computing, 1994.

• NOTE: Depending on time and interest, numerous other papers may be discussed in the area of distributed sytems.
  

Linux and Related Projects

[58] Shrimp: http://www.cs.princeton.edu/shrimp/

[59] Beowulf: http://www.beowulf.org/

[60] QoSockets: http://www.cs.columbia.edu/dcc/qosockets/

[61] DWCS: http://www.cs.bu.edu/fac/richwest/dwcs.html

[62] User-Level Sandboxing: http://www.cs.bu.edu/fac/richwest/sandboxing.html
 
[63] Familiar Linux: http://www.handhelds.org/geeklog/index.php

[64] LegOS: http://www.noga.de/legOS/

[65] Plex86: http://plex86.sourceforge.net/

[66] Bochs IA-32 Emulator: http://bochs.sourceforge.net/

[67] User-Mode Linux: http://user-mode-linux.sourceforge.net/

Additional Readings

Miscellaneous

• Gaurav Banga, Jeffrey Mogul, & Peter Druschel, "A scalable and explicit event delivery mechanism for UNIX"
• Rob Pike, Bell Labs, Lucent Technologies, "Systems Software Research is Irrelevant" .

Distributed Filesystems

• The SUN NFS - A. Tanenbaum, "Distributed Operating Systems", Prentice-Hall, 1995.
• M.N. Nelson, B.B. Welch and J.K. Ousterhout, `` Caching in the Sprite Network File System ", ACM Transactions on Computer Systems, 6, 1, pgs. 134-154, February 1988.
• P.V. Rangan and H.M. Vin, `` Designing File Systems for Digital Video and Audio ", Proceedings of the  Thirteenth ACM Symposium on Operating System Principles, pgs. 81-94, December 1991.

Scheduling

• Hui Zhang and Srinivasav Keshav, " Comparison of Rate-Based Service Disciplines ", Proceedings of ACM SIGCOMM, pp. 113-121, August 1991.

Threads

• K. Schwan and H. Zhou, "Dynamic Scheduling of Hard Real-Time Tasks and Real-Time Threads," IEEE Transactions on Software Engineering, Vol. 18, No. 8, pp. 736-748, August 1992.
• K. Schwan, H. Zhou, and A. Gheith, "Real-time threads," ACM Operating Systems Review, vol. 25, pp. 35-46, Oct. 1991.
  

Memory Management

• M.J. Feeley, W.E. Morgan, F.H. Pighin, A. R. Karlin, H.M. Levy and C.A. Thekkath, `` Implementing Global Memory Management in a Workstation  Cluster '', Fifteenth ACM Symposium on Operating System Principles, Dec. 1995.
  

QoS Management

• Baochun Li and  Klara Nahrstedt, " A Control-based Middleware Framework for Quality of Service Adaptations ", IEEE Journal of Selected Areas in Communication, Special Issue on Service Enabling Platforms, 1999, Vol. 17, No. 9, September 1999, pp. 1632-1650.
• The Monet Research Group at the University of Illinois, Urbana-Champaign: http://cairo.cs.uiuc.edu/papers.html.
• C. Aurrecoechea and A. Campbell and L. Hauw, " A Survey of QoS Architectures ", Multimedia Systems Journal, Special Issue on QoS Architecture,  1997.

Communication Mechanisms

• D.D. Clark, "The Structuring of Systems Using Upcalls", Proceedings of Tenth ACM Symposium on Operating Systems Principles, pgs. 171-180, Dec. 1985.

Linux-Related Papers

• Werner Almesberger, " Linux Network Traffic Control -- Implementation Overview ", April 1999.

Other Topics for Future Reference

• Group communication in distributed systems.
• Process/thread migration and load-balancing.
• Protection and security.