Concurrent Programming, HW 6

1. Critical section. 
   1. Give an example of a situation where it would be wise to protect critical sections by disabling interrupts, but not with busy wait (e.g., with test-and-set instructions) or semaphores? Why?
   2. Give an example of a situation where it would be wise to protect critical sections with busy-wait instructions, but not with interrupt disabling or semaphores? Why?
   3. Give an example of a situation where it would be wise to protect critical sections with semaphores, but not with busy-wait instructions or interrupt disabling? Why?
   4. Give an example of a situation where it would be wise to protect critical sections within a monitor, but not wih semaphores? Why?
   5. Explain concept baton passing in critical section problem solutions. When is it needed and why? How is it implemented?
      
      
2. 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. 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, filling the pot one portion at most 100 bees 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. Make sure, that no bear will starve.
   
   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 (B processes) and the monitor.
    
4. Fill in the Student Feedback form.
   In Question 11 (Your opinion on course material) discuss your opinion on using BACI-software in this course. Did using BACI support your learning? Was the time spent usefully? Was writing C-- programs difficult?
   In Question 14 ("How would you like to develop the course?") Give at least your opinions on(a) the course lectures and (b) the project. (a) Did you find the small discussion questions useful? Would it be better, if the instructor would just lecture all the time? What is your opinion on the lecture discussion item topics. (b) How could you make the project more "better"?
   
   Take copies of these answers with you to the practice session for discussion.
    
5. [2 htp] Read the article Data Structures in the Multicore Age (Nir Shavit, Comm ACM vol. 54 no. 3 - March 2011, ACM pdf, local pdf) and consider the following questions based on that article.
   1. What is the actual problem in the 1^st (Lock-based Stack) solution?
   2. How is it solved in the 2^nd (LockFreeStack) solution?
   3. What is the critical section in the 1^st and 2^ndsolution?
   4. What does the backoff algorithm really do in the 1^st and 2^nd solution? When is it used?
   5. How does the 3^rd solution (EliminationBackoffStack) really work?
   6. What does the backoff-algorithm really do in the 3^rd solution? When is it used?