Comp111 -- Midterm Exam

Mon Nov 6, 2006
open book and notes
No electronics of any kind allowed.

  1. (30 points) Consider the resource matrices given as follows:
     
    Requested
        r1  r2  r3  r4 
    p1   3  10   3   4
    p2  10   0   6   4
    p3   1   1   2   2 
    p4  10  10  10  10 
    
    Allocated
        r1  r2  r3  r4 
    p1   3  10   3   4
    p2   7   0   3   4
    p3   0   0   2   2 
    p4   0   0   0   0 
    
    Total resources 
        r1  r2  r3  r4 
        10  10  10  10 
    
    Is this state safe? If so, give an order in which processes can complete their work. If not, identify a process that cannot finish.
  2. Consider two producer-consumer examples described in class:

    Example 1:
     
    #define SIZE 100
    int bot=0, top=0;
    mutex incoming, outgoing; 
    int queue[SIZE];
    void enqueue(int c) {
      lock(incoming);
      if ((top+1)%SIZE!=bot) { queue[top]=c; top=(top+1)%SIZE; }
      unlock(incoming);
    }
    int dequeue() {
      int out;
      lock(outgoing);
      if (bot!=top) { out = queue[bot]; bot=(bot+1)%SIZE; } 
      else { out = 0; }
      unlock(outgoing);
      return out;
    }
    





    Example 2:
     
    semaphore excl = 1; // used as binary semaphore
    semaphore avail = 0;  // number used
    semaphore unused = SIZE-1; // number free/available
    void producer() {
      while (1) {
        int thing = produce(); 
        semWait(unused); 
        semWait(excl); enqueue(thing); semSignal(excl); 
        semSignal(avail); 
      }
    }
    void consumer() {
      while (1) {
        int thing; 
        semWait(avail); 
        semWait(excl); thing = dequeue(); semSignal(excl); 
        semSignal(unused); 
        consume(thing); 
      }
    }
    
    1. (20 points) Suppose that these two examples are used together. Are all the locks necessary or not? If so, explain why. If not, identify locks that can be removed. If there are two possibilities for which locks can be removed, eliminate the ones with the slowest runtimes. Justify your answer.
    2. (20 points) Rewrite all code above to eliminate all semaphores and utilize only binary mutexes. The behavior should be exactly the same as before.
  3. (30 points) In class there was some discussion of states of a process between which there cannot be transitions. For the case of UNIX/Linux, identify the state transitions that cannot occur for a process, and explain why each of these transitions is impossible.