Concurrent programming, exam 18.1.2011  

Write in each answer sheet course name, date, your name, signature and student id.

  1. [9 p] Critical section. 
    1. Give a code level example on a situation, where critical section is composed of two distinct code segments. Explain.
    2. Give an example of a situation where it would be wise to protect critical sections with semaphores, but not with busy-wait instructions or interrupt disabling? Why?
    3. Give an example of a situation where it would be wise to protect critical sections with monitor instead of semaphores? Why?

     
  2. [9 p] Deadlocks.
    1. [2 p] What is the deadlock problem? Give a concrete example on deadlock, based on the Dining Philosophers problem.
    2. [4 p] Which four conditions must be in effect for deadlock to occur? Show that they exist in your example.
    3. [3 p] Explain the main principles of Banker's algorithm to prevent deadlocks from occurring. How would it work in the Dining Philosophers problem, using your example in part (a)?
       
  3. [9 p] Monitor.
    1. [1 p] What is a monitor?
    2. [2 p] How does a monitor solve critical section problem?
    3. [2 p] How does a monitor solve synchronization problem?
    4. [2 p] In which different places in the monitor may the processes executing there may need to wait for their execution turn?
    5. [2 p] What does the concept monitor signalling semantics mean? How does monitor signalling semantics affect the implementation of the monitor methods? How do the programs using the monitor need to take in consideration the monitor signalling semantics?

  4. [9 p] Readers/writers Problem. There is one solution for the problem on reverse page.
    1. [2 p] The given solution involves baton passing split semaphores. Explain what this means and how does it present itself in the solution.
    2. [2 p] Assume that no one is using the database. First two readers (r1 and r2) want to use it, then one writer (w3), and finally third reader (r4). The first reader (r1) is still reading the database when the third reader (r3) arrives. How does the algorithm work in this case? Explain the algorithm operation up to the moment when all four processes have completed their database access. Who waits and where? Who releases whom and when? Who can use the database and when?
    3. [2 p] Given algorithm gives preference to readers. Explain what this preference means and how is it implemented in the algorithm.
    4. [3 p] Modify the algorithm so that it gives preference to writers. Explain what this preference means and how is it implemented in the algorithm. How does the algorithm now work with the situation given in part (b)?
      (You may give your modification directly to the algorithm given on the reverse side. In that case remember to return exam paper and write your name and signature on it)

img