SyntaxPilot
Courses/CS Fundamentals for Placements/Lesson 32
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

CS Fundamentals for Placements · Lesson 32 of 90

Page table structures and segmentation

multilevel (hierarchical) pagingtwo-level paging numericalsouter page tablehashed page tableinverted page tablehuge pagessegmentationsegment tablesegment base and limitsegmentation faultsegmentation vs pagingsegmented pagingswapping and swap space

These are the notes for CS Fundamentals for Placements, episode 32. Last episode you invented paging. Today the page table itself becomes the problem: it is far too big. We measure it live, then shrink it with multilevel (hierarchical) paging, hashed page tables and inverted page tables, make the TLB go further with huge pages, and then look at memory the way a programmer sees it: segmentation, the segment table with base and limit, a real segmentation fault, segmentation vs paging, segmented paging, and finally swapping and swap space. Every term is explained in plain words the first time it appears, and there is a full glossary at the end.

All program outputs below are real: every C program was compiled with gcc 13.3 -O2 (the SyntaxPilot compiler's flags: gcc -O2 -Wno-unused-result main.c -o main -lm) and run on Linux x86-64 on 5 November 2026.

Recap: paging in 30 seconds

  • A page is a fixed-size piece of a program's address space (here 4 KB = 4096 bytes).
  • A frame is a piece of physical RAM of exactly the same size.
  • The page table (one per process) says which frame holds each page.
  • A virtual (logical) address splits into a page number and an offset (the byte inside the page). With 32-bit addresses and 4 KB pages, the offset is 12 bits (2^12 = 4096) and the page number is the other 20 bits.
  • The MMU (memory management unit, the address-translating hardware in the CPU) replaces the page number with a frame number and keeps the offset.
  • Each row of the page table is a page table entry (PTE): the frame number plus bits such as valid (this page is mapped) and dirty (this page was written).
  • The TLB (translation lookaside buffer) is a small, fast cache of recent translations.
virtual address  = | page number (20 bits) | offset (12 bits) |
                              │ page table
                              ▼
physical address = | frame number          | same offset      |

Problem 1: how big is ONE page table?

A flat page table is one simple array with an entry for every page of the address space, whether the program uses it or not. Let's compute its size.

#include <stdio.h>
// One flat page table per process: one entry for EVERY page
void flat(int bits, int pte_bytes) {
    unsigned long long pages = 1ULL << (bits - 12);   // 4 KB pages
    unsigned long long mb = (pages * pte_bytes) >> 20;
    printf("%d-bit: %llu entries x %d B = %llu MB per process\n",
           bits, pages, pte_bytes, mb);
}
int main(void) {
    flat(32, 4);
    flat(48, 8);                     // 524288 MB = 512 GB!
    // a small program really uses only 2 MB = 512 pages
    printf("used: 512 of %d entries = %.2f%%\n",
           1 << 20, 512 * 100.0 / (1 << 20));
}

Output:

32-bit: 1048576 entries x 4 B = 4 MB per process
48-bit: 68719476736 entries x 8 B = 524288 MB per process
used: 512 of 1048576 entries = 0.05%
  • 1ULL << n is 2^n as an unsigned long long (a 64-bit unsigned integer); >> 20 divides by 2^20 = 1,048,576, turning bytes into MB.
  • 32-bit: 2^20 entries × 4 B = 4 MB per process. 100 processes = 400 MB of tables.
  • 48-bit (with 8-byte entries): 2^36 entries × 8 B = 512 GB per process. Impossible.
  • A small program uses about 2 MB = 512 pages, so only 0.05% of the table is useful.
  • Worse: a flat table is one array, so it needs 4 MB of contiguous (side-by-side) RAM, the very problem paging was invented to escape.

Why it failed: a flat table pays for the whole address space, but real programs use only a few small regions of it (code at the bottom, the stack at the top, a big empty gap between). Such an address space is called sparse.

Fix 1: multilevel (hierarchical) paging

The story: finding a book in a huge library

Big library Paging
The board at the door: rows 1 to 1024, and where each row's shelf list is Outer page table (indexed by the first part of the page number)
The shelf list inside each row Inner page table (indexed by the second part; gives the frame)
An empty row: no shelf list is printed, the board just says "empty" Missing inner tables: unused regions cost nothing
The page inside the book The offset, unchanged

A table of tables is called multilevel paging or hierarchical paging. The outer table is also called the page directory.

Two-level paging: split the page number

32-bit virtual address:
| p1: 10 bits | p2: 10 bits | offset: 12 bits |
   outer index   inner index   byte in the page

p1     = va >> 22            (shift right: drop the low 22 bits)
p2     = (va >> 12) & 0x3FF  (& with a mask keeps the low 10 bits)
offset = va & 0xFFF          (keep the low 12 bits)
  • >> (shift right) moves bits to the right, dropping the ones that fall off (episode 3).
  • & (bitwise AND) with a mask keeps only the bits that are 1 in the mask. 0x3FF is ten 1 bits; 0xFFF is twelve.
  • Why 10 + 10? 2^10 = 1024 entries × 4 B = 4096 B = exactly one page. So every table, outer or inner, fits in one frame and can be placed anywhere in RAM: no contiguous 4 MB array any more.
        va ──► p1 ──► outer table[p1] ──► inner table ──► [p2] ──► frame
                                                                      │
                                         physical = frame << 12 | offset

Two-level translation in C

#include <stdio.h>
// Two-level paging, 32-bit address = 10 | 10 | 12 bits
int inner1[1024], inner3[1024];       // only 2 inner tables exist
int *outer[1024];                     // outer table: 1024 pointers
void translate(unsigned va) {
    unsigned p1 = va >> 22, p2 = (va >> 12) & 0x3FF, off = va & 0xFFF;
    printf("0x%08X -> p1=%u p2=%u off=0x%03X", va, p1, p2, off);
    if (!outer[p1]) { printf("  no inner table: page fault\n"); return; }
    unsigned frame = outer[p1][p2];
    printf("  frame 0x%X -> 0x%X\n", frame, frame << 12 | off);
}
int main(void) {
    outer[1] = inner1; outer[3] = inner3;     // the OS fills these in
    inner1[3] = 0x2A5;  inner3[0] = 0x07;
    translate(0x00403A7C);
    translate(0x00C00010);
    translate(0x80000000);
    printf("tables: 4 KB outer + 2 x 4 KB inner = 12 KB, flat: 4 MB\n");
}

Output:

0x00403A7C -> p1=1 p2=3 off=0xA7C  frame 0x2A5 -> 0x2A5A7C
0x00C00010 -> p1=3 p2=0 off=0x010  frame 0x7 -> 0x7010
0x80000000 -> p1=512 p2=0 off=0x000  no inner table: page fault
tables: 4 KB outer + 2 x 4 KB inner = 12 KB, flat: 4 MB
  • outer is an array of 1024 pointers (variables holding addresses); a global array starts as all zeros, i.e. NULL (the "points nowhere" pointer).
  • %08X prints a number in hexadecimal, padded to 8 digits.
  • frame << 12 | off puts the frame number in the high bits and the offset in the low 12 bits: the physical address.
  • Address 0x80000000 has p1 = 512, where there is no inner table: a page fault, a trap into the OS because the page is not mapped (next episode handles it properly).
  • Total table memory: 12 KB instead of 4 MB.

Numerical: memory accesses and effective access time (EAT)

Every level is one more memory access. With 2 levels and no TLB, one memory reference costs 3 accesses: the outer table, the inner table, then the data. In general: levels + 1 accesses on a TLB miss.

TLB lookup = 10 ns, memory access = 100 ns, TLB hit ratio = 90%, 2 levels
TLB hit : 10 + 100         = 110 ns
TLB miss: 10 + 3 x 100     = 310 ns
EAT     = 0.9 x 110 + 0.1 x 310 = 99 + 31 = 130 ns     (no TLB at all: 300 ns)

The effective access time (EAT) is the average time per memory reference: hit ratio × hit time + miss ratio × miss time. The hit ratio is the fraction of lookups found in the TLB.

Numerical: how many levels?

48-bit virtual address, 4 KB pages, 8-byte entries
offset       = 12 bits  →  page number = 48 - 12 = 36 bits
one table    = 4096 / 8 = 512 entries = 2^9  →  9 bits per level
levels       = 36 / 9 = 4

Real hardware does exactly this. 64-bit x86 processors (Intel and AMD) use 4-level paging with 48 address bits (bits 0 through 47), for 256 TiB of virtual address space. Intel's 5-level paging adds another 9-bit level, using bits 0 through 56 (57 bits), for 128 PiB; it first appeared in the Ice Lake processors, and Linux supports it since kernel 4.14 (source: Wikipedia, "Intel 5-level paging"). 1 TiB (tebibyte) = 2^40 bytes; 1 PiB (pebibyte) = 2^50 bytes.

The price: a TLB miss means walking 4 or 5 levels, so the TLB matters even more.

Fix 2: hashed page tables

The story: letters in pigeonholes

A hostel has 10,000 rooms but the mail room has only 8 pigeonholes. A letter goes into a pigeonhole chosen by a rule (say, the last digit of the room number). Rooms 4005 and 1235 land in the same pigeonhole, so you check each letter in it.

Mail room Hashed page table
The "last digit" rule Hash function: turns a big number (the page number) into a small slot number
The 8 pigeonholes The hash table; each pigeonhole is a bucket
Two rooms, same pigeonhole A collision
Checking each letter in the pigeonhole Searching the chain, a linked list of entries in the bucket

Each entry holds (page number, frame number, pointer to the next entry). Only pages that are really used have entries, which suits huge, sparse 64-bit address spaces.

#include <stdio.h>
// Hashed page table: bucket = page number % 8, a chain for collisions
struct entry { unsigned page, frame; struct entry *next; };
struct entry *bucket[8];
struct entry pool[6] = {{0x4005, 12}, {0x7F21, 40}, {0x000D, 3},
                        {0x4015, 25}, {0x1235, 9}, {0x0010, 77}};
void lookup(unsigned page) {
    int steps = 0;
    for (struct entry *e = bucket[page % 8]; e; e = e->next)
        if (++steps, e->page == page) {
            printf("page 0x%04X: bucket %u, %d step(s) -> frame %u\n",
                   page, page % 8, steps, e->frame);
            return;
        }
    printf("page 0x%04X: bucket %u, not found -> page fault\n", page, page % 8);
}
int main(void) {
    for (int i = 0; i < 6; i++) {             // insert at the chain's head
        unsigned b = pool[i].page % 8;
        pool[i].next = bucket[b]; bucket[b] = &pool[i];
    }
    lookup(0x7F21); lookup(0x4005); lookup(0x2222);
}

Output:

page 0x7F21: bucket 1, 1 step(s) -> frame 40
page 0x4005: bucket 5, 4 step(s) -> frame 12
page 0x2222: bucket 2, not found -> page fault
  • % is the remainder (modulo): 0x7F21 % 8 = 1, 0x4005 % 8 = 5.
  • Bucket 5 holds four pages (0x4005, 0x000D, 0x4015, 0x1235: all leave remainder 5), so 0x4005 (inserted first, now at the end of the chain) takes 4 steps.
  • ++steps, e->page == page uses the comma operator: count a step, then compare.
  • Lesson: a good hash function spreads pages evenly so chains stay short. A variant, the clustered page table, stores several neighbouring pages in one entry.

Fix 3: inverted page tables

The story: one register for the parking lot

Housing society parking Inverted page table
Every flat keeps its own list of parked cars (200 flats = 200 lists) Per-process page tables (100 processes = 100 tables)
One guard's register: one row per parking spot, "spot 7 → flat B2's car" One entry per physical frame: (process ID, page number)
To find B2's car, read the register line by line Finding a page means searching the table

An inverted page table (IPT) has exactly one entry per frame of physical memory. Entry i says which process (by its PID, process ID) and which page of that process is in frame i. The frame number is the entry's position. Wikipedia: "The IPT combines a page table and a frame table into one data structure", and "Inverted page tables are used for example on the PowerPC, the UltraSPARC and the IA-64 architecture."

#include <stdio.h>
// Inverted page table: ONE entry per physical FRAME, for all processes
struct { int pid; unsigned page; } ipt[8] = {
    {1, 0x10}, {2, 0x10}, {1, 0x11}, {3, 0x05},
    {2, 0x3A}, {1, 0x7F}, {3, 0x06}, {2, 0x11}};
void find(int pid, unsigned page) {
    for (int frame = 0; frame < 8; frame++)          // search every entry
        if (ipt[frame].pid == pid && ipt[frame].page == page) {
            printf("pid %d page 0x%02X -> frame %d (searched %d)\n",
                   pid, page, frame, frame + 1);
            return;
        }
    printf("pid %d page 0x%02X -> not in RAM: page fault (searched 8)\n",
           pid, page);
}
int main(void) {
    find(1, 0x10); find(2, 0x10); find(2, 0x11); find(3, 0x99);
    printf("table size = number of frames = 8, however many processes\n");
}

Output:

pid 1 page 0x10 -> frame 0 (searched 1)
pid 2 page 0x10 -> frame 1 (searched 2)
pid 2 page 0x11 -> frame 7 (searched 8)
pid 3 page 0x99 -> not in RAM: page fault (searched 8)
table size = number of frames = 8, however many processes
Per-process page table Inverted page table
Entries one per page, for each process one per frame, for the whole system
Indexed by page number frame number
Size grows with number of processes × address space physical RAM only
Lookup direct index (fast) search for (PID, page): slow, so real systems add a hash table and rely on the TLB
Shared pages easy (two PTEs point at one frame) hard: each frame records only one owner

Fix 4: huge pages (for the TLB)

The TLB holds only a limited number of translations. A program that touches 1 GB of data:

Page size Pages for 1 GB TLB entries needed
4 KB (normal) 1 GB / 4 KB = 262,144 262,144
2 MB (huge) 1 GB / 2 MB = 512 512
1 GB (huge) 1 1

A huge page is a page much larger than the normal size. One TLB entry then covers far more memory (fewer TLB misses), and the page walk is shorter. The Linux kernel documentation says "x86 CPUs normally support 4K and 2M (1G if architecturally supported) page sizes." The price is internal fragmentation: a half-used huge page wastes the rest of it (episode 30). Databases and virtual machines are typical users.

Segmentation: the programmer's view

The story: a school bag with compartments

School bag Segmentation
Slicing the bag into equal slices (a slice may hold half a lunchbox) Paging: equal 4 KB pages, blind to what's inside
Compartments: books, lunchbox, water bottle Segments: code, data, stack, heap
Each compartment has its own size Each segment has a base and a limit
"Nobody writes in the textbook" Protection per segment (code read-only, stack read-write)

Segmentation divides a program's memory into segments: variable-size logical parts that match how the programmer thinks of the program: the code (instructions), the data (global variables), the stack (function calls and local variables), the heap (memory from malloc).

The segment table

  • A logical address is a pair: (segment number, offset).
  • The segment table has one row per segment: base (where it starts in physical memory) and limit (its length).
  • Translation: if offset < limit, physical = base + offset; otherwise trap (addressing error). This is where the name segmentation fault comes from.
  • The STBR (segment-table base register) says where the segment table is in memory; the STLR (segment-table length register) says how many segments the process has (segment number must be < STLR).
(s, d) ──► segment table[s] = (base, limit)
             d < limit ? ── no ──► TRAP: addressing error
                │ yes
                ▼
           physical = base + d
#include <stdio.h>
// Segmentation: address = (segment number, offset)
const char *name[3] = {"code", "data", "stack"};
int base[3]  = {4000, 9000, 15000};   // where each segment starts
int limit[3] = {1200,  600,  2000};   // how long each segment is
void translate(int s, int offset) {
    printf("(%-5s, %4d) -> ", name[s], offset);
    if (offset >= limit[s]) {
        printf("TRAP: limit is %d, segmentation fault\n", limit[s]);
        return;
    }
    printf("physical %d\n", base[s] + offset);
}
int main(void) {
    translate(0, 100);  translate(1, 599);
    translate(2, 1500); translate(1, 750);
}

Output:

(code ,  100) -> physical 4100
(data ,  599) -> physical 9599
(stack, 1500) -> physical 16500
(data ,  750) -> TRAP: limit is 600, segmentation fault

%-5s prints a string left-aligned in 5 characters; %4d prints a number right-aligned in 4. Offset 599 is the last legal byte of the 600-byte data segment; 750 traps.

A real segmentation fault: writing to read-only memory

#include <stdio.h>
int main(void) {
    char *word = "hello";             // text stored in a READ-ONLY area
    printf("word = %s, now changing the first letter...\n", word);
    fflush(stdout);
    word[0] = 'H';                    // try to write to read-only memory
    printf("word = %s\n", word);
}

Output:

word = hello, now changing the first letter...
Segmentation fault

A string literal (text in double quotes) is stored in a read-only area next to the code. The memory exists, but its protection says read-only, so the hardware traps the write and the OS stops the program (signal SIGSEGV, exit code 139). fflush(stdout) pushes the first line out before the crash. Fix: char word[] = "hello"; makes a writable copy in an array, and then word[0] = 'H' prints word = Hello.

Segmentation vs paging

Paging Segmentation
Piece size fixed (e.g. 4 KB) varies (each segment its own length)
Visible to the programmer? no yes: matches code, data, stack
Address page number + offset (segment number, offset)
Table page table (frame per page) segment table (base + limit)
Waste internal fragmentation (last page) external fragmentation (holes between segments)
Protection and sharing per page per segment (natural: share the code segment)

Because segments have different sizes, placing them in RAM brings back variable partitions and external fragmentation (episode 30).

Segmented paging: segments made of pages

Segmented paging splits every segment into pages. The address has three parts:

| segment s | page p | offset d |
s → segment table entry: limit + address of THAT segment's page table
p → the segment's page table → frame
physical = frame + d

Numerical: offsets inside a segment are 16 bits and pages are 1 KB (1024 bytes, 10 bits). Then p = offset / 1024 (6 bits) and d = offset % 1024 (10 bits). For (segment 2, offset 5000): p = 5000 / 1024 = 4, d = 5000 − 4096 = 904. Page 4, byte 904 of segment 2.

You keep the programmer's segments with their own protection, and since every piece is a page, there is no external fragmentation (only a little internal fragmentation in each segment's last page).

