Concurrent programming, exam 20.1.2012                      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. There is one code segment u1 that updates the values of variables f1, ..., f8 and also another code segment r1 that only reads the values of variables f1, ..., f8.
    1. Under what circumstances neither of code segments (u1 and r1) must be protected as critical section?
    2. Under what circumstances both of code segments (u1 and r1) must be protected as critical section? Do they then belong to the same critical section, or do they form two different critical sections?
    3. Under what circumstances code segment u1 must be protected as critical section, but r1 does not need to protected as critical section?
       
  2. [9 p] Deadlocks.
    1. [2 p] What is the deadlock problem? Give a concrete example on deadlock, based on the Dining Philosophers problem.
    2. [4 p] Which four conditions must be in effect for deadlock to occur? Show that they exist in your example in part (a).
    3. [3 p] Based on previous four conditions (part b), give three different methods to prevent deadlocks in advance with Dining Philosophers Problem. Explain, why each method works to prevent deadlocks.

  3. [9 p] Producer-Consumer problem. There is one producer and one consumer. Buffer size is 1000.
    1. Describe the problem. Especially explain, what synchronization and communication problems are involved. What do you gain with larger buffer?
    2. Give a solution using semafors. Present the pseudocode for producer and consumer. Declare clearly all your semafores with their initial values. Explain why your solution is correct.
    3. Assume now, that we know from th eoverall system logic that the number of elements in the buffer can never be more than 10. How does this affect the problem solution and the synchronization and communication problems in it. Give the solution using semafors. Present the pseudocode for producer and consumer. Declare clearly all your semafores with their initial values. Explain why your solution is correct.
       
  4. [9 p] Monitor.
    1. [1 p] What is a monitor?
    2. [2 p] How does a monitor solve critical section problem?
    3. [2 p] How do condition variables (and operations on them) differ from semaphores?
    4. [4 p] Give the monitor-based solution the Producer-Consumer problem in Problem 3. Present the pseudocode for producer, consumer and the monitor. Explain why your solution is correct.
      Especially remember, that only the synchronization problem should be solved in the monitor and all other work ("producing" buffer items, buffer filing/emptying, "consuming" buffer items) happens outside the monitor.