Name: ________________________________ Login: _____________

Comp111 Midterm Exam
Oct 27, 2011 - 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. (20 points) One student wrote the following code as an initial experiment in assignment 3:
     
    int status; 
    void reaper(int sig) { 
        wait(&status); 
        fprintf(stderr, "reaped\n"); 
    } 
    main() { 
        signal(SIGCHLD, reaper); 
        if (fork()) { 
    	wait(&status); 
    	fprintf(stderr, "done\n"); 
        } else { 
    	execl("./a.out", "./a.out", NULL); 
        } 
    } 
    
    The student complained that "signal handling didn't work" because the "done" message printed but the "reaped" message did not. What actually caused this behavior?
    Answer: The wait in the main races with the wait in the status handler. Only one wins, because a child status can only be reaped once.
  2. (20 points) The following implementation of a bounded buffer does not work as expected. What is wrong with the implementation, what behavior results from the error, and how could you fix the problem without adding more locks or semaphores?
     
    void init() { 
        sem_init(&used,0,0);       	   // nothing is used
        pthread_mutex_init(&enqueue_mutex,NULL);   // mutex unlocked
        pthread_mutex_init(&dequeue_mutex,NULL);   // mutex unlocked
    } 
    int full() { return (end+1)%SIZE==begin; } 
    char dequeue() { 
        char out; 
        sem_wait(&used);        // wait for input
        pthread_mutex_lock(&dequeue_mutex); 
        out = queue[begin]; begin=(begin+1)%SIZE; 
        pthread_mutex_unlock(&dequeue_mutex);  
        return out; 
    } 
    

    Answer: There are two separate problems, both with enqueue:
  3. Consider the following resource allocation matrix:
    Requested Granted Deficit
    R1R2R3R4 R1R2R3R4 R1R2R3R4
    P10 0 0 0 - P10 0 0 0 = P10 0 0 0
    P22 1 1 1 P21 1 1 1 P21 0 0 0
    P33 2 2 2 P32 2 2 2 P31 0 0 0
    Totals
    R1 R2 R3 R4
    3 3 3 3
    1. (10 points) Is this a safe situation? Why or why not?
      Answer: It is not safe, because there is no completion schedule. In any such schedule, P1 finishes, but P2 and P3 are deadlocked and each awaits one more unit of R1.
    2. (5 points) Could use of the Banker's algorithm result in this situation? Why?
      Answer: The Banker's algorithm avoids such a situation by denying the resource request that led to it. Thus such a situation cannot evolve when one is using it.
    3. (5 points) For a system in this situation, is there any way that P3's request for resource 1 could decrease by 1? Why?
      Answer: In this situation, P3 is blocked. so it can't request anything. All that can happen is that something or someone can kill it. Thus it is not possible to undo the deadlock in that fashion.
  4. (20 points) Write a code fragment that arranges to write output to a file "foo.txt" when printing to stdout. Explain each step.
    Answer: There are two valid approaches:
     
    FILE *fp = fopen("foo.txt", "w");
    close(fileno(stdout)); 	// set up a dup target. 
    dup(fileno(fp)); 
    close(fileno(fp)); 	// optional
    
    Alternatively, one could avoid opening the file for formatted output, and just use the dup'd buffer:
     
    int fd = open("foo.txt", O_WRONLY|O_CREAT); 
    close(fileno(stdout)); 	// set up a dup target. 
    dup(fd); 		// dup into the target. 
    close(fd); 		// remove the old descriptor. 
    
    Most programmers agree that the second approach is cleaner, because one doesn't leave an unused file pointer (fp) around.
  5. (20 points) You are writing a producer/consumer music player. The producer reads music files from disk, while the consumer plays them on an audio card. Compare the following implementations: What are the pros and cons of each potential solution?
    Answer:

    Name: ________________________________ Login: _____________

  6. (Advanced; 10 points extra credit) The following thread routine:
    int i=0; 
    void * thread(void *v) { 
       int j; 
       for (j=0; j<1000; j++) i++; 
    } 
    
    has the behavior that occasionally, for n copies running concurrently, i can be less than 1000*n. Explain exactly why.
    Answer: i++ need not be atomic. If it is, there is no problem, but it is often not atomic, at the mercy of the compiler. Thus we can have a schedule like the following between two threads:
    LDA #i (A==10)
    LDA #i (A==10)
    INCA (A==11)
    INCA (A==11)
    STA #i (i==11)
    STA #i (i==11)
    (where I hope you will excuse my primitive assembler code) which leads to i being set to 11 twice rather than to 12.