Swapping and swap space

The story: a full dining hall

Dining hall OS
Every table is taken, a new family arrives RAM is full, a new process needs memory
A family waiting for dessert moves to the lobby Swap out: copy a process (or pages) from RAM to disk
The lobby Swap space (the backing store): a reserved area on disk
The family returns to any free table Swap in: copy it back, possibly to a different place

Swapping moves a process temporarily out of RAM to the backing store and later back in. Swapping in at a different address needs execution-time binding (episode 30). The medium-term scheduler (episode 17) decides which process to swap out.

Numerical: a 100 MB process, disk transfer rate 50 MB/s. Swap out = 100 / 50 = 2 s; swap in = 2 s; total 4 s of copying.

Whole-process swapping is very slow, so modern systems with paging swap individual pages that haven't been used for a while (next episode: demand paging).

The whole chain

Step Obvious attempt What broke Fix
1 One flat page table 4 MB per process (512 GB at 48 bits), 0.05% used, needs contiguous RAM Multilevel paging (12 KB instead of 4 MB)
2 More and more levels 4-5 memory accesses on a TLB miss Hashed page table (only used pages)
3 One table per process 100 processes = 100 tables Inverted page table (one entry per frame)
4 4 KB pages for 1 GB of data 262,144 TLB entries needed Huge pages (512 or 1)
5 Blind equal slices Doesn't match code/data/stack; no per-part protection Segmentation (base, limit, protection)
6 Variable-size segments External fragmentation Segmented paging
7 RAM is full No room for a new process Swapping to swap space

