CSE 120 (Fall 2002) -- Homework #3

1. Nachos VM Worksheet

2. Chapter 9: 9.10, 9.14

   9.10  Consider a paging system with the page table stored in memory.

      a. If a memory reference takes 200 nanoseconds, how long does a paged memory reference take?
      b. If we add TLBs, and 75 percent of all page-table references are found in the TLBs, what is the effective memory reference time? (Assume that finding a page-table entry in the TLBs takes zero time, if the entry is there.)

   9.14  Explain why it is easier to share a reentrant module using segmentation than it is to do so when pure paging is used.

3. Chapter 10: 10.2, 10.9, 10.19

   10.2  Assume that you have a page-reference string for a process with m frames (initially all empty). The page-reference string has length p; n distinct page numbers occur in it. Answer these questions for any page-replacement algorithms:

       a. What is a lower bound on the number of page faults?
       b. What is an upper bound on the number of page faults?

   10.9  Consider a demand-paging system with the following time-measured utilizations:

       CPU utilization: 20%
       Paging disk: 97.7% (demand, not storage)
       Other I/O devices: 5%
   

   For each of the following, say whether it will (or is likely to) improve CPU utilization. Briefly explain your answers.

      a. Install a faster CPU
      b. Install a bigger paging disk
      c. Increase the degree of multiprogramming
      d. Decrease the degree of multiprogramming
      e. Install more main memory
      f. Install a faster hard disk, or multiple controllers with multiple hard disks
      g. Add prepaging to the page-fetch algorithms
      h. Increase the page size
   

   10.19  We have an operating system for a machine that uses base and limit registers, but we have modified the machine to provide a page table. Can we set up the page tables to simulate base and limit registers? How can we do so, or why can we not do so?

4. [Crowley] Suppose we have an average of one page fault every 20,000,000 instructions, a normal instruction takes 2 nanoseconds, and a page fault causes the instruction to take an additional 10 milliseconds. What is the average instruction time, taking page faults into account? Redo the calculation assuming that a normal instruction takes 1 nanoseconds instead of 2 nanoseconds.

5. [Crowley] Suppose we have a computer system with a 44-bit virtual address, page size of 64K, and 4 bytes per page table entry.
   1. How many pages are in the virtual address space?
   2. Suppose we use two-level paging and arrange for all page tables to fit into a single page frame. How will the bits of the address be divided up?
   3. Suppose we have a 4 GB program such that the entire program and all necessary page tables (using two-level pages from above) are in memory. (Note: It will be a lot of memory.) How much memory, in page frames, is used by the program, including its page tables?

6. [Tanenbaum] If FIFO page replacement is used with four page frames and eight pages, how many page faults will occur with the reference string 0172327103 if the four frames are initially empty? Now repeat this problem for LRU.