Written assignment #2

This assignment is meant to help you in the final review of the course. You don't have to turn in this assignment (and we will not grade it even if you do). We will not post the solution either. You are encouraged to meet the instructor and the TAs for solutions to the problems or any other questions you might have. Note that this set of questions are not meant to be complete for your final exam preparation. In particular, it does NOT replace the need of reviewing lecture notes and the textbook. Also note that the final exam may contain materials covered before the midterm exam.

  1. CPU scheduling: Imagine two users: one launches short processes one by one while the other launches long processes one by one. In a fair scheduling environment, each user should acquire equal amount of resource. Explain the differences in the degree to which the following scheduling algorithms discriminate in favor of or against the short-process user.
  2. Synchronization:
  3. Deadlock: Consider a system consisting of m resources of the same type, being shared by n processes. Resources can be requested and released by processes only one at a time. Can a deadlock occur in this system if the following two conditions hold? If so, show how. If not, explain why not.

  4. Paging: Consider a reference string 1,2,3,4,2,5,6,2,3,2,1,6,7; and a system with only 4 frames (all frames initially empty).
  5. Caching and prefetching: Caching and prefetching are employed to improve file system performance. Prefetching is particularly effective for data accesses that follow sequential access patterns. When the OS detects a sequential access pattern, should it use an LRU replacement policy for prefetched pages in I/O buffers? Explain why. Assume that the access time for a prefetched page is initialized to its prefetch time. If LRU is a bad choice, what replacement policy should the OS employ for those pages?

  6. Disk scheduling: Consider disk scheduling algorithms such as FCFS (First-Come-First-Serve), SSTF (Shortest-Seek-Time-First), SCAN, and C-SCAN (Circular Scan).
  7. Security: In some secure systems, processes are only allowed to communicate through well-monitored channels (e.g., sockets and pipes) and certain information is prohibited from being passed to specific processes. However, two collaborating processes may pass banned information through covert channels. In one case, process A modulates its CPU usage in well synchronized time slots. To pass a binary message ``010'', it will stay idle for one time slot, spin like crazy for the next, and stay idle for the third slot. Process B can learn the binary message by checking CPU idleness at each time slot. Suggest a way to prevent such CPU-modulating covert channel communications.

  8. Reliability: In a multi-threaded server, an invalid memory access (an attempt to access an invalid memory location) causes the whole server to crash. Dr. Foobar proposes a scheme to improve server reliability in the presence of invalid memory accesses. In his scheme, an invalid read access returns some randomly generated data while an invalid write access is simply discarded. In both cases, the server keeps running without crashing. The goal is that although the thread that makes the invalid memory access may not complete properly, other threads in the server will not be affected. Describe at least two scenarios under which Dr. Foobar's scheme will fail.

  9. Virtual machines: A virtual machine monitor (VM monitor) is a piece of software that provides execution environments with an interface identical to the bare hardware. These execution environments are called virtual machines (VMs). An operating system and its user programs run in each VM. A VM monitor may support multiple VMs. When it does so, the VM monitor must allocate physical memory pages among those VMs. It is possible that multiple VMs contain memory pages with exactly the same content. One particular cause is that several VMs may run the same OS and the read-only OS kernel code segment would be identical across those VMs. It would save some memory space if we can let those VMs share a single physical copy of identical memory pages.