in English Toisella puolella suomeksi

Concurrent programming, Final examination 15.1.2008

Write in each answer sheet your name, signature, id-number, course name, and page nr/total nr of pages.

  1. [15 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? Especially, will location C need protection as it only changes one variable value? How about location D, where only one variable value is read? How about location E, where only one variable is read and then reset.
    2. Show (with pseudo-code), how critical sections are protected by disabling interrupts. In what type of environment would this be a reasonable solution? Why?
    3. Show (with pseudo-code), how critical sections 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?
    4. Show (with pseudo-code), how critical sections are protected with semaphores. In what type of environment would this be a reasonable solution? Why?
    5. Assume now that the program is implemented in distributed environment, and that variables X, Y and Z are located in shared file server. Variable values are read and written with messages. How should one protect the critical sections now in practice?

     
  2. [15 p] Monitors
    1. What is a monitor? What problem does it solve?
    2. What advantages do monitors have as compared to semaphores? Give an example.
    3. What advantages do semaphores have as compared to monitors? Give an example.
    4. What is monitor "signaling semantics"?
      What is IRR (Immediate Resumption Requirement, "Signal and Urgent Wait", E<S<W) signaling semantics?
      How does IRR in practice differ from (e.g.) Java signalling semantics E=W<S?
    5. What is the problem associated with monitor without IRR? Give a concrete example where signaling semantics without IRR will lead to erroneous result but where signaling semantics with IRR would work out fine.
       
  3. [15 p] Deadlocks
    1. What is a deadlock and when can the system deadlock?.
    2. How does Dijkstra's Deadlock Detection Algorithm (DDA) work in principle? It used arrays A (allocation matrix) and Q (request matrix) as well as vectors R (all resources), V (free resources) and W (working vector).
    3. Assume that DDA will find 3 deadlocked processes (threads) in your system. What happens next?
    4. How can one (statically) prevent deadlocks from occurring so that deadlocks need not to be considered at resource reservation times?
    5. How can one (dynamically) prevent deadlocks from occurring so that deadlock possibility is considered with each resource reservation?
       
  4. [15 p] Bees and semaphores. 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 carry honey to a pot, one portion each bee each time until the pot is full. When the pot is full (H portions of honey), the bee that deposited the last portion wakes up the bear. The bear starts eating and the bees pause filling the pot until the bear has eaten all the honey and the pot is empty again. Then the bear starts sleeping and bees start depositing honey again.

    The bees can deposit their honey into the pot concurrently, but the pot must never receive more than H portions of honey.

    Give the solution for filling up the pot and emtpying it with semaphores. Present he code for bees (N processes) and bear. Explain verbally which situations demand mutual exclusion and/or synchronization and how those problems are solved in your solution.