← 一覧へ
コンピューティング・組込み
#가상메모리#요구페이징#페이지교체#LRU#워킹셋
最終更新 · 2026-10-29

仮想メモリ(Virtual Memory)とページ置換アルゴリズム

1. 概要

A. 定義

仮想メモリとは、各プロセスに対して物理メモリの大きさとは無関係な連続的で独立したアドレス空間(仮想アドレス空間)を提供し、実行に実際に必要な部分だけを物理メモリに置いておくオペレーティングシステムのメモリ管理技法である。その中核的な実現手段が要求ページング(demand paging)であり、物理メモリが満杯のときどのページを追い出すかを決める規則がページ置換アルゴリズムである。

仮想メモリの根本的な発想は、「プログラム全体が同時にメモリに存在する必要はない」という観察から出発する。ほとんどのプログラムは特定の時点でコード・データの一部領域だけを集中的に参照するため(局所性)、実行中の部分だけを物理メモリに置き、残りをディスク(スワップ領域)に残しても正常に動作する。OSは仮想アドレスを物理アドレスへ変換するMMU(Memory Management Unit)とページテーブルを通じてこの幻想を作り出し、プログラマは物理メモリ容量をほとんど意識せずに大きなアドレス空間を扱うことができる。

B. 登場背景と必要性

初期のシステムではプログラム全体が物理メモリに載らなければ実行できなかった。この制約は二つの深刻な問題を生んだ。第一に、物理メモリより大きなプログラムは実行そのものが不可能であり、開発者はオーバーレイ(overlay)を手ずから設計してコード片を交互に載せた。第二に、多重プログラミングの度合いが物理メモリ容量に縛られ、同時に走らせられるプロセス数が制限された。仮想メモリは「実際に必要な部分だけを載せる」ことでこの二つの制約を同時に解き、物理メモリを超えるプログラムの実行と高い多重プログラミングの度合いの双方を可能にした。

何より仮想メモリはプログラミングモデルそのものを単純化した。開発者は自分のプログラムが物理メモリのどこに載るのか、他のプログラムとどう空間を分けるのかをまったく気にせず、0番地から始まる清浄で連続したアドレス空間を仮定してコーディングできる。再配置(relocation)と保護をハードウェアとOSが透過的に処理してくれるからであり、この抽象化がなければコンパイラ・リンカ・ローダの複雑さは今とは比較にならないほど大きくなっていたであろう。

必要性は今日いっそう大きくなった。一台のサーバで数百個のコンテナ・プロセスが同時に走り、各プロセスは数GBの仮想アドレス空間を使うが、実際の常駐集合(RSS)はその一部にすぎない。仮想メモリがなければ、このような過剰割当(overcommit)に基づく密度の高い資源共有は不可能である。また仮想アドレス空間の隔離はプロセス間保護(あるプロセスが他のプロセスのメモリを侵せないこと)の土台となり、共有ライブラリのメモリ共有、mmapに基づくファイルマッピング、書込み時コピー(Copy-on-Write)といった現代OSの中核機能はすべて仮想メモリの上に立つ。

C. 特徴

仮想メモリはいくつかの本質的な特徴をもつ。第一に透過性であり、アプリケーションは自らが要求ページングされているという事実を知らなくてよい。第二に局所性への依存である。仮想メモリの性能は参照の時間的・空間的局所性が良いほど急激に向上し、局所性が崩れれば性能も崩れる。第三にディスクI/Oとの強い結合であり、ページフォルトが発生すると数十マイクロ秒〜数ミリ秒のディスクアクセスが割り込み、CPU数千〜数万サイクルに相当する遅延が生じる。まさにこの巨大なコスト差のために、ページフォルト率を下げる置換アルゴリズムの品質がシステム性能を左右する。

これらの特徴は、仮想メモリがメモリ階層(memory hierarchy)の一層であるという事実に由来する。レジスタ-キャッシュ-主記憶-補助記憶へと連なる階層において、仮想メモリは「主記憶を補助記憶のキャッシュのように使う」メカニズムに当たる。CPUキャッシュが主記憶のブロックを自動的に昇降させるように、仮想メモリはディスクのページをメモリへ昇格させ、キャッシュの局所性・置換・一貫性の概念がそのままページ水準で再現される。ただしミス(フォルト)コストがキャッシュミスより数千倍大きいため、ハードウェアが専任するキャッシュとは異なりソフトウェア(OS)が精緻な方針で介入する点が決定的な違いである。

