仮想記憶とページング｜コンピュータ基礎

🎓 レベル：標準　|　重要度：A（必須）

📎 前提：物理メモリと論理アドレス　|　関連：ページ置換アルゴリズム・メモリ階層とキャッシュ

要点（BLUF）

論理アドレス空間を固定サイズ（典型4KB）のページに、物理メモリを同サイズのフレームに分け、ページテーブルで「どのページがどのフレームか」を対応づける。
仮想アドレスは上位＝ページ番号、下位＝オフセット。変換するのはページ番号だけで、オフセットはそのまま使う。
ページテーブル参照はメモリアクセスを増やすので、TLB（変換結果のキャッシュ）で高速化する。物理にないページはディスクから持ってくる（ページフォルト）。

概念 ── 連続でなくてよくする

物理メモリと論理アドレスのベース＋リミットは「1プロセス＝物理上の連続1ブロック」を要求し、断片化に弱い欠点がありました。ページングはこれを解きます。

論理空間も物理メモリも、固定サイズの小片に切ります。論理側の小片がページ、物理側がフレーム（どちらも例えば4KB）。あるプロセスのページ群は、物理メモリ上のバラバラのフレームに散らばってよい。対応関係をページテーブルが覚えます。

flowchart LR
    subgraph V["仮想空間（プロセスから見た連続）"]
      p0["ページ0"]; p1["ページ1"]; p2["ページ2"]
    end
    subgraph PT["ページテーブル"]
      e0["0 -> フレーム5"]; e1["1 -> フレーム2"]; e2["2 -> フレーム9"]
    end
    subgraph P["物理メモリ（実際はバラバラ）"]
      f2["フレーム2"]; f5["フレーム5"]; f9["フレーム9"]
    end
    p0-->e0-->f5
    p1-->e1-->f2
    p2-->e2-->f9

仕組み① ── アドレス変換の中身

仮想アドレスを2つに割ります。上位ビット＝ページ番号、下位ビット＝ページ内オフセット。ページサイズが4KB（=2^12）ならオフセットは下位12ビット。

手順：(1) ページ番号でページテーブルを引きフレーム番号を得る → (2) 物理アドレス = フレーム番号 × ページサイズ + オフセット。オフセットは変換しない（ページ内の位置は物理でも同じ）。

検証します（[[#対応ラボ]] の 03-02_address_translation.py）。

PAGE_SIZE = 4096
page_table = {0: 5, 1: 2, 2: 9}     # ページ番号 -> フレーム番号
def translate(vaddr):
    page, offset = vaddr // PAGE_SIZE, vaddr % PAGE_SIZE
    return page_table[page]*PAGE_SIZE + offset

実行結果（実機）:

仮想 0x00AB7: ページ0 オフセット0xAB7 -> フレーム5 -> 物理 0x05AB7
仮想 0x01003: ページ1 オフセット0x003 -> フレーム2 -> 物理 0x02003
仮想 0x02FFF: ページ2 オフセット0xFFF -> フレーム9 -> 物理 0x09FFF

オフセット部（下3桁の16進）が変換前後でそのまま保たれているのがポイントです。

仕組み② ── ページテーブルが巨大になる問題とTLB

単層ページテーブルは巨大化します。32ビット空間・4KBページなら、

仮想ページ数 = 2^(32-12) = 1,048,576 エントリ
1プロセスあたり単層ページテーブル = 4 MB（だから多段化する）

プロセスごとに4MBの表は非現実的。そこで多段ページテーブル（必要な部分だけ作る）や逆ページテーブルを使います。64ビットでは4段・5段が普通。

さらに問題は速度。素朴には1回のメモリアクセスに、ページテーブル参照のための余分なメモリアクセスが加わる（多段なら段数ぶん）。これでは遅い。

そこで TLB（Translation Lookaside Buffer）：最近の「ページ番号→フレーム番号」変換結果を保持する小さな高速キャッシュ（メモリ階層とキャッシュの発想そのもの）。

flowchart TB
    va["仮想アドレス"] --> tlb{"TLBに変換あり?"}
    tlb -->|"ヒット（高速）"| pa["物理アドレス"]
    tlb -->|"ミス"| walk["ページテーブルを辿る（遅い）"]
    walk --> fill["TLBに結果を登録"] --> pa

局所性（同じページを連続して触る）が高いのでTLBヒット率は高く、ほとんどの変換は高速に済みます。プロセス切り替えでTLBの中身が無効化されるのが、文脈切り替え（プロセスとスレッド）が見た目以上に高コストな一因です。

仕組み③ ── ページフォルトと「物理より大きく見せる」

ページテーブルの各エントリには「有効ビット（このページは今物理メモリにあるか）」があります。アクセスしたページが物理にない（ディスクに退避中／未割り当て）と、MMUがページフォルト例外を上げ、OSが介入します。

OSはディスクから該当ページを空きフレームへ読み込み（空きがなければ追い出すページを選ぶ＝ページ置換アルゴリズム）、表を更新して、中断した命令を再実行させます。これにより、物理メモリより大きな論理空間を、ディスクを裏地に使って見せられます（デマンドページング）。これはメモリ階層とキャッシュの「遅い層（ディスク）を速い層（DRAM）で隠す」をOSがやっている版です。

仕組みの直観 ── なぜこの設計か

固定サイズのページにする理由：可変サイズだと外部断片化（隙間だらけ）が起きる。固定サイズなら空きフレームはどれも等価で管理が簡単。代償は内部断片化（ページ末尾の余り）。
オフセットを変換しない理由：ページ内の相対位置は物理でも同じ。変換が必要なのは「どのフレームか」だけ。だからページ境界をビット境界に取り、割り算でなくビット切り出しで済む。
TLBを置く理由：変換のための追加メモリアクセスが性能を殺す。局所性を見越して直近の変換をキャッシュすれば、平均コストはほぼゼロに近づく。

⚠️ よくある誤解・落とし穴

「ページフォルト＝エラー／クラッシュ」→ 多くは正常動作（必要なページを今から読む合図）。異常なのは不正アドレスへのフォルト。
「ページテーブルはCPUが自動で作る」→ 表を作るのはOS。辿る（walk）のがハード（または一部ソフト）。役割分担を混同しない。
「TLBはデータをキャッシュする」→ TLBがキャッシュするのはアドレス変換。データのキャッシュ（L1等）は別物。
「ページサイズは大きいほど良い」→ 大きいとページテーブルは小さくなるが内部断片化とI/O単位が増える。トレードオフ。

対応ラボ

cs-foundations-study/labs/03-02_address_translation.py（実行して上記の変換とページテーブル規模を確認済み）。

確認できること：ページ番号/オフセット分割、変換、未マップ時のフォルト、表の肥大