Concurrent programming, midterm exam 29.2.2012                 suomeksiToisella puolella suomeksi  

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

  1. [5 p] Multithreaded application in a multicore system. Variables x, y and z are stored in shared memory. Code segment Code1 implements (high level language) statement "x=x+y" and code segment Code2 implements statement "x=x-z".
    1. [1.5 p] Give a scenario that leads to an erroneous result and where three threads concurrently execute code segment containing Code1. Variables x and y have initial values x=100 and y=10, in which case the correct result would be x=130.
    2. [1.5 p] Give a scenario that leads to an erroneous result and where two threads concurrently execute, one executing a code segment containing Code1 and the other a code segment containing Code2. Variables x, y and z have initial values x=100, y=10 and z=1, in which case the correct result would be x=109.
    3. [2 p] How should one protect code segments Code1 and Code2 so that the result would be correct in all possible scenarios? Give a detailed funtional answer. Explain why your solution is correct.
       
  2. [5 p] Deadlocks. We have three threads (A, B, and C) and four resource types (r, s, t and u). Each resourse can be used by one thread at a time. There are one unit of each resource type r, s and t, and two units of resourse type u. Thread A is using (in some order) resourses r and s, thread B uses resourses s, t and u, and thread C uses resourses r, t and u. Threads can not "steal" resourses from other threads and they reserve the resourses they need one at a time.
    1. [1.5 p] Give a resourse reservation scenario that leads to a deadlock. Explain why deadlock exists at the end of your scenario.
    2. [2 p] How does Dijkstra's algorithm (DDA) work in principle and how does it find out that deadlock exists in your scenario in part (a).
    3. [1.5 p] Bankers algorithm can not be used in this case, but deadlock can still be prevented, if one prepares for it. What principle can be used to prevent the deadlock from happening in this case and what changes are needed in resourse reservation code according to this principle. Explain in pseudocode level, how this change is implemented to prevent deadlocks from occurring in you scenario in part (a) .

  3. [5 p] Market stand. The salesman will bring every now and then a new bag of apples (25-30 apples) to the sales basket, which can take 200 apples. He will fill up the basket only if the whole bag will fit there. The clients (N of them) come every now and then, and pick 1-5 apples at a time for purchase. Clients will wait, if there are not enough apples in the basket. Clients are served in arrival order.

    Explain the synchronization problem above and solve it with semaphores. In your solution, give the pseudocode for (a) the salesman and (b) the clients. Remember to define the semaphores you use and their initial values.

    Note: You may use function Random(i,j) in your solution. It returns a random value in closed interval [i,j].