in EnglishToisella puolella suomeksi

Concurrent programming, Course examination 20.1.2009

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

  1. [9 p] Look at Algorithm 2.10 below. Assume K value 10.
     
                  Alg. 2.10
     
    1. Can variable n have end-value 10? If yes, give a scenario for it. If not, why not?
    2. Can variable n have end-value 11? If yes, give a scenario for it. If not, why not?
    3. Can variable n have end-value 0? If yes, give a scenario for it. If not, why not?
    4. Can variable n have end-value 1? If yes, give a scenario for it. If not, why not?
    5. What is thre real problem here and how should one fix it so, that the end-value for n would always be 0.

     
  2. [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.
     
  3. [9 p] Bees, bears and IRR monitors. Friendly bees (N bees) are feeding trapped bears (K 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, filling the pot one portion each bee at a time. When the pot is full (H portions of honey), the last bee to deposit honey wakes up one bear to eat. The bees pause filling the pot until the pot is empty again. Once a 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 using IRR (E<S<W) signaling semantics. So, the monitor contains only the synchronization problem solution - collecting honey, depositing in into the pot, and emptying the pot happens outside the monitor. Present he pseudocode for bees (N processes), bears (K processes) and the monitor. Explain verbally which situations demand mutual exclusion and/or synchronization and how those problems are solved in your solution. Make the required assumptions concerning the monitor features and write them down.
     
  4. [9 p] Look at the attached Ricart-Agrawala Algorithm 10.2.
    1. What is the meaning of the algorithm? What problem is is supposed to solve?
      What is the meaning of Main and Receive processes? What are they needed for?
      Could one combine them into one process? How or why not?
      What data structures are shared and which processes share them?
    2. What is the meaning of the set deferred and how is it updated? Why does one need variables requestCS?
      Could myNum values for different processes be the same? Why not or how are they handled?
    3. Assume that three processes (p1, p2 and p3) want to get into critical section all at the same time. Processes p1, p2 and p3 have myNum values 5, 10, 15. The system has also processes q1 and q2 that are not trying to get into the critical section right now. Show, how and in which order processes p1, p2 and p3 will get into critical section. Especially show all related messages (sender, receiver, message type, message contents) and how they are responded to.