Comp111 -- Midterm Exam Answers

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.
    Answer:

    First, we know that p4 will need to be last, becasue it needs all resources. So we can safely list it last and consider the rest without it.

    Next, consider process 1, which has all of its resources. Thus it will go first, and we can safely consider p2 and p3 without p1 and p4.

    Of p2 and p3, p3 needs the least resources and can go first.

    Thus one order is p1, p3, p2, p4 and the configuration is safe.

  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; 
    semaphore avail = 0; 
    semaphore unused = SIZE-1; 
    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(free); 
        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.
      Answer:
      The semWait(excl) and semSignal(excl) are redundant and can be eliminated. They should be eliminated rather than the mutexes, because semaphores are slower than mutexes.
    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.
      Answer:
      This is a tricky one. The key is that whenever there is a danger of a buffer overrun, we should block either producer or consumer until it is over. This is the purport of the "avail" and "free" semaphores. We've eliminated the "mutex" semaphore, so that all we have to do is to replace "avail" and "free" and we're done.

      First, we note that each semaphore can be replaced by a pair of mutexes and an integer variable, as follows:

       
      struct sem { 
          int semValue; 
          mutex semExcl, semDelay; 
      };
      typedef struct sem Sem; 
      void mySemInit(Sem *s, int value) { 
         s->semvValue=value; 
         s->semExcl=1;  // unlocked
         s->semDelay=0; // locked
      } 
      void mySemWait(Sem *s) { 
          lock(s->semExcl);			// lock for mutual exclusion 
          s->semValue = s->semValue - 1;	// the following actions are atomic (!)
          /* if there were no units available, release semValue and join the queue */
          if (s->semValue <= -1) {
      	unlock(s->semExcl);
      	lock(s->semDelay);	// blocks until someone unlocks it! 
          } else { 
      	unlock(s->semExcl);
          } 
      } 
      void mySemSignal(Sem *s) { 
          lock(s->semExcl);			// lock for mutual exclusion
          s->semValue = s->semValue + 1;	// increment semaphore
          /* if there were waiters in the queue, release one */
          if (semValue <= 0) unlock(semDelay);
          unlock(s->semExcl);			// no more mutual exclusion 
      } 
      
      All we have to do is to implement this for a semaphore, and we're done. Rewrite example 2 as:
       
      mutex mutex = 1; 
      Sem avail; 
      Sem unused; 
      void init() { 
          semInit(&avail,0); 
          semInit(&unused,SIZE-1); 
      } 
      
      void producer() {
        while (1) {
          int thing = produce(); 
          mySemWait(&unused); 
          enqueue(thing); 
          mySemSignal(&avail); 
        }
      }
      void consumer() {
        while (1) {
          int thing; 
          mySemWait(&avail); 
          thing = dequeue(); 
          mySemSignal(&unused); 
          consume(thing); 
        }
      }
      
      and we're done! Alternatively, we could write this into the code, but that's a bit less clear.

      Grading scale:

      • -5 for use of inappropriate mechanisms, e.g., spinlocks or monitors.
      • -10 if there are race conditions or other problems with your solution.
      • -15 if solution makes little sense.
  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.
    Answer:
    The main issue is that a sleeping process can be swapped out, after which it is not possible for it to transition directly back to "running". It must be swapped in first.