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: Suppose a program has three threads and a shared counter as shown below:
    int count = 10;
    Semaphore sem = 1;
    Thread1(...)               Thread2(...)               Thread3(...)
    {                          {                          {
      // do something            // do something            // do something
      sem.wait();                sem.wait();                sem.wait();
      count ++;                  count --;                  printf(``%d'', count);
      sem.signal();              sem.signal();              sem.signal();
    }                          }                          }
    

  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. Virtual memory: Increasing the page size enlarges the TLB reach (the amount of memory accessible from the TLB), which can potentially reduce TLB misses. We call this ``page size increase for TLB miss reduction''. How effective is this for the following five types of programming techniques: stack, hashed symbol table, sequential search, binary search, and executable code? Explain your answer.

  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.