Operating Systems, midterm exam, 26.2.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.

Note: Please return the answer for each question on separate answer sheet in proper pile!

  1. [6 p] Threads
    1. [3 p] How do kernel level threads (KLT) differ from user level threads (ULT)?
      What advantages are there in KLTs as compared to ULTs? What disadvantages?
    2. [2 p] Give an example on a situation where ULT T state can be "executing", but the instructions for that thread are not currently executed by the processor. When will T get really executed?
    3. [1 p] What problem is related to ULT blocking I/O and the overall processing speed of multithreaded applications? Why is the same problem not existing with KLTs?
       
  2. [6 p] Deadlocks
    1. [2 p] What is the deadlock problem? Give a concrete pseudocode example relating to Dining Philosophers Problem.
    2. [3 p] How do you prevent deadlocks from occurring at all? What advantage is there in preventing the deadlocks as compared to solving the same problem with solutions based on avoiding deadlocks (e.g., with Bankers algorithm) or detecting deadlocks (e.g., with DDA)?
    3. [1 p] Give a concrete example on preventing deadlocks relating to Dining Philosophers Problem. Explain why your solution is quaranteed to prevent deadlocks.
       
  3. [6 p] Editor, keyboard driver and semapfores. Text editor TE reads character buffer B one character at a time, and then makes the needed changes to the file beeing 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. [2 p] Describe the synchronization and communication problem between TE and DD. Who waits for whom and when? How is data transfer implemented?
    2. [4 p] Give the solution to this synchronization and communication problem using semafors and the buffer (B) in shared memory. Present the solution with pseudocode for TE and DD. Declare clearly all your semafores and other data structures (needed for synchronization) with their initial values. Explain why your solution is correct.

  4. [6 p] Running track and monitor. Running track is 400m long. Ann and her friends Bill and Charlie come here to run 4000m. Ann is social and wants to wait for her friends in some ways depending on her mood. Solve the resulting synchronization problem with monitor Synch, which has a method for each runner. Give the pseudocode for monitor Synch. Define monitor condition variables and other data structures, with their initial values. Use Signal and wait (Hoare) signalling semantics. Make your solution as simple as possible. The pseudocode for the runners is as follows: 
               Ann:                Bill:               Charlie:
           for (i=1 to 10)     for (i=1 to 10)     for (i=1 to 10)
              <run lap>           <run lap>           <run lap>
              Synch.AnnLap        Synch.BillLap       Synch.CharlieLap
    1. [3 p] Ann waits after every lap until both Bill and Charlie have caught up with her (equal number of laps). If both Bill and Charlie are ahead of Ann, Ann does not wait. Bill and Charlie do not wait for anybody.
    2. [3 p] Ann waits after every lap until either Bill or Charlie (or both) has caught up with her (equal number of laps). If either Bill or Charlie is ahead of Ann, Ann does not wait. Bill and Charlie do not wait for anybody.