Tietojenkäsittelytieteen laitos

Homework

Concurrent Programming, HW 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.

1. [2 hwp] 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.
   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?
       
2. Road crossing
   1. Show that the four conditions for deadlock are fulfilled in the road crossing example (see Fig. 6.1 [Stall05], or lesson 5 slide 8).
   2. For each condition, give an example on how one migyht prevent it from happening. Try to make the examples such that only one condition is not met, but the others can still be met.
       
3. Look at the example on how to avoid deadlock with Banker's algorithm (see Fig. 16.11 [Bacon93], or lesson 5 slides 44-45)
   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. We have the following subroutines and their operations need to be synchronized:
   1. When subroutine PrintOut (Pr, Db, ...) is running, no one else can use printer Pr or database Db.
   2. When subroutine Update (Db, ...) is running, no one else can use database Db.
   3. When subroutine Combine (Db1, Db2, Db3, ...) is running, no one else can use databases Db1, Db2, or Db3.

Implement the synchronization with semaphores, when actual databases are Payroll, Personnel, Customers and Inventory.

1. Explain, why your solution meet the requiremets stated above.
2. Explain, how mutual exclusion is implemented.
3. Explain, why your solution does not lead to a deadlock.
4. Explain, why your solution does not lead to starvation.
5. Explain, why the problem setup is unrealistic. Give at least two reasons. 

---

Teemu Kerola 27.11.2009 12:44