Operating Systems, midterm exam, 27.2.2013                 Toisella puolella suomeksi  

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

1. [8 p] Processes and threads.
   1. [2 p] How do processes and threads relate to each other? What do they have in common? How do they differ from each other?
   2. [2 p] What are kernel level threads (KLT) and user level threads (ULT)? Give concrete examples.
   3. [1 p] When would it be better to use ULTs and not KLTs? Give one concrete example.
   4. [1 p] When would it be better to use KLTs and not ULTs? Give one concrete example.
   5. [1 p] Is it possible that a process is suspended, but one of it's threads is in running state? Explain.
   6. [1 p] Is it possible that a process is in running state, but one of it's threads is in suspended state? Explain.
       
2. [8 p] One-lane bridge with semaphors. There runs a river between two villages A and B and the villages are connected by a narrow one-lane bridge, where cars are allowed to drive only in one direction (east, west) at a time. When cars are passing the bridge from A to B (westbound), then the cars willing to cross the bridge from B to A (eastbound) have to wait. The car processes call enter_bridge_direction before using the bridge, and exit_bridge_direction, when they leave the bridge.

    Process car [i = 1 to N] {
       .....
       enter_bridge_west()
          drive over the bridge westbound
       exit_bridge_west()
       ......
       enter_bridge_east()
          drive over the bridge eastbound
       exit_bridge_east()
       ......
       }  

1. [6 p] Write the code to solve this synchronization problem with semaphors. It has four methods to invoke for synchronization: enter_bridge_west, exit_bridge_west, enter_bridge_east, exit_bridge_east. Remember to define all your semaphors and other variables with their initial values.
2. [2 p] Modify you solution (part a) so that westbound cars have priority. Once the first westbound car arrives, all subsequent eastbound cars must wait until all westbound cars have crossed the bridge.
    
3. [8 p] Deadlocks. We have three threads (A, B, and C) and four resource types (r, s, t and u). There is one unit of each resource type r, s and t, and two units of resourse type u. Each resourse can be used by only one thread at a time. Threads can not "steal" resourses from other threads and they reserve the resourses they need in some order, one unit each. Thread A is using resourses r and s, thread B uses resourses s, t and u, and thread C uses resourses r, t and u.
1. [2 p] Give a resource reservation scenario that leads to a deadlock. Explain why deadlock exists at the end of your scenario.
2. [3 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). What is done, once the deadlock is found?
3. [3 p] Bankers algorithm can not be used to avoid deadlocks in this system, but deadlocks can still be prevented from occurring. What principle can be used to prevent deadlocks and what changes should be done to the resource reservation code accordingly? Explain, why deadlock is now theorethically impossible. Explain, how deadlock prevention works in practice with your part (a) scenario.