Memory Management

Virtual Memory

The OS’s process abstraction provides each process with a virtual memory space. Virtual memory is an abstraction that gives each process its own private, logical address space in which its instructions and data are stored. Each process’s virtual address space can be thought of as an array of addressable bytes from 0 up to some maximum address. Processes cannot access the contents of one another’s address spaces.

Operating systems implement virtual memory as part of the lone view abstraction of processes. That is, each process only interacts with memory in terms of its own virtual address space rather than the reality of many processes sharing the computers RAM simultaneously.

Process Address Space Layout

A process’s virtual address space is divided into several sections, each of which stores a different part of the process’s memory. The top part is reserved for the OS and can only be accessed in kernel mode. The text and data parts of a process’s virtual address space are initialized from the program executable file. The text section contains the program instructions, and the data section contains global variables. The stack and heap sections vary in size as the process runs. Stack space grows in response to the process making function calls, and shrinks as it returns from the function calls. Heap space grows when the process dynamically allocates memory space (via calls to malloc), and shrinks when the process frees memory space (with calls to free).

--------------------------------
|            OS Code           |
--------------------------------
|       Application Code       |
--------------------------------
|      Data (Global Vars)      |
--------------------------------
|             Heap             |
|             ⌄⌄⌄⌄             |
|                              |
|                              |
--------------------------------
|                              |
|                              |
|            ^^^^^             |
|            Stack             |
--------------------------------

Stack and Heap

• When you get done using heap memory, it needs to be cleaned up. This can be done using a process known as ‘garbage collection’, or manually by the developer when creating the app.
• Implementation of both the stack and heap is usually down to the runtime / OS.
• There are 2 memory constructs, stack and heap.

Stack

• A stack is a structure that represents a sequence of objects or elements that are available in a linear data structure. What does that mean? It simply means you can add or remove elements in a linear order. This way, a portion of memory that keeps variables created can function temporarily.
• Stored in computer RAM just like the heap.
• Variables created on the stack will go out of scope and are automatically deallocated.
• Much faster to allocate in comparison to variables on the heap.
• Implemented with an actual stack data structure.
• Stores local data, return addresses, used for parameter passing.
• Can have a stack overflow when too much of the stack is used (mostly from infinite or too deep recursion, very large allocations).
• Data created on the stack can be used without pointers.
• You would use the stack if you know exactly how much data you need to allocate before compile time and it is not too big.
• Usually has a maximum size already determined when your program starts.
• A collection of data needed for a single method is called a stack frame.

Heap

• Stored in RAM just like the stack.
• In C++, variables on the heap must be destroyed manually and never fall out of scope. The data is freed with delete, delete[], or free.
• Slower to allocate in comparison to variables on the stack.
• Used on demand to allocate a block of data for use by the program.
• Can have fragmentation when there are a lot of allocations and deallocations.
• In C++ or C, data created on the heap will be pointed to by pointers (from the stack) and allocated with new or malloc respectively.
• Can have allocation failures if too big of a buffer is requested to be allocated.
• You would use the heap if you don’t know exactly how much data you will need at run time or if you need to allocate a lot of data.
• Responsible for memory leaks.

Example:

int foo()
{
  char *pBuffer; //<--nothing allocated yet (excluding the pointer itself, which is allocated here on the stack).
  bool b = true; // Allocated on the stack.
  if(b)
  {
    //Create 500 bytes on the stack
    char buffer[500];

    //Create 500 bytes on the heap
    pBuffer = new char[500];

   }//<-- buffer is deallocated here, pBuffer is not
}//<--- oops there's a memory leak, I should have called delete[] pBuffer;

Why would an object be created on the heap or stack?

In computer science, whether an object is created on the heap or the stack depends on several factors, including object size, lifetime, dynamic allocation needs, sharing requirements, and polymorphism.

1. Object size: If the object is small, it can be created on the stack, but if it’s large, then it should be created on the heap.
2. Lifetime: If the object’s lifetime needs to transcend beyond the block/scope where it was created, objects should be created on the heap. Alternatively, if the object’s lifetime is within the context of the block/scope where it was created, objects can be created on the stack.
3. Dynamic allocation: Heap objects can be allocated dynamically at runtime, while stack objects need to be allocated at compile time.
4. Sharing: Heap objects can be shared between multiple threads, while stack objects are local to a single thread.
5. Polymorphism: Creating objects on the heap allows for polymorphism, where objects of different derived classes can be referenced using a base class pointer.

Free Space Management

