As oppose to dividing memory to different-size chunks, paging is to chop up memory into fixed-sized pieces.

It’s simple to manage: the OS keeps a free list of all free pages and graph the needed. To record where each virtual page of the address space is placed in the physical memory, the OS keeps a per-process data structure known as a page table. It stores the address translations for each of the virtual pages of the address space and letting us know where in physical memory each page resides.

To translate a virtual address that a process generated, we have to split the address into 2 components: the Virtual Page Number(VPN) and the offset within the page. The bit required for the virtual address is $log_2N$ where N is the size of the virtual address space. VPN can be then mapped to PPN(Physical Page Number) and the offset are the same for both of them.

Where Are Page Tables Stored?

Page table can be huge in size, so we store the page table for each process in memory instead of a special register

What’s Actually In The Page Table

Since page table is just a data structure that is used to map virtual addresses to physical addresses, any data structure could work. The simplest form is linear page table, an array whose index is VPN and entries are PPN.

For the contents of each PTE, we have a number of different bits in there worth understanding at some level

• Valid bit to indicate whether the particular translation is valid
• Protection bits to indicate whether the page could be read from, written to or executed from
• Present bit indicate whether this page is in physical memory or in disk
• Dirty bit indicate whether the page has been modified since it was brought into memory
• Reference bit to track whether a page has been accessed

TLB

Storing the mapping information between virtual and physical address in the physical memory and performing lookup is a very slow process. So how can we speed up the translation?

This is when the Translation-Lookaside Buffer, or TLB, comes in handy. TLB is part of MMU, and it’s simply a hardware cache of popular virtual-to-physical address translation. So we can basically understand it as address-translation cache. For each VA translation, the hardware first checks the TLB to see if the translation is already held. It will only perform the actual translation (going through the page table) if it’s not there.

TLB Basic Algorithm

The algorithm of the hardware works like this:

• It first extract the VPN from VA and check if the TLB holds the translation of this page
  • if so, this is a TLB hit and we can extract the PPN from the TLB entry
• if not(TLB miss), we will do more work
  • the hardware will access the page table to find the translation
  • it will also update the TLB with the translation
  • then it will retry the instruction but this time, since the translation is in TLB, it will be fast