第3章中盤（3.3後半〜3.5）。ページテーブルの実装とTLB、ページ置き換えアルゴリズム。
3.3後半 ページテーブルの実装
多段ページテーブル
仮想アドレス空間が64bitの場合、単純なページテーブルは現実的じゃない。
理論上の最大：2^64 = 18,446,744,073,709,551,616 バイト
1ページ = 4KB = 4096バイト
ページ数 = 2^64 / 2^12 = 2^52 個
1エントリ = 8バイトとして
ページテーブルのサイズ = 2^52 × 8 = 32ペタバイト
プロセス1個のページテーブルだけで32PB。話にならない。
実際のx86_64は64bitフルを使わず48bitに妥協している（一部の最新CPUは57bit）。64bitフルを使うと6〜7段の階層が必要になりメモリアクセスのオーバーヘッドが耐えられなくなるから。「理論上の最大は64bitだけど、現実のCPUは48bitに妥協している」という設計判断。
Linuxはこれを多段ページテーブルで解決してる。x86_64では4段構成。
仮想アドレス（48bit有効）
┌──────┬──────┬──────┬──────┬────────────┐
│ PGD │ PUD │ PMD │ PTE │ offset │
│ 9bit │ 9bit │ 9bit │ 9bit │ 12bit │
└──────┴──────┴──────┴──────┴────────────┘
名前は覚えなくていい。住所の階層構造だと思えばいい。
東京都 → PGD（一番大きい区分）
渋谷区 → PUD
代々木1丁目 → PMD
1番地 → PTE
101号室 → offset（ページ内の位置）
ポイントは使っていない部分のテーブルを作らないこと。
「渋谷区に建物がない」
→ 渋谷区のPUDを作らない
→ その下のPMD/PTEも全部省略
プロセスが実際に使う仮想アドレスはスカスカなので、使っていないエントリに対応するテーブルは丸ごと省略できる。結果として数MB〜数十MBで収まる。
Dockerとの絡み
# コンテナのプロセスの仮想アドレス空間を見る
cat /proc/$(pgrep nginx)/maps
コンテナ内のnginxも普通のLinuxプロセスなので、同じ多段ページテーブルで管理されてる。
逆引きページテーブル
発想を逆にしたアプローチ。
【普通のページテーブル】
仮想ページ番号をインデックスにして物理フレームを引く
仮想[0] → 物理フレーム52
仮想[1] → 物理フレーム7
【逆引きページテーブル】
物理フレーム番号をインデックスにして「誰が使ってるか」を引く
物理フレーム[0] → (プロセスA, 仮想ページ52)
物理フレーム[1] → (プロセスB, 仮想ページ7)
「逆」ってのはインデックスが仮想→物理の逆になってるという意味。物理メモリに1対1対応で直置きしてるだけとも言える。
メリット
普通のページテーブル
→ プロセスごとに1個必要
→ プロセス100個 × 仮想空間分 = 巨大
逆引きページテーブル
→ 物理メモリ全体で1個だけ
→ 物理メモリ16GB ÷ 4KB = 約400万エントリ（固定）
プロセスが何個増えてもテーブルのサイズが変わらないのが利点。
デメリット
「この仮想アドレスはどの物理フレーム？」を調べるのに全エントリを線形探索しないといけない。実用上はハッシュテーブルと組み合わせて使う。IBMのPOWERアーキテクチャ等で採用されてたがx86では使われていない。
TLB（Translation Lookaside Buffer）
多段ページテーブルで仮想→物理変換をするたびに4回メモリアクセスが必要になる。
仮想アドレス → PGD読む（1回目）
→ PUD読む（2回目）
→ PMD読む（3回目）
→ PTE読む（4回目）
→ やっと目的のデータを読む（5回目）
これを解決するのがTLB。CPUチップの中にある「最近使ったアドレス変換」のキャッシュ。
仮想アドレス → まずTLBを見る
↓
TLBヒット（あった！）→ 物理アドレスが即わかる（1サイクル以下）
↓
TLBミス（なかった）→ ページテーブルを4段たどる → TLBに登録
なぜ多段ページテーブルとTLBが別々に存在するか
置き場所が根本的に違うから。
多段ページテーブル → メインメモリ（RAM）の上にある → 100ns〜
TLB → CPUチップの中（L1キャッシュと同レベル） → 1ns以下
コンピュータ全体が「速いけど小さい層」を「遅いけど大きい層」で仮想的に拡張する構造になっている。
レジスタ（CPU内） 1サイクル 数十バイト
L1キャッシュ（CPU内） 4サイクル 32KB
L2キャッシュ（CPU内） 12サイクル 256KB
L3キャッシュ（CPU内） 40サイクル 数十MB
RAM 200サイクル 数十GB
ディスク（SSD） 数万サイクル 数TB
TLBもページテーブルもこの妥協の塔の中でどこに置くかという話。「速くて小さい層を、遅くて大きい層があるように見せる詐欺」の繰り返しがコンピュータアーキテクチャの歴史。
TLBとコンテキストスイッチ
プロセスAからプロセスBに切り替わる時、TLBの中身はプロセスAのもの。対処法は2つ。
| 方式 | 方法 | 特徴 |
|---|---|---|
| TLBフラッシュ | 切り替え時にTLBを全部消す | シンプル。切り替えのたびにTLBが冷える |
| ASID（Address Space ID） | TLBエントリにプロセスIDを付ける | フラッシュ不要。複数プロセスのエントリが共存 |
LinuxはASIDを使ってる（x86_64ではPCID: Process Context Identifier）。
k3sで大量のPodが動いている時、コンテキストスイッチが多発する。TLBフラッシュが多いと全体的なスループットが落ちる。
# コンテキストスイッチの回数を見る
vmstat 1
# cs列がコンテキストスイッチ数/秒
3.4 ページ置き換えアルゴリズム
問題設定
物理メモリが全部埋まった時に新しいページが必要になったら、誰かを追い出す必要がある。この「誰を追い出すか」がページ置き換えアルゴリズム。
追い出し方を間違えるとすぐまた必要になって読み戻す羽目になる。これが頻発する状態をスラッシングと呼ぶ。Proxmoxでメモリ割り当てが少ないVMがディスクアクセスしまくって重くなるあの状態。
OPT（最適アルゴリズム）
「将来一番長く使われないページを追い出す」
理論上の最適解。未来は見えないので実装不可能。ベンチマークの基準として使う。
FIFO（First In First Out）
一番古く入ったページを追い出す
シンプルだが問題がある。
古いページ ≠ 使われていないページ
ずっと使い続けている古いページを追い出して、すぐ読み戻す羽目になる。
NRU（Not Recently Used）
各ページに2つのビットを持つ。
参照ビット（R）: アクセスがあったら1
更新ビット（M）: 書き込みがあったら1
これで4クラスに分類する。
クラス0: R=0, M=0 → 最近アクセスも書き込みもない ← 最優先で追い出す
クラス1: R=0, M=1 → 最近アクセスはないが書き込みあり
クラス2: R=1, M=0 → 最近アクセスあり、書き込みなし
クラス3: R=1, M=1 → 最近アクセスも書き込みもあり ← 最後まで残す
更新ビット（M）がなぜ重要か
Mが1のページを追い出す → ディスクに書き戻す必要がある（ダーティページ）→ 遅い
Mが0のページを追い出す → ディスクに書き戻し不要（元のデータそのまま）→ 速い
R同じならMが0のクラスを優先して追い出す。
問題はスケール
ページが大量にある場合、全ページをスキャンして4クラスに分類する処理と定期的なRビットリセットが重くなる。
LRU（Least Recently Used）
一番最近使われていないページを追い出す
「最近使っていないなら、しばらく使わないだろう」という局所性の原理に基づく。精度は高いがメモリアクセスのたびに「最後にアクセスした時刻」を更新する必要があり、ハードウェアコストが重い。
Clock（時計）アルゴリズム
LRUの近似。全ページを時計の文字盤のように円形に並べ、各ページに参照ビット（0か1）を持つ。
ページにアクセスがあった → 参照ビットを1にする
置き換えが必要になったら時計の針を進める
├── 参照ビットが1 → 0にして次へ（チャンスを1回あげる）
└── 参照ビットが0 → こいつを追い出す
NRUより精度は落ちるが、スケールする。針を進めながら探すので参照ビット0を見つけた時点で終わり。
ワーキングセット
プロセスはある時間帯に「よく使うページの集合」が決まってくる。この集合をワーキングセットと呼ぶ。
W(k) = 直近k回のメモリアクセスで使われたページの集合
スラッシングとの関係
ワーキングセットが物理メモリに収まってる → ページフォルトがほぼ発生しない → 快適
ワーキングセットが物理メモリより大きい → 常にページフォルトが発生 → スラッシング
k3sでのmemoryRequestはワーキングセットの見積もり。kubectl top podで見えるメモリ使用量は実質的にワーキングセットのサイズ。
WSClock
ワーキングセットとClockを組み合わせた実用最強版。各ページに参照ビット（R）、更新ビット（M）、最後にアクセスした時刻（τ）を持つ。
針が進んだ時の判断
Rが1
→ ワーキングセット内 → Rを0にして時刻を更新、次へ
Rが0、かつ (現在時刻 - τ) < しきい値
→ ワーキングセット内 → 次へ
Rが0、かつ (現在時刻 - τ) >= しきい値
→ ワーキングセット外
→ Mが0 → 即追い出す
→ Mが1 → ディスクに書き戻し予約して次へ
Clockの軽さを保ちながらワーキングセットの概念を取り込んでいる。
Linuxの実際の実装
Linuxはアクティブリストと非アクティブリストを使ったLRU/Clock混合のマルチリストシステムを採用している。
アクティブリスト → 最近使ったページ
非アクティブリスト → しばらく使っていないページ
ページへのアクセスがあればアクティブリストへ昇格、しばらく使われなければ非アクティブリストへ降格、置き換えが必要なら非アクティブリストの末尾から追い出す。WSClockのワーキングセット概念をリストの昇格/降格で近似している。
アルゴリズムまとめ
OPT → 最適だが未来が見えないので実装不可、ベンチマーク用
FIFO → シンプル、古い≠使っていないので性能悪い
NRU → R/Mビットで4クラス分類、シンプルで実用的、スケールしない
LRU → 精度高い、ハードウェアコストが重い
Clock → LRUの近似、軽い
WSClock → Clockにワーキングセット概念を追加、実用最強
理論と実装の間のギャップを埋めるのが近似アルゴリズムで、OSもDBもそこだらけ。Proxmoxのスケジューラもk3sのリソース管理も「完璧じゃないけど十分に良い」を積み重ねてシステムが動いている。
ローカル vs グローバル置き換え
複数プロセスが動いている時、誰かのページを追い出す必要が出た場合の方針。
ローカル置き換え
→ 追い出すのは自分のページだけ
→ 他のプロセスに影響しない
→ でも自分のワーキングセットが増えた時に対応できない
グローバル置き換え
→ 誰のページでも追い出せる
→ ワーキングセットの変化に追従できる
→ でも暴走プロセスが他を圧迫できる
k3sとの絡み：
ローカル ≈ PodのmemoryLimit（そのPodの中だけで完結、超えたらOOMKiller）
グローバル ≈ Nodeのメモリ管理（全Pod込みでLinuxカーネルが全体を見て判断）
Linuxはcgroupでプロセスグループごとに上限を設けることでローカルっぽい制御もできる。それがDockerの--memoryフラグの正体。
マイナーフォルトとメジャーフォルト
ページフォルトには2種類ある。
マイナーフォルト（Minor Page Fault）
→ 物理メモリにはある
→ ページテーブルに登録されていないだけ
→ ディスクアクセスなし・速い
→ CoWの発動時もこれ
メジャーフォルト（Major Page Fault）
→ 物理メモリにない
→ ディスクから読み込む必要がある
→ 遅い・I/O発生
# プロセスのフォルト数を見る
/usr/bin/time -v ./your_program
# Podのフォルト数を見る
cat /proc/$(pgrep nginx)/stat | awk '{print "minor:", $10, "major:", $12}'
メジャーフォルトが多いPodはスラッシング候補。kubectl top podでメモリ使用量がrequestを常に超えているPodは要注意。
3.5 ページングシステムの設計問題
ページフォルトの正確なフロー
プロセスが仮想アドレスにアクセス
↓
TLBミス → ページテーブルを見る
↓
「メモリにない」フラグ → ページフォルト割り込み発生
↓
OSのページフォルトハンドラが起動
↓
1. アドレスが有効か確認（無効 → セグフォ SIGSEGV）
2. 物理フレームを確保（空きなし → 置き換えアルゴリズム発動）
3. ディスクからページを読み込む
4. ページテーブルを更新
5. TLBに登録
↓
フォルトした命令を再実行 → 成功
Dockerコンテナ内でセグフォが起きるとコンテナが落ちる。kubectl logsで「Segmentation fault」が見える。
ページサイズの設計問題
小さいページサイズ（4KB）
メリット: 内部断片化が小さい、ワーキングセットを細かく管理できる
デメリット: ページテーブルのエントリ数が増える、TLBミスが増える
大きいページサイズ（HugePage: 2MB or 1GB）
メリット: TLBエントリ1個で広い範囲をカバー、TLBミスが減る
デメリット: 内部断片化が増える
# HugePage確認
cat /proc/meminfo | grep Huge
# Proxmoxで設定
echo 512 > /proc/sys/vm/nr_hugepages
# 512 × 2MB = 1GB分のHugePage確保
KVMのVMに大量メモリを割り当てる時はHugePageを使うと速い。
I空間とD空間（NX bit）
I空間（Instruction Space）：コード（実行命令）を置く空間 D空間（Data Space）：データを置く空間
分離することでセキュリティが向上する。
I空間を書き込み禁止にする → コードを改ざんできない
D空間を実行禁止にする（NX bit）→ データ領域に埋め込んだコードを実行できない
→ シェルコード攻撃を防ぐ
Dockerコンテナでも有効で、カーネルレベルで保護されている。
共有ページとCopy-on-Write（CoW）
複数プロセスが同じライブラリ（例：libc）を使う時、メモリを共有する仕組み。
共有しない場合
プロセスA: libc 2MB + プロセスB: libc 2MB + プロセスC: libc 2MB = 6MB
共有する場合
物理メモリ: libc 2MB（1個だけ）
プロセスA/B/C: 全員同じ物理フレームを参照 = 2MB
各プロセスの仮想アドレスは別々でも、物理アドレスは同じ場所を指す。
CoWの仕組み
共有ページには書き込み禁止フラグを意図的に設定しておく。
プロセスAが共有ページに書き込もうとする
↓
ページフォルト発生（「書き込み禁止です」）
↓
OSが「CoWのページか」と判断
↓
そのページをコピーして別の物理フレームに置く
↓
プロセスAだけ新しいフレームを指すように更新
↓
BとCは元のフレームのまま
「書けないから別の場所に」じゃなくて「書かせないようにしておいて、書こうとした瞬間にコピーを作る」が正確。
fork()との絡み
fork()でプロセスをコピーする時
→ 親プロセスのメモリを全部コピーしたら重い
→ CoWなら「書き込みが発生するまでコピーしない」
→ 実際に書き込んだページだけコピーが発生
DockerのCoWはレイヤーが違う
Dockerでよく「CoWのおかげでイメージが軽い」と言われるが、あれはファイルシステム（OverlayFS）レベルのCoWであり、ここで説明したメモリ（RAM）上のCoWとは動いているレイヤーが違う。
メモリのCoW（本章の話）
→ RAM上の物理ページを共有
→ fork()時のプロセス間でのメモリ節約
ストレージのCoW（OverlayFS）
→ ディスク上のファイルレイヤーを共有
→ Dockerイメージレイヤーの差分管理
思想は同じ「書き込みが発生するまでコピーしない」だが、動いている場所が違う。
docker images のサイズが小さく見える → OverlayFSのCoW（ストレージ層）
実際の物理使用量を見るには → docker system df
共有メモリのコスト
プロセス間で意図的にメモリを共有する場合（multiprocessing.Value等）は複数のコストが発生する。
① CoWでページのコピーが走る
② 複数プロセスが同じメモリを触るのでロック（排他制御）が必要
③ キャッシュコヒーレンシ（別CPUコアのキャッシュを無効化する必要がある）
これが「書き込みを減らせ」「イミュータブルにしろ」の物理的な根拠。Goのchannel、RustのMPSC、KafkaのMessage Queue、k8sのPod間通信、全部「データを共有するな、コピーを渡せ」という同じ思想。
マップトファイル（Memory-mapped file）
ファイルを仮想アドレス空間に直接マッピングする仕組み。
通常のread()
ディスク → カーネルバッファ（コピー1回）→ ユーザーバッファ（コピー1回）
mmap()
ディスク → 仮想アドレス空間に直接見える（コピーなし）
アクセスした瞬間にページフォルトが発生して、その部分だけディスクから読む。デマンドページングと同じ仕組み。
tmpfsとの違い
mmap() → ディスクのファイルをメモリに見せる（ディスクが実体）
tmpfs → メモリをディスクに見せる（メモリが実体）
方向が逆。docker run --tmpfs /tmpや、k3sのemptyDir: medium: Memoryがtmpfs。Node再起動で消える。
DBのバッファプールとの違い
mmap()
→ OSがページ単位で管理
→ どのページをメモリに乗せるかOSが決める
→ DBの文脈（このテーブルはフルスキャンだからキャッシュ不要等）を知らない
バッファプール（MySQLのinnodb_buffer_pool等）
→ DBが自前でLRU管理
→ トランザクションの文脈を知っている
→ パフォーマンスが予測可能
MySQLもPostgreSQLも自前バッファプール派。SQLiteはmmap()派。
クリーニングポリシー
ダーティページ（書き込みが発生してディスクと内容が違うページ）をいつディスクに書き戻すか。
オンデマンド（置き換え時）
→ 追い出す時に初めて書き戻す
→ 普段は速い、置き換え時に遅延が発生
先読み書き戻し（ページデーモン）
→ 定期的にダーティページをバックグラウンドで書き戻す
→ 現代のLinuxではカーネルスレッド（bdi-writeback）がバックグラウンドで処理
→ 古いカーネルではpdflushと呼ばれていた
ライトバック競合
書き戻し中に同じページへ追加書き込みが来た場合、Linuxは書き戻しを止めない。
書き戻し中のページに追加書き込み
→ 書き戻しはそのまま完走させる
→ 追加書き込みは新しいダーティとして記録
→ 次のpdflushサイクルで再度書き戻す
途中で止めると中途半端な状態がディスクに残り、最悪ファイルシステム破損につながる。
これがジャーナリング（ext4、XFS）の存在理由。書き込み前に「これから何を書くか」をジャーナルに記録しておき、クラッシュしても再起動時にやり直せる。
# ダーティページの状況確認
cat /proc/meminfo | grep Dirty
# Dirty: まだ書き戻していないページ
# Writeback: 今書き戻し中のページ
# 強制的に書き戻す
sync
Proxmoxのストレージグラフで定期的にI/Oスパイクが見える場合、bdi-writebackカーネルスレッドが原因のことが多い。
まとめ
第3章中盤
├── 多段ページテーブル（住所の階層構造、使っている部分だけ作る）
├── 逆引きページテーブル（物理メモリに直置き、プロセス数に依存しない）
├── TLB（妥協の塔におけるCPU内アドレス変換キャッシュ）
│ └── コンテキストスイッチ時はフラッシュ or ASID
├── ページ置き換えアルゴリズム
│ ├── OPT（最適、実装不可）
│ ├── FIFO（シンプル、性能悪い）
│ ├── NRU（4クラス分類、スケールしない）
│ ├── LRU（精度高い、コスト重い）
│ ├── Clock（軽い近似）
│ └── WSClock（Clock + ワーキングセット、実用最強）
├── ローカル vs グローバル置き換え（k8sはmemoryLimitとcgroupで両方使う）
├── マイナーフォルト vs メジャーフォルト
├── ページサイズのトレードオフ（4KB vs HugePage）
├── NX bit（D空間を実行禁止にしてシェルコード攻撃を防ぐ）
├── 共有ページ + CoW（書こうとした瞬間だけコピー）
│ └── メモリのCoW（RAM上）とストレージのCoW（OverlayFS）は別レイヤー
├── マップトファイル（コピーなしでファイルを仮想空間に直接マッピング）
└── クリーニングポリシー（ダーティページをいつ書き戻すか）
次回は3.6〜3.8（実装上の課題、セグメンテーション、メルトダウン・スペクター）。