COS 318: Operating Systems, Fall 2013

Quiz 5: Virtual Memory and Virtual Machine Monitors

Due: 11:55pm, Wednesday, November 20

This quiz checks your understanding of the lectures and reading assignments. You may reference the textbook, lecture slides, and your notes. Online sites (e.g., Wikipedia) may also be consulted but you must cite them in your writeup.

Each question is worth three points. Please strive for clarity and brevity in your answers.

Submit your answers by clicking the "submit" link on the lecture schedule page. Only online submissions will be accepted. Please use this template when preparing your answers, and submit a plain ASCII text file.

Questions:

  1. Suppose a system has 64KB of physical memory and each process has 32KB of address space. The system uses virtual memory with paging and has a page size of 4KB. All addresses (virtual and physical) are given by 32-bit words. Consider a process with the following page table:

       VPN 0: 0x80000006
   VPN 1: 0x80000003
   VPN 2: 0x8000000d
   VPN 3: 0x80000002
   VPN 4: 0x80000005
   VPN 5: 0x00000000
   VPN 6: 0x8000000f
   VPN 7: 0x00000000

    The format of the page table is: the high-order (leftmost) bit is the VALID bit. If the VALID bit is 1, the rest of the bits are the Page Frame Number (PFN); if the VALID bit is 0, the page is not valid. For each virtual address listed below, either give the physical address to which it maps to or say that it is invalid.

    1. 0x00006e19
      Answer: 0x0000fe19
    2. 0x00004d35
      Answer: 0x00005d35
    3. 0x00005665
      Answer: Invalid

  2. Assume a system with 3 page frames and the following sequence of page accesses: 5, 4, 2, 1, 3, 2, 4, 1, 2, 3.

    For each of the following policies, indicate whether each reference results in a hit (H) or a miss (M) and the total number of hits. (Your answers should look something like: M, M, H, M, H, H, M, M, M, M - 3 hits.)

    1. MIN (Optimal)
      Answer: M, M, M, M, M, H, H, M, H, H – 4 hits
    2. FIFO
      Answer: M, M, M, M, M, H, M, H, M, H – 3 hits
    3. FIFO with 2nd Chance
      Answer: M, M, M, M, M, H, M, M, H, M – 2 hits
    4. LRU
      Answer: M, M, M, M, M, H, M, M, H, M – 2 hits
    5. NFU with Aging (assume an 8-bit counter)
      Answer: M, M, M, M, M, H, M, M, H, M – 2 hits

  3. What is copy-on-write (CoW)? How does a virtual memory system with paging implement CoW? Give an example of when CoW would be used. (Write one paragraph.)

    Suggested solution: CoW allows memory to be copied from one process to another with very little initial overhead. Many UNIX systems use it when a parent process forks a child. To implement CoW for a page, the VM system maps virtual pages in the address spaces of two different processes to the same page frame in physical memory; the virtual pages are marked read-only in both address spaces. Both processes can then read the page. However, if one process writes to the page, then a page fault occurs. At this time the OS copies the page to a new page frame and fixes the page table of the process to point to the new page.

  4. For a Type 1 hypervisor such as was discussed in lecture, describe how control is transferred between a process, the OS, and the VMM when the process does a system call.

    Suggested solution: The key is that any time a privileged instruction is executed by the process or OS, control traps to the VMM. So the control flow looks like:

    • Process executes system call (e.g., int 0x80)
    • Control traps to trap handler in VMM
    • VMM calls trap handler in OS at reduced privilege
    • OS trap handler decodes trap and executes syscall
    • OS trap handler executes return-from-trap (e.g., iret)
    • Control traps to VMM; do real return-from-trap
    • Process resumes execution