Homework 7 Solutions

22C:116, Fall 1995

Douglas W. Jones
  1. The problem: Solve the mutual suspicion problem in Pascal.

    The Solution:

    program suspicion( input, output );
    
       procedure user( procedure push( ... );
                       procedure pop( ... ) )
          ... user data structures
          ... user procedures ...
       begin
          ... user main program ...
       end { user }
    
       procedure stack;
          ... stack data structures ...
          procedure push( ... );
          ...
          procedure pop( ... );
       begin
          user( push, pop );
       end { stack };
    
    begin
       stack;
    end;
    
    When the above code is run, exactly one activation record is allocated for the user procedure and exactly one activation record is allocated for the stack procedure. The scope rules prevent the code from either procedure from referencing the activation record for the other, but because of the parameters passed from the trivial body of the stack routine to the user routine, the user can call push or pop to operate on the variables in the stack activation record.

    This solution is messy to generalize to multiple protected objects or to multiple instances of one protected type, and it does not generalize at all to dynamic instantiation of a protected abstract data type.

  2. The problem: Describe how you would construct a stack abstract data type on the CAP system, with the fundamental operations create_stack, push and pop.

    The Solution: First, note that insufficient syntactic information was given about the CAP system to allow detailed pseudocode, but the assignment asked for a description.

    In purely descriptive terms, create_stack, push and pop would have to be protected procedures -- segments the user could transfer control to but not inspect. These segments would share between them the key needed to lock and unlock sealed stack objects, and this key would not be given out into any other domain.

    create_stack would create a stack object and seal it using the key, then return that sealed object to the caller. To operate on the stack, the user would then pass this sealed object to push or pop; inside these routines, the object would be unsealed and manipulated. Since sealed objects contain capabilities, which are effectively pointers, this is call by reference semantics and there is no need to reseal the object and return it to the user after a push or pop operation.

  3. The problem: Describe, in some detail, an algorithm for detecting a cycle in a graph.

    A Solution

         Clear all markings from the graph;
         Assert that no cycle has yet been found;
         repeat
            Pick an unmarked vertex V;
            traverse-and-mark(V);
         until no unmarked vertices remain.
    
         traverse-and-mark(V):
            mark vertex V;
            for each edge 
               if V' is marked
                  assert that there is a cycle!
               else
                  traverse-and-mark(V');
    
    The above algorithm operates correctly only on undirected graphs. It is basically the spanning tree algorithm, augmented with an outer loop to take care of graphs that are not connected, and augmented with the code to assert that if there is an edge that is not in the spanning tree, that could only be so if there is a cycle.

    What about directed graphs? One approach is to simply treat them as undirected graphs, find the cycles, and then see if all the arrows point in the same direction around each cycle. Alternately, consider the following variation on the above algorithm:

         Clear all markings;
         Assert that no cycle has yet been found;
         repeat
            Pick an unmarked vertex V;
            traverse-and-mark(V);
         until no unmarked vertices remain;
    
         traverse-and-mark(V):
            mark vertex V as hot; 
            for each edge 
               if the mark on V' is hot
                  assert that there is a cycle!
               else if V' is unmarked
                  traverse-and-mark(V');
               else
                  V' is cold and already handled.
            mark vertex V as cold;
    
    Here, all vertices on the path from the root of the part of the graph currently under search are hot, while all previously searched vertices are cold.

  4. The problem: Given a UNIX system, could you automatically detect deadlocks? What problems stand in the way of doing so?

    An Answer: There many problems that prevent deadlock detection in UNIX systems. First, although semaphores and lockable files were added to later versions of UNIX, most UNIX applications still rely on busy waiting solutions to resource contention problems.

    Second, where processes do use semaphores, it is hard to determine whether the semaphore is being used for resource allocation or for producer-consumer synchronization. As a result, the set of processes on which a blocked process is waiting is ill defined, and it is unclear from the system point of view whether the applicable deadlock model is the and-model for resource allocation or the or-model that characterizes producer-consumer relationships.

    With pipes, it is possible, in theory, to determine the set of processes able to write the pipe, and thus, if only pipes are involved, the or-model clearly applies and deadlock detection would be possible, in theory. With resources such as lockable files, the system is clearly a serialized and-model, while semaphores allow non-serialized and-model operations. Thus, if a set of blocked processes includes both processes that are awaiting data from pipes, processes waiting on locked file records and processes that are blocked on semaphores, the system is not only a mixed model, but some of the vertices in the wait-for graph are of unknown type (and or or).

    Finally, all blocking primitives in UNIX have non-blocking variants. It is possible to test a semaphore without blocking; it is possible to test the lock on a file record without blocking, and it is possible to read a pipe without blocking if no data is available. Programs that use these nonblocking primitives frequently convert blocking into iteration, and as a result, situations that are, in reality, deadlocks, may never involve processes that are blocked from the kernel's perspective.