CSE 410 Computer Systems - Homework 8 - Spring 2009

CSE Home

About Us

Search

Contact Info

Due: Thursday, June 4, at 11 pm.

Some questions about virtual memory and paging. Adopted or adapted from exercises in Patterson and Hennessy and in Silberschatz et al.

1. Consider a virtual memory system with the following properties:
   • 40-bit virtual byte addresses
   • 16KB pages
   • 36-bit physical byte addresses
   What is the total size of the page table for each process on this processor under the following assumptions: single-level page table; the valid, protection, dirty, and use bits take a total of 4 bits; and that all the virtual pages are in use. (Assume that disk addresses of pages on disk are not stored in the page table.
   
   
2. Suppose we have a two-dimensional array A:

   int A[][] = new int[100][100];

   where A[0][0] is at location 200 in a paged memory system with pages of size 200, and each int occupies one memory location. As is true in Java, the array is stored in row-major order, meaning that the ints in row 0 occupy the first 100 locations assigned to the array, row 1 occupies the next 100 locations, and so forth. A small process that manipulates the array resides in page 0 (locations 0 to 199). Thus every instruction fetch will be from page 0.
   
   Assume that we run each of the following nested loops on a memory system that has three total page frames. How many page faults are generated by each of the following array-initialization loops, using LRU replacement and assuming that the first page frame contains the process code and the other two are initially empty?
   

   1. for (int j = 0; j < 100; j++)
        for (int i = 0; i < 100; i++)
          A[i][j] = 0;
      

   2. for (int i = 0; i < 100; i++)
        for (int j = 0; j < 100; j++)
          A[i][j] = 0;

   
   
3. A certain computer provides user processes with a virtual memory space of 2³² bytes. The computer has 2²⁰ bytes of physical memory. The virtual memory is implemented by paging and the page size is 4,096 bytes. A user process generates the (decimal) virtual address 11,123,456. Explain how the system establishes the corresponding physical location. What part of the translation is done purely in hardware and what part depends on software?
   
   
4. Consider a paging system with a single-level page table stored in memory.
   1. If a simple memory reference takes 100 nanoseconds, how long does a paged memory reference take? (Assume that there are no caches involved.)
   2. If we add a TLB (translation lookaside buffer) and 96% of all page table references are found in the TLB, what is the effective memory reference time? (Assume that retrieving a page-table entry from the TLB can be done in zero time if the entry is present.)
      
      
5. Assume that we have a demand-paged memory. Memory access time is 100 nanoseconds. It takes 8 milliseconds to handle a page fault if an empty page is available or the replaced page is not modified, and 20 milliseconds if the replaced page is modified and has to be written out to disk. Assume that the page to be replaced is modified 70% of the time. What is the maximum acceptable page-fault rate (fraction of memory references that generate a page fault) for an effective access time of no more than 200 nanoseconds?
   
   
6. Suppose we have a demand-paging system. It seems to be running slowly and when we measure the percentage of time that parts of the system are in use, we get the following numbers:
   • CPU utilization: 20%
   • Paging disk utilization: 98%
   • Other I/O devices: 5%
   Which, if any, of the following will probably improve CPU utilization? Explain your answer.
   1. Install a faster CPU
   2. Get a larger paging disk
   3. Get a faster paging disk
   4. Increase the number of active processes
   5. Decrease the number of active processes
   6. Install more main memory

Turn-in Instructions: Use the turn-in drop box link on the main course web page to submit a file containing your solutions. You can use any common file format, including plain text, word, or pdf. If you wish, you could also scan in a hand-written solution and submit that, but if you do that, please be sure your handwriting is neat and legible. Please be sure to include your name at the top of your answers.

	Computer Science & Engineering University of Washington Box 352350 Seattle, WA  98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX [comments to Hal Perkins]