Comp111 -- Midterm Exam Review 3
Midterm Exam 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?
    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?
    3. (10 points) Can the lock priority algorithm be applied to this situation? Why or why not?
  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.
    2. (15 points) The above while loops are considered bad programming practice. Why?
  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?
    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?