仮想メモリ

プログラムは仮想アドレスを使い、ハードウェアと OS が物理位置へ変換する。ページングはアドレスを仮想ページ番号と内部オフセットに分け、番号をフレーム番号へ置き換え、オフセットを保つ。0x7ffd4a2c はプログラムのビュー上の位置であり、同番号の物理位置にデータがある必要はない。

コストには段階がある。TLB に変換があればフレームを得られ、なければページテーブルを読む。許可されたマッピングでもデータが非常駐ならカーネルのフォールト処理が必要になる。本課は TLB 1、メモリ読み取り 100、ストレージサービス 1,000,000 サイクルで、変換とページ搬入の桁の差を示す。

マイナーフォールトはストレージ読み込みが不要な処理で、ゼロ初期化、コピーオンライト、ページキャッシュの再利用などがある。メジャーフォールトはストレージサービスを要する。両方ともカーネルに入るが費用は違い、本課は後者だけをモデル化する。実時間はキャッシュ、装置、システム状態による。

仕組み

6 ビットの仮想空間は 64 語で、8 語ずつ 8 ページに分かれる。物理側は 4 フレーム、計 32 語だ。P0 はコード、P1 はデータ、P2 はヒープ、P7 はスタック、P3–P6 は未マップの穴とする。合法な四ページは四フレームに入るが、仮想的に指定できる範囲は物理容量より大きい。

a[9] の 001001 は上位三ビット 001 の P1 と、下位三ビット 001 の語 1 に分かれる。va//PAGE と va%PAGE はフィールドの説明で、この固定の 2 のべきの配置に汎用除算は不要だ。

検索順は次のとおり。

1. TLB：ここは二つのフルアソシアティブ項目。ページ番号が一致すればフレームを得て、オフセットを保ってデータを読む。実 TLB は複数階層、容量、連想度などが異なる。
2. ページテーブル：TLB ミス後にメモリの項目を読む。モデルは valid とフレームを記録し、valid はここでは常駐を意味する。
3. ストレージ：マッピングあり、valid=0 なら本課のメジャーフォールト。空きフレームを取り、全ページを読み込み、有効化してアクセスを再開する。選択は空きリストにより、仮想番号とは無関係。
4. マッピングなし：穴のページは満たせず、モデルはプロセスを終了してセグメンテーションフォールトを示す。存在しないページをディスクへ探しに行かない。

式は pa = frame * PAGE + offset。同じ変換に使うページとフレームのサイズは等しく、内部位置は変わらない。実ハードウェアは huge page など複数サイズを支援でき、8 語は普遍定数ではない。

料金は TLB ヒットが 1+100=101、常駐ページのウォークが 1+100+100=201、メジャーフォールトが 1+100+1,000,000+100=1,000,201。変換後のデータ読み取りも必要だ。

ステップ実行

既定の 12 load は 0 1 2 · 8 9 10 · 16 17 18 · 3 4 5。コード、データ、ヒープ、再びコードを読む。

1. a[0]：P0、offset=0。TLB は空、マッピングはあるが valid=0 でフォールト。空きリストは F0 ではなく F2 を渡す。P0 の 8 語を F2 へ搬入し valid=1、TLB に P0→F2。1,000,201 サイクル。
2. a[1]：変換がヒットし、pa=2×8+1=17。101 サイクル。
3. a[2]：同ページのヒット、101。
4. a[8]：P1 は非常駐でウォーク後フォールト。次の空きは F0 で、隣接仮想ページが物理では逆順になる。1,000,201。TLB は P0→F2 と P1→F0 で満杯。
5. a[9]、a[10]：各 101 のヒット。
6. a[16]：P2 がフォールトして F3 へ入る。TLB は LRU で第 3 load が最後だった P0→F2 を除去する。P0 自体は F2 に残り、失うのはキャッシュした変換だけだ。
7. a[17]、a[18]：P2→F3 がヒット。
8. 第 10 load a[3]：P0 は TLB にないが、表は valid=1、F2 を示す。ページフォールトはない。201 サイクルで変換を再キャッシュする。
9. 第 11、12 load a[4]、a[5]：各 101。

合計はメジャーフォールト 3、TLB ヒット 8、フォールトなしのウォーク 1、メモリ読み取り 16、3,001,612 サイクル。300 万がストレージで、残る 1612 は TLB 12 回、表 4 回、データ 12 回の費用だ。アドレス分割に追加算術料金はない。線形バーの小さい部分は最小ピクセルの制約で見せており、両コストが近いという意味ではない。

TLB が節約するもの