Common mistakes

Mistake What you see Why Fix
Writing to a string literal (char *w = "hello"; w[0] = 'H';) Segmentation fault The text is in read-only memory char w[] = "hello";
Treating offset = limit as legal Wrong numerical answer Legal offsets are 0 .. limit − 1 Legal only if offset < limit
"Two-level paging = two memory accesses" Wrong EAT The data access is extra Levels + 1 accesses on a TLB miss
Searching an inverted table by page number only Wrong frame Many processes have a page 0x10 Search for (PID, page)
Splitting with the wrong shift (e.g. va >> 20 for p1) Wrong p1/p2 p1 is the top 10 bits p1 = va >> 22, p2 = (va >> 12) & 0x3FF
Saying segmentation has internal fragmentation Wrong theory answer Segments are exactly sized Segmentation → external; paging → internal
Forgetting 1ULL in 1 << 36 Wrong or undefined result (int is 32 bits) Shifting an int by ≥ 32 Use 1ULL << 36

Mini project: a two-level page table with a TLB

Write a C program that simulates a 32-bit, 10 | 10 | 12 two-level page table. Commands from stdin: map VA FRAME (create the inner table on demand, then set the entry), read VA (translate; print "page fault" for unmapped addresses) and stats. Add a 4-entry TLB with LRU replacement in front of it, count TLB hits, misses and memory accesses, and print the EAT for TLB = 10 ns, memory = 100 ns. Finally print the memory used by your tables and compare it with a flat 4 MB table.

