CS591 W1 - Operating Systems Seminar

"Experimental Operating Systems"

Overview

There is a semester-long project, so very good programming skills are essential. The 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.

In between paper discussions, we will look at some aspects of Linux. The Linux kernel shall be used to implement class projects, where appropriate. Not all projects require delving into the Linux kernel, so it may be possible to use a different OS or to work at user-level ("on top" of an OS), depending on the nature of the proposed project.

Grading

• class participation and quality of presentations during the course. You will be responsible for picking selected papers, presenting them in class, and discussing aspects of these papers with other class members;
• class project. This includes scope and complexity of the problem, the depth of results and/or interesting contributions resulting from the project, 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 project and class presentations, but there may be quizzes, so beware!

Class Notes

• Class notes for January 18 - The Linux Kernel Part 1 [.pdf format][.ppt format]. Also includes a list of suggested class projects.
• Gabriel De Simone's class notes on the Exokernel and SPIN.
• Class notes for January 30 - The Linux Kernel Part 2 [.pdf format][.ppt format].
• Class notes for February 1 - The Linux Kernel Part 3 [.pdf format][.ppt format].
• Class notes for March 13 - Linux Process Management [.pdf format][.ppt format].

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.

QoS Management

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

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

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

Threads

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

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

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

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

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

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

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

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

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

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

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

Food for Thought?

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 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.
• DWCS packet scheduling:
• See [10, 32] 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.
• 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 an OS, 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).
• 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.