Homework 6 Solutions

22C:116, Spring 1999

Due Friday Mar 12, 1999, in class

1. Part A: Locks are not as powerful as semaphores for solving communication and synchronization problems! Locks solve only mutual exclusion problems, and do nothing to solve problems such as the producer-consumer problem.

   Part B: Here is code to replace the semaphores in our thread package with locks.

   /****                                 *
    * thread manager extension for locks *
    *                                 ****/
   
   
   /* lock representation known only to lock methods */
   struct thread_lock {
           int lstate; /* either LOCKED or UNLOCKED */
           struct thread_queue queue;
   };
   #define LOCKED 0
   #define UNLOCKED 1
   
   void thread_lock_init( struct thread_lock * lk )
   /* call this to initialize lock lk to UNLOCKED */
   {
           lk->lstate = UNLOCKED;
           thread_queue_init( &lk->queue );
   }
   
   void thread_claim( struct thread_lock * lk )
   /* call this within a thread to claim a lock */
   {
           if (lk->lstate == UNLOCKED) {
                   lk->lstate = LOCKED;
   		/* deadlock */ lk->thread = current;
           } else {
                   if (_setjmp( current->state ) == 0) {
   	        	/* deadlock */ t->lock = lk;
   	        	/* deadlock detection algorithm */
                           thread_enqueue( current, &lk->queue );
                           current = thread_dequeue( &readylist );
                           if (current == thread_null) {
                                   /* crisis */
                                   thread_error = "possible deadlock";
   
                                   _longjmp( thread_death, 1 );
                           }
                           _longjmp( current->state, 1 );
                   }
           }
   }
   
   void thread_release( struct thread_lock * lk )
   {
   	struct thread * t = thread_dequeue( &lk->queue );
   	if (t == thread_null) {
   		/* deadlock */ lk->thread = thread_null;
                   lk->lstate = UNLOCKED;
   	} else {
   	        /* deadlock */ t->lock = thread_semaphore_null;
   		/* deadlock */ lk->thread = t;
   		thread_enqueue( t, &readylist );
   	}
   }
   
   

   Part C: To allow automatic deadlock detection, we have to add some new pointers to the representations of locks and threads. Specifically, in each thread, we put a pointer called current_lock, and in each lock, we put a pointer called current_thread. These pointers are manipulated as shown by the lines commented /*deadlock*/ in the above code.

   If we ever find a cycle in these pointers, we have a deadlock. The point where such a cycle can be created is commented /*deadlock detection algorithm*/ in the above code.

2. Assuming a strongly typed object oriented language, we could add garbage collection to the language using one new bit per object and one new method per class. The new bit would be a mark bit (as you might expect), and the new method would be "mark". The mark method, applied to some object, would set the mark bit on the object and then it would inspect every object referenced (by a pointer) from this object. If the referenced object was not marked, the mark method of the referenced object would be called. This recursively marks all objects reachable from some object.

   The problem remains of deciding what objects will serve as roots of the marking process. One solution is to treat each stack frame (activation record) as a special kind of object, so each distinct activation record format would have, associated with it, a marking method that calls the mark method of each object referenced from that activation record. To initiate marking, then, we simply call the mark method of the topmost activation record on the stack. This, in turn, calls the mark methods of everything pointed to from the current activation record, including the activation record below it on the stack, all the way back to the global level.

   An alternative to introducing new methods would be to augment each item on the heap or on the run-time stack with a data structure indicating what words in that item are pointers. Then, a single marking function could recursively traverse the stack and heap, marking each object reachable by any pointer. This universal marking function would be likely to be slower than having a specialized mark method for each class, but it would require less code.

3. Part A: In a non-networked system, the primary advantage of using a microkernel is that it allows most components of the operating system to be written as if they were user-level code; this simplifies practical debugging and it forces good software engineering discipline on the system designers by forcing them to modularize their design. Furthermore, it leads naturally to system architectures with interchangable or replacable components.

   Part B: If you had to implement UNIX using a microkernel-based approach, such items as the file system, timers, and probably all I/O would be outside the kernel, leaving behind only process and memory management, along with some kind of interprocess communication. In fact, Tannenbaum's Minix system (used in his lower-level operating systems text) is exactly such a re-implementation of UNIX based on such a microkernel.