Comp111 Midterm Exam Answers
Nov 5, 2014 - open books and notes

  1. Can you register a signal handler that will continue to function after a successful execl? Why or why not?
    Answer: Never. The signal handler is part of the running image of the current code. When one execl's, that image is replaced. Thus there is no way to make a signal handler persist over an execl.
  2. Suppose that you open a file and dup the descriptor. Does closing the dup'd descriptor close the original? Why or why not?
    Answer: No. A dup'd descriptor counts as an extra open file. It is indistinguishable from the original, but must be closed in order to be deactivated. Closing the original descriptor is part of most dup patterns and never modifies the dup'd descriptor.
  3. Why is it typically wasteful to make copies of all process memory when forking?
    Answer: A typical fork is followed by an exec. Since this exec replaces all memory, there is little point in duplicating all fork'd memory before the exec.
  4. The buddy system for memory allocation does not handle very large chunks, e.g., more than a page in size. Instead, available blocks are handled via a simple free list and the descriptor remembers the size. Why is this preferable to using the buddy system for large chunks?
    Answer: The buddy system breaks down only when internal fragmentation gets out of hand. Running the system for very large blocks would cause outrageous internal fragmentation -- on the order of many pages -- and would outweigh the original goal of trading space for time.

    Scoring: 10 if good, 8 if missed minor points, 5 if explanation inadequate. 3 if explanation mostly irrelevant.

  5. Consider the code:
     
    #define SIZE 20
    int begin=0, end=0; char queue[SIZE]; 		
    int empty() { return begin==end; } 		
    int full() { return ((end+1)%SIZE)==begin; }
    void enqueue(char c) {
        pthread_mutex_lock(&can_enqueue); //1 
        pthread_mutex_lock(&can_modify);
        int empty_before=empty(); 
        queue[end]=c; end=(end+1)%SIZE;
        int full_after=full(); 
        pthread_mutex_unlock(&can_modify); 
        if (empty_before) {
    	pthread_mutex_unlock(&can_dequeue);
        } 
        if (!full_after) {
    	pthread_mutex_unlock(&can_enqueue);
        } 
    }
    
    char dequeue() {
        char out; 
        pthread_mutex_lock(&can_dequeue); 
        pthread_mutex_lock(&can_modify); 
        int full_before = full(); 
        out = queue[begin]; begin=(begin+1)%SIZE; 
        int empty_after = empty(); 
        pthread_mutex_unlock(&can_modify); 
        if (full_before) {
    	pthread_mutex_unlock(&can_enqueue);
        } 
        if (!empty_after) {
    	pthread_mutex_unlock(&can_dequeue);
        } 
        return out; 
    }
    
    1. What would happen if I deleted or commented out the line marked '//1'? Why?
      Answer: This lock keeps the queue from overfilling. In the absence of this lock, the queue could over-fill and thus seem empty.

      Scoring: 10 if good, 8 if pointed out that the queue would be corrupted, but did not specify how.

    2. What would happen if I locked (and unlocked) can_modify inside the subroutines empty() and full()?
      Answer: This would cause a deadlock because during these routines, can_modify is already locked.

      Several people thought that I meant to move the lock and unlock, rather than to add extra lock and unlock. This is a misinterpretation. I did not count off for this misinterpretation, as it was widespread (1/2 of the class). The correct answer in this case is that this leads to a race condition between calls to enqueue and/or dequeue, and it is possible for the state of the queue to be corrupted in several ways.

      Scoring: 10 if good, 8 if minor errors, 5 if answer confused.

  6. Consider the Banker's algorithm tableau:

    Requested (and approved) Granted (and held) Deficit
    R1R2R3R4 R1R2R3R4 R1R2R3R4
    P11 0 0 0 - P11 0 0 0 = P10 0 0 0
    P23 0 0 0 P21 0 0 0 P22 0 0 0
    P30 2 0 0 P30 2 0 0 P30 0 0 0
    P43 2 2 0 P41 2 2 0 P42 0 0 0
    Totals
    R1 R2 R3 R4
    4 4 4 4

    1. Give a completion schedule for the above tableau and explain why.
      Answer: First, either P1 or P3 can execute. It doesn't matter which you choose. If you choose P1, then you then have enough resources to grant P2's request, and P2 can end. Then one has enough resources to grant P4's request. It does not matter when P3 is executed in the schedule.

      Thus the possible completion schedules are P3-P1-P2-P4, P1-P3-P2-P4, P1-P2-P3-P4, P1-P2-P4-P3.

      There was a bit of confusion here among several people about whether the completion schedule must be serial or parallel. It is serial. Parallel completion is not required for safety. At a deeper level, in Lamport's algorithm, completion schedules with parallelism are not considered "more safe" than serial schedules.

    2. If P1 requests 1 more unit of R1, is the resulting tableau safe? Why?
      Answer: This is safe because P1 can still run; there are enough remaining resources to grant the one unit.
    3. If P1 requests 2 more units of R1, is the resulting tableau safe? Why?
      Answer: This is unsafe, because there are not enough resources to grant P1's request. Since in the completion schedule it must run before P2, P4, these resources will not be released according to Banker's algorithm assumptions.
  7. Write a version of sem_wait(void) that has the exact behavior of sem_wait, but uses mutexes to turn a regular integer global variable
    int sem;
    into a semaphore.
    Answer: I quite intentionally gave you relevant code in a previous problem! The key is to use one mutex to block when the semaphore will go beneath 0, and another to lock the critical section. The semaphore never goes beneath 0. Thus one approach is:
     
    pthread_mutex_t crit; 	// lock for critical section 
    pthread_mutex_t waiter; // lock that makes code block during sem_wait 
    int sem; 		// the actual semaphore substitute 
    
    // the required code and answer to the problem
    void my_sem_wait() {
       pthread_mutex_lock(&waiter); // block until available 
       pthread_mutex_lock(&crit);
       --(sem);
       if (sem>0) { 
    	pthread_mutex_unlock(&waiter);
       } 
       pthread_mutex_unlock(&crit);
       return 0; // always
    }
    
    //-------------------------------
    // the answer above only makes 
    // sense in the following context
    //-------------------------------
    
    // the matching post is: 
    void my_sem_post (int sem) {
       pthread_mutex_lock(&crit);
       ++(sem);  
       if (sem>0) { 
    	pthread_mutex_unlock(&waiter); 
       } 
       // ignore "already unlocked" error
       pthread_mutex_unlock(&crit);
       return 0; // always
    }
    
    // and here is how one would initialize it. 
    void my_sem_init(int value) { 
       pthread_mutex_init(&waiter,NULL); 
       pthread_mutex_init(&crit,NULL); 
       sem = value; 
       if (sem<0) sem=0; // don't allow values < 0
       if (sem==0) {
    	 pthread_mutex_lock(&waiter); // value is 0 now
       } 
       return 0; 
    } 
    
    One subtlety of the above code is that according to 'man sem_wait', the semaphore never goes beneath 0. It blocks and queues up threads that are trying to take it beneath 0.

    Most of the class tried to do it with one mutex, and that isn't even possible. Those who tried made the matching sem_post impossible to write.

  8. (Extra credit; advanced) We mentioned in class that there is a method whereby one can avoid mutex locks by crafting each critical section to be logically atomic. What are the limits of this method? What kinds of atomicity could one use?
    Answer: There are only three ways that one can make something logically atomic:
    1. Instruction atomicity: the instruction runs isolated, cannot be interrupted, and cannot be run concurrently in multiple threads.
    2. Scheduler atomicity: one turns off the scheduler and all concurrent cores to isolate a section.
    3. Lock atomicity: one honors critical section locks.
    Of these, scheduler atomicity is quite expensive, because one has to stop "everything else" (and presumably all other useful work) in order to achieve atomicity, while instruction atomicity is limited to a small number of (machine language) instructions that must -- by their nature -- be atomic over all cores active in the machine.

    Thus, the drawbacks of not using locks include inefficiency (due to shutting down other components) and the lack of a large suite of instructions that do not shut down the hardware.

    Scoring: 10 if got all of these points, +5 if some elements present, +2 if any relevance to answer.

    A small number of people thought this was about resource management. It is about how we provide exclusive access to critical sections. Thinking of the critical section as a resource is just one way to think about this.