A memory trace with paging

Follow every memory access made by a loop that zeroes an array, as in the Paging chapter of OSTEP (Chapter 18). Each reference to code or data first needs a read of the page table, so the trace shows the cost of paging one access at a time.

Assumptions

Virtual address space
64KB (16-bit addresses)
Page size
1KB (10-bit offset, 6-bit VPN)
Page table
linear, at physical 1024, 4-byte entries
Code
VPN 1 → PFN 4, 4-byte instructions
Array
1000 ints at 40000–43999
Array pages
VPN 39→7, 40→8, 41→9, 42→10

Which iterations to trace

Each iteration of the loop makes 10 memory accesses.

Or try

i runs from 0 to 999.


  


  

  

    

      
A virtual and physical memory trace

      
Each square is one memory access. Code and array accesses are plotted by virtual address (left axis), with the matching physical address on the right.

      

      
    
        
  • Page-table read
    • 
        
  • Array write
    • 
        
  • Instruction fetch
    • 
      

    


    

      

        
The program


int array[1000];
for (i = 0; i < 1000; i++)
    array[i] = 0;

        

          
VAPAInstruction

          
        

        

          edi = 40000
          eax = 0
        

      


      

        
This access

        
Nothing accessed yet.

        

      

    

  


  

    

      
The page table

      
64 entries × 4 bytes, at physical 1024–1279. Only five entries are used.

      

      

    


    

      
Physical memory

      
Frames 0–11, 1KB each. The highlighted frame holds the current access.

      

      

        
0accesses

        
0page-table reads

        
0instruction fetches

        
0array writes

      

      

        

        
Half of every access goes to the page table.

      

      
Keyboard: ← → to step, Space to play or pause.