Concurrent programming, Final examination 15.8.2008

Write in each answer sheet your name, signature, student id, course name and page number.

[15 p] Critical section.
1. Give a concrete (pseudocode) example on critical section. Explain in detail, what is the actual problem here and how it should be solved.
2. Show (with pseudocode), how critical sections are protected with disabling interrupts.
  In what type of environment would this be a sensible solution? Why?
  In what type of environment would this not be a sensible solution? Why?
3. Show (with pseudocode), how critical sections are protected with busy-wait loop (e.g., with a test-and-set instruction).
  In what type of environment would this be a sensible solution? Why?
  In what type of environment would this not be a sensible solution? Why?
4. Show (with pseudocode), how critical sections are protected with semaphores.
  In what type of environment would this be a sensible solution? Why?
  In what type of environment would this not be a sensible solution? Why?
5. Show (with pseudocode), how critical sections are protected with monitors.
  In what type of environment would this be a sensible solution? Why?
  In what type of environment would this not be a sensible solution? Why?

[15 p] Mixed up with semaphores
The solution to the producer-consumer problem given below does not work correctly.

    char buffer[n];
    int  start = 0,  end = 0;
    sem  empties = n, fulls = 1, turn = 0;
   
    process Producer[i=1 to M] {               process Consumer[i=1 to N] {
    char data;                                 char result;
    ....                                       .....
    while (true) {                             while (true) {
        .....                                      .....
        produce data;                              P(turn);
        P(empties);                                P(fulls);
        P(turn);                                   result=buffer[start];
        buffer[end] = data;                        start= (start + 1) % n;
        end = (end + 1) % n;                       V(turn);   
        V(fulls);                                  V(empties);
        V(turn);                                   use result;
        }                                          }
    }                                           }

What errors there are in the solution and what functional problems do these errors cause? Give one scenario leading to a functional problem.
Would the solution work correctly, if there were only one producer and one consumer (M=N=1)? Explain.
Is it possible to increase parallelism for producers and consumers? If it is, then explain how.
Fix the given code to work correctly or write your own solution. Remember to add comments to your code though the code given does not include any comments! Explain how the errors in part (a) and performance issues in part (c) are taken into account.

[15 p] Monitors
1. What is a monitor? What problem does it solve?
2. What advantages/disadvantages do monitors have as compared to semaphores? Give examples.
3. What does the concept monitor signaling semantics mean?
  What is IRR (Immediate Resumption Requirement, "Signal and Urgent Wait", E<S<W) signaling semantics?
  How does IRR in practice differ from (e.g.) Java signalling semantics (E=W<S)?
4. When writing program code invoking (calling) monitors, does one have take into consideration the signalling semantics used in that monitor? If the answer is yes, how? If the answer is no, why not?
[15 p] Deadlocks
1. [6 p] What does the concept deadlock mean? Give example in pseudocode. When can deadlock occur?
2. What does the concept livelock mean? Give example in pseudocode. When can livelock occur?
3. What does the concept starvation mean? Give example in pseudocode. When can starvation occur?
4. How does Dijkstra's Banker's Algorithm work in principle? What problems does it actually solve? What information does it need and how does one obtain them? Will the algorithm always terminate? When is the algorithm used and how is it's result used?