Operating Systems (6 cr), separate exam, 15.8.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] 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] Scheduling
    1. [3 p] How should one select a good time quantum for Round Robin scheduler used in an interactive system? What problems will too long or too short time quantum cause?
    2. [1 p] How do the the goals for real time scheduling differ from those for ordinary scheduling?
    3. [2 p] How does RMS (Rate Monotonic Scheduling) work in principle?
      What specific real time scheduling problem does it solve and how?
    4. [3 p] What is priority inversion problem and how can one solve it? Give an example.

  3. [9 p] File Management
    1. [5 p] What is indexed sequential file and how does it work? When would it be good to use it? When would it be not good to use it? How does the normal (without B-tree) index work? When and why should one implement the index as a B-tree? How does the B-tree index work?
    2. [4 p] Explain concepts acces matrix, access control list, and capability list, and how they relate to each other. Which problem is solved with them? Give an example relating to Unix or Linux file management, using text file myfile.txt, which anyone can read but only the owner can modify.

  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 the 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.