2. 仮想メモリの動作構造

仮想メモリは、仮想アドレスを物理アドレスへ変換する過程と、参照しようとするページが物理メモリにないときディスクから引いてくる過程に分かれる。以下はアドレス変換と要求ページングの全体構造図である。

flowchart TD
    CPU["CPU: 仮想アドレス生成"] --> TLB{"TLB 照会"}
    TLB -->|"ヒット(hit)"| PA["物理アドレス計算"]
    TLB -->|"失敗(miss)"| PT["ページテーブル照会"]
    PT --> V{"有効ビット(valid)?"}
    V -->|"1 (メモリ常駐)"| PA
    V -->|"0 (ディスク)"| PF["ページフォルト発生"]
    PF --> OS["OS フォルトハンドラ"]
    OS --> FREE{"空きフレーム存在?"}
    FREE -->|"あり"| LOAD["ディスクからページ読込"]
    FREE -->|"なし"| REPL["ページ置換アルゴリズム<br/>犠牲ページ選定"]
    REPL --> DIRTY{"修正ビット(dirty)?"}
    DIRTY -->|"1"| WB["変更分をディスクへ書戻し(write-back)"]
    DIRTY -->|"0"| LOAD
    WB --> LOAD
    LOAD --> UPD["ページテーブル・TLB 更新"]
    UPD --> PA
    PA --> MEM["メモリアクセス完了"]

アドレス変換の第一の関門がTLB(Translation Lookaside Buffer)である。最近使った仮想→物理変換をキャッシュして大半のアクセスを数サイクルで終え、TLBが失敗して初めて遅いページテーブルウォーク(階層型テーブルでは複数回のメモリアクセス)が起こる。ページテーブルの各項目にはフレーム番号とともに有効ビット(メモリ常駐の有無)・修正ビット(dirty)・参照ビット(reference)・保護ビットなどが収められ、置換アルゴリズムと保護メカニズムの判断根拠となる。

アドレス変換にはページサイズという重要な設計変数が隠れている。ページが小さいと内部断片化は減るがページテーブル項目数とTLBへの圧迫が大きくなり、ページが大きいとテーブル・TLBの効率は良くなるが「不要な領域まで一緒に読み込む」損失と内部断片化が増える。汎用OSが4KBを既定値として長く保ってきたのはこのトレードオフの歴史的均衡点であり、第5節で扱う巨大ページはこの既定値を特定のワークロードで意図的に破ってTLB効率を極大化する選択である。

A. 要求ページングとページフォルト処理

要求ページングはページを参照される瞬間にのみ読み込む。有効ビットが0のページを参照するとハードウェアがトラップをかけてページフォルトを起こし、OSハンドラが①アドレス妥当性検証 → ②空きフレーム確保(なければ置換) → ③ディスクからページ読込 → ④ページテーブル・TLB更新 → ⑤失敗した命令の再実行の順で処理する。このとき犠牲ページの修正ビットが1なら先にディスクへ書き戻す(write-back)必要があるため二回のディスクI/Oを要し、0なら書込みを省略できる——置換対象の選定時に「清浄なページ」を好む理由である。

B. 仮想メモリが支える中核機能 — CoWとメモリマッピング

仮想メモリは単に「メモリを増やす」装置ではなく、現代OSの数々の中核機能が立つ土台である。代表が書込み時コピー(Copy-on-Write)である。fork()で子プロセスを作るとき親の全メモリを即座に複製するとコストが莫大なため、OSは二つのプロセスが同じ物理フレームを読取り専用で共有させ、どちらか一方が書込みを試みた瞬間にのみそのページを複製する。この遅延複製は変換層(ページテーブルの保護ビット)とページフォルトメカニズムがなければ実装できず、fork直後にexecする一般的なパターンで不要な複製をほぼすべて除去する。

