Operating Systems, separate exam, 13.6.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.
It works also as a renewal exam for both mid-term and term exams for the lecture course in Spring 2014.

  1. [9 p] Editor, keyboard driver and monitor. Text editor (TE) reads character buffer B one character at a time, and then makes the needed changes to the file being edited. Keyboard device driver (DD) reads the pressed keys (one at a time) and then writes the corresponding characters to the buffer B accordingly.
    1. [3 p] Describe the synchronization and communication problem between TE and DD. Who waits for whom and when? How is the data transfer implemented?
    2. [6 p] Give the solution to this synchronization and communication problem using a monitor. Present the solution with pseudocode for TE, DD, and the monitor. Declare clearly all your condition variables and other data structures with their initial values. Explain why your solution is correct.
       
  2. [9 p] Processor Scheduling
    1. [3 p] Give three different scheduling algorithms, explain how they work and how they differ in good/bad from the others.
    2. [3 p] How does multiprocessor scheduling differ from "ordinary" scheduling? Give one multiprocessor scheduling algorithm, explain how it works and what is good/bad with it.
    3. [3 p] How does real time scheduling differ from "ordinary" scheduling? Give one real time scheduling algorithm, explain how it works and what is good/bad with it.

  3. [9 p] File Managment
    1. [3 p] What is indexed sequential file and how does it work? What are the advantages as compared to sequential file? When and why should one implement the index as a B-tree?
    2. [3 p] What is indexed file and how does it work? What are the advantages as compared to indexed sequential file? When and why should one implement the index as a B-tree?
    3. [3 p] What is direct (hashed) file and how does it work? What are the advantages as compared to indexed file?

  4. [9 p] Muistinhallinta
    1. [3 p] A machine has 48-bit virtual byte addresses and 32-bit physical byte addresses. Page size is 4KB. How many entries are needed for a conventional page table? How many for an inverted page table?
    2. [3 p] What is a translation lookaside buffer (TLB) and its function in the address translation? What commonalities/differencies are there with TLB and cache (implementation, locality)?
    3. [3 p] A machine has 16-bit virtual byte addresses and 16-bit physical byte addresses. Page size is 1KB. How is physical memory referenced, when the user program refers to virtual memory location
      1. 00011001 01010101  
      2. 00110010 10101010
      3. 00001100 00111100

      and the following entries are found in the page table:

      Page Nr
      Frame Nr
      11
      110
      110
      11
      1100
      -
      11001
      1100
      110010
      -
    5.