Concurrent programming, exam 19.1.2010         in EnglishToisella puolella suomeksi

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

  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. What is the deadlock problem? Give a concrete example on deadlock. Which four conditions must be in effect for deadlock to occur? Show that they exist in your example. Explain the main principles of Dijktra's deadlock detection algorithm. What should one do if a deadlock is detected? Which two methods can one use to prevent deadlocks in advance?
     
  3. [9 p] The program has N threads and computation is based on multiple successive phases. Each thread must complete current phase (phase i), before any of them can proceed with the next phase (phase i+1). The same synchronization problem repeats now with phase i+1.

    Give the solution for this synchronization problem using semaphores. Explain why your solution is correct.
     
  4. [9 p] Bees and bear. Friendly bees (N bees) are feeding a 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 to a pot, filling the pot one portion each bee 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 to sleep. Below is a rough monitor solution where the bees fill up the pot one bee at a time outside the monitor.
    1. Modify the example so that at most 50 bees can be filling up the pot concurrently.
    2. How would your solution change, if the monitor would use IRR semantics?

      ada prot obj example