Comp111 -- Midterm Exam Review 3 Answers
Midterm Mon Nov 6, 2006
Open book and notes

  1. Suppose that one has the following resource tables for three resources:
    1. (15 points) Is this situation "safe" according to Lamport's bankers' algorithm (is there a way for all processes to complete)? Why or why not?
      Answer:
      From a quick estimate, process 1 can continue, while process 2 and 3 are blocked until process 1 completes. Process 1 completion takes 9 of 10 units of resource 1, 12 of 12 units of resource 2, and 7 of 7 units of resource 3. Neither process 2 nor process 3 can proceed until process 1 releases resources.
    2. (15 points) If process 1 hangs indefinitely without releasing resources or allocating any more resources, can the other processes complete? Why or why not?
      Answer:
      From part 1, no process other than process 1 can complete. If process 1 hangs, then regardless of whether allocations are done for it or not, the other processes are blocked awaiting resources and the whole scheme deadlocks. The banker's algorithm presumes that every process, with all needs satisfied, completes. Without this assumption, it fails to assure freedom from deadlock.
    3. (10 points) Can the lock priority algorithm be applied to this situation? Why or why not?
      Answer:
      Lock priority assumes that resource locks may be released before other locks are acquired. The banker's algorithm presumes that resources, once allocated, are allocated until completion. The programs for which the banker's algorithm functions cannot be changed to lock-priority without changing the programs according to the differing assumptions. The algorithms support distinct programming models and are not interchangeable.
  2. Consider the following producer-consumer code:
     
    #define SIZE 10
    int begin=0, end=0, queue[SIZE]; 
    mutex m; 
    int empty() { return begin==end; } 
    int full() { return begin==(end+1)%SIZE; } 
    void produce(int thing) { 
        while (full()) { /* do nothing */  } 
        mutex_lock(m); 
        queue[end]=thing; end=(end+1)%SIZE;  
        mutex_unlock(m); 
    } 
    int consume() { 
        while (empty()) { /* do nothing */ } 
        mutex_lock(m); 
        int ret = queue[begin]; 
        begin=(begin+1)%SIZE;
        mutex_unlock(m); 
        return ret; 
    } 
    
    Suppose that produce and consume are called independently and perhaps concurrently by multiple threads.
    1. (15 points) Does this code have race conditions? Why or why not? If there are race conditions, how would one eliminate them, using just the one mutex lock (m)? Hint: consider only equivalent effects.
      Answer:
      Consider the situation in which more than one thread has called produce or consume at the same time. Neither empty nor full is atomic. Thus it is possible that two threads would simultaneously get TRUE responses to !empty() or !full() even though there is only one element in the queue or left free, respectively.

      To fix this requires considerable changes to the code: we must lock before allowing empty() to be called, and then unlock before each repeat of the loop (to allow producers to produce!)

       
      int consume() { 
          while (1) { 
      	mutex_lock(m); 
      	if (!empty())  {
      	   int ret = queue[begin]; 
      	   begin=(begin+1)%SIZE;
      	   mutex_unlock(m); 
      	   return ret; 
      	} else { 
      	    mutex_unlock(m);
      	} 
          } 
      } 
      
      Produce must be changed in the same fashion.
    2. (15 points) The above while loops are considered bad programming practice. Why?
      Answer:
      The while loops consume CPU even though they do nothing. This does not allow the process to sleep. It is much better form to sleep while waiting for a condition so that other processes can accomplish work.
  3. The following questions concern operating system design issues and the locations of specific resources and variables within the OS.
    1. (15 points) Suppose that interrupt handling were done by individual processes rather than the kernel. What would be the impact of this decision? Is there any case in which this would be desirable? Why?
      Answer:
      The major impact is that the process in question would have to be swapped in before interrupts could occur. This means in particular that it must be locked into core before a typical interrupt must be serviced in a time that is considerably less than the swap delay. The other problem is that when servicing an interrupt, there would be the necessity for two context switches, one from the process currently executing to the kernel, and one to the process handling the interrupt. Altogether this is a bad scene and leads to poor performance and speed of interrupt handling (which can, in severe cases, lead to device malfunction). If one has only one process running, and that process is memory resident, there are no problems and the approach might be desirable.
    2. (15 points) Suppose that semaphores were stored in individual process space rather than the kernel, and that the first process that tries to manipulate the semaphore creates and owns it. Compare performance of this solution to storing semaphores in the kernel. Is there any situation in which this is desirable? Why?
      Answer:
      The main benefit is to user-level threading. If a semaphore is in a process, then user-level threads have access to it within the process without a system call. This is the case with the Java Virtual Machine. The main benefit is performance because the system call to manipulate a kernel semaphore takes considerable time due to mode switching between user and kernel mode. The problem with the approach is that should some other process try to read this semaphore, two mode switches are required in each direction: the reading system call in the referring process must switch to kernel mode, switch to the managing process, do something to the semaphore, and then switch back to kernel and then the context of the referrer. The management of the semaphore would typically utilize a signal to the owner process. So references from outside the process are much slower, while references from within are much faster.