Concurrent programming, Exam 6.5.2011         in EnglishToisella puolella suomeksi

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

  1. [10 p] Critical section. Assume that multi-threaded program has three variables (X, Y and Z) in shared memory and we want to protect them with critical section. Variables are may be referenced in 7 different code segments (A, B, C, D, E, F and G) in program, but in different program versions all those code segments are not used.  
     A: X <- 7    B: some1 <- X   C: Y <- 87      E: some5 <- Y   G: some5 <- Y
    Y <- 4       some2 <- Y                                      Y <- 0
    Z <- X+Y     some3 <- Z   D: some4 <- X   F: some6 <- Z
    In location A, the old values of variables Y and Z must not be visible once X has received a new value, and the new value of Z must the the sum of new values for X and Y. In location B, values for variables some1, some2 and some3 must be those of X, Y and Z at execution start time for this code sequence. In location G, variable value Y must be reset to zero immediately after reading its value.
    1. Assume that only code segments A, D, E, and F are used in program code. Which of these code seqments must be protected as critical section? Explain.
    2. Assume that only code segments B, C, D, E, and F are used in program code. Which of these code seqments must be protected as critical section? Explain.
    3. Assume that only code segments C, E, and G are used in program code. Which of these code seqments must be protected as critical section? Explain.
    4. Assume that all code segments A, B, C, D, E, F, and G are used in program code. Which of these code seqments must be protected as critical section? Explain.
       
  2. [10 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] Assume that you found a deadlock in 40 thread computation, and threads A, B, and C (of those 40 thread) are found to deadlocked. What do you do now when you do not want to interrupt the overall computation and you have been prepared for this circumstance? Make the needed assumptions and explain how your solution will still succeed with the overall computational goal.
    3. [4 p] Give two different methods to prevent deadlocks occurring at all. Explain basic principles of those methods and explain how they prevent deadlock from occurring. Explain how the methods would be used in the multi-threaded computation given in previous part (b).
       
  3. [10 p] Bees, bears and IRR monitors. Friendly bees (N bees) are feeding trapped bears (B bears) by collecting honey for them. The life of the trapped bears is just eating and sleeping. The bees collect honey and carry it into a pot, but at most 60 bees can be filling the pot at a time. When the pot is full (H portions of honey), the last bee to deposit honey wakes up one bear to eat. The bees pause filling the pot until the pot is empty again. Once a bear is finished eating the pot empty, it allows the bees to deposit honey again and goes back to sleep. Make sure, that no bear will starve.

    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 it into the pot, and emptying the pot happens outside the monitor. Present the pseudocode for bees (N processes), bears (B processes) and the monitor.