Homework 7 Solved

22C:116, Fall 1999

Douglas W. Jones

  1. Background Consider an object oriented programming environment where all objects inherit the following methods from the universal object superclass: 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.