X86 Architecture Basics: Memory Management

Memory Paging and Addressing

The address space that a program deals with is a virtual address space. That is, a program binary does not refer to physical memory addresses directly. A program deals with an address space as if the whole physical address space, such as the 4GB address space in 32-bit architecture, is available to it. The address space appears to the program as a linear or contiguous space. An address in the linear address space is known as the virtual address, which has to be mapped to a real physical address by the OS and hardware. In modern computer architecture the virtual address space is divided into units called pages, which can be of 4KB, 4MB or other size, including hugepages of 1GB.

The virtual address space together with paging facilitates following:

A program is not tied to physical memory address space.
A program can consider the physical memory as one linear address space even though it may reside in non-contiguous memory segments as shown in the figure above.
Irrespective of what is the size of physical memory, a program can use the whole virtual address space. For example, in 32-bit computer architecture a maximum of 4GB of physical memory can be supported. A program can use all of the 4GB as a virtual address space even though it may share the physical memory with many other programs each having its own 4GB virtual address space.
Protection at much granular level (page in this case as opposed to segment). As mentioned below each page can have its own access control flags, such as read only (for code pages), read and write (for data) and supervisor vs user accessible.

Note that, with the support of a feature called the physical address extension (PAE), current computer architecture can support more physical memory address space, for example, 64GB or more than that even with a 32-bit architecture. Obviously, modern 64-bit architecture can theoretically support 16 Exabyte of main memory. No matter what is the physical address space size, program address space should be orthogonal to the physical address space for the reasons mentioned above. In addition, many programs may have to deal with huge address spaces, such as main memory database, high-performance computing and Big Data applications. In addition, in a virtualized environment many hundreds of VMs with its many processes have to co-reside on a single physical computer (SMP or NUMA) and share the physical memory.

Page table can be organized in multiple hierarchies (typically 2 to 4) to save memory space occupied by the page table itself. For example, in a 4GB address space with 4KB page size there will be about 1 million pages. If each entry is 4 bytes, that amounts to 4MB page table size. A 2-level page hierarchy is shown in [FIG], where the second level tables can be allocated on-demand. The structure of a page table (PT) entry (PTE) is shown in [FIG], which contains the PT base address (PTBA) in the page directory (first level) and page frame number (PFN) in the page tables.

Virtual to Physical Address Mapping

The main memory unit or MMU maps linear or virtual addresses to physical addresses in page frames. Following are the major steps of virtual to physical address mapping:

When an OS schedules a process to run, it loads the page table directory base address of the process onto the privileged CR3 register. This is a privileged operation.
Assume that the EIP register points to an instruction as shown in the figure above. The ECX register contains a virtual memory address, which has to be translated into a physical memory address (PA). The MOV instruction will move the content of PA to the EAX register.
As shown in the figure above, the CPU sends the VA to the MMU that translates the VA to a PA.
The MMU attempts to map the VA to PA via the translation look-aside buffer (TLB) component of the MMU. The TLB is a fast associative memory caching the VA to physical address mapping. The TLB entries get invalidated or flushed out when new page table or directory address is loaded into CR3, which happens at context switches. If the VA is not in TLB, page walking is initiated, which can be done either in software (in OS) or hardware.
If the page of [ECX] has not been loaded into a page frame in physical memory as indicated by the present bit of 0, a page fault (vector number 14; see here) will be generated. The page fault handler will load the page from disk into a page frame and update PTE. The TLB is updated with the new VA to PA mapping. A page fault may also be generated when a program in user mode is trying to access a page with supervisor mode or program does not have the right read or write access permission as indicated by the R/W flag.

It is obvious from the figure that resolution of the physical memory location via page table walking introduces extra level of memory accesses, thus introducing extra latency.

The rate of page faults may potentially increase for following workloads, for example:

Memory intensive applications.
Applications spawning large number of child processes. A child process shares code and data with its parent. To optimize memory usage, a technique called the copy-on-write is used where the parent and child share the memory pages, instead of copying parent’s address space for the child. To avoid write conflict, the pages are marked as read-only. When a process P1 attempts to write a page, a page fault occurs and the page handler copies the page for P1 with write flag turned on.
Applications with low temporal and spatial locality. For example, program performing depth-first-search algorithms on a huge search space.

Google Sites

Report abuse