Tietojenkäsittelytieteen laitos

Homework

Concurrent Programming, Autumn 2006, HW 4

See Problems 2-4:
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.

When implementing this program in BACI, use only (other) shared variables for control. Possible waitings can be implemented with busy-wait type loops: while (xxx != 1) {};
BACI process control will always finally yield execution turn to other processes, i.e., waiting is not for ever, if there are other processes ready to excute.

1. Exercises 5.1 and 5.3 from text book.
    
2. Write in BACI program PlusMinus version, that does not protect critical sections properly. How do you know?

 
3. Write in BACI program PlusMinus version, that protects critical sections properly. How do you know? Explain.

 
4. Write in BACI program PlusMinus version, that may deadlock. What is fundamentally wrong in that program, i.e., where is the problem? How does deadlock make itself known in your program, i.e., how do you know it is deadlocked?

 
5. Show that the four conditions for deadlock are fulfilled in the road crossing example (see Fig. 6.1 [Stall05], or lesson 6 slide 5).
    
6. Look at the example on how to avoid deadlock with Banker's algorithm (see Fig. 16.11 [Bacon93], or lesson 6 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?
      

 

---

Teemu Kerola 23.11.2006 9:07