Concurrent programming, exam 13.8.2010         Other side in English

1. [18 p] Critical section. Observe a situation where 5 processes are concurrently executing a code segment that includes (high level language) code fragment "X=X+1". Integer valued variable X is in shared memory and it is initialized to zero (0). Code fragment "X=X+1" is keeping count of the processes that have compled this code segment. Assume first that code fragment "X=X+1" is not protected as a critical section.
   1. What final values are possible for X?
   2. Give a machine language level scenario, where final value for X is one (1).
   3. Give a machine language level scenario, where this critical section problem is not materialized. What is the final value for X in this case? What does it mean that the program executes correctly in this scenario?
   4. How would you protect this critical section in a uniprocessor environment? Explain. Why use this method and not something else?
   5. How would you protect this critical section in a multiprocessor environment? Explain. Why use this method and not something else?
   6. Assume now that the computation is distributed. What does that (distributed computing) mean in practice? How would one now implement the code fragment "X=X+1" and how would one now solve the critical section problem for it?
       
       
2. [9 p] Program has N threads and computation is based on multiple successive phases (phase 1, 2, ..., i, i+1, ...). Each thread must complete current phase (phase i), before any of them can proceed with the next phase (phase i+1). The same synchronization problem repeats now with phase i+1.
   

   Give the solution for this synchronization problem using a monitor. Explain why your solution is correct. Notice that only the synchronization problem is solved inside the monitor and actual computational work must be done outside the monitor. State all the assumptions needed for your monitor.
    

3. [9 p] Producer Consumer problem. There are many (K) producers and consumers. Buffer size (N) is finite. Describe the problem and give it a semaphore based solution. State all the assumptions needed for your semaphores. What type of synchronization and/or communication problems are involved and how are they solved?