No TLB も同じ 12 アドレスで、三フォールトの位置は変わらず、ストレージが全時間を支配する。メモリ読み取りは 16 から 24 へ増え、毎 load が表とデータを読む。

一変換アクセスに表読み取りが追加されても、実行全体が倍とは限らない。TLB ありでも四回はウォークしていたので、16→24 は 50% 増だ。TLB はキャッシュした変換の表読み取りを除き、ページデータの不足は消さない。

TLB thrash は四ページを三周し、二項目の容量を二ページ超える。各再訪前に変換を追い出し、ヒット率 0、全 load がウォークし、読み取りは 24 回で TLB なしと同じ。物理ページは残れるため、繰り返す TLB ミスは繰り返すメジャーフォールトではない。

tight loop は 12 load が一ページに収まり、フォールト 1、TLB ヒット 11、メモリ読み取り 13。ページ内局所性の効果を示す。

dTLB ミスが多くフォールトが少ないなら、変換の作業集合、配置、局所性、適する場合の大ページを調べる。メジャーフォールトが多ければ常駐量、初回接触、ファイル I/O を調べる。TLB 増量も容量ミスを直す場合があるが、通常プログラムが直接変えられるパラメーターではない。大ページは一項目の範囲を広げる一方、割当やメモリ使用の代価もある。

境界ケース

• 初回接触はフォールトし得るが必須ではない。本モデルは全合法ページが非常駐で始まる。実際は継承や事前読込、既存ページキャッシュもあり、ゼロ初期化やコピーオンライトはしばしばマイナーだ。ウォームアップ前後を分ける。
• TLB ミスはページフォールトではない。第 10 load の P0 は F2 にあり、201 サイクルの表とデータ読み取りで済む。
• segfault の第 4 load a[40] は未マップ P5。TLB と表を調べた後に終了し、ストレージやフレーム割当は行わない。後続二 load は灰色で課金しない。実システムでは権限違反も同様の信号になり、処理は OS とプログラムによる。
• ページ変換は使用サイズ内のオフセットを保つ。一語ごとを任意に並べ替える仕組みではない。
• 合法四ページに四フレームがあり、容量による物理追い出しは起きない。犠牲ページや dirty 書き戻しはページ置換のレッスンで扱う。

よくある間違い

• メジャーフォールトを普通の遅いメモリ読み取りと見る。本課はストレージが一読み取りの一万倍で、待機中にカーネルは他の仕事を実行できる。ストレージなしのマイナーとは別に数える。
• 表だから高速だと思う。ページテーブル自体がメモリ階層にあり、依存読み取りが複数必要になり得る。一般的な x86-64 は 4 段または 5 段で、キャッシュや大ページも費用を変える。
• 隣接仮想ページが隣接物理フレームだと思う。P0→F2、P1→F0 が反例。DMA は装置と OS のマッピング・固定要件に従う。連続物理が必要な装置も、scatter-gather や IOMMU で非連続フレームを扱うものもあり、malloc だけでは DMA を保証しない。
• 割当済みと常駐を混同する。合法なマッピングでも valid=0 があり、仮想サイズと常駐集合は違う。
• 総時間だけで TLB を診断する。本例はストレージが差を隠すので、TLB、minor、major を読む。
• segfault を必ずメモリ破壊の証拠とする。まずアクセスが許可されなかったという結果で、未マップ、読み取り専用への書き込み、実行不可ページなどの原因を調べる。

モデルの範囲

実システムは 4 KB 基本ページが多いが、他の基本サイズや大ページもある。x86-64 は 4 または 5 段で、ハードウェアウォーカーが表を読む。TLB は命令・データ別や複数階層を持ち、容量はコアによる。実項目には権限、dirty、accessed、実行不可などがあり、本課は権限とコピーオンライトを省く。

RAM が満杯の際の犠牲選択、dirty 書き戻し、常駐スラッシングもない。周期数は桁の説明用だ。DRAM は数十から百 ns 程度、ストレージフォールトは SSD、回転媒体、待ち行列、CPU 周波数、カーネル作業で変わり、100 万を実測定数とはしない。

対応イベントのある環境で測定する例：

perf stat -e page-faults,minor-faults,major-faults,dTLB-load-misses ./your-program

minor と major を分け、dTLB と併せて読む。macOS の vmmap と footprint は仮想・常駐量を示し、sudo fs_usage -f pathname は関連ファイル読み取りの確認を助ける。ただし全ファイル読み取りを一メジャーフォールトと同一視しない。道具とイベントの対応は環境による。