Concurrent programming, exam 22.9.2009

Toisella puolella suomeksi

Concurrent programming (4 cr), Course examination 22.9.2009

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

[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?
2. Show (with pseudo-code), how critical sections in these threads 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 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?
[9 p] Deadlock. We have four threads (A, B, C and D), each of which executing the codes given below. We have no knowledge on execution speeds - so we do not know how much time passes between semaphore operations. Each semaphore has initial value 1. You do remember that semaphore operations are P (i.e., wait) and V (i.e., signal).
1. ... P(s1) ... P (s2) ... P(s3) ... V(s3) ... V(s2) ... V(s1) ...
2. ... P(s2) ... P (s4) ... P(s5) ... V(s5) ... V(s4) ... V(s2) ...
3. ... P(s5) ... V(s5) ... P (s1) ... V(s1) ... P(s3) ... V(s3) ...
4. ... P(s6) ... P (s5) ... P(s1) ... V(s1) ... V(s5) ... V(s6) ...
All four threads are started at the same time, and are thus concurrently in execution.
1. Resource reservation graph displays, for each process, resources allocated and resources wanted. Describe the deadlock problem in terms of allocatable resources and resource reservation graph. What are the allocatable resources in this case? In which order the threads reserve/release them? Draw the resource reservation graph for the scenario where all four threads reach their first semaphore operation (P(s1), P(s2), P(s5), or P(s6)) at the same time.
2. Give a scenario leading to a deadlock and the resource reservation graph at deadlock time.
3. What are the four requirements needed for a deadlock and how are they materialized in this case.
[9 p] One-lane bridge There runs a river between two villages A and B and the villages are connected by a narrow one-lane bridge, where cars are allowed to drive only in one direction in a time. When cars are passing the brigde from A to B, then the cars willing to cross the bridge from B to A have to wait. The bridge is not very sturdy, and so maximum 5 cars are allowed on the bridge at a time. The car processes call procedure enter_bridge(direction) before using the bridge, and procedure exit_bridge(direction), when they leave the bridge:
```
 Process car (direction) {
    .....
    enter_bridge(direction);
    drive over the bridge
    exit_bridge(direction); 
    ......
    }
```
Give the code for procedures enter_bridge(direction) and exit_bridge(direction). The solution must be based on semaphores and P and V operations. The solution does not need to be fair, which means that the waiting times on the other end may be very long. (If there is a steady flow of cars going from A to B, then cars going from B to A may wait very long time.) Cars going in some direction must be allowed to proceed to the bridge in FCFS order.
[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.