Midterm Exam

CSC 256/456, 3-17-1999

Please, read the following notes carefully before starting the exam:


  1. (5 points) What are the reasons for providing functionality in the OS kernel, rather than in user space?
  2. (5 points) A user process goes through many different states during its lifetime. Define each of these states and explain the transitions between them.
  3. (5 points) The Banker's algorithm is a resource-allocation policy that is guaranteed to avoid deadlock. What is the main idea behind this algorithm? What are its drawbacks?
  4. (5 points) Discuss the effect of the length of the time slice in time-sharing systems.
  5. (10 points) Assuming a vertical kernel divided into top and bottom halves, how can we get mutual exclusion between processes in the top half? Consider both the uniprocessor and multiprocessor scenarios.
  6. (10 points) Why do many machines have multiple interrupt levels? How does a hardware designer decide which interrupts should occur at each level?
  7. (15 points) What is the motivation for segmented paging, as opposed to ordinary paging?
  8. (15 points) It is usually not possible to implement a Least-Recently-Used (LRU) page replacement policy, but we can always try to approximate it. Describe one such approximation strategy. How efficient is your strategy?
  9. (15 points) The blocks belonging to a file can be organized in at least three ways: in a linked list, using a File Allocation Table (FAT), or using indexes. What are the tradeoffs involved in these different organizations?
  10. (15 points) Describe the cylinder group concept introduced by the BSD Unix 4.2 system and explain why it improves file system performance.
  11. (15 points) Describe the priority inversion problem in priority-based CPU scheduling. Also, describe at least one way in which this problem could be tackled.
  12. (15 points) Time-sharing (with a global ready list), gang scheduling, and dedicated hardware partitions are three common multiprocessor scheduling strategies. Discuss the tradeoffs faced by the OS designer when deciding between these strategies.

Last Change: 1 February 1999 / scott@cs.rochester.edu
Exam by Ricardo Bianchini.