Fall 1999 Systems Qualifier

Answer 6 of 9 questions?

1.   You are designing a threads package for a bus-based shared memory multiprocessor using an invalidation-based cache coherence protocol. You can assume that the multiprocessor has an atomic read-and-increment memory operation.

You want your threads package to support both "shared" and "exclusive" modes for lock access. That is, if a group of processors want to get the lock in "shared" mode they will all get it simultaneously, so long as these requests come together and are not separated by a request for the lock in "exclusive" mode. Needless to say, there can be only one processor having the lock in exclusive mode at a time. When in "shared" mode, the lock becomes "free" when the last processor holding the lock in "shared" mode performs the unlock. The algorithm should be fair (i.e. it should follow FCFS discipline for granting lock requests). Analyze your algorithm from the point of view of number of messages on the bus that are needed (a) to request a shared lock, (b) to request an exclusive lock, (c) to release a shared lock, and (d) to release an exclusive lock.

2.   You are designing a flexible threads scheduler, but you are missing support from the OS kernel to build the type of scheduler you need. Namely, the kernel currently only allows you to schedule one new thread at a time, thereby frustrating your efforts to build co-scheduling support. (a) Define co-scheduling. (b) Define cheduler activation'. (c) Describe how you would generalize the notion of scheduler activation to support true co-scheduling, by describing the actions the kernel takes upon thread completion or blocking, and by listing the interactions of the kernel with your user-level co-scheduler.

3.   There are many problems when one wants to be 'hardnosed' about the support needed to make a system 'truly' real-time. First, define 'real-time' in this hardnosed sense. Second, for a multiprocessor operating system, describe explicitly the issues that arise when threads synchronization must be done 'real-time'. Third, indicate some solutions. Fourth, comment on the connection of real-time synchronization with threads scheduling. Assume that your threads scheduler has complete control over the hardware.

4.   First explain why SPIN's way of extending the kernel must utilize dynamic call binding, then state how events implement such bindings and how guards further refine dynamic call binding. In comparison, Exokernel uses much less mechanism to control how user-level code interacts with devices, one such mechanism being 'visible revocation'. Discuss whether such a mechanism would be useful for SPIN, too.

5.   Lamport's distributed mutual exclusion algorithm makes use of a logical clock to order requests that are made for a shared resource. It guarantees that requests are granted according to the `happens before'' order that is defined by timestamps read from the logical clock. The algorithm uses logical rather than real-time clocks because when the paper was written, it was believed that synchronized physical clocks were expensive to provide in distributed systems.

New technologies such as GPS make it possible to implement physical clocks that are closely synchronized. In particular, assume a physical clock system C that guarantees that times returned by C at two nodes at some real time never differ more than DELTA (thus, DELTA is a measure of how tightly the clocks are synchronized at different nodes). If requests A and B are made at nodes i and j at times tA and tB (these times are read from the clocks of the nodes where the requests are made), A happens before B if tB-tA > 2*DELTA. If the difference between tA and tB is less than 2*DELTA, the requests are ordered according to the unique identifiers of the nodes.

Will the distributed mutual exclusion algorithm developed by Lamport work correctly when timestamps are read from C instead of Lamport's logical clock? Explain your answer.

Is it possible to reduce the number of messages required for mutual exclusion when the synchronized clock C is used instead of Lamport clock? If your answer is yes, outline the more efficient algorithm and discuss why the synchronized clocks allow more efficient implementations. Otherwise, explain why C cannot help in reducing the message cost.

If an upper bound is provided on message delivery time and it is known that a node only needs the resource for a certain amount of time (per request), it should be possible to significantly reduce the message overhead of distributed mutual exclusion algorithms. Present the outline of an algorithm when these assumptions are made. Calculate the message cost of each access to the resource for the algorithm that you develop.

6.   Assume a distributed system in which processes on different nodes can interact with each other via a remote procedure call like facility. The execution of a call may result in calls to other nodes and it may update both volatile and persistent state stored at the node. We want to provide failure atomicity guarantees for a distributed computation that starts at a node N (N makes several remote procedure calls and the called nodes may make additional calls).

If N makes a call to node M, assume that along with the results of the call, M also returns if any of its volatile or persistent state was read or written when the call was executed. M collates such information from any nodes that it called and returns the collated information with its information and call results to N.

We have to employ a distributed commit protocol to ensure failure atomicity for the updates that are made by the distributed computation. Develop an efficient commit protocol that makes use of the information about accesses to data at various nodes which is received with the call return. Explain your answer and compare your protocol with the traditional two phase commit protocol.

7.   The xFS distributed file system makes use of cooperative caching to improve performance. When a node experiences a miss for a block of file data, the requested block may be fetched from the memory of another node rather than the server. This offers several benefits, including lower load on the server and improved performance when the network is fast. Cooperative caching attempts to use the collective caches of the nodes to improve global performance across all client nodes.

In cooperative caching, replacement of a block from a node cache is complicated because a block that has not been referenced at one node may be frequently referenced at another node. To improve performance of cooperative caching, a replaced block should be one that will not be used by any of the nodes in the near future. Develop an LRU (least recently-used) algorithm which ensures that the block to be replaced is one which has not been referenced by any node for the longest period. How would you implement such an algorithm? Are there any approximations of the global LRU algorithm developed by you which can be implemented more efficiently? Explain your answer.

If several algorithms can be used for block replacement in cooperative caching, it is necessary to develop a methodology for evaluating their effectiveness so the best one can

be chosen. Such an evaluation depends on many factors and often is quite complex. If you had to make a recommendation about what replacement algorithm to use, describe the evaluation methodology you will use to choose the best algorithm.

8.
(a) Conservative synchronization algorithms compute a quantity that is a lower bound on the time stamp of any messages a logical process can receive in the future from another logical process. Optimistic algorithms compute a quantity called Global Virtual Time. Are these quantities the same, or different? Explain.

(b) Transient messages are messages that have been sent by a process, but have not yet been received by the destination. Explain why these complicate the computation of GVT/LBTS values. Give one solution to solving this problem.

9.   A variation of the Time Warp algorithm avoids the use of anti-messages by never sending a message until it can be guaranteed the message will not later have to be cancelled (because of a rollback). (a) Develop an algorithm that implements such a mechanism. (b) Explain why such an algorithm might be better than Jefferson's original Time Warp algorithm.