Homework 6

22C:116, Spring 1999

Due Friday Mar 12, 1999, in class

1. Background: Automatic deadlock detection requires that it be possible to identify the relationships between processes and resources. Consider changing our thread package by replacing semaphores with a new category of synchronizing tool, the lock. If L is a lock, the operation lock(L) blocks until L is unlocked and then locks L, while unlock(L) changes the state of L to unlocked. In effect, locks are like binary semaphores, but with one additional constraint. The only thread that may legally unlock a lock is the same thread that locked it.

   Part A: Are locks as powerful as semaphores for solving communication and synchronization problems? To answer this, consider what problems can and cannot be solved with locks.

   Part B: Write code to replace the semaphores in our thread package with locks. Minimize your changes and do not turn in a complete listing, only listings of the fragments of the thread package you changed. The total code required is not large!

   Part C: Describe a deadlock detection algorithm appropriate for your implementation of locks.

2. Background: A typical implementation of an object oriented language such as C++ will use a record or structure to represent each instance of each class. The first item in this record will be a pointer to the class description record, and the remainder will hold the variables local to the instance, including pointers class instances used as components of this instance.

   The class description record begins with a field giving the size of each instance of the class (all instances must be the same size), followed by pointers to each of the methods of the instance. If x is a class member, the call:

   x.method(p)
   

   translates to (in C notation)

   (* x->my_class_descripition->method)(x,p)
   

   The Problem: Assume, first, that the object oriented language is strongly typed, unlike C++. Outline how you would modify the fundamental data structures of the implementation to support garbage collection -- that is, what fields would you add to each class instance record, what fields would you add to each class description record, and what new methods, if any, would you add to all classes (probably as methods of the base class from which all classes are descended).

3. Background: Consider the definition of a microkernel given in chapter 9 of Tannenbaum, and then look at UNIX. It is noteworthy that Tannenbaum's UNIX clone, MINIX, is based on a microkernel, even though it is not implemented on a multiprocessor or network. There also appears to be something of a microkernel inside Windows 95, although its nature is obscured by Microsoft's assertions about Windows in their federal antitrust case. The design of Multics also implied the use of a microkernel of sorts, inside the innermost ring of the system.

   Part A: Discuss the application of microkernels to non-networked systems. What are the advantages of such a design in that context.

   Part B: If you had to implement UNIX using a microkernel-based approach, what functions that are kernel functions in UNIX as it exists today would clearly belong outside of the microkernel?