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

  1. Consider the resource allocation diagram:

    1. Is this situation deadlocked? Why or why not?
    2. Is this situation "safe" according to Lamport's bankers' algorithm (is there a way for all processes to complete)? Why or why not?
    3. Does safety in the bankers' algorithm eliminate all possible kinds of deadlock? Why or why not?
    4. Does lack of safety in the bankers' algorithm guarantee deadlock? Why or why not?
  2. In the pseudo-code on page 231 of Stallings:
     
    monitor boundedbuffer; 
    char buffer[N]; 
    int nextin=0, nextout=0, count=0; 
    cond notfull, notempty; 
    void append(char x)  {
        if(count==N) cwait(notfull); 
        buffer[nextin]=x; nextin=(nextin+1)%N; count++; 
        csignal(notempty); 
    } 
    void take(char y) {
        if (count==0) cwait(notempty); 
        y=buffer[nextout]; nextout=(nextout+1)%N; count--;  
        csignal(notfull); 
    } 
    void producer() { 
        char x; 
        while(TRUE) { produce(x); append(x); } 
    } 
    void consumer() { 
        char y; 
        while(TRUE) { take(y); consume(y); } 
    }
    
    1. What is the difference between implementing this as a monitor and implementing it with semaphores? How would the code change in implementing it with semaphores, and why?
    2. What is the precise effect of eliminating both "if" statements from "append" and "take" so that the cwaits are called unconditionally?
    3. In the book, semaphore code often requires groups of semaphores to control one resource. Does making a single semop call to manipulate a group of semaphores execute faster than making separate semop calls for each semaphore? Why or why not?
  3. Consider the lock priority algorithm for deadlock prevention.
    1. Consider process A that locks W, X, and Y while process B locks X and Z. Show that deadlock cannot occur by enumerating the possible execution cases with time/space diagrams; show the order in which each process gets the lock on each resource.
    2. Why don't we simply force all processes to lock resources in a fixed and predetermined order?