Operating Systems (8 cr), separate exam and replacement exam, 17.6.2016

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 exam is both a separate (final) exam and the replacement exam for Spring 2016 lecture course.

Please select one of the following and mark your selection in your exam paper. The default selection is (d).
(a) Replacement exam for Spring 2016 lecture course miniexam 8: question 8.
      (There is no exams for miniexams 1-7 any more)
(b) Replacement exam for Spring 2016 lecture course midterm exam: questions 1-4.
      (This covers complete midterm exam, answer all questions 1-4)
(c) Replacement exam for Spring 2016 lecture course term exam: questions 5-8.
      (This covers complete term exam, answer all questions 5-8)
(d) This is ordinary separate exam and covers the whole course: questions 2-7.

1. [6 p] Cache
   1. [1 p] How does cache support spatial locality in program memory references?
   2. [1 p] How does cache support temporal locality in program memory references?
   3. [1 p] Why is cache implementation more difficult in multicore systems than 1-core systems?
   4. [1 p] How do you find the referenced data from cache? As an example, use read reference to 4-byte data in byte address 0x12345678 using a cache with block (line) size 16 bytes.
   5. [2 p] Cache access time is 500 ns, the memory access time for one cache block is 2 μs, and cache hit ratio is 95%. What is the average memory access time? State your assumptions and explain how your made the computation.
       
2. [6 p] Processes, threads, race conditions
   1. [2 p] Application S is implemented with 6 threads and it executes in a 4-core system. Thread s1 reads data from network, threads s2-s5 process the data, and thread s6 will save processed summary data into file system. Would it be advisable to implement S as kernel level, or as user level threads? Explain.
   2. [1 p] The initial value of shared variable Sum is zero (0). Four threads A, B, C and D will each execute eventually (machine language) code
      
                 100:     …
                 101:    LOAD R1, Sum          ;  R1  ← mem(Sum)
                 102:    ADD  R1, =1              ;  R1++
                 103:    STORE R1, Sum        ;  mem(Sum)  ←  Ri
                 104:    …
      
      The intent is that each thread will increment Sum by one, and that its final value it 4.  However, the program does not work properly in all scenarios. Give a scenario where final value for Sum is 3.
   3. [1 p] How do you solve the race condition problem given in part (a) with semaphores?
   4. [2 p] In the semaphore solution to the race condition the waiting thread is in suspended state, and so the waiting cost includes at least 2 thread switches. How could you solve this problem in a multicore system so that waiting would not require thread switches?
      
      
3. [6 p] Monitor, Deadlocks
   1. [2 p] How does monitor condition variable structure and operations differ from semaphore structure and operations?
   2. [1 p] How do you solve the race condition problem in previous problem (problem 2 part b) with a monitor?
   3. [1 p] Give an example on a deadlock?
   4. [1 p] Assume that threads are using five different resources (one thread can use one resource at a time). How can you quarantee that deadlock simply cannot occur, but threads can still execute (mostly) concurrently.
   5. [1 p] Assume that threads are using five different resources (one thread can use one resource at a time). Deadlock prevention (part d) is not practical for some reason, and deadlock occurs every now and then but rarely. How can you cope with deadlock problem now?
      
      
4. [6 p] Virtual Memory
   1. [2 p] How is 2-level virtual memory address translation done? Consider TLB in your answer. Use as an example virtual address 0x12345678 (byte address), when page size is 4KB.
   2. [1 p] What is a page fault and what is its cost in execution time? Explain.
   3. [1 p] What problem is solved with virtual memory replacement algorithm?
   4. [2 p] How does replacement algorithm Clock work?
      
      
5. [9 p] Processor Scheduling
   1. [2 p] What would be good size for time quantum in round robin (time slice) scheduling? When would time quantum be too small, and when too large?
   2. [2 p] For what type of system is Fair Share scheduling intended for, what system does it solve, and how does it work in main principles?
   3. [2 p] In real time systems, when can you use priority based scheduling (instead of the usual deadline scheduling)? What type of tasks are then scheduled and how are the priorities defined?


6. [9 p] Disk management and File Managment
1. [3 p] The Linus Elevator has two modifications to the basic Elevator algorithm: Linux Deadline Scheduler and Linux Anticipatory I/O Scheduler. Which problems do they solve, and how do they do it?
2. [2 p] Give an example situation where indexed sequential file would be best file organization type.
   Why would Sequential File be not good with your example?
   Why would Indexed File be not good with your example?
3. [1 p] How is the index in indexed sequential file used?
   
   
7. [9 p] Embedded systems, distributed systems
1. [2 p] In embedded operating system eCos the interrupt handling is done differently than usually. Why is it done this way and how are the interrupts processed in eCos?
2. [2 p] How does the remote procedure call (RPC) differ from ordinary procedure call? What problems are there when using RPC? How is RPC implemented?
3. [2 p] Which problem relating to distributed systems is solved with SOA model (Service Oriented Architecture)? What are the basic structures and functions in SOA model?
   
   
8. [9 p] Data Security, threats and techniques
1. [2 p] Computer viruses have four phases while in the system. What are those phases and how does the virus behave during them?
2. [2 p] Mention three (3) different techniques that make viruses hard to detect.
3. [2 p] How does Generic Decryption method detect most viruses?