in English Toisella puolella suomeksi

Concurrent programming, Final examination 27.3.2007

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

  1. [9 p] Monitor and protected objects
    1. What is a monitor? What problem does it solve? What advantages does it have as compared to semaphores? What disadvanteges?
    2. What is monitor "signaling semantics"? What is IRR (Immediate Resumption Requirement, "Signal and Urgent Wait", E<S<W) signaling semantics?
    3. 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.
       
  2. [9 p] Deadlocks
    1. Give a semaphore based solution to Dining Philosophers problem, that is vulnerable to deadlock. Give a deadlock scenario.
    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. Show, how DDA is used to detect the deadlock in your solution given in the 1st part (a) of this problem.
       
  3. [9 p] Linda.
    1. What is Linda and how is it used?
    2. How does the Algorithm 9.6 below work? What type of computational environment is it designed for? How does the algorithm end?
    3. Modify Algorithm 9.6 so that even with one or more worker process dying at any time the result is still correct?
  4. [9 p] One lane bridge. An island is connected to the mainland by a narrow bridge, where cars are allowed to drive only in one direction in a time. The car processes call procedure enter_bridge(direction) before using the bridge, and procedure exit_bridge(direction), when they leave the bridge. The parameter direction is the driving direction: “to the island” or “from the island”. The code for the car processes is 
     process car[1 to N] {
       ...
       enter_bridge(direction);
       drive on bridge;
       exit_bridge(direction);
       }

Give the code for procedures enter_bridge() and exit_bridge(). The solution must be based on semaphores and must allow several cars on bridge driving to the same direction. Waiting cars can proceed only after all cars crossing the bridge in the opposite direction have completed the crossing. The solution is not fair, because the waiting times on the other end may be very long. When the waiting ends, the cars must be allowed to proceed in FCFS order.