Practice

1. 32-bit addresses, 8 KB pages, 4-byte PTEs. How big is a flat page table?

Solution

8 KB = 2^13, so the offset is 13 bits and the page number is 32 − 13 = 19 bits. Entries = 2^19 = 524,288. Size = 524,288 × 4 B = 2 MB.

2. Segment 2 has base 3000 and limit 400. Map offsets 350 and 420.

Solution

350 < 400 → physical 3000 + 350 = 3350. 420 ≥ 400 → trap (addressing error / segmentation fault).

3. A hashed page table with 4 buckets (bucket = page % 4), inserting at the head. Insert pages 6, 10, 3, 14. Draw the chains.

Solution

6 % 4 = 2, 10 % 4 = 2, 3 % 4 = 3, 14 % 4 = 2. Bucket 2: 14 → 10 → 6. Bucket 3: 3. Buckets 0 and 1 are empty. Looking up page 6 takes 3 steps.

4. Why do inverted page tables make shared memory hard?

Solution

Each entry stores exactly one (PID, page) owner for its frame. Shared memory means two processes map the same frame, which a single entry can't record. Systems need an extra structure (or allow only one mapping at a time, causing page faults when the other process uses it).

5. Two-level paging, 32-bit, 10 | 10 | 12, 4-byte entries. A process uses the lowest 8 MB of its address space and the top 4 MB (its stack). How much memory do its page tables need?

