In my other blog post on memory segmentation, I talked about diving the process’s virtual address space into segments: code, heap, stack. Memory segmentation is just one approach to memory virtualization and another approach is paging. Whereas segmentation divides the address space into segments, paging chops up the space into fixed-sized pieces.

Each piece is divided into a virtual private number (VPN) and the offset; the number of bits that make up the offset is determined by the size of the page itself and the number of pages dictate the number of bits of the virtual private number.

To support the translation between virtual address to physical address, we need a page table, a per process data structure that maps the virtual address to the physical frame number (PFN).

Chapter 18 Paging (Introduction)

Two approaches when solving most any space management problem
Instead of diving the process into variable sized segments (i.e. code, stack, heap), we break down into fixed sized pieces called pages
Correspondingly, we view physical memory as an array of fixed size slots called page frames; each of these frames can contain a single virtual memory page

18.1 A simple example and overview

Summary

We divide a memory address into virtual private number (VPN) and the offset. The size of the page itself represents the number of bits for the offset. Similarly, the number of pages dictates the number of bits within the virtual private numbering scheme

18.2 Where are page tables stored

Summary

Assume for now that the page table is also stored in memory. And the page table can be expensive: imagine each page is 4KB (i.e. 12 bits) in a 32bit virtual address space. That means 20 bits required to represent each of the VPN. So, 2^20 equals roughly 4MB. Then, for each entry essentially maps the VPN to the PFN (physical frame number)

18.3 What’s actually in the page table

Summary

What are some additional bits we want to store in the page table entry? We can build a page table as an array (simple solution) and can index into the array. Once we indexed to the appropriate item, then we can look up (probably most importantly) the mapping between the virtual address and the physical number (reminds me of what we do at work on the data plane). Then, we can look up the mapping bits like protection, active, executable, read, write, etc.

18.4 Paging: Also Too Slow

Summary

Generating the virtual private number and Physical Table Entry address

In order to retrieve the memory data of an address, multiple steps are required. First, extract the virtual private number (VPN) by applying a mask (VPN_MASK) and then right shifting. Take this constructed address, multiply it by the size of a page table entry, then add this value to the address stored in the page table entry register. This address serves as the index into the page table, and from there, we can extract the physical frame number.

18.5 A memory trace

This translates into the following assembly