Concurrent programming, exam 19.8.2011         suomeksiToisella puolella suomeksi
  

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 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] Solutions for Critical Section (CS) problem. For each Critical Section solution method given below, give two answers: (i) when and in what environment can one solve the CS with this method? (ii) when and in what environment, and why one can not solve the CS with this method?
    1. disabling interrupts
    2. lock variable and busy-wait
    3. semaphore
    4. monitor
    5. Ricart Agrawala token-passing algorithm
       
  3. [9 p] Dining Philosophers and Semaphores
    1. [2 p] Describe the Dining Philosophers problem. Especially explain, what kind of synchronization and/or communication problems are involved.
    2. [2 p] What is a "semaphore"? (Use area, structure, operations, implementation, ...)
    3. [3 p] Give a deadlock free semaphore solution to the Dining Philosophers problem. Explain especially, how the synchronization and/or communication problems you mentioned are solved there.
    4. [2 p] Prove (or give an exhaustive explanation), that your solution is deadlock free.

  4. [9 p] Producer-Consumer problem and Monitor. There is one producer and one consumer. The consumer is much faster than the producer, and thus in practuce the buffer size (N) is infinite.
    1. [3 p] Describe the problem. Especially explain, what synchronization and communication problems are involved. What is the effect of theorethical infinite buffer size even though in practice the buffer is of course implemented with finite size?
    2. [6 p] 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.