Homework 7

22C:116, Fall 1999

Due Friday Oct 22, 1999, in class

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: Write pseudocode for the touch method of an object, assuming that the combined touch methods of all objects, taken together, are supposed to perform the marking phase of a mark-sweep garbage collector.

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

   Part C: What major problems remain unsolved by the definitions of this hypothetical programming environment and by your answers to part A and B that would cause difficulty in the use of mark-sweep garbage collection in this environment.

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? Note that our interest here is not in detecting possible deadlock, but rather, in accurately and promptly detecting any deadlock situation.

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. Explain this fact.

4. A Question What is 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?