Operating Systems, midterm exam, 9.3.2016                 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.
Please write the answer to each problem in its own answer sheet.
Each problem is also a miniexam of the same number. Problem 4 is miniexam 4.

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

  1. [6 p] Cache. Assume that memory reference is to one byte in byte address 0x12345678.
    1. [2 p] How does the cache find out whether referenced byte is present in cache or not?
    2. [1 p] If the referenced byte is found in cache, where in the cache is it located?
    3. [1 p] If the referenced byte is not in cache, how is the byte now accessed?
    4. [1 p] Any given size cache (e.g., 64 KB) is divided into cache lines (blocks).
      Why is the cache line size usually more (e.g., 8 or 16 words) than just 1-2 words?
    5. [1 p] Why is the cache line size still relatively small (e.g., 64 bytes), and not much bigger (e.g., 1 KB)?
     
  2. [6 p] Semaphores.
    1. [2 p] What is a semaphore? What problem does it solve? What data structures are involved in its implementation? What operations are there for it, and what do they do?
    2. [1 p] What is the producer/consumer problem? What synchronization and communication problems does it include?
    3. [1 p] Why is producer/consumer problem easier, if buffer size is infinite? In what type of practical situation relating to producer/consumer problem can one assume the buffer size infinite?
    4. [2 p] Give the semaphore solution for producer/consumer problem, assuming infinite buffer size and many producers/consumers. Present the pseudocode for producer and consumer. Declare clearly all semaphores with their initial values.

  3. [6 p] Deadlock.
    1. [2 p] Which four conditions must be valid that a deadlock is possible. Explain what each of those four conditions mean.
    2. [1 p] Give an example on a situation where all four conditions discussed above are valid, and a deadlock has occurred. Explain, why deadlock occurred.
    3. [1 p] Give an example on a situation where all four conditions discussed above are valid, but there is still no deadlock. Explain, why deadlock did not occur this time.
    4. [2 p] Give an example on a situation (application) where it would be sensible to use the Deadlock Detection Algorithm (DDA). How is DDA then used? When will DDA be run? What do you do, if DDA detects a deadlock? What do you do, if DDA does not detect a deadlock?

  4. [6 p] Memory management and virtual memory
    1. [2 p] How does virtual memory address translation happen in practice? As an example, use 1-level paging virtual memory with 32-bit byte addresses, 4KB page size, and referenced address 0x12345678.
      What address translation problem is solved with TLB and how does it do it?
    2. [2 p] What problem is solved with Clock algorithm, and how does it solve it?
    3. [2 p] What problem is solved with PFF (Page Fault Frequency) algorithm, and how does it solve it?