Comp111 -- Midterm Exam Review 1 Answers

Midterm Exam Mon Nov 6, 2006 - open book and notes

Midterm topics

All review questions in the book are fair game, as well as questions similar to assigned or auxiliary problems. The exam is open book and notes.

  1. Explain exactly why monitors are preferable to semaphores, with examples.
    Sketch of answer:
    The key is actually really subtle. A monitor is "stateless", which means that it does not retain a state between firings. This makes enumeration proofs of freedom from deadlock easier than for stateful things like semaphores, which often have a state explosion during the proof! For example, if we rewrite producer-consumer in terms of monitors, the assumable states are not proportional to the number of monitors!
  2. Compare overhead of the banker's algorithm with overhead of deadlock detection and kill. In which situations is each superior?
    Sketch of answer:
    The key is to figure out what you want to preserve. Suppose we want optimal throughput. Then the banker's algorithm is better than detect-and-kill, because in the latter case processes must be started over in order to complete. On the other hand, consider a time-sharing environment in which programs often have "runaway" bugs. Then the banker's algorithm is inferior to "detect and kill" because its assumptions are incorrect. Particularly, the assumption that all processes actually require what they request is incorrect in a situation where a student is debugging and is just as likely to interrupt a program with control-C as to keep it running!
  3. Consider the following resource allocation graph. Is the system deadlocked? If so, which processes are involved?


    Answer:
    Yes, it is deadlocked. There is a cycle P2,R3,P3,R2.
  4. Suppose for the banker's algorithm described in class, we have the following scheme:
     
                requested     allocated 
                r1 r2 r3 r4   r1 r2 r3 r4 
    process 1   2  5  3  2    1  0  3  2 
    process 2   1  5  1  1    1  1  0  0
    process 3   3  3  3  3    3  3  3  3
    
    and suppose that the total of available resources is
     
    r1 r2 r3 r4
    12 12 7  9
    
    Is this a safe state? Why or why not?
    Answer:
    It is safe if all processes can complete, one at a time. Let's start with process 3, which has resources to complete. After removing process 3, the resource matrix is:
     
                requested     allocated 
                r1 r2 r3 r4   r1 r2 r3 r4 
    process 1   2  5  3  2    1  0  3  2 
    process 2   1  5  1  1    1  1  0  0
    
    And remaining resources include:
     
    r1 r2 r3 r4
    10  9  4  7
    
    At this point, process 2 can run. This results in the matrix:
     
                requested     allocated 
                r1 r2 r3 r4   r1 r2 r3 r4 
    process 1   2  5  3  2    1  0  3  2 
    
    and available resources are:
     
    r1 r2 r3 r4
    10 12  4  7 
    
    At this point, process 1 can run, so the state is safe.
  5. What is the impact upon deadlock if one forces a set of otherwise unconstrained processes to allocate one resource unit at a time, even if they need a large number of resource units?
    Answer:
    This is a subtle question. Resource allocation works "better" if one knows all resource requirements in advance. If one constrains a system to only one resource unit per request, one loses the ability to predict safety far in advance, and the system gets closer to saturation before one knows that it's saturated. In the banker's algorithm, things work a lot better if resource requests are made as blocks, because the remaining resources are much greater if one process tries to allocate and is denied a large block of resources.