Paging

• A page is a sequence of N bytes where N is a power of 2.
• Let's assume that we have 1M of RAM. RAM is also called physical memory.
• We can subdivide the RAM into 4K pages. Thus 1M / 4K = 256 pages. 
• Thus, our RAM has 256 physical pages, each holding 4K.

Fig 1: Address translation from virtual to physical

Page Table

How is an address translated from virtual to physical?

Fig 2: Page Table

• First, like the cache, we split up a 32 bit virtual address into a virtual page (which is like a tag) and a page offset.
• We must convert the virtual page number to a physical page number.

For example,

• The virtual page consists of 20 bits. 
• A page table is a data structure which consists of 2²⁰ page table entries (PTEs). 
• The page table as an array of page table entries, indexed by the virtual page number.
• The page table's index starts at 0, and ends at 2²⁰ - 1.
• Suppose your program generates a virtual address. You'd extract bits B 31-12 to get the virtual page number. 
• Use that as an index into the above page table to access the page table entry (PTE).
• Each PTE consists of a valid bit and a 20 bit physical page (it's 20 bits, because we assume we have 1M of RAM, and 1M of RAM requires 20 bits to access each byte). 
• If the valid bit is 1, then the virtual page is in RAM, and you can get the physical page from the PTE. 
• This is called a page hit, and is basically the same as a cache hit.
• If the valid bit is 0, the page is not in RAM, and the 20 bit physical page is meaningless.
• This means, we must get the disk page corresponding to the virtual page from disk and place it into a page in RAM. This is called a page fault.