Concurrent programming, exam 13.4.2010  

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

  1. [9 p] Critical section. 
    1. What is the critical sections problem?
      Give a concrete example on a situation the critical section problem arises?
    2. Why does the solution for critical section problem in one processor environment not necessarily work in multiprocessor environment. Explain?
    3. Why is the solution for critical section problem in multiprocessor environment not necessarily good in single processor environment. Explain?
       
  2. [9 p] Deadlocks. What is the deadlock problem? Give a concrete example on deadlock, based on the Dining philosophers problem. Which four conditions must be in effect for deadlock to occur? Show that they exist in your example. Explain the main principles of Dijktra's deadlock detection algorithm.
     
  3. [9 p] Cave system. Cave system entrance is at one end and the exit at the other. Cave system visitors are let in in 10 person groups. New visitors wait until there are exacly 10 visitors after which they start the tour with their own guide. The visitors can browse the cave system independently and the guide will wait for them in the souvenir shop close to the exit. When everybody is ready to exit, the guide will let them out and goes to the entrance to collect another group. You may assume that all visitors will eventually want to get out from the cave system and that nobody will be lost.

    Assume that the guides and visitor are processes that are synchronized with semaphores. Write the pseudo codes describing the guide and visitor processes. Make the necessary assumptions for the semaphores and semaphore operations that you use.
     
  4. [9 p] Monitor. What is a monitor? How does a monitor solve critical section problem? In which different places in the monitor may the processes executing there need to wait for their execution turn? What does the concept monitor signalling semantics mean? How does the monitor signalling semantics affect the implementation of the monitor? How do the programs using the monitor need to take in consideration the monitor signalling semantics?