CPS 210
Operating Systems

Threads and concurrency

The classical OS view from Multics to Unix

The goal is to understand the basics of protection and the segmented memory model, dynamic linking, segment naming and binding, and the relationship between segments and permanent storage. The Unix effort was launched by Multics rejectionists:

Servers

  • Sandstorm/SEDA, papers by Matt Welsh et al (Berkeley): Read the SOSP 2001 paper [Welsh01] and take a look at the HotOS 2001 paper.
  • The Flash Web server, papers by Vivek Pai et al (Rice, Princeton): just scan to get an idea what it's all about and how it relates to SEDA (E-track).

Discussion questions for SEDA

What is "resource virtualization" and why do the authors claim that it is bad? How do the experiments support this point? Why was resource virtualization considered good in the past, and what do the authors claim has changed to make it less useful now?

What is the basis for the implicit claim that applications should have "an opportunity to participate in system-wide resource management decisions"? How does SEDA reflect this philosophy?

Compare/contrast the SEDA staged-event model to Unix pipes. How do the schemes for allocating resources (e.g., CPU and memory) to the pipe stages differ in these approaches? What does SEDA offer that is new?

How does "load conditioning" in SEDA help to improve performance? How does it help to improve fairness as measured by the Jain index? How is the resulting system better or worse from the point of view of a user (client)?

Kernel structure: microkernels to exokernels and beyond

  • Operating system support for database management, by Michael Stonebraker. A scan of the citation list on citeseer shows that this paper has been widely cited to justify alternative OS structures. (No reading, but scan the list of citations.)
  • SPIN, built by Brian Bershad, Stefan Savage, Przemyslaw Pardyak, Emin Gun Sirer, David Becker, Marc Fiuczynski (U. Washington). Figure out what it's about by reading sections 1-4 of the SOSP-15 paper [Bershad95].
  • Exokernel, built by Dawson Engler, Frans Kaashoek et al (MIT). Read sections 1-4 of the first SOSP paper ([Engler95], SOSP-15, 1995), and sections 1-3 and sections 7-10 of the second one (([Engler97], SOSP-16, 1997). These are available in postscript from Dawson's home page at Stanford.
  • Tanenbaum Ch 12 (Tc12) also discusses some of these structural issues.

Discussion questions for OS structure

Exokernel and SPIN share similar goals, but their approaches differ radically. What are the strengths and limitations of each approach? What forms of extensibility do they support well? (E.g., look at the Cheetah example for Exokernel, and the protocol forwarding and video server examples for SPIN.) How does this power interact/interfere with other goals of the OS?

Exokernel and SPIN were reactions to the microkernel approach of Mach, V, and other earlier systems, as discussed in the related work sections of the papers listed above. What are the strengths and limitations of the microkernel structure?

All three structures reflect a philosophy that flexibility dominates ease of application programming as a goal of kernel interface design. The architects of each approach expect that other system components provide the primary APIs (Application Programming Interfaces) for their systems. Compare/contrast their views about where the important APIs are in their proposed structures. How might these choices affect the future evolution of the systems or affect their robustness as they evolve?

What does the second (1997) Exokernel paper teach us about the Exokernel structure that was not known in 1995? Does their experience add weight to their original vision, or does it detract from it?

What might Matt Welsh and the other SEDA architects say about these alternatives today?

RAID and network storage

  • [Hitz94] File System Design for an NFS File Server Appliance, by Dave Hitz, James Lau, and Michael Malcolm, Network Appliance, USENIX Technical Conference, 1994.
  • Background reading: material on RAID, Unix file system (e.g., FFS), LFS, and NFS from Tanenbaum (see reading list on calendar).
  • [Patterson02] SnapMirror: File System Based Asynchronous Mirroring for Disaster Recovery (pdf), by Hugo Patterson, Stephen Manley, Mike Federwisch, Dave Hitz, Steve Kleiman, Shane Owara, in USENIX Conference on File and Storage Technologies, January 2002.

Resource management and scheduling

Virtual Machines

  • [Waldspurger02] Memory Resource Management in VMWare ESX Server, by Carl A. Waldspurger. In Proceedings of Operating System Design and Implementation (OSDI), December 2002. Get it from Carl's research page.
  • [Bugnion97] Disco: Running Commodity Operating Systems on Scalable Multiprocessors, by Edouard Bugnion, Scott Devine, and Mendel Rosenblum. In Proceedings of The 16th ACM Symposium on Operating Systems Principles, October 1997 [ps, html]. More information here.
  • [Chen01] When Virtual is Better than Real, by Peter Chen and Brian Noble (U. Michigan), Proceedings of the 8th Workshop on Hot Topics in Operating Systems (HotOS-VIII), 2001. [ps]

Energy-aware operating systems

  • [Flinn99] Energy-aware adaptation for mobile applications, by Jason Flinn and Satya. In SOSP, 1999. [pdf]
  • [Zeng01] ECOSystem: Managing energy as a first class OS resource, by H. Zeng, X. Fan, C. Ellis, A. Lebeck, and A. Vahdat. [pdf]

Metrics

OS robustness and evolution

  • [Chou01] An Empirical Study of Operating Systems Errors (postscript), by Andy Chou, Junfeng Yang, Benjamin Chelf, Seth Hallem, and Dawson Engler (Stanford), SOSP 2001.
  • [Gribble01] Robustness in Complex Systems (gzip postscript, pdf), by Steven D. Gribble (U. Washington), Proceedings of the 8th Workshop on Hot Topics in Operating Systems (HotOS-VIII).

Additional readings TBD