Operating Systems, midterm exam, 4.3.2015                 suomeksiToisella puolella suomeksi

Write in each answer sheet course name, date, your name, signature and student id.
For each question, it is sufficient to give a 1-2 page answer.
Write the answers to each problem in separate sheets.

NOTE: Please return the answer for each problem in its own pile!

  1. [6 p] Critical Section Problem. We have multithreaded application running in a multicore system.
    1. [1 p] Give a (pseudo)code level example on a critical section (code segment A), that is executed by threads P, Q, and R at some time. Explain, why is A a critical section?
    2. [1 p] Relating to your example in part (a), give a scenario, where computation result is correct, even when critical section is not protected properly.
    3. [1 p] Relating to your example in part (a), give a scenario, where computation result is erroneous if critical section is not protected properly.
    4. [2 p] Which critical section protection method would be good for this situation? Show, how the critical section protection (with your solution method) is implemented at pseudo code level for code segment A.
    5. [1 p] How will the situation in part (d) change, if the this same critical section includes also code segments B and C?
     
  2. [6 p] Deadlocks. Process P uses critical sections CS1 and CS2 (sometimes concurrently). Process Q uses critical sections CS1, CS3 and CS4 (sometimes concurrently). Prosessi R uses critical sections CS2 and CS4 (sometimes concurrently). Prosessi S uses critical sections CS3 and CS5 (sometimes concurrently).
    1. [2 p] Give a scenario leading to a deadlock, involving some or all of the given processes. Which processes end up deadlocked?
    2. [2 p] One possibility to avoid deadlocks is to reserve all resourses in some given order.
      Why are deadlocks avoided with this method?
    3. [2 p] How does reserving resourses in some given order exactly work in this case?
      What order and why?
      How is the deadlock scenario in part (a) avoided now? Give the relevant parts of your answer in pseudocode.
       
  3. [6 p] Producer-Consumer problem and semaphores. There is one producer and max 20 consumers. Buffer size is 10. The buffer operations Put() and Get() are available. You can write to (Put) and read from (Get) the buffer at the same time, but only one Put (or Get) operation can be executing at a time.
    1. [3 p] Describe the problem. Especially explain, what synchronization and communication problems are involved. Who waits for whom and when and why and how? When does the waiting end?
    2. [3 p] Give a solution using semaphores. Present the pseudocode for producer and consumer. The solution must allow one Put and one Get operation occur concurrently. Declare clearly all semaphores and other data structures with their initial values. Explain why your solution is correct.

  4. [6 p] Memory Managment
    1. [3 p] Assume that the machine instruction in execution will load an integer value from virtual memory address 0x1234BCDE to hardware register R2.
      How long does this take in the best case? Explain.
      How long does this take in the worst case? Explain.
      (Define the speeds for referenced HW modules at some sensible rough level.)
    2. [3 p] Explain concept "thrashing". What is the problem there? What causes it? How can you avoid it? How does Page Fault Frequency (PFF) algorithm relate to this?