Concurrent programming, exam 27.9.2011         Toinen puoli suomeksi

Write in each answer sheet the course name, date, your name, signature and student id.

1. [9 p] Critical section. 
   1. Give a code level example on a situation, where critical section is composed of two distinct code segments. Explain.
   2. Assume, that (i) critical section takes 10-30 machine instructions, (ii) critical section execution takes less than 0.001% of program execution time, (iii) multiple threads are executed concurrently in 8-core system, and (iv) threads have access to shared memory. How would you protect the critical section in this case? Explain your decision.
   3. Assume now, that requirement (iv) in previous case (b) is modified so that the threads do not use shared memory even though they execute in the same system. How would you protect the critical section in this case? Explain your decision.
       
2. [9 p] Deadlocks.
1. What is the deadlock problem? Which four conditions must be in effect for the deadlock to occur?
2. [3 p] Explain the main principles of Dijktra's deadlock detection algorithm. What should one do if a deadlock is detected? What should be done, if the algorithm does not find deadlocked processes?
3. How can one prevent deadlocks in advance? Give at least 2 different approaches.
4. Explain the main principles of Banker's algorithm and to what problem it is a solution for.
    
3. [9 p] Boom synchronization with semaphors. The program has N threads and computation is based on multiple successive phases. Each thread must complete current computation 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 semaphores. Remember the initalizations for the next phase. Explain why your solution is correct.


4. [9 p] Monitor.
1. [1 p] What is a monitor? To what problem is monitor solution for? How does the use of monitors relate to use of semafors?
2. How does a monitor solve the critical section problem? In what parts of the monitor code does critical section begin and end?
3. How do monitor condition variables differ from semafors? Consider at least intended use, internal structure and operations on them?
4. What does the concept monitor signalling semantics mean? How does monitor signalling semantics affect the implementation of the monitor methods? How do the programs using the monitor need to take in consideration the monitor signalling semantics?
5. (part d continued) Give a concrete pseudo code example where the same code works with one signalling semantics, but not with another. Explain why not.