いま一つがメモリマッピング(mmap)である。ファイルを仮想アドレス空間へマッピングするとread/writeシステムコールなしにポインタアクセスだけでファイルを扱い、カーネルが要求ページングで必要なブロックだけを読み込み、変更分を遅延書込みする。共有ライブラリを複数プロセスが一揃いの物理コードで共有すること、demand zeroingで新しいヒープページを0で埋めた共用フレームへマッピングし書込み時点でのみ実フレームを割り当てることも、すべて同じ原理である。このように仮想メモリは保護・共有・遅延割当という三つの軸でシステム効率を引き上げる。

C. 実効アクセス時間と性能感度

要求ページングの性能は実効アクセス時間(EAT)で定量化される。ページフォルト率をp、メモリアクセス時間をma、フォルト処理時間をpftとするとEAT = (1-p)×ma + p×pftである。たとえばma=100ns、pft=8ms(8,000,000ns)のとき、フォルト率がわずか0.1%(p=0.001)でもEAT ≈ 100×0.999 + 8,000,000×0.001 ≈ 8,100nsとなり、フォルトがないときの約80倍に跳ね上がる。性能低下を10%以内に抑えるにはフォルト率を約1/800,000以下に保つ必要があるという計算になる。この極端な感度が、「フォルトを最大限減らす」置換アルゴリズムと局所性確保がなぜ死活的かを数値で示している。

3. ページ置換アルゴリズム

物理メモリが満杯の状態で新しいページを載せるには既存のページを一つ追い出さねばならない。目標はまもなく再び使われるページは残し、当面使われないページを追い出してフォルト率を最小化することである。以下は代表的アルゴリズムの意思決定の流れである。

flowchart LR
    REQ["ページ置換が必要"] --> OPT["OPT: 未来最長期間<br/>未使用のページを置換"]
    REQ --> FIFO["FIFO: 最も先に<br/>入ったページを置換"]
    REQ --> LRU["LRU: 最も長く<br/>参照されないページを置換"]
    REQ --> CLOCK["Clock(二次チャンス):<br/>参照ビット0を置換"]
    OPT -.->|"実装不可、理論的下限"| BENCH["性能比較基準"]
    FIFO -.->|"Belady逆説あり得る"| SIMPLE["単純だが非効率"]
    LRU -.->|"局所性反映、実装コスト"| GOOD["準最適近似"]
    CLOCK -.->|"LRU近似、低コスト"| REAL["実務採用"]

A. OPT(最適置換)と理論的下限

OPT(Optimal、Beladyアルゴリズム)は「今後最も長く参照されないページ」を置換する。未来の参照列を知る必要があるため実際の実装は不可能だが、達成可能な最小フォルト数の理論的下限を提供し、他のアルゴリズムの性能を評価する物差しとして使われる。たとえば参照列7 0 1 2 0 3 0 4 2 3 0 3 2をフレーム3個で回すとOPTはFIFO・LRUより少ないフォルトで処理され、実務アルゴリズムがOPTにどれほど近づくかが設計品質の尺度となる。

B. FIFOとBeladyの逆説

