Operating Systems, separate exam, 15.11.2013              

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.

  1. [9 p] Concurrency 
    1. [3 p] What is a semafor? How does one solve the critical section problem with semafors? How is synchronization problem solved with semafors?
    2. [3 p] What is a monitor? How does one solve the critical section problem with monitor? How is synchronization problem solved with monitor?
    3. [3 p] Explain what is the Producer/Consumer problem? What is an "infinitely large" buffer and how does it relate to the solution? When could the solution be based on "infinitely large" buffer" even though in practice the buffer is (of course) finite?
    2.  
  2.  [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.
    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).
    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. 
    3.  
  3. [9 p] Real time scheduling
    1. [1 p] How do the the goals for real time scheduling differ from those for ordinary scheduling?
    2. [3 p] How does deadline scheduling work? What is good/bad with it?
    3. [3 p] How does RMS (Rate Monotonic Scheduling) work in principle?
      What specific real time scheduling problem does it solve and how?
    4. [2 p] What is priority inversion problem and how can one solve it?
    4.  
  4. [9 p] Disk scheduling
    1. [1 p] What problem is solved with disk scheduling algorithms? What criteria is used to evaluate different disk scheduling algorithms?
    2. [2 p] How does SSTF (shortest service time first) algorithm work? What is good/bad with it?
    3. [2 p] How does elevator (SCAN) algorithm work? What is good/bad with it?
    4. [2 p] How does N-Step-SCAN algorithm work? What does differ from elevator algorithm?
    5. [2 p] Can one apply disk scheduling algorithms (e.g., FIFO, PRI, SSTF, SCAN) also to SSDs (Solid State Disk)? Explain your answer.