Concurrent programming, exam 17.6.2011         suomeksiToisella puolella suomeksi
  

Write in each answer sheet course name, date, your name, signature and student id.
Course grading is done only in July.

  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 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, 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, 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.
    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"? (Use area, structure, operations, implementation, ...)
    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 are many producers and consumers. 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 producer, consumers and the monitor. Explain why your solution is correct.