Concurrent programming, term exam 8.5.2012                 suomeksiToisella puolella suomeksi  

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

  1. [5 p] Boom (barrier) synchronization with semaphors. The program has N threads and computation is based on multiple successive phases. Each thread must complete current computation phase (phase i), before any of them can proceed with the next phase (phase i+1). The same synchronization problem repeats now with the new phase (phase i+1).

    Give the solution for this synchronization problem using semaphores. Remember the initalizations for the next phase. Explain why your solution is correct.

  2. [5 p] Bees, bears and IRR monitors. Friendly bees (N bees) are feeding trapped bears (B bears) by collecting honey for them. The life of the trapped bears is just eating and sleeping. The bees collect honey and carry it into a pot. Many bees can fill the pot concurrently, but the pot must not spill over. When the pot is full (H portions of honey), the last bee to deposit honey wakes up bear who has slept the longest time to eat. The bees pause filling the pot until the pot is empty again. Once the bear is finished eating the pot empty, it allows the bees to deposit honey again and goes back to sleep.

    Give the synchronization solution for filling up the pot and emptying it with a monitor. So, the monitor contains only the synchronization problem solution; collecting honey, depositing it into the pot, and emptying the pot happens outside the monitor. Present the pseudocode for bees (N processes), bears (B processes) and the monitor.

  3. [5 p] Look at the Ricart-Agrawala Algorithm 10.2. below.
    1. [3 p] What is the meaning of the algorithm? When does a process know that it is its turn to enter critical section? What is the meaning of Main and Receive processes? What data structures are shared and which processes share them?
    2. [1 p] Assume that there are hundreds of processes and most of them will hardly ever use critical section. They are so called quiescent nodes. What problem can these quiescent nodes cause and how does this algorithm solve that problem?
    3. [1 p] In line p3 in Receive there is an "<<" operator. What does it do and why is it there? Could you replace it with normal "<" operator? Why?

k