Operating Systems, separate exam, 14.6.2013                 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.

This is an ordinary separate exam and covers the whole course. If you want to have it graded also as a renewal exam, please note so in your answer sheet. The renewal exam replaces only one course exam, either the one that you missed or the one that you received least points from. The renewal exam points are scaled to course exam points and your grade will include all course components. As a separate exam, your grade is based solely on this exam. Better grade wins. The exam will be graded only after midsummer.

  1. [9 p] Critical section problem 
    1. Give a code level example on a critical section. Give a scenario (relating to your example), where computation result is erroneous if critical section is not protected properly.
    2. Explain, why the computation result in that same scenario is correct when critical section is protected. Why is the result now correct in all possible scenarios?
    3. Which critical section protection method would be good for this situation? Why this method and not one of the two other methods that you know of? Explain. Show, how the critical section protection is implemented at pseudo code level in this case.
     
  2. [9 p] Monitor and one-lane bridge
    1. [4 p] Monitor and the synchronization problem. Explain, how synchronization problem solution inside a monitor differs from the similar semaphore solution. What are the synchronization primitives inside a monitor and how do they differ from corresponding semaphore operations?
    2. [5 p] There runs a river between two villages A and B and the villages are connected by a narrow one-lane bridge, where many cars are allowed to drive only in one direction (east, west) at a time. For example, 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. Westbound (eastbound) car processes call enter_bridge_west (east) before using the bridge, and exit_bridge_west (east), when they leave the bridge.

      Write the monitor code to solve this synchronization problem. It has four methods to synchronize cars: enter_bridge_west, exit_bridge_west, enter_bridge_east, exit_bridge_east. Remember to define all your condition variables and other variables with their initial values.

  3. [9 p] Processor short term scheduling
    1. [5 p] When is the scheduling algorithm working properly? Which problem does the Round-Robin scheduling algorithm solve? Round-Robin is not always perfect - which Round-Robin algorithm problem is solved with Fair-Share scheduling and how?
    2. [4 p] How does real-time scheduling differ from that of ordinary system? What are the goals for a good real-time scheduling? What is the priority inversion problem and how can it be solved?
     
  4. [9 p] Virtual memory
    1. [1 p] Which problem is solved with virtual memory?
    2. [2 p] What is locality principle, what types of it exists, and how is it related to virtual memory?
    3. [2 p] What is thrashing, when does it occur, and how is it related to virtual memory?
    4. [2 p] What is TLB, which problem does it solve, and how is it related to virtual memory?
    5. [2 p] Which problem is solved with virtual memory replacement algorithm? Give one replacement algorithm and describe briefly how it works with an example reference string.