Toisella puolella suomeksi

Concurrent programming (4 cr), Course examination 7.4.2009

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

1. [9 p] Look at Algorithm 2.10 below. Assume K value 10.
    
                
    
   1. Can variable n have end-value 10? If yes, give a scenario for it. If not, why not?
   2. Can variable n have end-value 11? If yes, give a scenario for it. If not, why not?
   3. Can variable n have end-value 0? If yes, give a scenario for it. If not, why not?
   4. Can variable n have end-value 1? If yes, give a scenario for it. If not, why not?
   5. What is thre real problem here and how should one fix it so, that the end-value for n would always be 0.
       
2. [9 p] Deadlocks. System S has five resources: large memory blocks A (2 units) needed for data processing, data base B (1 unit), data base C (1 unit), printers D (2 units) and keyboard focus E (1 unit). Each resource can be used only one process at a time.
   
   System S has four processes, P1-P4. P1 has one unit each of resources A, C and D. P2 has one unit each of resources A and B. P3 has one unit of resource D. P4 has no resources reserved for it currently.
   
   To advance now, P1 needs one unit each of resourecs B and E, P2 needs one unit each of resources C and E, P3 needs one unit of resource E, and P4 needs one unit each of resources A, C and E.
   
   
   1. What is a deadlock? What does it mean that the system is not deadlocked?
   2. When can a system be deadlocked?
   3. Is the system S deadlocked or not?
   4. How would one check deadlock existance in system S using Dijkstra's Deadlock Detection Algorithm (DDA)? It uses arrays A (allocation matrix) and Q (request matrix) as well as vectors R (all resources), V (free resources) and W (working vector).
   5. How can one prevent deadlock from appearing in advance (in general and specifically in this case)?
       
3. [9 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.
       
4. [9 p] One-lane bridge with semaphores
   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 noy very sturdy, so maximum amount of 10 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 thy leave the bridge.

    Process car [i = 1 to N] {
       .....
       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 (wait and signal). The solution does not need to be fair, which means that the waiting times on the other end may be very long. However, the cars must be allowed to eneter the bridge in arrival order.