CS591 Operating Systems II Spring 2002

• Instructor: Rich West
• Email: richwest@cs.bu.edu
• Office hours: Th 3-6pm
• Office: MCS 289
• Class location: B24
• Lecture times: TR 11:00-12:30pm
• Syllabus (Subject to change)

Prerequisites:

• CS552
• Proficiency with the C programming language (if in doubt, please see the instructor).

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 for implementing your project is required.
• 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

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 candidates for potential conference papers.

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.
• There are no exams or written assignments outside the projects and class presentations, but there may be quizzes, so beware!

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", O'Reilly, ISBN: 0-596-00002-2, October 2000.
• The above book has a useful bibliography section, covering many of the most relevant books and sources of documentation.
• A. Rubini, "Linux Device Drivers", O'Reilly, ISBN: 1-56592-292-1,  1998.
• M. Beck, H. Bohme, M. Dziadzka, U. Kunitz, R. Magnus and D. Verworner, "Linux Kernel Internals", Second Edition, Addison-Wesley, 1998.
• R. Card, E. Dumas and F. Mevel, "The Linux Kernel Book", John Wiley and Sons, Inc., 1998.
• 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, "Intel Architecture Software Developer's Manual, Vol. 3: System Programming", 1999.
• http://developer.intel.com/design/pentiumii/manuals/24319202.pdf
• 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/
• ...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.

Scheduling

[5] Clifford W. Mercer, Stefan Savage and Hideyuki Tokuda, " Processor Capacity Reserves: Operating System Support for Multimedia Applications ", In the Proceedings of the IEEE International Conference on Multimedia Computing and Systems, May 1994, pp. 1-10.

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

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

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

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

[10] Richard West, Karsten Schwan and Christian Poellabauer, " Scalable Scheduling Support for Loss and Delay Constrained Media Streams ", Proceedings of the 5th IEEE Real-Time Technology and Applications Symposium, June 1999.

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

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

QoS Management

[14] 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/ ).

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

(Adaptive / Feedback) Control-Based Service Management

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

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

Threads

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

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

Memory Management

Distributed System Concepts and Shared Memory

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

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

Communication Mechanisms

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

High Performance Communications

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

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

Linux Projects

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

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

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

[35] DWCS: http://www.cc.gatech.edu/~west/dwcs.html
 

Extensible Systems

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

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

[38] Peter Druschel, Vivek Pai and Willy Zwaenepoel, "Extensible Kernels are Leading OS Research Astray" .
 

Miscellaneous

[40] Rob Pike, Bell Labs, Lucent Technologies, "Systems Software Research is Irrelevant" .

Additional Readings

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. Here is a (working) revision of the paper.

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.
• Synchronization.
• Process/thread migration and load-balancing.
• Protection and security.

Suggested Projects

