Tietojenkäsittelytieteen laitos

Homework

Concurrent Programming, Autumn 2006, HW 3

These will be covered in practise session during the week 46, 13-17.11.2006.
Note: Everybody should be in a study circle by now. If you are not and still need partner(s), please send email to instructor.

1. Look at Dekker algorithm (alg 3.10, p.60). At the end of the algorithm variables turn and wantp (or wantq) are given new values. Could one also give them in reverse order (statement p10 before p9)? Prove your conclusions.
    
2. Exercises 3.11 and 3.12 from text book
    
3. Exercise 4.1 from text book
    
4. Exercise 4.2 from text book
    
5. [2 hwp] We have six variables X1, X2, X3, X4, Ctrl, and Sum in shared memory. They all have initial values zero. We have two 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 (50, 50, 50, 50, 100 ja 200).
   
   Implement this program in BACI, using only (other) shared variables for control. Possible waitings can be implemented with busy-wait type loops: while (...) {};
   BACI process control will always finally yield execution turn to other processes, i.e., waiting is not for ever.
   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 3 or 10 computing programs?
      (You do not need to implement this, but you may if you want!)

 

---

Teemu Kerola 06.11.2006 16:38