• malloc is one example of a library used to manage pages of a process’s heap; the OS manages the address space of a process.
• Managing free space is simple when the space being managed is divided into fixed-size units. When a client requests memory, just return the first available segment.
• Free space management becomes difficult when the free space you are managing consists of variable-sized segments.
• This is external fragmentation.
• The generic data structure used to manage free space in the heap is known as the “free list”. The free list contains links to all free chunks of space in the managed memory.
• Any modern memory allocator will handle both splitting and coalescing.
• Most allocators store a little bit of extra information in a header block which is kept in memory. The header contains the size of the allocated region, and potentially a magic number to provide additional integrity checking, additional pointers to speed up deallocation, etc.

Memory Addresses

Because processes operate within their own virtual address spaces, operating systems must make an important distinction between two types of memory addresses. Virtual addresses refer to storage locations in a process’s virtual address space, and physical addresses refer to a location in RAM.

At any point in time, the OS stores in RAM the address space contents of many processes as well as OS code that it may map into every process’s virtual address space.

Virtual Addresses

• Virtual memory is the per-process view of its memory space, and virtual addresses are addresses in the process’s view of its memory. If two processes run the same binary executable, then they will have the exact same virtual addresses for function code and for global variables in the address spaces.
• Processors generally provide some hardware support for virtual memory. An OS can make use of this hardware support to perform virtual to physical address translation quickly, avoiding having to trap to the OS to handle every address translation.
• The memory management unit (MMU) is the part of the computer hardware that implements address translation. The CPU has a memory management unit (MMU) to add flexibility in accessing memory. The kernel assists the MMU by breaking down the memory used by a process into chunks called ‘pages’. The kernel maintains a data structure, called a ‘page table’, that maps a process’s virtual page addresses into real page addresses in memory. As a process accesses memory, the MMU translates the virtual addresses used by the process into real addresses based on the kernel’s page table.

Paging

Although many virtual memory systems have been implemented over the years, paging is now the most widely used implementation of virtual memory.

It is said that the operating system takes two approaches when solving most any space-management problem: the first approach is to chop things up into variable-sized pieces (i.e. segmentation), this can lead to fragmentation and becomes difficult to manage over time. The second approach chops things up into fixed-sized pieces (i.e. paging). With paging, we divide a process’s address space into a number of fixed-sized units known as ‘pages’. We then view physical memory as a number of fixed-sized slots called “page frames”, each of which can contain a single virtual memory page.

In a paged virtual memory system, the OS divides the virtual address space of each process into fixed-sized chunks called pages. The OS defines the page size for the system. Page sizes of a few kilobytes are commonly used in general purpose operating systems today. 4 KB is the default page size on many systems. Physical memory is similarly divided into page-sized chunks called frames. Because pages and frames are defined to be the same size, any page of a process’s virtual memory can be stored in any frame of physical RAM.

You can get a system’s page size by looking at the kernel configuration:

getconf PAGE_SIZE
4096

Physical memory (100 MB total (we choose a small size here for simplicity)): Pages frames:

|------------------|
|- Frame 0 (25MB) -|
|------------------|
|- Frame 1 (25MB) -|
|------------------|
|- Frame 2 (25MB) -|
|------------------|
|- Frame 3 (25MB) -|
|------------------|

These frames can exist practically anywhere in physical memory. The OS keeps track of the virtual-to-physical mapping in a “page table”. The page table is a “per-process” data structure.

Page table for process with PID 8012:

|---------------------------------------------|
|- Virtual Frame 0 (25MB) > Physical frame 0 -|
|---------------------------------------------|
|- Virtual Frame 1 (25MB) > Physical frame 6 -|
|---------------------------------------------|
|- Virtual Frame 2 (25MB) > Physical frame 1 -|
|---------------------------------------------|
|- Virtual Frame 3 (25MB) > Physical frame 3 -|
|---------------------------------------------|

Virtual and Physical Addresses in Paged Systems

Paged virtual memory systems divide the bits of a virtual address into two parts; the high-order bits specify the page number on which the virtual address is stored, and the low-order bits correspond to the byte offset within the page (which byte from the top of the page corresponds to the address).

Similarly, paging systems divide physical addresses into two parts; the high-order bits specify the frame number of physical memory, and the low-order bits specify the byte offset within the frame. Because frames and pages are the same size, the byte offset bits in a virtual address are identical to the byte offset bits in its translated physical address. Virtual addresses differ from their translated physical addresses in their high-order bits, which specify the virtual page number and the physical frame number.

Virtual Address Structure

