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

Name: ______________Answers____________________ Login: ______couch________

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?
    Answer: Suppose that there are two threads, where the first thread executes the first lock(A) just before or after the second thread executes the second lock(B). Then there is deadlock, because the first thread is waiting for B while the second is waiting for A.
  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.
    Answer: The key is that the semaphores are in kernel memory, which requires switching to kernel mode and back again for each call. There are 8 calls, so there are at least 16 context switches from user to kernel mode and back again. Some people noted that initialization requires at least one more context switch; perhaps more. Others pointed out that using semop could reduce the number of context switches to 8 (and that would also eliminate the potential for deadlock in the problem above!).
  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.
    Answer: There were two acceptable answers:
    1. FILE *f  = fopen("file.txt", "r"); // open a formatted file pointer
      close(0);       // close stdin
      dup(fileno(f)); // dup the file *descriptor* for the open file
      
    2.  
      int fd = open("file.txt", O_RDONLY); // open a raw file descriptor (an int)
      close(0); // close stdin
      dup(fd);  // dup the descriptor (which is the return for open). 
      
    Other "cleanup" steps weren't required and I didn't deduct for them.
  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.
    Answer: There are multiple "bugs", but I was looking for one in particular.
    1. There is no error return when trying to enqueue into a full queue or dequeue from an empty one.
    2. There is a race condition in which two enqueues to an almost full queue can inadvertently erase the queue.
    3. There is a race condition in which two dequeues from an almost empty queue can fill the queue with garbage.
    To understand the race condition (b), suppose that The race condition (c) is similar. Pointing out either (b) or (c) was worth full credit. There was partial credit for pointing out (a).