Solution

One inner table covers 1024 pages × 4 KB = 4 MB. The lowest 8 MB needs 2 inner tables, the top 4 MB needs 1. Total = outer 4 KB + 3 × 4 KB = 16 KB (a flat table: 4 MB).

6. Three-level paging, TLB = 20 ns, memory = 100 ns, hit ratio = 80%. EAT?

Solution

Hit = 20 + 100 = 120 ns. Miss = 20 + 3 × 100 + 100 = 420 ns (three tables + data). EAT = 0.8 × 120 + 0.2 × 420 = 96 + 84 = 180 ns.

7. 39-bit virtual addresses, 4 KB pages, 8-byte entries, each table one page. How many levels?

Solution

Page number = 39 − 12 = 27 bits. Entries per table = 4096 / 8 = 512 = 9 bits. Levels = 27 / 9 = 3.

8. Segmented paging with 1 KB pages: segment 1, offset 3100. Page number and d?

Solution

p = 3100 / 1024 = 3 (3 × 1024 = 3072), d = 3100 − 3072 = 28.

Quick quiz

32-bit virtual address, 4 KB pages
split: p1 = 10 bits, p2 = 10 bits,
       offset = 12 bits
virtual address = 0x00801005
// what are p1, p2 and the offset?

A. p1 = 8, p2 = 1, offset = 0x005 B. p1 = 2, p2 = 1, offset = 0x005 C. p1 = 2, p2 = 0, offset = 0x1005 D. p1 = 0, p2 = 0x801, offset = 0x005

