in EnglishToisella puolella suomeksi

Concurrent programming, Course examination 12.12.2008

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

  1. [11 p] Critical section. 
    1. What is the critical section problem?
    2. When would it be good to solve the problem with disabling interrupts and when not?
    3. When would it be good to solve the problem with a lock variable and busy-wait and when not?
    4. When would it be good to solve the problem with a semaphore and when not?
    5. When would it be good to solve the problem with a monitor and when not?
    6. When would it be good to solve the problem with Ricart Agrawala token-passing algorithm and when not?
       
  2. [11 p] Deadlocks. System S has five resources: large memory blocks A (2 units) needed for data processing, data base B (1 unit), data base C (1 unit), printers D (2 units) and keyboard focus E (1 unit). Each resource can be used only one process at a time.

    System S has four processes, P1-P4. P1 has one unit each of resources A, C and D. P2 has one unit each of resources A and B. P3 has one unit of resource D. P4 has no resources reserved for it currently.

    To advance now, P1 needs one unit each of resourecs B and E, P2 needs one unit each of resources C and E, P3 needs one unit of resource E, and P4 needs one unit each of resources A, C and E.

    1. What is a deadlock? What does it mean that the system is not deadlocked?
    2. When can a system be deadlocked?
    3. Is the system S deadlocked or not?
    4. How would one check deadlock existance using Dijkstra's Deadlock Detection Algorithm (DDA)? It uses arrays A (allocation matrix) and Q (request matrix) as well as vectors R (all resources), V (free resources) and W (working vector).
    5. How can one prevent deadlock from appearing in advance (in general and specifically in this case)?
       
  3. [11 p] Bees and bear. 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 collect honey and carry it to a pot, filling the pot one portion each bee pot at a time. When the pot is full (H portions of honey), the last bee to deposit honey wakes up the bear 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 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 in into the pot, and emptying the pot happens outside the monitor. Present he code for bees (N processes), the bear 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. [11 p] Look at the attached Ricart-Agrawala Algorithm 10.3.
    1. What is the meaning of the algorithm? 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?
    2. What is the meaning of the set requested and how is it updated? What is the meaning of the set granted and how is it updated?
    3. Assume that three processes (p1, p2 and p3) want to get into critical section all at the same time. The critical section was last reserved for p1 at time 550, for p2 at time 7700, and for p3 at time 33. The system has no other processes. 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.