Tietojenkäsittelytieteen laitos

Concurrent Programming, HW 5

1. Exercise 6.6 from text book.
    
2. [2 hwp] 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. The solution needs not to be fair, which means that 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. If you want, you can try out your algorithms in BACI, by placing the into the bridge simulator dummy solution. (While running the simulation, observe the values of shared variables west_bound and east_bound, and check that the "animated bridge" has proper number of of cars. You may tune the system parameters better if you so wish. If you have too much time, you may want to tune the simulation graphics better - see jBACI Concurrency Simulator User Guide).
   
   Check that your algorithm works at least in the following cases:
   1. First car comes to direction A or B?
   2. There are 5 cars on the bridge toward A, and a new one arrives towards A or B?
   3. There are 4 cars on the bridge toward A, a new one arrives towards B, and then a new car towards A?
   4. There are cars on bridge, and they leave making bridge empty. There were cars waiting in th eother direction.
   5. There are cars on bridge, and they leave making bridge empty. A new cars arrives towards A or B?
   6. Modify your answer to the situation where there can be at most 3 cars on the bridge due to weight limitiations.
       
3. Redo problem 1 in homework set 4 (BACI PlusMinus program) with monitor.
   1. Make a program version that does not protect critical sections properly. How do you know?
   2. Make a program version that protects critical sections properly. How do you know? Explain.
   3. How would your program need to be modified for 4 or 10 computing processes?
      Note, that you do not need to implement the suggested modification in BACI. But, you can try to do it anyway, if you want to.
   4. Would it be useful to have 10 computing processes? Why?
      What would be the upper limit for useful number of computing processes? Why

 
4. Look at the Algorithm 7.3 in text book (p. 152). Notice the typo in algorithm.
1. What significant differences does algorithm 7.3 have when compared to the multiple producers/consumers solution given in lectures (lecture 6, slide 16; Andrews, Fig 4.5)? Which one is better/worse and why?
2. What does the concept monitor signalling semantics mean?
3. Algorithm 7.3 is based on IRR signaling semantics. Give a scenario where the algortihm does not work properly if signalling semantics E=S=W were be used.
4. How should one modify the algorithm 7.3 for E=S=W monitor signalling semantics?