Operating Systems (6 cr), separate exam, 21.11.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 (6 cr).

  1. [9 p] Deadlocks
    1. [2 p] Consider the basic solution to Dining Philosophers Problem where each philosopher, when hungry, first reserves the left side fork and then the right side fork. Give a scenario not leading to a deadlock.
    2. [2 p] Consider the basic solution to Dining Philosophers Problem where each philosopher, when hungry, first reserves the left side fork and then the right side fork. Give a scenario leading to a deadlock.
    3. [3 p] Which four conditions must hold for possible deadlock? Show that they hold in the basic solution to Dining Philosophers Problem. If all these four conditions hold, is deadlock eventually inevitable?
    4. [2 p] Deadlocks can be completely avoided by reserving resources in some given order? Why does this method work? Which one of the four conditions (part c) is now broken and how? Explain how this solution method would work with Dining Philosophers Problem.
       
  2. [9 p] Processor Scheduling
    1. [3 p] Which problem is solved with (short term, processor, normal non real-time system) scheduling algorithm? When does it work well? When does it work badly? What criteria is used to evaluate the goodness of the algorithm?
    2. [3 p] Mention three (3) different scheduling algorithms for uniprocessor environment and explain the main principles on how they work. For each algorithm, give an example situation where it would be better than the others.
    3. [3 p] How does real-time system scheduling differ from normal (uni- or multicore non real time system) scheduling? Why are the normal scheduling algorithms not suitable in general for real-time system scheduling? Mention one scheduling algorithm specifically suitable for real-time system scheduling, and explain the main principles on how it works.

  3. [9 p] File Managment
    1. [3 p] What is indexed file and how does it work? How many indexes do you need?
    2. [2 p] What kind of access is the indexed file designed for? Why are serial files or indexed serial files not suitable for this kind of access?
    3. [2 p] How do you implement the indexes (without B-tree) for indexed files? How many indexes do you need?
    4. [2 p] Often it is advisable to implement the index with a B-tree. How does a B-tree index work in principle, and why is it faster than a normal (non B-tree) index? How many B-tree indexes do you need?

  4. [9 p] Virtual memory.
    1. [3 p] How does paging virtual memory address translation work? Give an example with 32-bit byte address 0x12345678, when page size is 4 KB. Which frame and physical memory location is referenced and how do you find it?
    2. [3 p] Why is virtual memory often implemented with multiple levels? What does it really mean? How does 2-level paging virtual memory address translation work? Give an example with 32-bit byte address 0x12345678, when page size is 4 KB and page table has 1024 elements (rows). Which frame and physical memory location is referenced and how do you find it?
    3. [3 p] What is inverted page table, how does it work, and what advantages/disadvantages it has when compared to ordinary page table? Give an example with 32-bit byte address 0x12345678, when page size is 4 KB. Which frame and physical memory location is referenced and how do you find it?
    5.