UNIVERSITY OF WISCONSIN-MADISON
Computer Sciences Department
Operating Systems Depth Exam Spring 1999

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

Question 1. Deadlock:

One strategy for combating deadlock is detection and recovery.
1A
A resource allocator accepts three kinds of request from other processes: 
    allocate(resource_class, number_of_units)
    release(resource_class, number_of_units)
    check_for_deadlock()
Outline an algorithm for implementing these functions.
 
1B
Suppose there are several resource allocators, each responsible for some set of resource classes. A client process sends each request to the appropriate allocator. (Assume there is some mechanism for clients to figure out the appropriate allocator for each request.) A check_for_deadlock request can be sent to any allocator. Allocators may exchange messages with each other to detect deadlock. Outline a deadlock detection algorithm in this environment. You may ignore the possibility of process or communications failures, but assume that communication between allocators is relatively expensive.

Question 2. Capabilities:

Jones and Wulf introduced the notion of amplification: When a capability is passed as an argument to a procedure, its set of rights may be increased so that that procedure can do things with the capability that the caller could not.
2A
Give examples of the usefulness of amplification. In particular, describe how it can be used to implement protected subsystems.
 
2B
To what extent can the UNIX "Set UID" feature be used to provide the functionality of amplification? In what ways does it fall short?

Question 3. Disk Organization:

In the "classic" Unix file system, the contents of a file are stored in a set of small blocks allocated more or less randomly from a free list.
3A
The Berkeley "fast file system" changed the representation of files to improve the performance of a single process sequentially reading or writing a single large file. Briefly outline those changes that are specifically related to improving performance of this kind of access.
 
3B
Suppose you have to design a new file system for a uniprogramming environment to support a single dedicated application. >From time to time this application creates or destroys files, but most of the time, it is sequentially reading one file at a time (with the choice of which file to read a uniform random variable). The application only runs 9 to 5 on weekdays. Design an appropriate file organization for this system.

Question 4. Password Security:

It has long been known that, for remote login, sending passwords in clear text over a network is risky.
4A
Describe the security threat that a user on a remote system may encounter when remotely logging in to their home system (assuming that they are using conventional account name/password authentication). What points in path from user to home system are vulnerable this threat?
 
4B
Assume that each traveling user has a device (called a "smart card") with the following characteristics: Design a protocol that you can use during the login session so that the remote users can authenticate themselves to their home systems without be subject to the threats in part 1 of this question. Be sure to describe the steps taken by the user, the steps taken by the home system, and the functionality of the smart card.

Question 5. The Web and File servers:

In many ways, a Web server and an Andrew file server are similar. Compare the functionality of each of these systems in the following areas:

Question 6. Thread Scheduling

6A
List two main differences between user-level threads and processes.
 
6B
Typical implementation of a thread package works as follows. The package provides user-level thread abstractions to the application, allowing cheap creation and destruction of threads. The package the kernel for a number of light-weight processes (also known as kernel-level threads), typically each light-weight process corresponds to one processor in the system. The threads package performs thread scheduling by binding user-level threads to light-weight processes. Explain why such a scheme is unsatisfactory from a user application's point of view, particular those applications that wish to precisely control the schedule of threads to processors.
 
6C
Suggest some enhancements to kernel mechanisms (including new system calls or upcalls) that correct this problem.

Question 7. Distributed Shared Virtual Memory

Distributed shared memory (DSM) gives processes an illusion of a shared virtual address space, even though they may be on different computers connected by a network. This question concerns a page-based DSM system like the Ivy system described in Memory Coherence in Shared Virtual Memory Systems by Li and Hudak.
7A
Explain how to implement DSM using conventional paging hardware. What changes need to be made to the page fault handling code in the virtual memory system? Concisely described the related data structures and extra processing that needs to be done to service a page fault.
 
7B
What is false sharing and why is it bad for page-based DSM?
 
7C
Suggest one or two mechanisms that can reduce the false-sharing problem.