Homework 7 Solved

22C:116, Fall 1999

1. Background Consider an object oriented programming environment where all objects inherit the following methods from the universal object superclass:
   • next -- identity of the next object in the heap
   • prev -- identity of the previous object in the heap
   • marked -- returns a boolean value
   • mark(v) -- future calls to marked will return v
   • done -- causes the object to deallocate itself
   • touch -- a "virtual method" that must be defined for every object
   In addition, the environment defines first and last as global functions that return pointers to the first and last objects currently allocated on the heap, and the heap manager raises the heap-empty exception when an allocation cannot be performed.

   Part A: Here is pseudocode for the touch method of an object, so that the touch methods of all objects, taken together, will perform the marking phase of a mark-sweep garbage collector.

   	touch:
             myself.mark(true)
   	  for each field f of this object
               when f is a reference to another object
                 if not f.marked
                   f.touch
                 endif
               end when
             end for
   

   Note, in most cases, the mark method will not have any iteration, but rather, will consist of explicit statements, for each field that is an object reference, as follows:

   	touch:
             myself.mark(true)
             if not fieldone.marked
               fieldone.touch
             endif
             if not fieldtwo.marked
               fieldtwo.touch
             endif
             .
             .
             .
   

   Part B: Here is pseudocode for a sweep function that can be called on receipt of a notice of a heap-empty exception.

   	sweep:
             o = first
             repeat
   	    if o.marked
   	      o.mark(false)
               else
   	      o.done
               endif
               oo = o
               o = o.next
             until oo = last
   

   Part C: The major problems that remains unsolved by the definitions of this hypothetical programming environment and by the answers to part A and B given above are:

   First, we leave it to the user to call touch on the roots of the data structure and then call sweep in response to a heap-empty exception and then retry the allocation.

   Second, we've done nothing to help identify the roots of the data structure. A reasonable definition would be: All global object references plus all object references in local variables of any stack frame are roots. Writing user-level code to find and mark these is difficult, particularly when there is deeply nested recursion.

   Third, of course, we said nothing about the underlying heap manager.

2. A Question: How difficult would it be to add automatic deadlock detection to the toy thread package we have dealt with in this class?

   It would be impossible. All deadlock models require the ability to construct a wait-for graph. We simply have no way to construct this graph because, when a thread waits on a thread-semaphore, we have no idea what other thread is expected to signal that semaphore. The fact that we are dealing with an or-model, as opposed to an and-model or a single-resource model is irrelevant.

3. A Question Spin-locks (binary semaphores implemented using busy waiting) of some kind required in a symmetrical shared memory multiprocessor setting while they are never needed in a uniprocessor. This is because, on a uniprocessor, simply disabling interrupts gives the current kernel thread or process exclusive use of all resources. On a multiprocessor, when a thread or process disables interrupts, the effect is only local on one CPU, so no exclusive access to resources is provided. Therefore, to enter a low-level critical section in the kernel, we must disable interrupts (locking out other activity on this CPU) and then use a spin lock (locking out activity on other CPUs).

4. A Question The difference between the use of the word Kernel in descriptions of the UNIX operating system and in descriptions of distributed systems, for example, in section 9.4 of Tannenbaum, is as follows:

   The UNIX kernel is a large object containing file syste, process scheduler, and many other system resources. The kernels of modern operating systems, on the other hand, are small; typically, they contain only minimal scheduling, memory management, process management and interprocess communications mechanisms, leaving things like file systems and accounting entirely outside the kernel.