Answer

B. 0x00801005 >> 22 = 2. (0x00801005 >> 12) = 0x801, and 0x801 & 0x3FF = 1. 0x00801005 & 0xFFF = 0x005.

Interview questions

  1. Why is a single-level page table a problem? It needs an entry for every page of the address space: 4 MB per process for 32-bit (4 KB pages, 4 B entries), 512 GB for 48-bit; most entries are unused, and it needs contiguous memory.
  2. How does multilevel paging save memory? The outer table points to inner tables; inner tables for unused regions are never created, and each table fits in one page.
  3. What is the cost of multilevel paging? One extra memory access per level on a TLB miss (levels + 1 total); the TLB hides most of it.
  4. How many levels does x86-64 use? Four (48-bit addresses, 9 bits per level + 12-bit offset); Intel's 5-level paging extends to 57 bits.
  5. What is a hashed page table? A hash table keyed by the virtual page number, with chains of (page, frame, next) for collisions; good for sparse 64-bit address spaces.
  6. What is an inverted page table? Pros and cons? One entry per physical frame storing (PID, page). Size depends only on RAM; but lookups need a search (hash + TLB) and sharing pages is hard.
  7. What are huge pages and why use them? Pages of 2 MB or 1 GB (on x86) instead of 4 KB; one TLB entry covers more memory, so fewer TLB misses; the cost is internal fragmentation.
  8. What is segmentation? Dividing memory into variable-size logical segments (code, data, stack, heap); addresses are (segment, offset), translated with a segment table of base and limit.
  9. What causes a segmentation fault? Accessing memory outside the allowed range or with the wrong permission (e.g. writing to read-only memory); the hardware traps and the OS sends SIGSEGV.
  10. Paging vs segmentation? Fixed vs variable size; invisible vs programmer-visible; internal vs external fragmentation; page table vs segment table.
  11. What is segmented paging? Each segment is divided into pages, with a page table per segment: the programmer's view without external fragmentation.
  12. What is swapping? What is swap space? Moving a process (or pages) out of RAM to disk and back; swap space (backing store) is the disk area that holds them.

