CS591
Operating Systems II
Spring 2004



Prerequisites:

Overview:

Grading

Grading is based on:
In-class presentation(s) 15%
Semester project proposal, milestone* and final report 30%
Class projects 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 potential candidates for submission to conferences.

General Notes

Project Ideas

Syllabus (subject to change)

Date

Topic

Reading

Notes

January 12 Introduction
  Discussion of course outline

     
January 19


Introduction to Linux:

Linux memory management

Bovet and Cesati, Chapters 1-3
Class rescheduled due to holiday.

For those unfamiliar with kernel internals here is a primer to help you write system calls and kernel modules.




January 26
Holiday, no class  




February 2
OS Structures

[1] -- Jason

[2] -- Luis [PPT]






February 9
Threads

[4] -- Dan K.

[7] --- Vance Chen

Project proposals due




February 17
Scheduling

[15] -- Meghan Callahan

[10] -- Snyder

Tuesday is Monday schedule




February 23
Real-time Scheduling

[11] -- Snyder [PPT]

[14] -- Mike Keefe [PPT]

[pinwheel] -- Pete Swan [PPT]



March 1
Real-time Scheduling

[16,17] -- Snyder[PPT]

[vds] -- Dana Zhang







March 8 Spring Break -- No class!  




March 15
Synchronization; Extensible Systems

[13] -- Andrew

[27] -- Rouben







March 22
Extensible Systems
Professor West gave two presentations





March 29
Virtual Machines
[31] -- Jason G. [PDF ]
[40] -- Albert [PPT ]
Project milestones due
  • Draft paper including: related  work, implementation and/or analysis details, and any results if available.




April 5
Virtual machines
[39] -- Anu
[36] -- Luis

 


April 12 Communication mechanisms and abstractions
[37] -- Greg
[46] -- Dan L.





April 21
Distributed systems concepts
[55] -- Alvin [PPT]
[56] -- Sam

Wednesday is Monday schedule.
 


April 26

Systems Research is Irrelevant;

Project Presentations (15 minutes each)

Jason, Luis & Albert, Dan K., Mike K., Andrew, Rouben, and Dan L.

April 30
Project Presentations (15 minutes each)

Vance C., Meghan, Pete, Anu, Greg, Alvin, Sam
Project reports due April 30 by 5:00pm
  • Completed paper with layout similar to those read in class.
  •  Include: full results, related work, description of actual  work completed, and conclusions/future work.



 

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.

Threads

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

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

Scheduling and Synchronization

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

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

[pinwheel] Holte, Rosier, Tulchinsky, and Varvel, "The Pinwheel: A Realtime Scheduling Problem."

[PFair] Baruah, Cohen, Plaxton, and Varvel, "Proportionate Progress: A Notion of Fairness in Resource Allocation."

[VDS] West and Zhang, "Virtual Deadline Scheduling."

[power] Aydin, Melhem, Mosee, and Alvarez, "Power-Aware Scheduling for Periodic Real-Time Tasks."


QoS and Resource Management

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

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

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

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

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

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

Extensible Systems

NOTE: See also Reference [3] (above) on SPIN.

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

[29] Douglas P. Ghormley, Steven H. Rodrigues, David Petrou, Thomas E. Anderson, "SLIC: An Extensibility System for Commodity Operating Systems", in Proceedings of the USENIX Annual Technical Conference, June 1998.

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

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

Virtual Machines

[35] G. Popek and R. Goldberg, "Formal Requirements for Virtualizable Third Generation Architectures", Communications of the ACM, 17(7), July 1974, pp 413-421.

[36] Edouard Bugnion, Scott Devine, Kinshuk Govil, Mendel Rosenblum, "Disco: Running Commodity OperatingSystems on Scalable Multiprocessors ", in ACM Transactions on Computer Systems, volume 15, number 4, pp 412-447, 1997.

[37] J. Sugerman, G. Venkitachalam, and B. H. Lim, "Virtualizing I/O Devices on VMware Workstation's Hosted Virtual Machine Monitor", USENIX Annual Technical Conference, pages 1--14. USENIX Association, 2001.

[38] S. King et al., "Operating System Support for Virtual Machines", USENIX Annual Technical Conference, 2003.

[39] J. Scott Robin and Cynthia Irvine, "Analysis of the Intel Pentium's Ability to Support a Secure Virtual Machine Monitor", USENIX Security Symposium, 2000.

[40] P. Barham, B. Dragovic, K. Fraser, S. Hand, T. Harris, A. Ho, R. Neugebauer, I. Pratt and A. Warfield, "Xen and the Art of Virtualization", Symposium of Operating System Principles, 2003.

Communication Mechanisms and Abstractions

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

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

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

[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

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

[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 Casual Relationshops in Distributed Computation: In Search of the Holy Grail", Distributed Computing, 1994.


Linux and Related Projects

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

[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

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.

Scheduling

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

Threads

Memory Management

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


Last updated: January 29th by Rich West.