Tietojenkäsittelytieteen laitos

Homework

Concurrent Programming, Autumn 2007, HW 4

These will be covered in practise session during the week 47, 19-23.11.2007.

Program PlusMinus. We have six variables X1, X2, X3, X4, Ctrl, and Sum in shared memory. They all have initial values zero. We have five computing processes, each of which will execute a loop 50 times. The critical section in the loop does the following:

• If variable value Ctrl is odd, subtract 1 from each Xi. Otherwise, add 2 to each Xi.
• Finally add 1 to Ctrl and store the sum of all Xi's into Sum.

Once the computing processes have stopped, print out the values of all six shared variables.

1. Write a semaphore version of BACI program PlusMinus, that protects critical sections properly.
   Use BACI semaphores in your code.
   How do you know that your program is correct? Explain.
    
2. Show that the four conditions for deadlock are fulfilled in the road crossing example (see Fig. 6.1 [Stall05], or lesson 5 slide 5).
    
3. Look at the example on how to avoid deadlock with Banker's algorithm (see Fig. 16.11 [Bacon93], or lesson 5 slides 33-34)
   1. Process P2 requests resource R5 which is available. Can the request be granted without danger for deadlock?
   2. Process P4 requests resource R5 which is available. Can the request be granted without danger for deadlock?
   
    
4. [2 hwp] 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 thy 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. 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.
    

---

Teemu Kerola 06.11.2007 13:11