仮想メモリとページングの仕組み - アドレス変換・ページテーブル・TLB・ページフォルトを図解で理解する
仮想メモリを実験で体感できる名著。
OS理論の世界的定番教科書。
ページング実装を深く追う一冊。
当サイトは Amazon.co.jp を宣伝しリンクすることで紹介料を得る手段を提供する、Amazonアソシエイト・プログラムの参加者です。価格・在庫はリンク先の最新情報をご確認ください。
Cで書いたプログラムがポインタの値を表示すると、複数のプロセスがまったく同じアドレスを指しているのに互いに干渉しない、という不思議な光景に出会います。これを可能にしているのが仮想メモリ(virtual memory)です。プログラムが見ているアドレスは、実際のメモリチップ上の位置とは別物で、その間をページング(paging)という仕組みが取り持っています。この記事では、仮想アドレスから物理アドレスへの変換、ページテーブル、TLB、ページフォルトといった要素を、図解を交えて土台から順に整理します。
なぜ仮想メモリが必要か
現代のOSでは、プログラムが使うアドレスは仮想アドレス(virtual address)です。一方、実際にメモリチップにアクセスするための本当のアドレスを物理アドレス(physical address)と呼びます。この二つの対応関係を保持しているのが後述するページテーブルで、CPUのメモリ管理ユニット(MMU)がハードウェアで変換を行います。
なぜこんな回りくどい仕組みが必要なのでしょうか。仮想メモリが提供する価値は大きく四つあります。
- プロセス分離: 各プロセスは自分専用のアドレス空間を持ち、他プロセスのメモリを直接触れません
- 物理容量の抽象化: プログラムは物理RAMの実サイズやレイアウトを気にせず、連続した広大な空間があるかのように書けます
- メモリ保護: ユーザーモードのコードからカーネルのメモリへはアクセスできず、権限違反はハードウェアが弾きます
- 効率的なプロセス間共有: 同じ物理ページを複数プロセスの仮想空間へ写像することで、コピーせずに共有できます
物理アドレスを直接指定する世界の問題点
もし仮想メモリがなく、すべてのプログラムが物理アドレスを直に指定していたらどうなるでしょうか。プログラムAが物理アドレスの0x1000を使い、プログラムBも同じ0x1000を使ったら、両者は同じメモリを踏み合ってしまいます。これを避けるには、リンク時や実行時にプログラムごとの配置をずらす調整が必要になり、しかもあるプログラムのバグが平気で他プログラムやOSのメモリを破壊できてしまいます。仮想メモリは「各プロセスに、自分だけの広大なアドレス空間があるように見せる」ことで、この衝突と保護の問題を一挙に解決します。プロセスとアドレス空間の関係は並行と並列・プロセスとスレッドもあわせて読むと整理しやすいでしょう。
ページとページフレーム
仮想メモリを実現する基本単位がページ(page)です。仮想アドレス空間は固定サイズのページに区切られ、物理RAMも同じサイズの区画に分割されます。物理側の区画をページフレーム(page frame、物理ページ)と呼びます。ページとページフレームは同じ大きさなので、任意の仮想ページを任意の物理ページフレームへ、パズルのピースのように割り当てられます。
仮想アドレス空間 物理メモリ(RAM)
+------------------+ +------------------+
| 仮想ページ 0 | ---------+ | フレーム 0 |
+------------------+ | +------------------+
| 仮想ページ 1 | ----+ +----> | フレーム 1 |
+------------------+ | +------------------+
| 仮想ページ 2 | -+ +---------> | フレーム 2 |
+------------------+ | +------------------+
| 仮想ページ 3 | -+---------+ | フレーム 3 |
+------------------+ (未割り当て) +------------------+
... | +--> | フレーム 4 |
+-------------> +------------------+
ページ単位で管理することで、連続した仮想アドレスをバラバラの物理フレームに散らして置けます。物理メモリに虫食いの空きしかなくても、ページ単位なら無駄なく詰められるわけです。
なぜ4KB＝オフセット12ビットなのか
多くのアーキテクチャで標準のページサイズは4KB(4096バイト)です。4096は2の12乗なので、ページ内のどこを指すかを表すページオフセットは12ビットで足ります。この12という数字が、後で出てくるアドレス分割の要になります。ページを大きくすればページテーブルのエントリ数は減りますが、少ししか使わないデータのために大きなページを丸ごと確保すると無駄(内部断片化)が増えます。4KBは、この管理コストと無駄のバランスとして長く使われてきた値です。
アドレス変換の仕組み
アドレス変換の核心はシンプルです。仮想アドレスを上位と下位の二つに割ります。
- 上位ビット: 仮想ページ番号(VPN、Virtual Page Number) — どのページか
- 下位ビット: ページオフセット — そのページ内の何バイト目か
変換で書き換わるのはVPNの部分だけで、オフセットは変換の前後で不変です。VPNをページテーブルで引いて対応する物理ページ番号(PPN)を得たら、物理アドレスはその物理ページ番号にもとのオフセットを連結したものになります。
仮想アドレス (例: 4KBページ)
+---------------------------+------------------+
| 仮想ページ番号 (VPN) | オフセット(12b) |
+---------------------------+------------------+
| |
| ページテーブルで変換 | そのまま
v v
+---------------------------+------------------+
| 物理ページ番号 (PPN) | オフセット(12b) |
+---------------------------+------------------+
物理アドレス
素朴に考えると、VPNからPPNへの対応表(ページテーブル)を一枚の大きな配列で持てばよさそうです。しかし64ビットの広大なアドレス空間で全VPN分のエントリを平坦に並べると、表そのものが巨大になりすぎます。そこで実際には、表を階層化して必要な部分だけを持つ多段ページテーブルが使われます。
x86-64の4段ページテーブル(PML4 → PDPT → PD → PT)
x86-64の標準は、48ビットの仮想アドレスを使う4段ページテーブルです。48ビットを次のように分割します。
48ビット仮想アドレス = 9 + 9 + 9 + 9 + 12
+-----+-----+-----+-----+--------------+
|PML4 |PDPT | PD | PT | オフセット |
| 9b | 9b | 9b | 9b | 12b |
+-----+-----+-----+-----+--------------+
上位から順に、PML4(Page Map Level 4)、PDPT(Page Directory Pointer Table)、PD(Page Directory)、PT(Page Table)の各段のインデックスとして9ビットずつを使い、末尾12ビットが4KBページ内オフセットになります。各段のテーブルを順にたどっていくのがページテーブルウォーク(page walk)です。
CR3レジスタ
|
v
[PML4] --(9bで選ぶ)--> [PDPT] --(9b)--> [PD] --(9b)--> [PT] --(9b)--> 物理ページ
+ オフセット(12b)
= 物理アドレス
各段のインデックスが9ビットなのには理由があります。9ビットは512通り、つまり1テーブルあたり512エントリです。各エントリ(PTE、Page Table Entry)は8バイトなので、8バイト × 512 = 4096バイトとなり、テーブル一枚がちょうど1ページ(4KB)に収まります。9ビットという分割は、テーブル自体をページに気持ちよく載せるための必然だったわけです。
このウォークは1回のアドレス変換につき、最大で4回のメモリ参照を要します。つまり本来のデータアクセス1回のために、変換で余分に何度もメモリを読むことになります。この重さをどう隠すかが次のTLBの話につながります。
5段ページ(LA57)と48ビットから57ビットへの拡張
扱えるメモリが増えるにつれ、48ビットでは足りない場面が出てきました。そこでIntelは段を一つ増やした5段ページング(Intel 5-level paging、LA57)を導入しました。仮想アドレスを48ビットから57ビットへ拡張し、仮想アドレス空間を256TiBから128PiBへと広げます。最上位に新しい段(PML5)を追加した形で、CR4レジスタのbit12(LA57)で有効化します。最初にこれを実装したのはIce Lake世代です。
段が増えれば当然ウォークも長くなります。5段ページ時は、1回の仮想メモリアクセスのために最悪6回の物理メモリアクセスが発生します(4段では最悪5回。ウォークの4回または5回に、目的データの読み取り1回が加わる勘定です)。段を深くして広大な空間を扱えるようにする代償として、変換コストは増えるというトレードオフになっています。
NOTE
ページテーブルウォークの回数を減らす工夫がヒュージページ(huge page)です。x86-64ではPDレベルで2MiB、PDPTレベルで1GiBの大きなマッピングを直接張れます。途中の段で「ここから先はまとめて1枚の大ページ」と示すことで、ウォークの段数とTLBミスを減らせます。大量の連続メモリを扱うDBやVMで効果を発揮します。
なお、x86-64で扱える物理アドレスは最大52ビット(実装依存)です。仮想アドレスのビット幅と物理アドレスのビット幅は別物である点に注意してください。
TLB - 変換を速くするキャッシュ
毎回のアクセスで4段も5段もページテーブルをたどっていては、いくらハードウェアが速くても割に合いません。そこで登場するのがTLB(Translation Lookaside Buffer)です。TLBは、最近使われたVPNからPPNへの変換結果(PTE)をキャッシュしておく専用のハードウェアです。
仮想アドレス
|
v
[TLBを引く] --- ヒット --> すぐに物理ページ番号が分かる(高速)
|
ミス
|
v
[ページテーブルをウォーク] --> 得た変換をTLBへ挿入 --> 物理ページ番号
x86では、TLBミスが起きるとハードウェアのステートマシンが自動でページテーブルをウォークし、得られた変換をTLBへ挿入します(ハードウェア管理TLB)。OSのソフトウェアが介在しないので、ミス時のペナルティは比較的小さく抑えられます。
同じページ内のデータには連続してアクセスすることが多く(局所性)、いったんTLBに載れば以降の同一ページへのアクセスはウォークなしで済みます。TLBのヒット率はワークロード依存なので具体的な数値は一概に言えませんが、多くの場合きわめて高くなり、これが仮想メモリのオーバーヘッドを実用上小さく保っています。キャッシュで遅い層を隠すという発想はCDNとCache-Controlのキャッシュ戦略とも通じるものがあります。
デマンドページングとページフォルト
プログラムがメモリを要求したとき、OSはその場で物理ページを割り当てるとは限りません。多くの場合、デマンドページング(demand paging)という遅延割り当てを行います。確保の時点では仮想的な予約だけを行い、実際に最初のアクセスがあった瞬間に本当の物理ページを用意します。使われないまま終わるメモリに物理RAMを割かずに済むので、メモリを効率よく使えます。
このとき鍵になるのがページフォルト(page fault)です。CPUがアクセスしようとした仮想ページに有効な物理ページの割り当てがない(あるいは権限が合わない)と、ハードウェアが例外を上げてOSのページフォルトハンドラへ制御を移します。ハンドラの処理はおおむね次の流れです。
- アクセスの権限を確認する(不正な書き込みなどはここで弾き、必要ならプロセスを止める)
- 物理ページを割り当てる(空きが足りなければ、後述のスワップでディスクからページを読み込む)
- 正しい権限を設定してPTEを作成または更新する
- フォルトを起こした命令を最初からやり直す(再実行)
命令を再実行すると、今度は正しいマッピングが存在するので、アクセスは何事もなかったように成功します。プログラムから見ればフォルトは透過的で、少し待たされただけに見えます。
minor faultとmajor fault
ページフォルトは、その処理にディスクI/Oを伴うかどうかで二種類に分けられます。
- major fault(メジャーフォルト): 目的のページの内容をディスクから読み込む必要があるフォルト。スワップやファイルからの読み出しを伴い、I/O待ちが発生するので相対的に重い
- minor fault(マイナーフォルト): 内容はすでにメモリ上にあり、ページテーブルの対応づけを作るだけで済むフォルト。たとえば別プロセスが読み込み済みのライブラリを共有する場合などで、ディスクI/Oは不要
同じ「フォルト」でも体感コストはまるで違います。性能を追うときは、フォルトの総数だけでなくmajor faultの数に注目すると、ディスクを叩いて遅くなっている箇所が見えてきます。
# プロセスのmajor/minorフォルト数を見る(Linux)
ps -o min_flt,maj_flt,rss,vsz,comm -p <PID>
# あるいは /proc から
cat /proc/<PID>/stat # 10列目=minflt, 12列目=majfltスワップとスラッシング
物理メモリが足りなくなると、OSはしばらく使われていない物理ページの内容をディスク(スワップ領域)へ退避し、空いたフレームを別の用途に回します。これがスワップ(swap)です。退避したページに再びアクセスがあれば、major faultとしてディスクから読み戻します(スワップイン)。ディスクはRAMよりはるかに遅いので、スワップが増えると体感速度は目に見えて落ちます。
ここで重要な概念がワーキングセット(working set)です。ワーキングセットとは、ある時点でプロセスが実際に頻繁に触っているページの集合を指します。全アクティブプロセスのワーキングセットの合計が物理メモリに収まっているうちは快適ですが、これを超えると悲劇が起きます。
ワーキングセット合計 <= 物理メモリ → 快適
ワーキングセット合計 > 物理メモリ → スラッシング
スラッシング(thrashing)は、必要なページ集合が物理メモリに収まらず、あるページを読み込むために別のページを追い出す、を延々と繰り返す状態です。CPUは本来の計算ではなくページの出し入れに時間を費やし、システム全体のスループットが崩壊します。スワップの発生はvmstatで観察できます。
# 1秒ごとに表示。si=スワップイン, so=スワップアウト(単位KB/s)
vmstat 1
# si/so が継続的に大きい値ならスラッシングを疑うページ置換アルゴリズム
物理メモリが満杯のときに新しいページを載せるには、どれかを追い出す必要があります。「どのページを追い出すか」を決めるのがページ置換アルゴリズムです。代表的な三つを比べます。
| アルゴリズム | 追い出す対象 | コスト | 特徴 |
|---|---|---|---|
| FIFO | 最も長く滞在しているページ | 低い | 単純だが、よく使うページも順番で追い出しうる |
| LRU | 最も長く使われていないページ | 高い | 局所性に沿い性能が良いが、完全な実装は高コスト |
| Clock | 参照ビットで近似的に選ぶ | 低い | LRUを安価に近似。実システムで広く使われる |
理想は「これから最も長く使われないページ」を追い出すこと(最適置換)ですが、未来は分からないので近似します。LRU(Least Recently Used)は「最近使われていない=これからも使われにくい」という局所性の仮定に立ちます。ただし厳密なLRUはアクセスのたびに順序を更新せねばならず高コストなので、実際には参照ビットを使うClockアルゴリズムで安価に近似するのが定番です。
FIFOとLRUの違いは、短い参照列を手でトレースすると分かります。ページフレームが3枚のとき、参照列A B C A B D A B C を追ってみます。
- FIFO: 到着順で追い出す。Dを入れるとき最古のAを追い出すが、その直後にAが再び来てフォルトする、という取りこぼしが起きやすい
- LRU: 最後に使った時刻で追い出す。よく使うAやBを保持しやすく、同じ参照列でフォルトが少なくなる傾向
Beladyのアノマリー
直感的には、ページフレーム(物理ページの枚数)を増やせばフォルトは減りそうです。ところがFIFOでは、特定のアクセスパターンにおいてフレームを増やしたのにフォルトが増えるという逆転現象が起こり得ます。これをBeladyのアノマリー(Belady's anomaly)と呼びます。
一方、LRUのようなスタックアルゴリズムはこの現象を起こしません。スタックアルゴリズムには、フレーム数が多い側の保持集合が少ない側の保持集合を必ず包含するという性質(包含性)があり、この包含性のおかげでフレームを増やしてフォルトが増えることが原理的にないのです。FIFOはこの性質を満たさないため、アノマリーの余地が残ります。
mmapとコピーオンライト
仮想メモリの応用として、ファイルをアドレス空間へ直接写像するmmapがあります。mmapでファイルをマップすると、その領域へのアクセスがそのままファイルの読み書きになります。この領域はファイルにバックされるため、内容の退避先はスワップではなく元のファイルです。対して、mallocで得るような裏にファイルを持たない匿名メモリ(anonymous memory)のページは、退避先がスワップになります。
もう一つの重要な応用がコピーオンライト(COW、Copy-on-Write)です。forkで子プロセスを作るとき、素直に親の全メモリを複製するとコストが膨大です。そこで実装では、fork直後は親子が同じ物理ページを共有し、両者のPTEを読み取り専用に設定します。どちらかがそのページに書き込もうとした瞬間にページフォルトを起こし、ハンドラがそのページだけを私的にコピーして、書き込んだ側にコピーを割り当てます。
fork直後(共有・読み取り専用)
親のページX ---+
+---> [物理ページ P] (read-only)
子のページX ---+
子が書き込んだ瞬間(COW発動)
親のページX -------> [物理ページ P]
子のページX -------> [物理ページ P'] (Pの私的コピー)
読むだけなら共有のままコピーは発生しないので、forkが速く、メモリも節約できます。実際に書き換えられたページだけが遅延コピーされる、という無駄のない設計です。メモリを自動管理するという点ではガベージコレクション(GC)の仕組みとも問題意識が重なります。
まとめ: 日々の挙動を原理で説明する
仮想メモリとページングを押さえると、日常で出会う挙動が原理から説明できるようになります。
- RSSとVSZの違い:
psで見えるVSZは仮想アドレス空間の予約サイズ(デマンドページングで未割り当ての領域も含む)、RSSは実際に物理メモリに載っている量です。VSZが巨大でもRSSが小さいのは、確保だけして触っていないページが多いからです - スワップで遅くなる: ワーキングセットが物理メモリを超えると、major faultとスワップが多発してスラッシングに陥ります。
vmstatのsi/soで観察できます - OOM Killer: スワップも尽きて物理メモリを工面できなくなると、Linuxのカーネルはプロセスを強制終了して空きを作ります。これは物理ページの割り当てが最終的に破綻した結果です
自分のプログラムのメモリ挙動を確かめるには、次のコマンドが入口になります。
# ページサイズを確認(多くの環境で4096バイト)
getconf PAGE_SIZE
# プロセスの物理常駐量(RSS)と仮想サイズ(VSZ)
ps -o rss,vsz,comm -p <PID>
# ページごとの内訳(RSS, 共有/私的, スワップ量など)を細かく見る
cat /proc/self/smaps | less
# smaps の Rss/Pss/Private_Dirty/Swap 各行が、その領域の実態を表す「アドレスは仮想、対応はページテーブル、速度はTLB、割り当ては遅延、不足はスワップ」——この五点を軸に据えると、メモリまわりの現象をばらばらの謎ではなく一つの仕組みの現れとして読み解けるようになります。
コラム: Atlas(1962)のone-level store
仮想メモリの発想は最新技術ではなく、半世紀以上前に生まれました。仮想メモリ(当時はone-level storeと呼ばれました)を世界で初めて実装したのは、1962年に稼働したマンチェスター大学のAtlasです。当時のプログラマは、小さな高速メモリと大きな低速メモリ(ドラム)の間で、どのデータをいつ移すかを手作業で管理していました。Atlasはこの出し入れを機械が肩代わりし、プログラマには一段の大きなメモリがあるかのように見せました。今日のページングとページフォルトによる自動的なデータ移動は、このAtlasのアイデアの延長線上にあります。基本のアイデアが数十年にわたり生き続けているのは、コンピュータサイエンスの面白いところです。低レベルのビット表現に興味が湧いたら浮動小数点数とIEEE 754もおすすめです。
参考リンク
- Intel 5-level paging(Wikipedia): https://en.wikipedia.org/wiki/Intel_5-level_paging
- mmap(2) - Linux manual page: https://man7.org/linux/man-pages/man2/mmap.2.html
- Atlas (computer)(Wikipedia): https://en.wikipedia.org/wiki/Atlas_(computer)
- Belady's anomaly(Wikipedia): https://en.wikipedia.org/wiki/B%C3%A9l%C3%A1dy%27s_anomaly
