in EnglishToisella puolella suomeksi

Concurrent programming (4 cr), Course examination 2.6.2009

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

  1. [9 p] Critical section
    1. Give an example of a situation where it would be wise to protect critical sections by disabling interrupts, but not with busy wait (e.g., with test-and-set instructions) or semaphores? Why?
    2. Give an example of a situation where it would be wise to protect critical sections with busy-wait instructions, but not with interrupt disabling or semaphores? Why?
    3. 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?

     
  2. [9 p] Deadlocks
    1. [3 p] Give a semaphore based solution to Dining Philosophers problem, that is vulnerable to deadlock. Give a deadlock scenario. Explain, why the sceraio leads to deadlock.
    2. [6 p] Deadlock can occur only when certain conditions are met. Describe these conditions and, for each of them, describe how you would modify your previous answer (in part a) such way that it avoids deadlock by breaking just this condition.

     
  3. [9 p] Bees, bear and semafors. Friendly bees (N bees) are feeding trapped bear by collecting honey for it. The life of the trapped bear is just eating and sleeping. The bees collect honey and carry it into a pot, filling the pot one portion at a time. When the pot is full (H portions of honey), the last bee to deposit honey wakes up the bear to eat. The bees pause filling the pot until the pot is empty again. Once the bear is finished eating the pot empty, it allows the bees to deposit honey again and goes back to sleep.

    Give the synchronization solution for filling up the pot and emptying it with a semafors. Present the pseudocode for the bees (N processes) and the bear. Explain verbally which situations demand mutual exclusion and/or synchronization and how those problems are solved in your solution. Make the required assumptions concerning the semafors and write them down.
     
  4. [9 p] Bees, bears and IRR monitors. Friendly bees (N bees) are feeding trapped bear by collecting honey for it. The life of the trapped bear is just eating and sleeping. The bees collect honey and carry it into a pot, filling the pot one portion at a time. When the pot is full (H portions of honey), the last bee to deposit honey wakes up the bear to eat. The bees pause filling the pot until the pot is empty again. Once the bear is finished eating the pot empty, it allows the bees to deposit honey again and goes back to sleep.

    Give the synchronization solution for filling up the pot and emptying it with a monitor using IRR (E<S<W) signaling semantics. So, the monitor contains only the synchronization problem solution - collecting honey, depositing in into the pot, and emptying the pot happens outside the monitor. Present the pseudocode for the bees (N processes), the bear and the monitor. Explain verbally which situations demand mutual exclusion and/or synchronization and how those problems are solved in your solution. Explain also, which part of your solution is based on IRR signaling semantics. Make the required assumptions concerning the other monitor features and write them down.