CS591 W1 - Operating Systems Seminar

"Experimental Operating Systems"

Instructor: R. West
Instructor's office: MCS 289
Days/Time: TR 12:30-2:00pm
Location: MCS 135
Prerequisites: CS552, STRONG PROGRAMMING SKILLS! (if in doubt, please see me).


This course is a research-oriented, operating systems seminar. Papers relating to advanced operating system concepts are discussed. Class members are required to present some of the papers in this course.

There is a semester-long project, so very good programming skills are essential. The project involves:

The project will be based around one, or more, of the papers that are discussed in class and will involve some advanced systems concept(s).

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 is based on:
In-class paper presentation(s) 15%
Project proposal, milestone* and final report 30%
Class project and end of semester presentation / demonstration 50%
Class participation 5%

* 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

Class Notes

Syllabus (subject to change)






January 16 Introduction (discussion of course outline)     Instructor
January 18 The Linux kernel, Part 1   Writing system calls.
Kernel-loadable modules.
January 23 OS Structures [1], [2]   Jason Gloudon (paper 1)
January 25 OS Structures [2], [3]   Gabriel de Simone (papers 2  & 3)
January 30 The Linux kernel, Part 2   Debugging the kernel.
Tracking time in the kernel.
Task queues, timer queues, top/bottom half handlers.
February 1 The Linux kernel, Part 3   Signals and Interrupts.
Project Proposals due.
February 6 Scheduling [4]-[10] Linux process scheduling.
SMP support.
Ted Bach (papers 6 & 9)
February 8 Scheduling [4]-[10] Discussion of differences between thread and packet scheduling. Dhiman Barman (paper 8)
February 13 Scheduling [4]-[10], [32]   Instructor (paper 10)
February 15 Linux QoS Management [11]-[13] Discussion of traffic control, differentiated service support, filters, classes and queues in Linux.  Dhiman Barman (see notes and ref. 11)
February 20 - Monday Schedule -   - No Class -  
February 22 QoS Management [11]-[13]   Huan Luo (paper 13)
February 27 QoS Management [11]-[13]   Instructor
March 1 Control-Based Service Management [14]-[15]   Marwan Fayed (papers 14 & 15)
March 6 - Spring Recess -   - No Class -  
March 8 - Spring Recess -   - No Class -  
March 13 Threads [16]-[18] Linux thread/process model Instructor
March 15 Threads [16]-[18]   Yuriy Vaysman (papers 16 & 17)
March 20 Threads [16]-[18]   Sumit Mehrotra (paper 18)
March 22 Memory Management   Discussion of Linux memory management, virtual memory, address spaces. Instructor
March 27 Virtual Memory [19] Project milestone. Yu Han (paper 19)
March 29 Distributed System Concepts and Shared Memory [20]-[22] Distributed shared memory. Stanislav Rost (paper 21)
April 3 Distributed System Concepts and Shared Memory [20]-[22] Causal memory, Lazy release consistency etc. Yangui Tao (paper 22)
April 5 Communication Mechanisms [23]-[24] Remote procedure calls, upcalls. Stanislav Rost and Gabriele de Simone (issues relating to upcalls)
April 10 Communication Mechanisms [23]-[24] (Optimistic) Active messages. Kin Moon Leung (paper 24)
April 12 Linux Projects: QoSockets [31]   Kin Moon Leung, Huan Luo and Jason Gloudon (design and issues relating to QoS-based sockets)
April 17 High Performance Communications [25]-[27]   Nick Marcantonio (paper 25)
April 19 High Performance Communications [25]-[27]   Greg Paull (paper 26)
April 24 Linux Projects: RTLinux [28] These topics are subject to change. May cover papers not discussed from previous topics.  
April 26 What has become of OS research? [33] A discourse on the state of OS research.  
May 1 Project Presentations   Projects due.  

Reading List

Books and Documentation Sources

OS Structures

[1] J. Liedtke, ``On Micro-Kernel Construction'', Proceedings of the 15th ACM Symposium on Operating System Principles, ACM, December 1995.

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


[4] Thomas E. Anderson, Brian N. Bershad, Edward D. Lazowska and Henry M. Levy, "Scheduler Activations: Effective Kernel Support for the User-Level Management of Parallelism", 13 ACM Symposium on Operating System Principles, Oct. 1991, ACM SIGOPS Notices, 25, 5, December 1991.

[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

[11] http://qos.ittc.ukans.edu/ (see specifically, http://qos.ittc.ukans.edu/howto/index.html).

[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

[14] Ashvin Goel, David Steere, Calton Pu and Jonathan Walpole, "SWiFT: A Feedback Control and Dynamic Reconfiguration Toolkit", OGI CSE Technical Report 98-009, poster presented at 2nd Usenix Windows NT Symposium, September 1998. (See also the Quasar project at OGI, http://www.cse.ogi.edu/sysl/, for a detailed list of related papers).

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


[16] B. D. Marsh, M. L. Scott, T. J. LeBlanc, and E. P. Markatos, "First-class User-level Threads", Proceedings of the Thirteenth Symposium on Operating System Principles (SOSP), October 1991.

[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

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

Distributed System Concepts and Shared Memory

[20] L. Lamport, ``Time, Clocks, and the Ordering of Events in a Distributed System", Communications of the ACM, 21, 7, pgs. 558-565, July 1978.

[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

[23] A. Birrell and B. Nelson, "Implementing Remote Procedure Calls", ACM Transactions on Computer Systems, 2, 1, pgs. 39-59, February 1984

[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

[25] A. Montz, D. Mosberger, S.W. O'Malley, L.L. Peterson, T.A. Proebsting and J.H. Hartman, "Scout: A Communications-Oriented Operating System", The University of Arizona, Department of Computer Science, TR 94-20, June 1994.

[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

[28] RTLinux: http://www.rtlinux.org/

[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?

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

Additional Readings

Distributed Filesystems

As this is a seminar course and not a conventional advanced operating systems course, we might not cover filesystems issues. However, filesystems is a very important topic, so I have included a couple of references that are useful. This is by no means an extensive list. If anybody is interested in knowing more, please consult me.


This is a network-oriented paper but it covers some interesting algorithms, particularly relevant for packet scheduling.


QoS Management

The following papers/links provide a more network-oriented view of QoS management.

Communication Mechanisms

Linux-Related Papers

Other Topics for Future Reference

Suggested Projects

NOTE: The following projects are merely suggestions. You are free to chose other projects as long as they have sufficient scope and relevance to the course. Many of the following projects vary substantially in scope and complexity. Exactly how much you achieve with any project will depend on the difficulty of the project and the number of people in your group, if you decide not to work alone. You should try to define what you hope to achieve with your project in the current semester. Projects that may extend beyond the end of the course, thereby forming the basis of a research project, are encouraged.
Last updated: Thursday, March 15, 2001 by Rich West.