• Implementing a real-time thread library:
• Provide ability to specify the thread scheduling policy.
• Provide a mechanism to specify/bound the delay of synchronization.
• Involves writing a new thread API.
• Possible support or "hooks" for interaction between kernel/user-level threads.
• A thread continuation mechanism:
• Implement an extension of Linux bottom-half handlers (or active message handlers -- SEE BELOW) to continue as threads that are scheduled for future execution if they do not complete in certain time bounds.
• A thread migration / load balancing system:
• Implement a mechanism to migrate threads to different hosts, in order to redistribute the demand for resources "more evenly" in a distributed system environment.
• Scheduler activations in Linux:
• Provide the mechanism for interaction between kernel/user-level threads.
• See [4] above.
• A Linux "upcall" mechanism:
• Essentially the opposite of a system call.
• Provide a means for the kernel to invoke handlers in user-space and pass parameters to these handlers.
• Provide a generalizable framework for implementing and scheduling handlers in different process/thread contexts.
• A real-time memory allocator / garbage collector:
• Provide a mechanism to preallocate, or bound the delay of allocation and de-allocation of memory.
• Possibly implement a replacement for the "slab allocator" in Linux.
• A distributed shared memory (DSM) system:
• Devise a scalable DSM system that supports application-specific consistency protocols.
• Provide a mechanism by which applications can customize the underlying DSM system to be more efficient / scalable.
• An event-based mechanism for implementing adaptive systems:
• Implement an event-channel mechanism that has the ability to pass "control" events between publishers (event generators) and subscribers (event handlers).
• Provide support for events to be delivered within an address-space and the same thread, between threads within the same address space, between address spaces on the same host, and between address spaces on different hosts.
• Support the ability to specify handler and event-generator functions.
• Support the multicasting of events to multiple subscribers.
• Provide "hooks" to schedule, dispatch, filter and transform events before they are ultimately delivered to subscribers.
• A data flow management mechanism:
• Similar to the event-based mechanism described above, construct a mechanism to manage the distribution of data, and functions that manipulate the data, in a distributed system or wide-area network. This would be applicable to, for example, web servers that wish to cache data at different locations, and/or perform some form of filtering or processing on the data as it is delivered along the path from source to destination.
• A kernel event notification mechanism:
• Similar to the idea presented in [39], implement a way to signal to processes event occurrences in the kernel that applications wish to be notified about.
• A QoS-based socket library:
• Modify the network subsystem in Linux to support per-socket-descriptor service disciplines.
• Extend the library and corresponding network subsystem to support "end-to-end" QoS guarantees on a per-socket basis.
• Migrating sockets:
• Investigate ways to migrate socket connections between different pairs of end-points.
• DWCS or some other form of packet scheduling:
• See [10, 35] above.
• Implement DWCS as a packet-level service discipline in the Linux subsystem. A version of DWCS is already working as a replacement CPU scheduler in Linux.
• Develop a new approach to fair queueing or study improvements to the existing packet schedulers in Linux.
• Predictable resource management in Linux:
• Investigate the behavior of the Linux 2.4.x kernel (and possibly compare to the TimeSys kernel) to see how to guarantee predictable scheduling points and management of resources. The Monta Vista kernel patch may be helpful here.
• Scheduling of bottom-half handlers and/or an investigation of the behavior of softirqs and tasklets in the 2.4.x Linux kernels.
• A heap-based priority scheduler in Linux:
• Alter the current "runqueue" data structure, which is a doubly-linked list, and replace with a heap data structure.
• Implement a priority-based scheduler, or use DWCS, to take advantage of the new runqueue structure.
• Evaluate the performance of the new scheduler (in terms of latency) to support large-scale processing.
• Alternatively, implement a separate runqueue data structure for real-time processes i.e. a class-based runqueue mechanism, similar to that provided by Solaris.
• Microsecond resolution timers for Linux:
• The University of Kansas has a UTIME project, to implement microsecond timers in Linux.
• Integrate UTIME into a real-time scheduler such as DWCS and evaluate the ability to perform fine-grained scheduling.
• A QoS management framework ala QuO:
• Implement a framework for QoS management, either as a middleware layer "on top" of Linux, or by a combination of kernel extension and user-level libraries.
• My Dionisys work might be helpful here, and you could certainly port Dionisys to Linux.
• A real-time communications protocol:
• Implement a protocol that attempts to bound the delay of delivery of packets across a network (for example, like the now old XTP protocol).
• Modifications to the network protocol stack to provide per-application flow guarantees.
• e.g., apply changes/extensions to TCP to control the congestion windows and hence bandwidth allocations to different network connections.
• A feedback-control system/mechanism for flow/error/rate/congestion control:
• Implement a component-based system, like the SWiFT toolkit, or a specific instance, to evaluate the performance of an adaptive flow, error, rate or congestion control scheme.
• Active messages for Linux:
• Implement an active messaging system in Linux.
• The idea is that the first message in a flow of messages specifies the handler function to process the subsequent messages in the same flow.
• This is similar to a one-way, or asynchronous RPC-mechanism.
• Investigate different ways to implement active messaging e.g., at user-level or (partly) within the kernel, to improve performance.
• Investigate different ways to schedule/activate the message handler(s)
• Investigate different ways to avoid unnecessary copying of data i.e., from the network device to the kernel, and from the kernel to user-level where it is handled.
• An extension model for Linux:
• Taking the concepts outlined in systems such as SPIN, construct a secure/protected extension model in Linux.
• Extend the idea behind Linux kernel-loadable modules and provide a mechanism using which a user can safely link service extensions into Linux.
• Scalable web server design:
• e.g., investigate improvements to Tux or khttpd by providing kernel hooks to improve scalability.
• Linux on PDAs or embedded devices:
• Study the use of Linux on embedded devices, including PDAs, to perhaps support the construction of ad-hoc networks. This may involve issues in loss-tolerant communication, network protocol design and (adaptive) management of processing and communication resources.
• Multimedia data compression, encryption, layered encoding etc...:
• Investigate adaptative approaches for multimedia content delivery in networking environments with changing resource availability and needs.
• Filesystem enhancements for real-time or multimedia applications.
• Investigate ways to implement efficient network attached storage support for distributed applications.
• Security or capability enhancements to Linux:
• Add features that improve the security and protection provided by the OS.