title: Calculating Virtual Memory page table and translation lookaside buffer
body: <p>I am answering some problems related to virtual memory and would like some help in clarifying or confirming my understanding on how this stuff is done.</p>
  
  <p>The questions are as follows:</p>
  
  <blockquote>
    <p>Given a byte-addressable system with 32 bit words, a virtual address space of 4 gigabytes,  a physical address space of 1 gigabyte, and a page size of 4 kilobytes. There is an assumption that page table entries are rounded up to 4 bytes.</p>
    
    <p>a) What is the size of the page table in bytes?</p>
    
    <p>b) Now assume that a 4-way set-associative translation lookaside buffer is implemented, with a total of 256 address translations.  Calculate the size of its tag and index fields.</p>
  </blockquote>
  
  <p>My answers are as follows:</p>
  
  <p>A:</p>
  
  <blockquote>
    <p>The size of the page table is equal to the number of entries in the page table multiplied by the size of the entries. </p>
    
    <p>The number of entries in the page table is equal to the memory size divided by the page size: 2^32/2^12=2^20.  </p>
    
    <p>The size of the entries is equal to the word size minus the bits used for the number of entries in the page table: 32-20=12. </p>
    
    <p>Hence, the page table size is: (2^20) * 12 bits = 12582912 bits = 1572864 bytes</p>
  </blockquote>
  
  <p>However, I found <a href="http://www.d.umn.edu/~gshute/os/address-translation.xhtml#page-table-size" rel="nofollow">this</a> (under the heading of "Page Table Size"), which uses basically identical numbers.</p>
  
  <blockquote>
    <p>Page Table Size = ((virtual address space size)/(page size)) * (page table entry size)
                     = (4 GB/4 KB) * 4 B = 4 MB</p>
  </blockquote>
  
  <p>Which answer is correct?</p>
  
  <p>Next, B:</p>
  
  <blockquote>
    <p>I am unsure of how to calculate part B. I believe that the Tag is calculated by adding the number of blocks, plus the offset, plus the index. This is a 4 way set associative, so there are 4 blocks in each set. The index is 8 bits because the base index size is 10 bits and is decreased by 2, also because it is a 4 way set associative. However, I am unaware of how to calculate the offset, which is needed to help calculate the tag.</p>
  </blockquote>
  
  <p>Any help would be much appreciated.</p>