Assignment 8, Solutions

A Problem: Express the marking algorithm as a variation on the universal graph meta-algorithm. Then, explain where the recursive version stores the set S during its computation and explain what queueing discipline is used (fifo, lifo) and whether the graph is traversed in breadth-first or depth first order.

        S = set of roots of the data structure
        mark all elements of S
        repeat
            e = element of S
            S = S - e
            for each e' reachable from e
                if e' not yet marked
                    mark e'
                    S = S + e'
                endif
            endfor
	until S empty

The set S in the recursive version consists of the pointers in the local variables and parameters of all the activation records of the recursive marking routine. The recursive version maintains S in LIFO order (because activation records are pushed on a stack), and it traverses the graph in a depth first order.

A Problem: Give an example of a programming error that could lead to this message even when a deadlock is not possible under the formal definition of a deadlock. Also describe how a deadlock could exist under the example thread manager and yet not be detected by the code as it currently stands.

        {
                thread_semaphore s;
                thread_semaphore_init( &s, 0 );
                thread_wait( &s  );
        }

Note that the above error will lead to the possible deadlock error message if this bit of code is executed by the only non-blocked thread. Since the semaphore s is not shared, it is not a deadlock.

If there are other non-blocked threads, then the thread manager will never notice this error, nor will it notice a real deadlock.

A Problem: Explain why this is an entirely unreasonable assignment! (Hint: The problem is not a lack of time.)

General purpose deadlock detection requires that we be able to identify which threads are waiting on which semaphores, and it requires that we be able to determine which semahpores might be signalled by which threads. The semaphore abstraction contains no way to determine the latter, so we have insufficient data to implement any such algorithm.

Sure, SETI@home is a distributed system. It uses the internet as its interconnection structure, and processes exchange messages by E-mail. This is a very loosely coupled distributed application, but it is most certainly a distributed application.

The USENET message distribution system also qualifies as loosely coupled. Although the NNTP protocol used to communicate between the cooperating servers that make up USENET could be considered tighter coupling than is used by SETI@home, the total USENET system is also a very loosely coupled distributed server.

Problem 20 on page 580.

On a shared memory system, send and receive involve a memory-to-memory copy, possibly directly from the sender's buffer to the receiver's buffer, or possibly via an intermediate buffer. Synchronization between sender and receiver may be done by semaphores or similar scheduler mechanisms.

In a multicomputer, the copying between sender and receiver or between sender and intermediate buffer is likely to be done by DMA hardware attached to the communications channel; while semaphores may be used for user to interrupt service routine synchronization at each end, the transport of the message itself is also part of the synchronization between sender and receiver.