Concurrent programming, exam 1.6.2010         SuomeksiToisella puolella suomeksi
Write in each answer sheet course name, date, your name, signature and student id.
  1. [9 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 referenced in 5 different locations (A, B, C, D and E) in program:  
     A: X <- 7      B: some1 <- X    C: Y <- 87    D: some4 <- X    E: some5 <- Y
        Y <- 4         some2 <- Y                                      Y <- 0
        Z <- X+Y       some3 <- 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 E, variable value Y must be reset to zero immediately after reading its value.
    1. Which of these (pseudo-)code sequences (A, B, C, D and E) must be protected as critical section and why? Who do the other sequences have no need for protection?
    2. Give a scenario leading to an erroneous situation, if the critical sections are not protected. Explain why the result is erroneous and what caused the error. Will the same error happen every execution time?
    3. Show (with pseudo-code), how critical sections in these threads are protected with busy-wait loops (e.g., with test-and-set instruction). In what type of environment would this be a reasonable solution? Why?
       
  2. [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.
    So, the thread pseudocode is roughly as follows: 
    for i=1 to nPhases
  <compute Phase i>
  Boom.PhaseDone(myId)
    Give the solution for this synchronization problem with monitor Boom. Monitor Boom has method PhaseDone, which each thread calls at the end of each execution phase. Explain why your solution is correct.
     
  3. [9 p] Questions
    1. Explain the concept private semaphore? When would you use one?
    2. What is the difference between semaphore wait() and monitor waitC() operations?
    3. How does Bankers algorithm differ from Dijkstra's DDA-algorithm? What do they have in common?
       
  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 semaphore solution.
    1. Modify the example below so that many bees (at most 50) can be filling up the pot concurrently.
    2. Modify the example below so that there are two bears which are woken up to eat in alternate turns.
       
                                             Semaphore Pot