Homework 7 Solutions

22C:116, Fall 2000

1. Part a: Give readable pseudocode for an algorithm to traverse a graph with the above represenation searching for a cycle, as would be required for deadlock detection.

   BOOLEAN hascycle( refvertex v )
   /* precondition:  All marks are zero;
      returns TRUE if the graph reachable from V contains a cycle;
      final values of marks are:
       0 - not visited
       1 - visited on the path from V to a cycle
       2 - visited and not involved in a cycle
   */
   {
       refitem i;
       if (v->marks = 1) return TRUE;
       if (v->marks = 2) return FALSE;
   
       v->marks = 1; { indicate that this vertex is being checked }
       for (i = v->list; i != NULL; i = i->next ) {
           if (hascycle( i->edge )) return TRUE;
       }
       v-> marks = 2; { indicate that this vertex has been checked }
       return FALSE;
   }
   

   Part b: Give readable pseudocode for an algorithm to traverse a graph with the above represenation and mark each reachable vertexs, as would be required for garbage collection.

   void mark( refvertex v )
   /* precondition:  All marks are zero;
      final values of marks are:
       0 - not visited
       1 - reachable from v
   */
   {
       refitem i;
       if (v->marks = 1) return;
   
       v->marks = 1; { indicate that this vertex is reachable }
       for (i = v->list; i != NULL; i = i->next ) {
           mark( i->edge );
       }
   }
   

2. The Problem: Write a mark-sweep garbage collector for this machine, so that a user program could use the following routine:

   char * gc_malloc(s)
   {
       char * p = malloc(s);  /* first try */
       if (p != NIL) return p;
       mark(root);
       sweep();
       return malloc(s);      /* second try */
   }
   
   void mark( char * v )
   {
       int i;
       char * * p;
       if (marked(v)) return;
   
       mark(v);
       p = (char * *)(((int *)v)[1])
       for (i = *(int *)v; i > 0; i--) {
           mark( *p );
       }
   }
   
   void sweep()
   {
       char * p = first();
       while (p != NULL) {
           char succp = succ(p);
           if (marked(p)) {
               unmark(p)
           } else {
               free(p)
           }
           p = succp;
       }
   }