• Every virtual address issued by a process is split into two parts by the hardware:
  • Virtual Page Number (VPN) — identifies which page the address falls in
  • Page Offset — the byte position within that page
• The page size determines how many bits go to the offset. A 4 KB page needs 12 bits (2^12 = 4096).
• The remaining bits form the VPN.

32-bit virtual address with 4 KB pages (12-bit offset, 20-bit VPN):

 31                 12 11                 0
 |-------- VPN -------|------ Offset ------|
 |     20 bits        |      12 bits       |
 |--------------------|-------------------|

64-bit virtual address with 4 KB pages (common on x86-64):

 63          48 47          12 11          0
 |-- unused --|---- VPN -----|-- Offset ---|
 |  16 bits   |   36 bits    |   12 bits   |
 |------------|--------------|-------------|

(x86-64 only uses 48 bits for virtual addresses in practice; bits 48–63 are sign-extended.)

Translating a Virtual Address to a Physical Address

When the CPU accesses a virtual address, the MMU performs the following steps:

Step 1: Split the virtual address
+------------------+----------------+
|   VPN            |   Offset       |
+------------------+----------------+

Step 2: Use VPN to index into the page table
+------------------+      +---------------------+
|   VPN            | ---> | Page Table Entry    |
+------------------+      | (contains PFN +     |
                          |  valid/dirty/prot   |
                          |  flags)             |
                          +---------------------+

Step 3: Combine PFN with original offset
+------------------+----------------+
|   PFN            |   Offset       |  <-- Physical Address
+------------------+----------------+

• The offset is never translated — it passes through unchanged. Only the VPN is replaced by the PFN.
• If the page table entry’s valid bit is 0, the page is not in physical memory and a page fault is triggered — the OS loads the page from disk and retries.

Concrete Example

Assume:

• 16-bit virtual address space
• Page size: 256 bytes → offset = 8 bits (2^8 = 256)
• VPN = upper 8 bits

Virtual address: 0x026C  =  0000 0010 0110 1100

Split:
+----------+----------+
|  VPN     |  Offset  |
|  0x02    |  0x6C    |
| (page 2) | (byte 108)|
+----------+----------+

Page table lookup (VPN 0x02):
+---------+-------------------+
| VPN     | PFN               |
+---------+-------------------+
|  0x00   | 0x05              |
|  0x01   | 0x08              |
|  0x02   | 0x03  <-- match   |
|  0x03   | 0x07              |
+---------+-------------------+

Physical address = PFN 0x03 + offset 0x6C:
+----------+----------+
|  PFN     |  Offset  |
|  0x03    |  0x6C    |
+----------+----------+
= 0x036C

Page Table Entry (PTE) Flags

Each entry in the page table stores more than just the PFN — it also carries protection and status bits:

+-----+-----+-----+-----+-----+-------- PFN --------+
|  V  |  R  |  W  |  X  |  D  |   Physical Frame #  |
+-----+-----+-----+-----+-----+--------------------+
  ^     ^     ^     ^     ^
  |     |     |     |     Dirty: page has been written to
  |     |     |     Execute: page can be executed
  |     |     Write: page can be written
  |     Read: page can be read
  Valid: page is present in physical memory (0 = page fault)

A Page Table Entry (PTE) also includes a dirty bit that is used to indicate if the in-RAM copy of the page has been modified.

Page Table Structure

Linear (Single-Level) Page Table

• The simplest form: a flat array stored in memory, indexed directly by the VPN.
• Entry i in the array is the PTE for virtual page i.
• The OS stores the base address of this array in a register (e.g., CR3 on x86).

VPN 0  +------------------+
       | PTE 0 (PFN + flags)|
VPN 1  +------------------+
       | PTE 1 (PFN + flags)|
VPN 2  +------------------+
       | PTE 2 (PFN + flags)|
  ...  +------------------+
VPN N  | PTE N (PFN + flags)|
       +------------------+

The size problem:

• 32-bit address space, 4 KB pages → 2^20 = 1,048,576 entries
• Each PTE is 4 bytes → 4 MB per process, just for the page table
• With 100 running processes → 400 MB of memory consumed by page tables alone
• A 64-bit address space makes this completely impractical

Multi-Level Page Tables

• Rather than one large flat array, split the VPN into multiple parts and build a tree of page tables.
• Only allocate inner table nodes for regions of the address space actually in use — large unmapped gaps consume no memory.
• Each level of the tree is itself a page-sized table (fits in one 4 KB page).

Two-level example (x86 32-bit, 10|10|12 split):