Glossary

Term Meaning in plain words Example
Page Fixed-size piece of a program's address space 4 KB
Frame Piece of RAM the same size as a page frame 0x2A5
Page table Table mapping each page to its frame, one per process page 3 → frame 0x2A5
Page table entry (PTE) One row of a page table: frame + bits frame, valid, dirty
Valid bit / dirty bit "This page is mapped" / "this page was written"
Offset Byte position inside a page or segment 0xA7C
MMU Hardware that translates virtual addresses to physical ones
TLB Small fast cache of recent translations
Flat (single-level) page table One array with an entry for every page 4 MB for 32-bit
Sparse address space Address space where only a few regions are used code at bottom, stack at top
Contiguous Side by side in memory, one unbroken block a 4 MB array
Multilevel (hierarchical) paging Page tables arranged as a table of tables two-level 10 | 10 | 12
Two-level paging Page number split into outer and inner indices p1, p2
Outer page table (page directory) First-level table; points to inner tables outer[1024]
Inner page table Second-level table; gives the frame inner1[1024]
Shift right (>>) Move bits right, dropping the low ones va >> 22
Bitwise AND with a mask (&) Keep only the bits that are 1 in the mask va & 0xFFF
Page fault Trap to the OS because a page isn't mapped or not in RAM p1 = 512, no inner table
Effective access time (EAT) Average time per memory reference 130 ns
Hit ratio Fraction of lookups found in the TLB 90%
4-level / 5-level paging x86 64-bit schemes using 48 / 57 address bits 256 TiB / 128 PiB
TiB, PiB Tebibyte = 2^40 bytes; pebibyte = 2^50 bytes
Hash function Rule turning a big key into a small slot number page % 8
Hash table Array of buckets addressed by a hash function 8 buckets
Bucket One slot of a hash table bucket 5
Collision Two keys hashing to the same bucket 0x4005 and 0x1235
Chain (chaining) Linked list of all entries in one bucket 4 entries in bucket 5
Linked list Items where each points to the next e->next
Hashed page table Page table stored as a hash table keyed by page number
Clustered page table Hashed table whose entries cover several neighbouring pages
Inverted page table (IPT) One entry per physical frame: (PID, page) ipt[8]
PID (process ID) The number that names a process pid 2
Shared page One frame mapped by several processes shared library code
Huge page A page much larger than normal 2 MB, 1 GB
Internal fragmentation Wasted space inside an allocated block half-used huge page
External fragmentation Free memory split into holes between blocks between segments
Segmentation Dividing memory into variable-size logical segments code, data, stack
Segment One logical part of a program the stack
Code / data / stack / heap Instructions / globals / function calls and locals / malloc memory
Segment table Table of (base, limit) per segment data: 9000, 600
Segment base Where a segment starts in physical memory 9000
Segment limit Length of a segment; offset must be below it 600
STBR / STLR Registers holding the segment table's address / number of segments
Trap Interrupt caused by the running program, handing control to the OS offset 750
Segmentation fault (SIGSEGV) OS stopping a program that touched memory illegally writing to "hello"
String literal Text in double quotes in C code, stored read-only "hello"
Read-only memory region Memory that may be read but not written where literals live
Protection bits Permission bits (read, write, execute) per page or segment code: read + execute
Segmented paging Segments divided into pages, a page table per segment (s, p, d)
Swapping Moving a process (or pages) between RAM and disk swap out, swap in
Swap out / swap in Copy from RAM to disk / back to RAM 2 s each
Swap space (backing store) Disk area reserved for swapped-out memory swap partition
Medium-term scheduler OS part that decides which process to swap out episode 17
Execution-time binding Addresses translated on every access, so a process can move episode 30

Summary

  • A flat page table is huge and mostly empty: 4 MB per process at 32 bits, 512 GB at 48 bits, only 0.05% used (live).
  • Multilevel paging (10 | 10 | 12) builds a table of tables; unused regions need no inner tables: 12 KB instead of 4 MB (live). Each level costs a memory access (levels + 1 on a TLB miss); the TLB hides it (EAT 130 ns). x86 64-bit: 4 levels, 48 bits; 5-level paging: 57 bits.
  • Hashed page tables store only used pages in buckets with chains (live: a 4-entry chain). Inverted page tables keep one entry per frame, (PID, page), searched (live); size depends only on RAM, but sharing is hard.
  • Huge pages (2 MB, 1 GB) let one TLB entry cover far more memory.
  • Segmentation gives memory the programmer's shape: (segment, offset), segment table with base and limit, trap if offset ≥ limit (live), per-segment protection (live: writing to a string literal → Segmentation fault). It suffers external fragmentation, fixed by segmented paging.
  • Swapping moves processes or pages to swap space on disk when RAM is full; whole-process swapping is slow (100 MB at 50 MB/s = 4 s).

Next episode: Virtual memory and demand paging: page faults, demand paging, copy-on-write, thrashing and the working set.