Paging: translating addresses with a page table

A process with code, heap and stack in a 64-byte virtual address space of 16-byte pages, mapped onto 128 bytes of physical memory in 16-byte page frames, following the Paging chapter of OSTEP (Chapter 18). Every translation reads the page table, which is itself stored in memory.

Or try

Use decimal, hex (0x…) or binary (0b…), from 0 to 63.

Change the page table
Frame 0 belongs to the OS. Clear Valid for an unused page, Writable for a read-only page, or Present for a page that is out on disk. 


  


  

  

    

      
Virtual address space

      
64 bytes in four 16-byte pages.

      

        

        

        

      

    


    

      

        
Address bits

        
The offset is copied as is. Only the page number is translated.

        

          
Virtual6 bits

          

            —
            

              

              

            

            
          

          
VPN → page table → PFN

          
Physical7 bits

          

            —
            

              

              

            

          

        

      


      

        
Page table

        
One entry (PTE) per virtual page, stored in frame 0.

        

          PTBR = 0
          sizeof(PTE) = 1 byte
        

        

          

            
PageStored atPTEPFNDAR/WPV

            
          

        

        

          
Inside one entry

          

        

        

          
PFN
Page frame number: which physical frame holds the page (bits 7–5).

          
D
Dirty: set by the hardware when the page is written.

          
A
Accessed: set by the hardware when the page is read or written.

          
R/W
Protection: 1 means the page may be written, 0 means read-only.

          
P
Present: 1 if the page is in memory, 0 if it has been swapped to disk.

          
V
Valid: 1 if the page is part of the address space at all.

        

      

    


    

      
Physical memory

      
128 bytes in eight 16-byte frames.

      

        

        

        

        
No physical address: the hardware raised a fault.

      

      
Frame 0, byte by byte

      
The page table occupies bytes 0–3. The rest belongs to the OS.

      

    

  


  

    

      
What the hardware runs


// VPN_MASK = 0x30  SHIFT = 4  OFFSET_MASK = 0x0F  PFN_SHIFT = 4
// PTBR = 0  sizeof(PTE) = 1 byte

      

    

    

      
Translations

      

        
VirtualAccessVPNOffsetPFNPhysical

        
      

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

    

  


  

    
Page tables add up

    
Every process has its own page table, kept in the OS's memory. On a context switch the OS loads the new process's table address into PTBR.

    

      

        
In this 128-byte machine

        

          Processes
          
          1
          
        

        

        

        

      

      

        
In a real machine

        

          
          
          
          
          
        

        

        

          

          
page tables

        

        

        

          
A real 32-bit x86 page-table entry

          

            PFNunusedGPATDAPCDPWTU/SR/WP
          

                    
Same idea as the 1-byte entries above, with more room. The PFN takes bits 31–12 and the flags take bits 11–0, with P at bit 0. Extra flags cover user/supervisor access, caching and global pages.