Operating Systems Depth Exam

	UNIVERSITY OF WISCONSIN-MADISON Computer Sciences Department
Operating Systems Depth Exam		Fall 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. Network File Systems:

Consider a client computer's access to a file located on a file server. You can answer this question in the context of any network file system and OS with which you are familiar.

Some assumptions: (1) the size of the read is for a "block", where block is the natural transfer and allocation unit of the file system, (2) the server and client currently have nothing in their caches.

A.: For a a read operation by a process on the client computer, trace the flow of control from the client process to the server file system. You should list progress though each significant step, including user and server processes, and major kernel component, including file system, disk driver, and networking. Be sure to indicate each time the data block is copied from the time it leaves the server's disk until it is available in the client's address space.
B.: Caching can improve client response time and reduce system load. Describe places where caching can be used in a network file system, and explain what benefit can be obtained for each of these places.

Question 2. Virtual Memory:

A.: What is an inverted page table? Describe its function?
B.: What are the similarities and differences between an inverted page table and a Translation Lookaside Buffer (TLB)?
C.: Why is an inverted page table more suitable for implementing WSclock than it is for implementing Working Set?

Question 3. Java and Monitors:

Java's monitors differ from the classic Hoare monitors in that they allow only one (implicitly declared) condition variable per locked region (monitor).

A.: Does this difference effect your implementation of a shared queue (bounded buffer) monitor class? Explain.
B.: Does this difference effect your implementation of an N-readers/1-writer monitor class? Explain

For the two cases above, you can provide code or pseudo code in whatever language you wish. If you use Java, just assume that you have a built-in "condition" class type for condition variables.

Question 4. Disconnected Computing and Time:

Assume that you have a network file system, such as Coda, that allows disconnect operation.

A.: How are timestamps used when reconnecting the client after disconnected operation?
B.: How does this scheme depend on the clocks of the client and server or the clocks of multiple clients that share the same file being synchronized? Explain.
C.: Assume the clocks differ by 1 second. Will this cause any problems in practice? Assume that the clocks differ by 1 hour. Will this cause any problems in practice?

Question 5. Process Creation:

UNIX creates new processes with the fork() operation, and starts them executing a particular executable file with the exec operation. Another type of process creation operation supported by other operating systems is CreateProcess(filename). This operation creates a new process that immediately begins executing the program found in file filename.

A.: Compare this functionality to that provided by the UNIX fork.
B.: Describe the advantages and disadvantages of each design. Consider how you would use these operations to implement all the features of a shell, including redirection and pipes.

Question 6. Distributed Barriers

Barriers are a synchronization mechanism that requires all processes in a program to reach a given point before proceeding. Each process calls barrier(b) and each process blocks until all processes have made the barrier call; when the last process makes the barrier call, all processes are unblocked.

Assume that you are writing distributed programs that run on a network of UNIX workstations. These workstations support standard stream (TCP/IP) and datagram (UDP) message communications.

A.: How would you implement barrier synchronization in this environment? Assume that you want to make the operations as fast as possible (minimal delay).
B.: Is load on the network (assume a typical Ethernet) likely to be a problem in your solution? If yes, describe in what cases this will occur. If no, explain why not.

Question 7. Disk Allocation:

Consider the problem of allocating contiguous, variable-sized chunks of physical memory.

A.: Briefly describe first-fit, best-fit, and worst-fit policies and compare their expected performance.
B.: A variation of first-fit, sometimes called "progressive first-fit" or "next fit," starts each search of the free list from the point where the last search left off, rather the beginning. In what way would you expect this version of the algorithm to perform better?

For parts C and D, the problem is similar - to allocate and release contiguous regions in a large array of bytes, but in this case the "array of bytes" is a file on disk. This problem arises, for example, in allocating and deleting records in a database file.

C.: How do the policies of parts A and B compare in this setting?
D.: An alternative to searching for free space in the file is simply to append to the end of the file. What are the good and bad points of this "append-only" algorithm? Can you suggest an algorithm that combines the advantages of append-only with the advantages of the other algorithms?