Imagine you are packing books into a library. In the last chapter, every process needed one continuous shelf. After a few processes came and went, the library had lots of small empty gaps, and a big new process could not fit anywhere even though the total free space was more than enough. That problem was external fragmentation.
Now imagine a smarter librarian. She cuts every book into equal-sized chapters, puts each chapter in any free slot on any shelf, and keeps a small index card that says "chapter 0 is in slot 17, chapter 1 is in slot 4, chapter 2 is in slot 30". The book no longer needs to be in one piece, so every free slot is useful.
That is exactly what paging does with memory. It is the memory-management technique used by practically every modern operating system: Linux, Windows, macOS, Android and iOS all rely on it.
In this chapter we will learn what pages and frames are, how a logical address is split and translated, work through number-based examples (the kind asked in GATE and university exams), run a small C program that shows real page numbers on Linux, and look at the trade-offs of page size. The next chapter, Page Tables & TLB, goes deeper into how page tables are stored and made fast.
The Problem Paging Solves
In Contiguous Memory Allocation & Fragmentation we saw that if a process must occupy one continuous block of physical memory:
Free memory gets broken into small holes (external fragmentation).
A process may be rejected even when the total free memory is enough.
Compaction can fix it, but moving processes around is slow.
Physical memory (contiguous allocation)
| OS | P1 | free 3 KB | P2 | free 2 KB | P3 | free 4 KB |
New process P4 needs 8 KB.
Total free = 3 + 2 + 4 = 9 KB → enough in total
Largest single hole = 4 KB → P4 cannot be loaded!Paging removes the root cause: a process no longer needs to be contiguous in physical memory.
What is Paging?
Paging is a memory-management scheme in which the logical address space of a process is divided into fixed-size blocks called pages, physical memory is divided into blocks of the same size called frames, and any page can be placed in any free frame. A per-process page table records which frame holds each page.
Three words to remember:
Term | Belongs to | Meaning |
|---|---|---|
Page | Logical (virtual) memory of a process | A fixed-size block of the process's address space |
Frame (page frame) | Physical memory (RAM) | A fixed-size slot in RAM, same size as a page |
Page table | Each process (kept by the OS) | Maps page number → frame number |
A picture makes it clear. Process A has 4 pages. Physical memory has 8 frames:
Process A Page table of A Physical memory (8 frames)
(logical)
page → frame frame 0 : OS
page 0 ─────────► 0 → 5 frame 1 : A page 3
page 1 ─────────► 1 → 6 frame 2 : (free)
page 2 ─────────► 2 → 3 frame 3 : A page 2
page 3 ─────────► 3 → 1 frame 4 : another process
frame 5 : A page 0
frame 6 : A page 1
frame 7 : (free)The process thinks it lives in one neat block from page 0 to page 3. In reality its pages are scattered across frames 5, 6, 3 and 1. The page table hides this from the program.
Key idea: the program sees a continuous logical address space; physical memory is allowed to be non-contiguous. The page table glues the two views together.
Why Pages and Frames Have the Same Size
Because pages and frames are the same size, any page fits exactly into any frame. There is no "this hole is too small" problem any more. The OS just needs a list of free frames; if a process needs n pages and there are at least n free frames, it can be loaded.
Page sizes are always a power of 2 (512 bytes, 4 KB, 2 MB, ...). We will see in a moment that this makes address translation almost free: no division is needed, just splitting the bits of the address.
Splitting a Logical Address
Every logical address generated by the CPU is split into two parts:
Logical address (m bits in total)
+-----------------------+------------------+
| page number p | offset d |
+-----------------------+------------------+
(m − n) bits n bits
page size = 2^n bytesPage number (p) → which page of the process. Used as an index into the page table.
Page offset (d) → which byte inside that page. Copied unchanged into the physical address.
In decimal terms:
p = logical address ÷ page size (integer division)
d = logical address mod page size
physical address = frame number × page size + dIn binary, when the page size is 2^n, dividing by 2^n just means "take the high bits" and the remainder is "the low n bits". That is why hardware can do it instantly.
How the Hardware Translates
CPU generates logical address
│
▼
+------------+--------+
| p | d |
+------------+--------+
│ │
│ index │ (offset is copied as is)
▼ │
+-------------+ │
| Page table | │
| p → f | │
+-------------+ │
│ │
▼ ▼
+------------+--------+
| f | d | physical address → goes to RAM
+------------+--------+The MMU (Memory Management Unit), which we met in Memory Management Basics, performs this translation on every single memory access. Notice that only the page number changes; the offset stays the same, because a page and its frame have the same internal layout.
Worked Example 1: Decimal Addresses
Let the page size be 1024 bytes (1 KB). A process has 4 pages with this page table:
Page | Frame |
|---|---|
0 | 5 |
1 | 2 |
2 | 7 |
3 | 0 |
Translate the logical address 2500.
Step 1: p = 2500 ÷ 1024 = 2 (integer division)
Step 2: d = 2500 mod 1024 = 452
Step 3: page table[2] = frame 7
Step 4: physical address = 7 × 1024 + 452 = 7168 + 452 = 7620Let us do a few more so the pattern sticks:
Logical address | Page p | Offset d | Frame | Physical address |
|---|---|---|---|---|
100 | 0 | 100 | 5 | 5 × 1024 + 100 = 5220 |
2500 | 2 | 452 | 7 | 7 × 1024 + 452 = 7620 |
3071 | 2 | 1023 | 7 | 7 × 1024 + 1023 = 8191 (last byte of frame 7) |
4096 | 4 | 0 | — | Invalid: the process has only pages 0 to 3, so the MMU raises a trap |
The last row is important. The page table also acts as protection: a process can only reach frames that appear in its own page table. Trying to use a page number outside the table (or one marked invalid) causes a trap to the OS, which on Linux usually ends as the famous Segmentation fault.
Worked Example 2: Hexadecimal Addresses
Real systems use a 4 KB page size (4096 = 212 bytes) and hexadecimal addresses. With 4 KB pages, the offset is the low 12 bits, which is exactly the last 3 hex digits (each hex digit is 4 bits).
Translate the 32-bit logical address 0x00403A7C, assuming the page table maps page 0x403 to frame 0x1F2.
Logical address = 0x00403A7C
└─────┘└─┘
page offset (last 3 hex digits = 12 bits)
Page number p = 0x00403 (= 1027 in decimal)
Offset d = 0xA7C
Page table[0x403] = frame 0x1F2
Physical address = frame bits followed by offset bits
= 0x1F2 | A7C
= 0x1F2A7CNo multiplication needed: we just replace the page number with the frame number and keep the offset. This is the real reason page sizes are powers of 2.
Seeing Pages on a Real Linux System
Let us ask Linux for its page size and split two real addresses into page number and offset. (These are virtual addresses. The physical frame numbers are hidden from normal programs for security reasons.)
#include <stdio.h>
#include <stdint.h>
#include <unistd.h>
int global_counter = 42;
int main(void) {
long page_size = sysconf(_SC_PAGESIZE); /* ask the OS for the page size */
int local_value = 7;
printf("Page size: %ld bytes\n\n", page_size);
uintptr_t addrs[2] = { (uintptr_t)&global_counter, (uintptr_t)&local_value };
const char *names[2] = { "global_counter", "local_value" };
for (int i = 0; i < 2; i++) {
uintptr_t va = addrs[i];
uintptr_t page = va / (uintptr_t)page_size; /* virtual page number */
uintptr_t offset = va % (uintptr_t)page_size; /* offset inside page */
printf("%-15s VA = 0x%012lx page = 0x%09lx offset = 0x%03lx (%lu)\n",
names[i], (unsigned long)va, (unsigned long)page,
(unsigned long)offset, (unsigned long)offset);
}
return 0;
}gcc -std=c17 -Wall -Wextra pagesplit.c -o pagesplit
./pagesplitOutput on x86-64 Linux (your addresses will differ on every run because of address space layout randomization, but the page size and the pattern will be the same):
Page size: 4096 bytes
global_counter VA = 0x5f40ad705010 page = 0x5f40ad705 offset = 0x010 (16)
local_value VA = 0x7ffcce1bcaa8 page = 0x7ffcce1bc offset = 0xaa8 (2728)Look at the hex: the page number is simply the address with its last 3 hex digits removed, and the offset is those last 3 digits. Exactly what we did by hand.
Loading a Process: The Free-Frame List
The OS keeps track of every physical frame in a frame table: one entry per frame saying whether it is free and, if not, which process (and page) uses it. Loading a process becomes very simple:
Find the size of the process in pages, say
n.Check that at least
nframes are free.Take any
nfree frames (they do not need to be next to each other).Load page
iinto the i-th chosen frame and writei → frameinto the new process's page table.
Free-frame list before: 14, 13, 18, 20, 15
New process needs 4 pages:
page 0 → frame 14
page 1 → frame 13
page 2 → frame 18
page 3 → frame 20
Free-frame list after: 15No searching for a "big enough hole", no first-fit / best-fit decision, no compaction. That simplicity is a big part of why paging won.
In the chapter Virtual Memory & Demand Paging we will relax one more rule: a process will not even need all its pages in memory to start running.
Internal Fragmentation in Paging
Paging removes external fragmentation completely, because every free frame is usable. But it introduces a small amount of internal fragmentation.
Processes are rarely an exact multiple of the page size, so the last page is usually only partly used.
Example: page size 4096 bytes, process size 10,300 bytes.
Pages needed = ceil(10300 / 4096) = 3
Used in last page = 10300 − 2 × 4096 = 2108 bytes
Wasted = 3 × 4096 − 10300 = 1988 bytes (internal fragmentation)Worst case: the process needs just 1 byte of its last page → almost a whole page (page size − 1 bytes) is wasted.
On average: about half a page per process (per memory region, to be precise) is wasted.
With 4 KB pages that is only about 2 KB per region, which is why internal fragmentation in paging is usually acceptable.
Choosing the Page Size
If small pages waste less memory, why not use tiny pages? Because every page needs a page-table entry, and the hardware has to cache translations. It is a trade-off:
Factor | Small pages (e.g. 4 KB) | Large pages (e.g. 2 MB) |
|---|---|---|
Internal fragmentation | Low | High |
Page table size | Large (many entries) | Small (few entries) |
Memory covered by the TLB cache | Small → more TLB misses | Large → fewer TLB misses |
Disk I/O per page (with virtual memory) | Many small transfers | Fewer, bigger transfers |
Precision (only bring in what is needed) | Good | Poor (may load data that is never used) |
What real systems use:
x86-64 (Intel / AMD): 4 KB base pages, plus huge pages of 2 MB and 1 GB.
ARM64: 4 KB, 16 KB or 64 KB base pages depending on configuration (Apple Silicon Macs use 16 KB).
Linux can use huge pages automatically through Transparent Huge Pages (THP) for big memory regions such as databases and JVM heaps.
You can check your system's base page size from the shell:
getconf PAGESIZE4096Paging Numericals: The Formulas
Exam questions on paging almost always use the same handful of relationships. Let:
logical address =
mbits, physical address =xbits, page size =2^nbytes
Quantity | Formula |
|---|---|
Offset bits |
|
Page number bits |
|
Number of pages (= page table entries) |
|
Frame number bits |
|
Number of frames |
|
Page table size |
|
Numerical 1
A logical address space has 64 pages of 1 KB each, mapped onto a physical memory of 32 frames. How many bits are in the logical and physical addresses?
Offset bits : 1 KB = 2^10 → 10 bits
Page bits : 64 pages = 2^6 → 6 bits
Logical addr : 6 + 10 = 16 bits
Frame bits : 32 frames = 2^5 → 5 bits
Physical addr: 5 + 10 = 15 bitsNotice that the logical address space can be bigger than physical memory. That only becomes useful with virtual memory, which we will study soon.
Numerical 2
A system has 32-bit logical addresses, 4 KB pages and 4-byte page-table entries. What is the size of the page table of one process?
Offset bits = log2(4096) = 12
Page number bits = 32 − 12 = 20
Number of entries = 2^20 = 1,048,576
Page table size = 2^20 × 4 bytes = 4 MB (per process!)4 MB of page table for every process, even a tiny one, and it would have to be contiguous in memory. That is clearly a problem, and solving it (multi-level, hashed and inverted page tables) is the main topic of the next chapter.
Protection and Sharing with Paging
Paging gives two more benefits almost for free:
Protection
Each process has its own page table, so it simply has no way to name another process's frames. This is the basis of process isolation.
Each page-table entry carries extra bits, such as valid/invalid, read/write and execute permissions. Writing to a read-only code page, for example, causes a trap. (We list all the common bits in Page Tables & TLB.)
Sharing
If two processes run the same program or use the same library (for example the C library libc), the read-only code pages can be shared: both page tables simply point to the same frames.
Process A page table Physical memory Process B page table
page 0 (libc code) → 12 ──► frame 12 ◄── 12 ← page 0 (libc code)
page 1 (libc code) → 13 ──► frame 13 ◄── 13 ← page 1 (libc code)
page 2 (A's data) → 40 41 ← page 2 (B's data)Only one copy of the library sits in RAM, no matter how many processes use it. Each process still has its own private data pages.
Advantages and Disadvantages of Paging
Advantages | Disadvantages |
|---|---|
No external fragmentation | Some internal fragmentation (last page) |
Very simple allocation: any free frame works | Page tables take memory (4 MB per process in the naive 32-bit case) |
Easy protection (per-page permission bits) | Each memory access needs a translation; without a cache this doubles memory accesses |
Easy sharing of code pages | Needs hardware support (MMU) |
The foundation for virtual memory and demand paging | Pages do not match the logical units (functions, arrays) the programmer thinks in |
The last disadvantage is what Segmentation (two chapters ahead) tries to address.
Contiguous Allocation vs Paging
Feature | Contiguous allocation | Paging |
|---|---|---|
Process in physical memory | One continuous block | Scattered across frames |
External fragmentation | Yes | No |
Internal fragmentation | With fixed partitions | Yes, last page only |
Translation hardware | Base + limit registers | Page table (+ TLB) |
Compaction needed? | Sometimes | Never |
Common Mistakes
Confusing pages and frames. Pages are logical (per process); frames are physical (in RAM). The page table maps pages to frames.
Translating the offset. The offset is never changed. Only the page number is replaced by the frame number.
Saying paging has no fragmentation. It has no external fragmentation, but it does have internal fragmentation in the last page.
Using the physical address size to count pages. The number of page-table entries depends on the logical address size; the size of each entry depends on the number of frames (plus control bits).
Forgetting units. 1 KB = 210 bytes, 4 KB = 212, 1 MB = 220, 1 GB = 230. Mixing 1000 and 1024 gives wrong bit counts.
Thinking one page table is shared by all processes. In the standard scheme every process has its own page table. (The inverted page table in the next chapter is the exception.)
Interview Questions
What is paging?
A memory-management scheme that divides a process's logical address space into fixed-size pages and physical memory into same-size frames. Any page can go into any free frame, and a per-process page table records the mapping. It allows a process to be non-contiguous in physical memory.
What is the difference between a page and a frame?
A page is a fixed-size block of logical (virtual) memory belonging to a process. A frame is a fixed-size block of physical memory. They are the same size; the page table maps pages to frames.
How is a logical address translated in paging?
The address is split into a page number (high bits) and an offset (low bits). The page number indexes the page table to get a frame number. The physical address is the frame number followed by the same offset, i.e. frame × page size + offset.
Why are page sizes powers of 2?
So that splitting an address into page number and offset is just taking the high and low bits, with no division. Building the physical address is also just concatenating frame bits and offset bits.
Does paging suffer from fragmentation?
No external fragmentation, because any free frame can hold any page. It does have internal fragmentation, because the last page of a process is usually only partly used, wasting on average half a page.
What are the trade-offs of a larger page size?
Larger pages mean smaller page tables, more memory covered by each TLB entry and more efficient disk I/O, but more internal fragmentation and less precise loading. Smaller pages are the opposite.
How does paging help with sharing and protection?
Each process has its own page table, so it can only reach frames mapped in it, and each entry has permission bits (valid, read/write, execute). For sharing, page tables of different processes can point to the same frames, e.g. read-only library code.
32-bit addresses, 4 KB pages, 4-byte entries: how big is the page table?
Offset = 12 bits, so 20 bits of page number and 220 entries. 220 × 4 bytes = 4 MB per process.
Summary
Paging splits logical memory into pages and physical memory into same-size frames; a process's pages can go into any free frames.
The page table (one per process) maps page number → frame number.
A logical address = page number + offset. Translation replaces the page number with the frame number; the offset is unchanged.
Physical address =
frame × page size + offset; with power-of-2 page sizes this is just bit concatenation.Paging eliminates external fragmentation but has some internal fragmentation (about half a page on average).
Page size is a trade-off: small pages waste less memory but need bigger page tables and cause more TLB misses. 4 KB is the common base size, with 2 MB / 1 GB huge pages available on x86-64.
Paging naturally supports protection (per-page bits, private page tables) and sharing (common frames for shared code).
A single flat page table can be huge (4 MB for 32-bit with 4 KB pages). The next chapter, Page Tables & TLB, shows how real systems shrink it and make translation fast.