Homework 11 Solutions

22C:116, Fall 1995

Douglas W. Jones
  1. 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?

    The Answer: It demands that no failure, at any point during the operation, reveal any internal details of the transaction. The consequences of failure must be either that the transaction appears to have never started or that it appears to have executed to completion.

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

    The Answer: So long as the outcome of the overlapped transactions are identical to the outcomes of executing the transactions in strict sequence, the overlap of their execution is permissable. This does not imply that any particular implementation of the transactions will actually allow such overlap, but only that such an implementation would be considered correct were it produced.

  2. The problem: Given locks that provide an indication of abnormal critical section exit, write code to atomically exchange two variables, each with lock and data fields.

    An incorrect solution

    if not claim_lock( a.lock )
        -- a may have been corrupted
        if a.status = update
            a.data = a.backup;
            a.status = done;
        endif
    endif
    if not claim_lock( b.lock )
        -- b may have been corrupted
        if b.status = update
            b.data = b.backup;
            b.status = done;
        endif
    endif
    
    a.backup = a.data;  b.backup = b.data;
    
    a.status = update;  b.status = update;
    
    temp = a.data;
    a.data = b.data;
    a.data = b.data;
    b.data = temp;
    
    a.status = done;  b.status = done;
    
    release_lock( b.lock );
    release_lock( a.lock );
    
    This is typical of the solutions people implemented with such error-reporting locks. The code does reduce the vulnerability of the system to failures, but it is incorrect because a failure between the two lines that set the status indicators to done will lead to non-atomic semantics.

    In fact, no solution that tries to give atomicity to the two variables independently will work. Thus, using an atomic pointer assignment, for example, to update each of the two variables will still result in non-atomic semantics unless there is a single global coordinator! As a result, much of the effort made by the developers of this error-reporting locking mechanism was wasted, since the user still needs to go through the exercise of implementing atomic transactions from scratch.

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

    The answer: This is clearly an example of a resource model, and in two-phase locking, resources are claimed one at a time. Thus, this is a single-resource deadlock model -- that is, one with a single outgoing arc per vertex in the deadlock graph. As a result, all deadlocks in the graph are simple cycles.

    The problem, part B: Describe a protocol (a distributed algorithm) for detecting the fact that a set of atomic transactions are deadlocked.

    The answer: When a process attempts to claim a lock and would be blocked, or when a process has waited for a while and finds that the resource is still unavailable, it may initiate deadlock detection.

    To search for a deadlock, a process would send a probe message to the manager of the resource it is awaiting. On receiving such a probe, every resource manager or user process must respond in one of the following ways:

    The above protocol will always terminate in a finite time (assuming that each process that receives a probe responds in a finite time), and the result will always be a reply to the originator of the probe indicating either deadlock or no deadlock. Presumably, if a user process learns of a deadlock, it can abort the transaction it had under way.