Operating Systems – Memory Virtualization – Paging

August 25, 2020 | minutes read

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


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

Generating the virtual private number and Physical Table Entry address

18.2 Where are page tables stored


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)

Physical Frame Number (PFN) and metadata bits (e.g. active, dirty, read-only, executable)

18.3 What’s actually in the page table


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


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

Memory Trace – for loop


This translates into the following assembly

Initialization loop

I’m Matt Chung. I’m a software engineer, seasoned technology leader, and father currently based in Seattle and London. I love to share what I know. I write about topic developing scalable & fail-safe software running in the AWS cloud, digital organization as a mechanism for unlocking your creativity, and maximizing our full potentials with personal development habits.

View all articles