Homework 7

22C:116, Fall 2000

Due Friday Oct 13, 2000, in class

1. Background: Consider the following abstract data structure: Each vertex in a digraph is represented by a record containing a field that may be marked and a list of pointers to other vertices in the digraph, where each such pointer represents an edge in the graph. Concretely, in C and Pascal:

   typedef struct vertex * refvertex    type refvertex = ^ vertex;
   typedef struct item * refitem             refitem = ^ item;
   struct vertex {                           vertex = record
           int marks;                                    marks: integer;
           refitem list;                                 list: refitem;
   };                                                 end;
   struct item {                             item = record
           refitem next;                               next: refitem;
           refvertex edge;                             edge: refvertex;
   };                                               end;
   

   Assume that the marks field of each vertex is initially zero!

   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. Your algorithm will most likely be recursively formulated, and while it would be better if the algorithm was modestly efficient and terminated with the marks all set back to zero, this is not a requirement of this problem!

   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. Your algorithm will most likely be recursively formulated, and while it would be better if the algorithm was modestly efficient and terminated with the marks all set back to zero, this is not a requirement of this problem!

2. Background: Consider a heap manager supporting the fundamental heap operations:
   • malloc(s) returns a pointer to a block of s bytes, or nil if none available.
   • free(b) deallocates the block pointed to by b.
   • marked(b) returns a boolean, the value of the mark bit on block b.
   • mark(b) sets the mark bit on block b.
   • unmark(b) clears the mark bit on block b.
   • succ(b) returns a pointer to the next non-free block in the heap, or nil.
   • first() returns a pointer to the first non-free block in the heap.
   Note that first and succ presume that the heap's underlying data structures allow all blocks that are currently allocated to be found and scanned in order. User programs never use firs and succ, and these disclose nothing about the user's data structure, but only disclose the physical layout of items in the heap.

   Assume that there is some pointer called root pointing to a block in the heap. Assume that each block in the heap may contain pointers to other blocks, with the constraint that the pointers are either valid pointers to non-free blocks or nil.

   Assume that all blocks begin with an integer field called count, a count of the number of pointers in the block, and that all pointers in a block come immediately after count and before any other non-pointer data in the block.

   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 */
   }