Comp111 Midterm Exam
Nov 3, 2009 - open books and notes

No electronic devices of any kind allowed, including cellphones, calculators, pagers, etc. Please turn these off before beginning the exam.

Please show all work on these pages. Make sure that your work for each problem is clearly marked. These pages will be graded and returned electronically, like exercises.

  1. (30 points) Consider the following code, simplified by using high-level subroutines for lock and unlock actions:
     
    mutex A, B; // two binary mutex locks
    void foo() { 
        lock(A); 
        lock(B); 
        something_critical(); 
        unlock(A); 
        unlock(B); 
        lock(B); 
        lock(A); 
        something_else_critical(); 
        unlock(B); 
        unlock(A); 
    }
    
    Suppose that multiple threads are invoked, all of which execute foo(). Based upon these locks alone, can these threads deadlock? If so, how?
  2. (20 points) Suppose that in the above code, lock and unlock are implemented using binary kernel semaphores rather than user mutexes. Then how many context switches are needed to execute one instance of foo() above? Explain your answer.



















  3. (30 points) Present C code that opens a file for input and dups it to the standard input of your process. Explain each step.
  4. (20 points) Suppose we have a classical ring queue as discussed in class:
     
    int full() { 
        int ret; 
        lock(A); 
        ret = ((last+1)%SIZE==first); 
        unlock(A); 
        return ret; 
    } 
    int empty() { 
        int ret; 
        lock(A); 
        ret=(first==last); 
        unlock(A);
        return ret; 
    } 
    void enqueue(int i) { 
        if (!full()) { 
    	lock(A); 
    	queue[last] = i; 
    	last = (last+1)%SIZE; 
    	unlock(A); 
        } 
    } 
    int dequeue() { 
        if (!empty()) { 
    	lock(A); 
    	int out = queue[first]; 
    	first = (first+1)%SIZE;
    	unlock(A); 
    	return out; 
        } 
    } 
    
    This has a bug. Explain what happens when enqueue and dequeue are used in different threads, and why.