Toisella puolella suomeksi

Concurrent programming, Final examination 23.9.2008

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

1. [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(s1) ... V(s3) ... V(s2) ...
   2. ... P(s2) ... P (s4) ... P(s5) ... V(s2) ... V(s4) ... V(s5) ...
   3. ... P(s5) ... P (s6) ... P(s1) ... V(s6) ... V(s1) ... V(s5) ...
   4. ... P(s5) ... P (s1) ... V(s1) ... P(s3) ... V(s5) ... V(s3) ...

   All four threads are started at the same time, and are thus concurrently in execution.

   1. Give a scenario leading to a deadlock and the resource reservation graphs leading to it.
   2. What are the four requirements needed for a deadlock and how are they materialized in this case.
   3. Will the the system always reach a deadlock? If yes, why? If no, then give one scenario that does not lead to a deadlock.
   
    
2. [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 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.
    
3. [9 p] Spaghetti in a monitor
   As a result of hard thinking the dining philosophers (N persons) had at last realized that it is really possible to eat spaghetti with only one fork and after having practiced for awhile had become very efficient eaters with one fork. Now they could eat even all at the same time and no one had to wait hungry for others to finish. But this caused a new problem as the spaghetti bowl at their table was almost always empty. The solution for this was to hire a help boy to make spaghetti. The philosophers can again return their normal routine of eating spaghetti and thinking. The boy makes more spaghetti, fills the bowl with it (M portions) and carries it to the table. Then the boy eats spaghetti in the kitchen (that is his salary) and falls asleep. Each philosopher when eating takes one portion of spaghetti. If the bowl is empty, the philosopher will wake up the boy to make more spaghetti.
   
   Represent the philosophers and the help boy as processes and use a monitor for their synchronization. Write code for the monitor and for the processes that simulate the actions of the philosophers and the help boy.
    
4. Distributed Mutual Exclusion
   Look at the attached Ricart-Agrawala Algorithm 10.2.
   1. What is the meaning of Main process? What is the meaning of Receive process? What is it needed for? Could one combine it with Main process? What is the meaning of deferred set?
   2. Assume that three processes (A, B and C) want to get into critical section at the same time. Last time critical section was reserved for C, and before that to B. Who will get into critical section next and on what grounds? Show how the selection is made. Especially show all messages (sender, receiver, message type, message contents) involved in the decision.
   3. Assume now that the process selected in previous case (b) has completed its critical section and wants to have it again. Who (A, B or C) will now get into critical section next? Can it be the same process as in the previous case?
   4. Can all processes get the same myNum value? If yes, what prevents many processes to access critical section concurrently? If no, explain why not?