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. Synchronization: The following algorithm, developed by Dekker, is the first known correct software solution to the critical section problem for two processes. The two processes, P0 and P1, share the following variables:
             bool flag[2];  /* initially both flags are false */
             int turn = 0 or 1;
    
    The following program is for process Pi (i=0 or 1), with Pj (j=1 or 0) being the other process:
             for (;;) {
                flag[i] = true;
                while (flag[j])
                   if (turn==j) {
                      flag[i] = false;
                      while (turn==j);  /* spin wait */
                      flag[i] = true;
                   }
                ...
                critical section
                ...
                turn = j;
                flag[i] = false;
                ...
                remainder section
                ...
             }
    
    Explain that the algorithm satisfies all three requirements (mutual exclusion, progress, bounded waiting) for the critical section problem.

  2. 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).
  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. Caching and prefetching: Caching and prefetching are employed to improve file system performance. Caching file content in memory can reduce disk I/O if the same content is accessed again in the future. Prefetching allows large chunks of disk I/O to be performed sequentially, which improves the disk I/O throughput if prefetched content is eventually used.
  5. Disk scheduling: Consider disk scheduling algorithms such as FCFS (First-Come-First-Serve), SSTF (Shortest-Seek-Time-First), SCAN, and C-SCAN (Circular Scan).
  6. Reliability: Device drivers are probably the buggiest part of an OS kernel since their developers (hired by device manufacturers) may not be as nerdy as the core kernel developers.
  7. 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.