Demand Paging — A busy restaurant !

Introduction

When you call malloc, the system does not immediately reserve physical RAM for your data, except for a tiny amount needed to track internal metadata. Instead, a mechanism called demand paging operates behind the scenes to provide physical memory only when it is strictly necessary.

Imagine you, the process, call a busy restaurant to book a table. The host, the kernel, accepts your request, but does not actually set aside a specific empty table right then. Instead, the host gives you a promise: we will have a seat for you when you get here. The host records your reservation ID, which is like a virtual address.

The real work begins when you actually show up. Your arrival creates a momentary interruption for the host. In computers, that moment is a page fault. First, the host checks the ledger to confirm your reservation ID is valid. If it is valid, the host locates an empty table, meaning physical RAM, and assigns it to you. Only once you are seated does the transaction become real. This is the moment, and not before, that you are actually consuming physical resources.

The Mechanics: Pages, Frames, and the PFN

To understand the experiment, first understand what a page is.

Linux does not manage memory byte by byte. It uses 4KB blocks.

• Virtual page: the 4KB block of address space your program sees.
• Physical frame: the actual 4KB slot in hardware RAM.

The translation happens in the page table. When your program tries to access a variable, the MMU, or Memory Management Unit, looks up your virtual page to find the corresponding PFN, or Page Frame Number. The PFN is the ID of the physical slot.

The critical rule is simple: if the page table entry is empty and no PFN has been assigned, the CPU triggers a page fault.

The Experiment

The goal of this experiment is to show how demand paging works in practice. We allocate 100 chunks of 12KB each in a loop. In total, that requires about 1.2MB of physical RAM when fully used. The experiment prints stats such as PSS and page faults.

#define CHUNK_SIZE (1024 * 12)  // 12 KB
#define NUM_PTRS 100           // Total 1200KB

Each malloc needs 3 pages to house a chunk: 4KB + 4KB + 4KB = 12KB.

Malloc Loop Analysis: Lighter Demand Paging

void *ptrs[NUM_PTRS];

printf("--- EXPERIMENT START ---\n");
print_stats("1. Baseline");

for (int i = 0; i < NUM_PTRS; i++) {
    ptrs[i] = malloc(CHUNK_SIZE);
    printf("- mallocing %d\n", i);
    print_stats("- After malloc");
}

print_stats("2. After Malloc (Virtual Only)");

malloc needs to write a metadata header, approximately 16 bytes, at the beginning of the chunk.

• Because 12KB is page-aligned, the header falls on the first page of the 3-page block.
• Writing the header triggers a page fault for that first page.
• Result: you get 1 page fault and 4KB of physical memory immediately.

After the malloc loop completes, the program causes about 100 page faults and about 400KB of physical RAM growth. The baseline when the process starts was 100 page faults and 81KB PSS, required by the kernel to initialize the process and not related to malloc.

--- EXPERIMENT START ---
1. Baseline                  | PSS:    81 KB | PageFaults: 100
- mallocing 0
- After malloc               | PSS:    86 KB | PageFaults: 102
- mallocing 1
- After malloc               | PSS:    90 KB | PageFaults: 103
...
- mallocing 99
- After malloc               | PSS:   482 KB | PageFaults: 201
2. After Malloc              | PSS:   482 KB | PageFaults: 201

Memset Loop Analysis: Heavy Demand Paging

for (int i = 0; i < NUM_PTRS; i++) {
    // This is where the Page Fault Storm happens!
    printf("- memsetting %d\n", i);
    memset(ptrs[i], 0xAA, CHUNK_SIZE);
    print_stats("- After memset");
}

print_stats("3. After Memset (Demand Paging!)");

memset writes every byte of each chunk because it sets the entire allocation to 0xAA.

• Some bytes fall in the first page, for which a page fault already occurred during the malloc phase. The page table already has a valid entry there, so no page fault occurs for that page.
• For the second and third pages, a page fault occurs because the page table does not have the present bit set. The MMU finds the available physical frame after the fault.
• Result: you get 2 page faults and 8KB of physical memory immediately.

After the memset loop completes, the program causes about 200 more page faults and about 800KB more physical RAM growth.

- memsetting 0
- After memset               | PSS:   494 KB | PageFaults: 204
- memsetting 1
- After memset               | PSS:   502 KB | PageFaults: 206
- memsetting 2
- After memset               | PSS:   510 KB | PageFaults: 208
...
- memsetting 99
- After memset               | PSS:  1286 KB | PageFaults: 402
3. After Memset              | PSS:  1286 KB | PageFaults: 402

Summary

• The illusion: processes see linear virtual memory, but the OS manages fragmented physical frames.
• The trigger: malloc is cheap; it mostly updates metadata. memset is expensive; it triggers heavier demand paging.
• The mechanism: accessing a virtual page with no physical frame triggers a page fault. The kernel catches the fault, allocates a 4KB physical frame, and updates the page table.
• The evidence: the 12KB allocation required exactly 3 pages. malloc faulted in the first page for metadata, and memset faulted in the remaining two pages for data.