Concurrent programming, exam 17.8.2012                      Toisella puolella suomeksi  

This course is worth 6 cu, if you have done the project, and o/w 4 cu.
If you have done the project with earlier lecture course, please mention about it and give the year for your course.
Write in each answer sheet course name, date, your name, signature and student id.

1. [9 p] Critical section problem in multithreaded application in a multicore system. The values of shared variables f1, ..., f8 must be always consistent:  whenever they are updated, all values must be updated in a consistent fashion, and one should never be able to read inconsistent values.
   1. [3 p] Assume now, that there is only one code segment that updates the values of variables f1, ..., f8. Do you need a critical section to protect this code segment or not? Explain.
      There are also other code segments that read these values, but they are never run concurrently with updates. So, you may ignore them in this part (a) of the problem.
   2. Assume now, that code segment u1 updates the values of variables f1, ..., f8, and possibly concurrently executing code segments r1 and r2 read their values. What critical sections are now needed to protect code segments u1, r1 and r2? Explain.
   3. Assume now, that, in addition to part (b) assumptions, possibly concurrently executing code segment r3 only reads the value of f7. What critical sections are now needed to protect code segments u1, r1, r2 and r3? Explain.
   4. Assume now, that, in addition to part (c) assumptions, possibly concurrently executing code segment u2 only updates the value of f7. What critical sections are now needed to protect code segments u1, u2, r1, r2 and r3? Explain.
   
   
2. [9 p] Deadlocks. Application App with 4 threads (P, R, S and T) is using three resources (A, B and C) and that can sometimes lead to a deadlock. There is one of each resource, and you can not increase their number. each resourse may be used by only one thread at a time.
1. [3 p] Explain the deadlock problem. Give a scenario leading to a deadlock in application App. Present the scenario with appropriate pseudocode.
2. [3 p] Which four conditions must be in effect for deadlock to occur? Show that they exist in your scenario in part (a).
3. [3 p] Give some (one) concrete method that would prevent deadlocks from occurring in advance. Explain especially, how your method would work in the original deadlock scenario in part (a), and why it would prevent that deadlock from occurring.
    
3. [9 p] Semaphore
1. [4 p] What is a "semaphore"? (Purpose, structure, operations)
2. Explain concept "binary semaphore".
3. Explain concept "private semaphore".
4. Explain concept "blocking semaphore".
5. Explain concept "split semaphore".
6. Explain concept "baton passing" when used with semaphores.


4. [9 p] Producer-consumer problem. There is one producer and one consumer. Buffer size (N) is finite. Describe the problem and give a solution using a monitor with IRR (E<S<W) signalling semantics. So, the monitor contains only the synchronization problem solution and buffer filing/emptying happens outside the monitor. Present the pseudocode for (a) the producer, (b) the consumer and (c) the monitor. Explain why your solution is correct.