Virtual address (32 bits):
+----------+----------+--------------+
|  VPN1    |  VPN2    |   Offset     |
| 10 bits  | 10 bits  |   12 bits    |
+----------+----------+--------------+
     |           |
     |           +-------> indexes into a second-level page table
     +-----------------> indexes into the Page Directory

The walk:

CR3 register
     |
     v
+--------------------+         (Page Directory — 1024 entries)
| PDE 0              |
| PDE 1              |
| ...                |
| PDE[VPN1] ------+  |
| ...             |  |
+--------------------+
                  |
                  v
         +--------------------+   (Second-level Page Table — 1024 entries)
         | PTE 0              |
         | PTE 1              |
         | ...                |
         | PTE[VPN2] ---+     |
         | ...          |     |
         +--------------------+
                        |
                        v
                  +----------+----------+
                  |   PFN    |  Offset  |  <-- Physical Address
                  +----------+----------+

• If PDE[VPN1] is not valid, the entire second-level table for that region is not allocated — saving 4 MB for every 4 MB gap in the address space.

x86-64 Four-Level Page Table (9|9|9|9|12)

x86-64 uses a 48-bit virtual address split into four 9-bit VPN fields plus a 12-bit offset:

Virtual address (48 bits used):
+-------+-------+-------+-------+--------------+
|  PGD  |  PUD  |  PMD  |  PTE  |   Offset     |
| 9 bits| 9 bits| 9 bits| 9 bits|   12 bits    |
+-------+-------+-------+-------+--------------+

CR3
 |
 v
+-------+    +-------+    +-------+    +-------+    +---------+
|  PGD  | -> |  PUD  | -> |  PMD  | -> |  PTE  | -> | PFN +   |
| [idx] |    | [idx] |    | [idx] |    | [idx] |    | Offset  |
+-------+    +-------+    +-------+    +-------+    +---------+
  ^             ^             ^             ^
  bits 47-39    bits 38-30    bits 29-21    bits 20-12

Page Table Size Comparison

Translation Lookaside Buffer (TLB)

Although paging has many benefits, it also results in a significant slowdown to every memory access. In a paged virtual memory system, every load and store to a virtual memory address requires two RAM accesses; the first reads the page table entry (PTE) to get the frame number for virtual-to-physical address translation, and the second reads or writes the byte(s) at the physical RAM address. Thus, in a paged virtual memory system, every memory access is twice as slow as in a system that supports direct physical RAM addressing.

One way to reduce the additional overhead of paging is to cache page table mappings of virtual page numbers to physical frame numbers. When translating a virtual address, the MMU first checks for the page numbers in the cache. If found, then the page’s frame number mapping can be grabbed from the cache entry, avoiding one RAM access for reading the PTE.

A translation look-aside buffer (TLB) is a hardware cache that stores (page number, frame number) mappings. It is a small, fully associative cache that is optimized for fast lookups in hardware. When the MMU finds a mapping in the TLB (a TLB hit), a page table lookup is not needed, and only one RAM access is required to execute a load or store to a virtual memory address.

CPU issues virtual address
         |
         v
   +------------+     hit     +----------------------+
   |    TLB     | ----------> | Use cached PFN       |
   +------------+             +----------------------+
         |
       miss
         |
         v
   +------------+
   | Page Table | (walks the page table in memory)
   | Walk       |
   +------------+
         |
         v
   +------------------+
   | Load entry into  |
   | TLB, retry       |
   +------------------+

• A TLB hit resolves the address in ~1 cycle. A TLB miss takes tens to hundreds of cycles (memory access to walk the page table).
• Context switches (switching between processes) require either flushing the TLB or tagging entries with an ASID (Address Space Identifier) so entries from different processes can coexist.
• With a warm TLB, the number of page table levels has no runtime impact.

Demand Paging

A user process doesn’t need all of its memory to be immediately available in order to run. The kernel generally loads and allocates pages as a process needs them; this system is known as on-demand paging or just demand paging. Let’s see how a program starts and runs as a new process:

1. The kernel loads the beginning of the program’s instruction code into memory pages.
2. The kernel may allocate some working-memory pages to the new process.
3. As the process runs, it may determine that the next instruction in code isn’t in any of the memory pages that the kernel loaded initially. At this point, the kernel will take over and load the necessary page into memory, and then lets the program resume execution.

Page Faults

If a memory page isn’t ready when a process wants to use it, the process triggers a page fault. If a page fault occurs, the kernel takes control of the CPU from the process in order to get the page ready. There are two kinds of page faults, major and minor.

