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

  1. [9 p] Deadlocks
    1. [2 p] What is the deadlock problem? Give a concrete example,.
    2. [2 p] How does Dijkstra's Deadlock Detection Algorithm (DDA) work in principle? What data does it require? When is it run?
    3. [2 p] Assume that deadlock is possible in your system and that you have prepared for it in advance. Assume also that DDA has determined a deadlock to exist. What happens now? Give at least 2 different solutions.
    4. [3 p] How do you prevent deadlocks from occurring at all with Bankers algorithm? What data does it require? How does it work in principle? How would it work with your example in part (a)?
       
  2. [9 p] Producer-Consumer problem with semafors. There are one each. Buffer size is 200.
    1. [2 p] Describe the problem. Especially explain, what synchronization and communication problems are involved.
    2. [3 p] Give a solution using semafors. Present the pseudocode for producer and consumer. Declare clearly all your semafores and other data structures with their initial values. Explain why your solution is correct.
    3. [4 p] Give a solution using a moniotr. Present the pseudocode for producer, consumer, and monitor. Use the monitor only to solve the synchronization problem. Declare clearly all monitor condition variables and other data structures with their initial values. Explain why your solution is correct.

  3. [9 p] Scheduling.
    1. [3 p] What problem is solved with scheduling?
      How does it relate to user-level threads? How does it relate to kernel level threads?
    2. [3 p] What specific features are there in multiprocessor system scheduling?
      What specific features are there in real time system scheduling?
    3. [3 p] Explain how Rate Monotonic Scheduling works in principle, what environment is it supposed to be used in, and what good/bad features they have when compared to other scheduling policies for the same environment.

  4. [9 p] Memory Managment
    1. [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?
    2. [3 p] What problem does the paging virtual memory replacement algorithm really solve? When is it run? What data does it need? What hardware support does it need?
    3. [2 p] How does the paging virtual memory replacement algorithm Clock work in principle? What data does it need? What hardware support does it need? What is good/bad as compared to the LRU algorithm?
    4. [1 p] Give a simple example of page reference sequence where the first page selected for replacement will be different for the Clock and the LRU page replacement algorithms. Assume that the process is allocated 3 frames, and the reference string contains page numbers from the set 0,1,2,3. Explain.