Homework 11

22C:116, Fall 1995

Due Friday Nov. 10, 1995, in class

1. Background: Atomic transactions are very similar to critical sections, but a careful look at the definitions given in section 11.4.2 of the text will reveal that there are two significant differences:

   Part A: In what way the statement that some part of a program must be performed as an atomic transaction more demanding than the statement that that part of the program must be performed as a critical section?

   Part B: Why is it sometimes possible to overlap the execution of two atomic transactions, violating the notion of mutual exclusion?

2. Background: On an interactive computer system, users may generally abort their current interactive application at any moment. For example, under UNIX, a user may hit control-C to kill the current application. Consider such a system, with the following added features, shared memory regions, and mutual exclusion locks. The locks supported by this hypothetical system have the following semantics:

   The type lock is a data structure that may be declared in any shared memory region. Effectively, a lock is a binary semaphore.

   The operation claim_lock(x) blocks the caller until no other process has claimed the lock x. Normally, this operation returns true, but in the event of an abnormal release, the return will be false.

   The operation release_lock(x) releases the lock x, but only if the caller had previously claimed it (if not, it is an error). This is the normal way that locks are released.

   If a process is aborted, any locks it has claimed will be released by the abort operation. The next process to claim a lock released in this way will receive an indication, in the value returned by claim_lock, that the lock was abnormally released.

   The following code illustrates the use of these primitives to atomically exchange the contents of two variables, each protected by its own lock.

   (void) claim_lock( a.lock );
   (void) claim_lock( b.lock );
   temp = a.data;
   a.data = b.data;
   b.data = temp;
   release_lock( b.lock );
   release_lock( a.lock );
   

   The problem: The above code does not take into account the possibility of a process being aborted while in this critical section. Modify the code (and, if needed, the data structures implied by the code), so that the result has atomic semantics. You may not be able to avoid exposing the user to knowledge that a process was aborted while in the critical section, but you should provide a clearly defined way to determine what the correct values of a and b are.

3. Background: Detecting deadlocks in a distributed system is never done by building a graph model of the current state of that system, and then searching for cycles in the graph. Rather, it is done by sending messages between processes that traverse the actual process graph.

   The problem, part A: What deadlock model applies to the problem of detecting deadlocked atomic transactions using two-phase locking protocols?

   The problem, part B: Describe a protocol (a distributed algorithm) for detecting the fact that a set of atomic transactions are deadlocked. Your description should clearly state what condition causes a process to initiate this protocol.