Operating Systems Depth Exam

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

Instructions: There are seven questions on this exam; answer any six of the following seven questions.

1. Networking

Consider the following file transfer application that uses a TCP-like protocol to reliably service a client's request. The protocol has the following characteristics:

The protocol runs across a network that can carry 1000 byte packets (including headers), a 20ms one-way latency and 50Kbps bandwidth in each direction.
Each transmitted packet consists of a total of 50 bytes of packet header plus the data payload.
The client initiates a three-way handshake, piggybacking a 100 byte request on the third packet of the handshake.
After receiving a request, a server responds by sending all data as fast as possible ie. without window flow control.
The client sends one cumulative acknowledgment for every 2 two data packets received.
After the last data packet in the file has been acknowledged, the server sends a FIN packet which the client must acknowledge before the connection is closed.

A.: Draw a time line diagram of all packets transferred between a client and a server in a transfer of a 5700 byte file (including connection set-up and tear down).
B.: How many packets and how much network traffic (in bytes) does the transfer generate?
C.: How much time elapses between the time the client initiates the three-way handshake and the time the server receives the last bytes of the acknowledged FIN?

2. Scheduling

A round-robin scheduler that must handle both I/O bound and CPU-bound processes in a fair and efficient fashion. One problem is that I/O bound processes tend to relinquish the CPU before their quantum expires, but CPU-bound processes do the opposite. As a result, I/O-bound processes would tend to receive a smaller share of the CPU time. If the quantum is made small to mitigate this effect, CPU-bound jobs suffer because their throughput will be low due to increased context switching overhead. The UNIX BSD scheduler solves the problem by maintaining a FIFO ready queue for each priority level and grants the CPU to the process at the head of the highest priority queue. The priority level of a process in this scheme is not fixed, but manipulated by the scheduler as the process switches between scheduling states. Furthermore, the size of the quantum depends on the priority of the executing process.

A.: Draw a state diagram to show the different states that a process can be in, labeling the arcs with the events that cause a state transition.
B.: When should a process' priority be heightened? Why?
C.: When should a process' priority be lowered? Why?
D.: Should the quantum interval relate to priority level?
E.: Can processes with low or lower priority starve under heavy load?
F.: Describe the load under which this algorithm gives maximal CPU utilization.

3. File System

You have been asked to modify/optimize the Berkeley Fast File System(FFS) for a specific workload as follows:

There is a flat name-space for files; that is, there are no directories.
Users tend to access files around the same time that have file names that are alphabetically close to each other.
Most files are small but most of the data (and most of the data transfers) are in large files.

You should also target the following storage technology:

Multi-zone disks (a zone is a region with a constant density of sectors/track; zones further from the disk spindle have a higher density).
Disks where it is very expensive to activate different disk heads; in fact, switching between disk heads is much more costly than seek time or rotational delay.

Since you are starting with a working code base, we recommend that you use as many abstractions already defined in FFS as possible.

A.: Thoroughly explain how both data blocks and i-nodes are allocated to maintain the locality of the workload. Specifically, you should focus on the global heuristics for allocating blocks of existing files and of new files. Be sure to explain why your layout will optimize the performance of the disk.
B.: What is the problem with using a disk scheduling algorithm such as SCAN in this environment? How should it be changed?

4. Capabilities

This question investigates some of the requirements and challenges of using capabilities as a protection mechanism.

A.: One key requirement of a capability is that it is unable to be forged by user processes. Two common approaches that require hardware support for maintaining the integrity of capabilities are tagging and partitioning. First, give a brief overview of each approach. Second, discuss the relative advantages and disadvantages of each.
B.: One challenge in a capability-based system is ensuring that a subroutine cannot keep a capability after it returns control back to its caller. Discuss one approach for ensuring this property.

5. Kernel Calls:

When a user process calls the kernel, it appears to the code in the user process like it is making a simple function call. But the path, from a call such as read() to the functions in the kernel that performs the file system read, is much more complex than a simple function call.

A.: Describe in detail the kernel call path from the user process to the appropriate function in the kernel. Be sure to describe the role of the system call library, interrupt handling, and other operating system and processor features that complete the path.
B.: Why is such a complex mechanism needed? Why isn't a simple function call sufficient?

6. Fast Networks and File Systems:

Consider a file, system such as AFS, that has substantial caching mechanisms. Assume that we have universally available high-speed networking (end-to-end performance in the range of 10 Gb/second).

A.: Will this new network environment lead to the elimination of client caching? Why or why not. Be sure to describe each way in that caching benefits current network file systems and how each of these benefits would be effected by the faster network.
B.: Will this new network environment lead to the elimination of server replication of files or file system partitions? Why or why not. Be sure to describe each way in that server replication benefits current network file systems and how each of these benefits would be effected by the faster network.

7. Remote Procedure Calls

This question explores the ins and outs of remote procedure calls, and how they are used to build distributed services.

A.: One key component of any RPC system is stub generation. Describe the process of stub generation, and how it eases the process of distributed application development. What types of problems are avoided through the automation of this process?
B.: Naming is an important ingredient in any RPC system. First, describe where the issue of naming arises (i.e., discuss when clients and servers would utilize a name service). Then, describe how a particular RPC system utilizes a naming service (the RPC system as described by Birrel and Nelson, Sun RPC, or Java RMI are all suitable). For this last part of the question, a rough outline of the important steps and interactions is all that is needed.
C.: Finally, one key question that arises in building a distributed service is how to partition work across the client and the server. First, describe why is partitioning important. Then, present and discuss a general set of guidelines which one could use to partition a service across a client and server.

ÿý{ïM4÷nyÿ]wß8óžÿ×M7ï¾øë