• A page fault occurs when a process tries to access a page that is not currently stored in RAM. The opposite is a page hit. To handle a page fault, the OS needs to keep track of which RAM frames are free so that it can find a free frame of RAM into which the page read from disk can be stored.
• Minor page faults occur when the page is in main memory, but the MMU doesn’t know where it is.
• Major page faults occur when the desired memory page isn’t in main memory at all, which means that the kernel must load it from disk or some other slow storage media. Major page faults will bog down a system. Some major page faults are unavoidable, like when the system loads the code from disk when running a program for the first time.

You can drill down to the page faults for individual processes by using the top, ps, and time commands. You’ll need to use the system version of time for this:

/usr/bin/time cal > /dev/null
0.00user 0.00system 0:00.00elapsed 100%CPU (0avgtext+0avgdata 2824maxresident)k
0inputs+0outputs (0major+130minor)pagefaults 0swaps

As you can see in the output above, there were 0 major page faults and 130 minor page faults when running the cal program.

Page Fault Flow Control

• There are three cases to understand when a TLB miss occurs:
  1. The page was both present and valid. In this case, the TLB miss handler can simply grab the PFN from the PTE, retry the instruction (this time resulting in a TLB hit), and continue on.
  2. The page is valid but not present.
  3. The page is invalid and not present. The reason for the page being invalid is most likely due to a bug.

How Linux Organizes Physical Memory

At boot, the kernel organizes and partitions RAM into a tree-like hierarchy consisting of nodes, zones, and page frames (page frames are physical pages of RAM). The top level of the hierarchy is made up of nodes, which represent a collection of memory that is local to a particular CPU or group of CPUs. Each node contains one or more zones, which are collections of page frames that share similar characteristics. The zones are further divided into page frames, which are the smallest unit of memory that can be allocated by the kernel.

Any processor core can access any physical memory location, regardless of which node it belongs to. However, accessing memory that is local to the core’s node is faster than accessing memory that is located on a different node. This is because local memory access avoids the overhead of traversing interconnects between nodes.

NUMA vs. UMA

Essentially, nodes are data structures that are used to denote and abstract a physical RAM module on the system motherboard and its associated controller chipset. Actual hardware is being abstracted via software. Two types of memory architectures exist, UMA (Uniform Memory Access) and NUMA (Non-Uniform Memory Access).

NUMA

• In a NUMA architecture, each processor has its own local memory, and accessing local memory is faster than accessing memory that is located on a different node. This is because local memory access avoids the overhead of traversing interconnects between nodes.
• NUMA architectures are commonly used in high-performance computing systems, where multiple processors are used to perform complex computations. By using NUMA, these systems can achieve better performance and scalability than traditional UMA architectures.
• NUMA systems must have at least 2 physical memory banks (nodes) to be considered NUMA.
• One can use the lstopo command to view the NUMA topology of a system. The output will show the number of nodes, the amount of memory in each node, and the CPUs that are associated with each node. hwloc is another tool that can be used to view the NUMA topology of a system. It provides a graphical representation of the system’s hardware topology, including the NUMA nodes and their associated memory and CPUs.
• The number of zones per node is dynamically determined by the kernel at boot time based on the amount of memory in the node and the system architecture. The kernel typically creates three zones per node: DMA, DMA32, and Normal. The DMA zone is used for memory that is accessible by devices that use direct memory access (DMA), the DMA32 zone is used for memory that is accessible by 32-bit devices, and the Normal zone is used for all other memory. In addition to these standard zones, the kernel may also create additional zones based on the system architecture and configuration. You can view /proc/buddyinfo to see the memory zones and their associated page frames.

cat /proc/buddyinfo
Node 0, zone      DMA      0      0      0      0      0      0      0      0      1      1      2
Node 0, zone    DMA32      6      6      8      7      5      6      7      4      8      9    283
Node 0, zone   Normal   3170   7694  10543   8113   5011   1761    552    182     55     66  10595

UMA

• In a UMA architecture, all processors share the same physical memory, and accessing any memory location takes the same amount of time, regardless of which processor is accessing it.
• In Linux, UMA systems are treated as NUMA systems with a single node. This means that the kernel still uses the same data structures and algorithms for managing memory, but there is no need to consider the locality of memory access.

Policies

• If we know the number of cache hits and misses, we can calculate the Average Memory Access Time (AMAT): AMAT = (memory access time) + ((cache hit probability) * disk access time)
• FIFO: typical first in, first out page replacement policy, nothing fancy here
• Random: Remove a random page or pages when under memory pressure
• LRU/LFU: Least recently used/Least Frequently used
• MRU/MFU: Most recently used/most frequently used