paging、TLB、page fault はどのように機能しますか?

Question

IT Interview Practice · Accepted Answer

**Paging** と **segmentation** は仮想アドレス空間を構成する 2 つの方法です。現代のシステムは圧倒的に paging ベースです (時にその上に薄い segmentation の層があります)。

## Paging

仮想メモリと物理メモリは固定サイズの **page** と **frame** (通常 4 KB) に切り分けられます。**page table** が仮想ページ → 物理フレームをマッピングします。アドレスは **ページ番号 (page number)** (テーブルへのインデックス) と **オフセット (offset)** に分かれます:

```text
 virtual address  =  [ page number | offset ]
                          │            │
              page table[page] = frame │
                          ▼            ▼
 physical address =  [   frame    | offset ]
```

page table は大きいため、**多段 (multi-level)** (木構造) またはハッシュ化され、ハードウェアの **MMU** によって辿られます (walk)。

## TLB: 高速化する

メモリアクセスごとに多段 page table を辿るのは致命的です。**TLB (Translation Lookaside Buffer)** は、CPU 内にある最近の仮想→物理変換の小さく高速なキャッシュです:

```text
CPU needs addr → TLB hit?  ── yes ──▶ get frame immediately (~1 cycle)
                    │
                    └── no (TLB miss) → walk the page table, fill the TLB (slower)
```

TLB のヒット率は通常 99% 超です。ミスは高コストで、だからこそ **spatial locality (空間的局所性)** や **huge page** (2 MB — 同じ RAM を覆うのにエントリが少なくて済む) といった機能がパフォーマンスに重要になります。

## Page fault

page table エントリがそのページが **RAM にない** (または保護ビットが侵害された) と示す場合、MMU は **page fault** trap を発生させます。OS がそれを処理します: ディスクからページをロードする (*major* fault)、新しいページをゼロ埋めする、または copy-on-write。ディスクに当たる page fault は数百万サイクルかかります — だから working set を RAM に保つことが重要です。

## Segmentation

**Segmentation** はメモリを **論理単位** — code、data、stack — ごとに **可変サイズ** のセグメントに分け、`[segment selector | offset]` としてアドレス指定します。プログラム構造に自然にマップしますが、**外部断片化 (external fragmentation)** (可変サイズの穴) に悩まされます。純粋な segmentation はほぼ歴史的なもので、x86 は痕跡的な形を残していますが、Linux はそれをフラット化し paging に依存します。

## なぜ重要なのか

paging、TLB、page fault は「仮想メモリ」が実パフォーマンスと出会う場所です。面接官はこれで、抽象をハードウェアコストと結びつけられるかを確認します: なぜ huge page が TLB ミスを減らすか、なぜ page fault の嵐がレイテンシを沈めるか、なぜ cache/TLB に優しいアクセスパターンが速く走るか。memory-mapped file、copy-on-write、スラッシングの必須の背景知識でもあります。

Paging

TLB: 高速化する

Page fault

Segmentation

なぜ重要なのか

関連する質問