FIFOは最も先に読み込まれたページを置換する。実装は単純だが、「ずっと前に載ったが使われ続けているページ」まで追い出す盲点がある。さらに致命的なのがBeladyの逆説(Belady's Anomaly)で、フレーム数を増やしたのにかえってフォルトが増える非直観的現象がFIFOに現れる。参照列1 2 3 4 1 2 5 1 2 3 4 5はフレーム3個のときより4個のときフォルトが多くなる古典的反例である。これはFIFOが局所性をまったく反映しないことを示し、スタックアルゴリズムの性質をもつLRU・OPTではこの逆説は発生しない。

C. LRUとその近似

LRU(Least Recently Used)は「最も長く参照されなかったページ」を置換する。過去の参照パターンが近い未来にも続くという局所性仮定に基づきOPTに近い性能を出すが、正確なLRUは参照のたびにタイムスタンプを更新するか参照順リストを維持せねばならずハードウェアコストが大きい。そこで現実には近似技法を使う。代表がClock(二次チャンス)アルゴリズムで、フレームを円環に並べて参照ビットを検査し、1なら0に消して進み(もう一度チャンス)、0に出会えば置換する。修正ビットも合わせて見る改良Clockは「参照なし+清浄」ページを優先的に置換し、write-backまで節約する。Linux・Windowsなど実際のOSはこのClock系に多段LRUリスト(active/inactive)と老化(aging)を組み合わせた変種を使う。

以下の表は代表的アルゴリズムを性能・コスト・特性で比較する。表だけでは「なぜ」が見えないので、差の原因を併せて読むべきである。

アルゴリズム 置換基準 フォルト性能 実装コスト Belady逆説 実務採用
OPT 未来最長未使用 最適(下限) 実装不可 なし 評価基準用
FIFO 読込順序 悪い 非常に低い 発生 ほぼ不使用
LRU 最近未使用 優秀 高い(HW) なし 近似形のみ
Clock 参照ビット巡回 良好(LRU近似) 低い なし(近似) 広く使用
LFU 参照頻度最小 状況依存 中 あり得る 限定的(キャッシュ等)

性能差の根は「どれだけ未来をよく予測するか」にある。FIFOは読込時点しか見ず使用パターンを無視するので予測力がなく、LRUは「最近使ったならまたすぐ使う」という局所性で未来を近似するので強い。ClockはLRUの予測力を参照ビット一つで安価に真似て性能とコストの均衡点をとったため実務を支配する。LFUは長期の人気ページに強いが、初期に一瞬多く使われ捨てられたページが高い頻度数のために居座るキャッシュ汚染の問題があり、老化技法と併せて使わねばならない。

D. 数値比較の例 — 同じ参照列、異なる結果

アルゴリズムの差を実感するには、同一条件でフォルト数を直に数えてみるのが効果的である。フレーム3個、参照列2 3 2 1 5 2 4 5 3 2 5 2を仮定しよう。FIFOは読込順序しか見ないので後で再び使われるページ(2)を無頓着に追い出してフォルトが多くなり、LRUは最近参照された2・5を保存してフォルトを減らし、OPTは未来を知って最も遅く使われるページを追い出して最小フォルトを出す。一般にこの参照列でフォルト数はOPT < LRU ≤ FIFOの順に現れ、OPTが示した下限にLRUが近くFIFOが最も劣るという教科書的な序列が再現される。肝心なのは同じメモリ容量(フレーム数)でも置換方針だけでフォルト率が大きく変わるという点であり、第2節のEAT感度と結びつけるとこのフォルト数の差はやがて体感性能の数十倍の差へ増幅されうる。

この序列が常に固定なわけではない。参照列に明確な局所性がなく無作為に近ければどのアルゴリズムもOPTに大きく及ばず、FIFOが運よくLRUに似たりBelady逆説で逆転したりする場合も生じる。すなわち置換アルゴリズムの優劣は参照パターンに依存するので、設計者は対象ワークロードの実トレースでフォルト率を測って方針を選ぶのが原則である。

実務の置換方針はここから一歩進んでスキャン(scan)耐性まで考慮する。大容量ファイルを一度だけ順次読む作業は膨大なページをLRUの最上段へ押し込み、肝心の頻用ページを追い出すが、これを防ぐためLinuxは新しく入ったページをすぐactiveへ昇格させず、inactiveリストで再参照を確認してから昇格させる二段階昇格構造をもつ。データベースバッファプールのLRU-K・2Q・ARCといった方針も「一度使ったもの」と「何度も使ったもの」を分離し順次スキャンがキャッシュを汚染できないようにする、同じ問題意識の産物である。

4. フレーム割当とスラッシング — 置換だけでは足りない理由

A. フレーム割当方針

置換アルゴリズムがいかに優れていても、プロセスに与えられたフレーム数そのものがワーキングセットより小さければフォルトが激増する。フレーム割当は固定割当(均等・比例)と可変割当に分かれ、置換範囲を自分のフレームに限る局所置換と全体から奪う大域置換にも区別される。大域置換は活発なプロセスにフレームを集中できるが、あるプロセスのフォルトが他のフレームを奪って連鎖的な性能低下を招きうる。

割当方式の選択は公平性と効率の緊張をそのまま露わにする。均等割当はすべてのプロセスに同数のフレームを与えて単純だが、小さなプロセスはフレームが余り大きなプロセスは不足する。比例割当は仮想アドレス空間の大きさに比例して分けこれを緩和するが、「大きいからといって活発に使うわけではない」という落とし穴がある。そこで現代OSはフォルト挙動を見て実時間で調整する可変割当+大域置換を基本としつつ、あるプロセスの暴走が全体を引き下げないようcgroupメモリ制限のような上限を併せて置く。

B. スラッシングとワーキングセットモデル

この問題の極端がスラッシング(thrashing)である。多重プログラミングの度合いを過度に高めると各プロセスのフレームがワーキングセット以下に縮み、CPUが仕事をせずページ置換(ディスクI/O)にばかりかかりきりになる状態になる。このときCPU利用率を上げようとプロセスをさらに載せるとスラッシングが加速する悪循環に陥る。解法がワーキングセットモデル(Working Set Model)で、直近Δ時間の窓で参照されたページ集合(WS)をプロセスが必要とするフレームとみなし、全プロセスのWS合計が物理フレームを超えないよう多重プログラミングの度合いを調整する。もう一つの手法であるPFF(Page Fault Frequency)はフォルト率が上限を超えればフレームを増やし、下限を下回れば回収してフォルト率を目標帯域に制御する。(※ スラッシングの詳細は[[thrashing]]、メモリ分割技法は[[paging-vs-segmentation]]参照。)

具体的な事例として、メモリの逼迫したLinuxサーバでメモリ圧迫が大きくなるとkswapdが絶えずページを回収しディスクスワップI/Oが急騰し、vmstatのsi/so列が跳ね上がって応答が事実上止まるが、これは教科書のスラッシングが運用現場でそのまま再現される場面である。多くの組織がこうしたサービスでスワップを制限したりcgroupメモリ制限・OOM方針を併せて設計したりする理由がここにある。

5. 深化 — 現代OS・ハードウェアにおける仮想メモリ

A. ページテーブル・TLBの拡張

古典理論は依然として有効だが、現代システムは規模とハードウェアの発展に合わせて仮想メモリを大きく拡張した。第一に多段・逆ページテーブルである。64ビットアドレス空間を線形ページテーブルで扱うとテーブル自体が非現実的に大きくなるため、x86-64は4〜5段の階層ページテーブルを使い、テーブルウォークのコストを減らすため多段TLBとテーブルキャッシュを置く。第二に巨大ページ(Huge Page、2MB・1GB)で、ページサイズを大きくしてTLB項目一つが広い領域を覆うようにしTLBヒット率を高めテーブルウォーク回数を減らす——データベース・JVM大容量ヒープ・仮想化で性能が数%〜数十%改善された事例が報告されている。第三に仮想化のネストページング(EPT/NPT)で、ゲスト仮想→ゲスト物理→ホスト物理の二段変換をハードウェアが処理しソフトウェアのシャドーページテーブルのオーバーヘッドを除去した。

この拡張の隠れたコストがアドレス変換そのものの遅延である。5段ページテーブルでTLBが失敗すると最大5回のメモリアクセスが必要で、ネストページングでは各段ごとにホスト変換がまた割り込んで最悪の場合24回に達するメモリアクセスが発生しうる。そこでハードウェアはページテーブル上位段をキャッシュする専用キャッシュ(page-walk cache)を置き、ソフトウェアは巨大ページとメモリアクセス局所性でTLBヒット率を高めてこのコストを相殺する——すなわち「ページテーブルを大きくする」拡張と「変換を速くする」最適化は常に対で進む。

巨大ページはただではない。透過的巨大ページ(THP)がメモリを過度に先取りしたり、巨大ページを確保しようとカーネルが小さなページを集めるメモリ圧縮整理(compaction)の遅延がテール遅延を悪化させたりした事例も報告されている。そこでデータベース運用ではTHPを切りhugetlbfsで明示的巨大ページだけを使うよう勧めるベンダが多い——ハードウェア機能一つを入れ切りする決定さえワークロード特性と計測なしには逆効果を生みうることを示す実例である。

B. 階層化メモリと回収方針の進化

最近の動向も活発である。CXLに基づくメモリ拡張・階層化メモリ(tiered memory)はDRAMと遅い遠隔メモリを階層化し、OSがホット・コールドページを自動的に昇降(promotion/demotion)させるが、これは本質的に「ページ置換の多階層化」である(関連: [[cxl]])。LinuxのMGLRU(Multi-Gen LRU)は従来のactive/inactive二段LRUを複数世代へ拡張し大規模メモリで回収決定の精度と効率を高めた2022年以降の代表的改善である。また書込み時コピー・demand zeroing・メモリ圧縮(zswap/zram)はすべて仮想メモリ層で物理メモリを節約する技法で、コンテナ密集環境の集積度を引き上げる。

とりわけメモリ圧縮はディスクスワップの代替として注目される。コールドページを遅いディスクへ追い出す代わりにCPUで圧縮してメモリ内に保管(zram・zswap)すれば、ディスクI/Oなしに実効メモリを増やせる。Androidが限られたRAMで多数のアプリをバックグラウンドに保つ秘訣がまさにzramであり、KubernetesノードでもOOM Killを減らそうと圧縮スワップを有効にする運用が増えている。これは「ページをどこにどんな形で置くか」という仮想メモリの本質的な問いがディスク・圧縮・遠隔メモリという多様なバッキングストアへ拡張されていることを示している。

6. 考慮事項および示唆(技術士の観点)

  • 適用戦略 — ワークロード別の方針選択: 遅延敏感サービス(Web・DB)はスワップを抑制し巨大ページ・十分なワーキングセットフレームを確保してフォルトを構造的に遮断すべきであり、バッチ・分析ワークロードはメモリオーバーコミットと階層化メモリを活用し集積度を高めるというように目的に合ったメモリ方針を分離設計すべきである。単一の最適設定はなく参照局所性の分析が先行すべきである。
  • トレードオフ管理: ページサイズは内部断片化(大きく)とTLB効率(大きく)の均衡、オーバーコミットは集積度(高く)とOOMリスク(高く)の均衡、大域/局所置換は全体効率とプロセス間隔離の均衡点である。これらの相反をvmstat・perf・フォルト率で定量測定し調整する力量が求められる。
  • 観測・検証体系の制度化: 仮想メモリ品質は平均ではなくフォルト率・スワップI/O・TLBミス率・メジャーフォルトの分布に現れるので、これらを常時計測しSLOと連動させスラッシングの兆候を早期警報する観測体系がなければ性能チューニングは根拠を失う。
  • 容量見積りとの連携: 仮想メモリは物理メモリの超過使用を許すが、それが無限のメモリを意味するわけではない。ワーキングセットの合計が物理メモリを超えた瞬間に性能が非線形に崩壊するので、サーバ・コンテナ容量見積り時にRSS・ワーキングセットに基づく実測需要を根拠にメモリを配分しスワップを安全網としてのみ使う設計原則が必要である。
  • セキュリティ・隔離との連携: 仮想アドレス隔離はプロセス保護の土台だが、Meltdown・Spectreのような投機的実行の副チャネルはアドレス変換・TLB経路を悪用した(関連: [[speculative-execution-branch-prediction]])。カーネルページテーブル隔離(KPTI)などの緩和策が性能を犠牲にするので、メモリ管理設計は今やセキュリティ-性能トレードオフまで併せて扱わねばならない。
  • 設計原則としての局所性確保: 置換アルゴリズムをいかに精緻化してもプログラム自体の参照局所性が悪ければフォルトを防げない。データ構造のメモリ配置(配列 vs 連結リスト)、反復の参照順(行優先 vs 列優先)、データ指向設計などアプリ水準の局所性最適化がOSメモリ管理と対になって初めて性能が完成し、技術士は下部メカニズムと上部設計を併せて俯瞰できねばならない。
  • 展望と連携技術: CXL階層化メモリ・MGLRU・メモリ圧縮は「遅い大容量層を置換方針で管理する」方向へ収束し、今後の仮想メモリはDRAMを超えて異種メモリ階層全体を司るデータ配置エンジンへ進化するであろう。クラウド資源管理([[finops]])・コンテナ集積度と直接境を接するので、OSメモリ原理の理解はインフラコスト最適化の土台となる。

参考資料


一言まとめ: 仮想メモリは要求ページングで必要なページだけを読み込み物理メモリを超えたアドレス空間とプロセス隔離を提供する技法であり、フォルト率に極度に敏感であるがゆえにOPT・FIFO・LRU・Clockなどの置換アルゴリズムとワーキングセットに基づくフレーム割当でスラッシングを防ぎ、現代では巨大ページ・ネストページング・MGLRU・CXL階層化メモリへ拡張されている。