UNIVERSITY OF WISCONSIN-MADISON
Computer Sciences Department
Operating Systems Depth Exam Fall 1998

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

Question 1. Swap Space:

1A.
What is "swap space" (or backing store)?
1B.
Swap space can be allocated as a special region (partition) on the disk or it could be a special file. Describe the advantages and disadvantages of these two approaches. Be sure to discuss issues related to performance, functionality, and cleanliness of design.

Question 2. Checkpointing:

Consider a checkpoint facility in an operating system. Such a facility would save the state of a running program so that it could continue execution on a different host from the one on which it was previously running. Assume that this facility is built into the operating system kernel.
2A.
Given a conventional UNIX system (Solaris, Linux, etc.), describe what process state needs to be saved to checkpoint a running process?
2B.
Ideally, the stopped process should not be able to know that it has been checkpointed and restarted. Describe how process ID's (pids) and clocks can make transparent checkpointing more difficult. Can these problems be fixed?
2C.
Many programs use sockets and pipes for communication. What problems arise when you want to checkpoint and restart such programs?

Question 3. Authenication:

The Kerberos authentication service produces tickets that a client can use to authenticate itself to a service. Each administrative domain (such as the Computer Sciences Department) runs its own Kerberos service to provide authentication to its services.

Assume that two domains wanted to cooperate, so that each domain could give access (i.e., tickets) to limited services in the other domain.

3A.
How would the two domains initially authenticate each other? Identify which services would be available to the other domain.
3B.
Under this cooperating-domain scenario, describe how client c in domain 1 can request a ticket to a service s in domain 2. Consider whether c should contact its local ticket-granting service or directly contact the TGS in domain 2.

Question 4. Polling vs. Signals:

Control programs need to test conditions in the outside world that occur at arbitrary times, usually without waiting for one to occur. For example, a network server program must check for new connections while continuing to service existing clients, and a microprocessor-based motor control must check for control signals (e.g., stop!) while monitoring and adjusting the speed of a motor.
4A.
Discuss the relative merits of polling for events vs. asynchronous notification that events have occurred. Consider performance issues and the impact on overall program structure.
4B.
A thread schduler may need to schedule threads that may be polling and/or waiting for asynchronous events (such as interrupts, signals or I/O events). How does this complicate the responsibility of the scheduler to make efficient use of system resources? How can the threads help the scheduler do a better job?

Question 5. File Systems:

5A.
What are the problems of Berkeley Fast File System that motivated the Log-Structured File System?
5B.
Outline the design of the Log-Structured File System.
5C.
Unfortunately, Log-Structured File System has not been very successful commercially. Rather, some commercial file systems log metadata changes only, and use the traditional Fast File System algorithms to manage data blocks. Explain the advantages and disadvantages of this metadata-logging approach compared with the Log-Structured File System.

Question 6. Networking:

6A.
The protocol used by the World Wide Web, HTTP, is built on top of TCP. Everytime a browser contacts a Web server, it establishes a TCP connection, sends the request, waits for the response, then closes the connection. Describe the performance problems of building HTTP on top of TCP.
6B.
To ensure cache consistency, most Web browsers poll the Web server every time a cached copy of a page is visited. Assume that a Web page U never changes, and U's size is 10KB. If U is cached at a browser that uses the polling approach for cache consistency, what percentage of network packets to the Web server would the Web cache reduce? State any assumptions you need to make to answer this question.
6C.
Suggest two approaches other than polling for Web cache consistency. You can borrow ideas from distributed file system research. Discuss the pros and cons of the two approaches versus the polling approach.

Question 7. Deadlock:

7A.
Define the term "deadlock". There are four conditions that must hold before deadlock is possible. Name them.
7B.
Outline an algorithm that detects whether there is a deadlock. The algorithm should be able to cope with multiple resource classes, each of which has some limited number of units available.
7C.
When should the algorithm be invoked? The answer to this question depends on the characteristics of the system to which it is to be applied, such as the rate of resource requests, the granularity of resources, and the expected rate of deadlock. List three possible choices and discuss the criteria you would use to choose among them.