Toisella puolella suomeksi

Concurrent programming, course exam 14.12.2007

Write in each answer sheet your name, signature, id-number, course name, and page nr/total nr of pages.

1. [10 p] Critical section
   1. What does the concept critical section mean? Give a comprehensive definition.
   2. When and in what type of environment would it be wise to protect critical sections by disabling interrupts, and not using test-and-set instructions or semaphores? Why?
   3. When and in what type of environment would it be wise to protect critical sections with test-and-set instructions and not using interrupt disabling or semaphores? Why?
   4. When and in what type of environment would it be not wise to protect critical sections with test-and-set instructions? Why?
   5. Assume now, that your system does have a test-and-set instruction, but it has a fetch-and-add instruction executing atomically the following statements:

      fetch-and-add (common, local, x) is
        local <- common
        common <- common+x

      How is critical section protection done with fetch-and-add instruction? Give the algorithms for competing processes p and q. Clearly mark, which variables are shared and which are private for each process.

2. [10 p] Synchronizing with messages. Computation is parallellized to N processes, each running in its own node. Process communication is based on channel messages. For error tolearance the computation has a set check points - if something goes wrong, computation can always be renewed from latest check point. Every time a process reaches certain check point, it saves its computational state information on disk. Computation may resume only after all processes have finished saving their state for that checp point.
   
   In this problem we do not consider how computation will resume after some error is found. We concentrate only on process synchronization when saving the check point information.
   
   Define the channels needed in your solution and write the synchronization algorithms.
    
3. [10 p] Bees and semaphores. Friendly bees (N bees) are feeding a trapped bear by collecting honey for it. The life of the trapped bear is just eating and sleeping. The bees carry honey to a pot, one portion each bee each time until the pot is full. When the pot is full (H portions of honey), the bee that deposited the last portion wakes up the bear. The bear starts eating and the bees pause filling the pot until the bear has eaten all the honey and the pot is empty again. Then the bear starts sleeping and bees start depositing honey again.
   
   The bees can deposit their honey into the pot concurrently, but the pot must never receive more than H portions of honey.
   
   Give the solution for filling up the pot and emtpying it with semaphores. Present he code for bees (N processes) and bear. Explain verbally which situations demand mutual exclusion and/or synchronization and how those problems are solved in your solution.

 
4. [10 p] Little questions (max 1/2 page answer for each question)
   1. Why is it difficult to analyze concurrent programs? When error occurs, you could just normally execute the program close to the error appearance point and study the data structures in software development environment to locate the error. What is the point?
   2. How can one prove that a concurrent program works correctly according to its specifications?
      How can one comprehensively prove the code to be incorrect?
   3. What does concept baton passing mean in concurrency control? Why and when is it needed? How is it implemented?
   4. How does concurrent problem solution with protected objects differ from semaphore based solution? Give a good example?
   5. What concurrency problem is solved with transaction memory? Give an overall description on how transaction memory works?