UNIVERSITY OF WISCONSIN-MADISON Computer Sciences Department
Operating Systems Qualifying Exam Fall 2005

Instructions: There are seven questions on this exam; answer any six of the following seven questions. This exam has three (3) pages.

Question 1. Page Replacement:

  1. Describe the Working Set model of program behavior. How is the working set of a process defined? What are the main features of any memory management algorithm inspired by the working set model?
  2. Describe the Working Set (WS) algorithm for memory management. Why is the WS algorithm, as strictly defined, impractical to implement in a real system? What sort of approximations or compromises are commonly used to create "working-set-like" algorithms?
  3. Any useful memory allocation algorithm must have a component that exercises "load control": controlling the number of active processes. Why? What is the WS policy on load control?
  4. The WS-CLOCK algorithm of Carr and Hennessy combines features of the CLOCK (also called "Second Chance") algorithm with features of WS. One difference between WS and WS-CLOCK is that WS-CLOCK only keeps track of the resident portion of the working set. How does this fact interfere with load control? What does WS-CLOCK do to mitigate this problem?

Question 2. Remote Execution Security:

In the Condor system, a user can submit a program to run remotely on another computer. The program is linked with a special Condor version of the C library; when it runs, all system calls (such as open(), read() or write()) it makes are sent back from the remote (execution) machine to the submitter's home (desktop) machine and executed by a daemon process there.
  1. We want to prevent the submitter's program from abusing the execution machine. Describe three things that a program might try to do that would violate the security of the execution machine, and describe a strategy for preventing this abuse.
  2. We also want to prevent the owner of the execution machine (who has root/superuser priviledges) from using a submitted program as a tool for gaining inappropriate access to the files or resources on the submitter's desktop machine. Describe one way in which the execution machine's owner could make such an access, and describe how you might prevent or limit such abuses.

Question 3. System Support for Multi-Threaded Applications:

  1. Imagine that you have a multi-threaded application to port to a new system that has both user-level and kernel-supported threads. What are the advantages and disadvantages of using user-level versus kernel threads? Would knowing any of the characteristics of your multi-threaded application help in deciding between the two?
  2. It turns out that you don't have to choose between a user-level and kernel-supported threads, because this OS also has support for scheduler activations. But, unfortunately, there isn't yet a traditional thread system implemented on top of scheduler activations -- this is your job! First, what events must your thread system communicate with the kernel? For each possible event, give a short example of how the event could occur. Second, what events sent by the kernel must your thread system be able to handle? For each event, briefly describe how your thread system should react.

Question 4. Disk Access:

Disk seek and rotation costs increasingly dominate all disk access time. The time to position the disk head is often orders of magnitude more than any time spent transferring data blocks.

However, in some modern disks, the platter size has gotten to be quite small, leading to smaller seek costs but the same rotational delay. Hence, rotational delay is increasingly the dominant component of positioning.

In this question, you will discuss how different parts of the storage subsystem should change in response to the increasingly dominant cost of rotation.

  1. Discuss how this trend affects file system layout.
  2. Discuss how this trend affects disk scheduling.

Question 5. AFS:

The AFS distributed file system has very well defined consistency semantics. In each of the following scenarios, describe what the resulting state is at the file server. That is, if a different client was then looking through the directory tree, what would they see? Why?
  1. A user creates a new file foo in a directory /bar, and opens the file for writing.
  2. A user creates a new file foo in a directory /bar, opens the file for writing, and writes two blocks to the file.
  3. A user creates a new file foo in a directory /bar, opens the file for writing, writes two blocks to the file, and closes the file.
  4. A user creates a new file foo in a directory /bar, opens the file for writing, writes two blocks to the file, closes the file, and then deletes the file.

Question 6. Distributed Consistency:

Databases usually require that all sites are updated consistently; that is, queries are atomic and appear as if they were globally serialized. The Grapevine system introduced a new model of consistency for naming and location data.
  1. Describe the consistency model used in Grapevine.
  2. What was the motivation for this new model? Describe its advantages and disadvantages.
  3. How does this consistency model compare to that developed by Chandy and Lamport in their work on distributed snapshots?

Question 7. Virtual Machines:

The original virtual machines from the 1970's were powerful and useful, but could cause substantial degradation of the performance of the operating systems running under the the virtual machine. Describe three causes of this performance degradation and how each of these problems was addressed by the Disco system.