CSE 120: Homework #4

Spring 2009

1. Nachos VM Worksheet

2. (8.9)  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.)

3. (8.12)  Consider the following segment table:

   Segment	Base	Length
   0	219	600
   1	2300	14
   2	90	100
   3	1327	580
   4	1952	96

   What are the physical addresses for the following logical addresses?

       a. 0,430
       b. 1,10
       c. 2,500
       d. 3,400
       e. 4,112

4. (9.10)  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
   

5. Consider the following information about a virtual memory system that employs both paging and segmentation.
   • The word size is 32 bits.
   • The page and segment table entries each occupy one word.
   • The page size is 512 words.
   • A page table occupies at most one page.
   • A virtual address is n bits long and is a reference to a word. It has the form (s₁, s₂, p, w).
   Let |s₁|, |s₂|, |p| and |w| denote the length, in bits, of each of the four address components. Hence, n = |s₁| + |s₂| + |p| + |w|.

      a. What is the value of |w|?
      b. What is the maximum number of pages per segment and what is the corresponding value of |p|?
      c. Using the determined values of |w| and |p|, which of the following is choices for |s₁| and |s₂| is preferable?

   |s₁| = |w| and |s₂| = n - |p| - |w| - |s₁|
   or
   |s₂| = |w| and |s₁| = n - |p| - |w| - |s₂|

   
   Would either choice result in a larger virtual address space? Explain.

6. If a large number of programs is kept in main memory, then there is almost always another ready program when a page fault occurs. Thus, CPU utilization is kept high. If, however, we allocate a large memory space to each of a few programs, then each program produces a smaller number of page faults. Thus, CPU utilization is kept high. Are these two arguments correct? Which policy, if either, should be preferred? Why?

7. [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 nanosecond instead of 2 nanoseconds.

8. [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?

9. [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.