ページ置換アルゴリズム

ページ置換アルゴリズムとは

ページ置換アルゴリズムは、仮想記憶システムにおいて、物理メモリが不足した際にどのページを二次記憶装置（ディスクなど）に退避させるかを決定する仕組みです。この処理は、ページフォールトが発生し、新たなページをメモリにロードする必要があるものの、空きページが存在しない場合に実行されます。

ページアウトされたページに再度アクセスする際には、ページイン処理が必要となり、この際にI/O待ち時間が発生します。ページ置換アルゴリズムの性能は、このI/O待ち時間の合計をどれだけ小さくできるかによって評価されます。優れたアルゴリズムは、ハードウェアから得られる限られた情報に基づいて、ページインの回数を最小限に抑えつつ、アルゴリズム自体の処理時間とのバランスを取る必要があります。ページ置換アルゴリズムは、オンラインアルゴリズムの一種として分類されます。

歴史的背景

ページ置換アルゴリズムの研究は1960年代から1970年代にかけて活発に行われました。その結果、LRU（Least Recently Used）アルゴリズムの近似手法やワーキングセットアルゴリズムなど、洗練されたアルゴリズムが開発されました。しかし、ハードウェアの進化やソフトウェアの利用形態の変化に伴い、従来のアルゴリズムが前提としていた条件が変化し、再び研究が進められるようになりました。

具体的には、以下の変化がページ置換アルゴリズムに影響を与えました。

主記憶容量の増大: メモリ容量がギガバイト単位になったことで、全メモリページを定期的にチェックするアルゴリズムの現実味が薄れました。
メモリ階層の複雑化: CPUキャッシュのミスが性能に大きな影響を与えるようになり、ページ置換アルゴリズムの重要性が増しました。
ソフトウェアの参照局所性の低下: オブジェクト指向プログラミングの普及により、メモリ参照パターンが複雑化し、ガベージコレクションによる影響も無視できなくなりました。
カーネルアーキテクチャの変化: 仮想記憶とファイルシステムキャッシュの統合が進み、ページ置換アルゴリズムはより広い範囲のページを考慮する必要が出てきました。

これらの変化に伴い、ページ置換アルゴリズムは、単にメモリ待ち時間を最小化するだけでなく、カーネル内の他のサブシステムのメモリ確保要求にも関わる必要が出てきました。

ローカル置換とグローバル置換

ページ置換アルゴリズムは、ローカル置換とグローバル置換の2種類に分類できます。

ローカル置換: ページフォールトが発生したプロセスが使用しているページの中から置換対象を選択します。これにより、プロセスの独立性が高まり、スケーラビリティが向上します。
グローバル置換: メモリ上の任意のページを置換対象として選択します。

ローカル置換は、プロセスに割り当てるメモリ量を決定するメモリパーティションの概念が前提となります。一般的なパーティション手法としては、固定パーティションやワーキングセットモデルに基づくバランスセットアルゴリズムがあります。

事前クリーニング

ページを置換する際には、変更されたページ（ダーティページ）の内容を事前に二次記憶装置に書き戻す必要があります。これを事前クリーニングと呼びます。事前クリーニングは、実際にページを置換する前に書き戻し処理を行うことで、置換時のI/O待ち時間を短縮する効果があります。

ただし、過度に事前クリーニングを行うと、I/Oバンド幅を浪費する可能性もあるため、スループットとターンアラウンドタイムのバランスを考慮した運用が必要です。

先行ページング

先行ページングは、次に必要となる可能性のあるページを事前にメモリにロードする技術です。これにより、ページフォールトの発生を抑制し、システムの性能を向上させることができます。先行ページングは、事前クリーニングと組み合わせて使用されることが多く、メモリ上に不要なページを事前に退避させておくことで、より効率的なページ管理を実現します。

主要なページ置換アルゴリズム

理論上最適なページ置換アルゴリズム (OPT)

OPTアルゴリズムは、最も長い間使われないページを置換するという理想的なアルゴリズムです。しかし、将来のページアクセスを予測する必要があるため、実際には実装が困難です。OPTは、他のアルゴリズムの性能を評価する際の基準として用いられます。

NRU (Not Recently Used)

NRUアルゴリズムは、最近使われていないページを置換するアルゴリズムです。ページが参照されたり変更されたりすると、それぞれのビットが立てられ、一定時間ごとに参照ビットがクリアされます。そして、ページ置換が必要になった際には、以下の4つのカテゴリに分類し、カテゴリ番号の小さい順に置換を行います。

カテゴリ0: 参照なし、変更なし
カテゴリ1: 参照なし、変更あり
カテゴリ2: 参照あり、変更なし
カテゴリ3: 参照あり、変更あり

FIFO (First-In First-Out)

FIFOアルゴリズムは、最初にメモリにロードされたページを最初に置換する、最もシンプルなアルゴリズムです。実装は容易ですが、性能はあまり高くありません。

セカンドチャンス

セカンドチャンスアルゴリズムは、FIFOアルゴリズムを改良したもので、FIFOの先頭のページを参照し、参照ビットが立っていなければ置換、立っていれば参照ビットをクリアしてキューの末尾に移動させるという処理を繰り返します。これにより、頻繁に参照されるページが置換される可能性が低くなります。

クロック

クロックアルゴリズムは、セカンドチャンスアルゴリズムを効率化したもので、ページを円環状のリストとして管理し、針が指すページを参照し、参照ビットが立っていなければ置換、立っていれば参照ビットをクリアして針を移動させるという処理を繰り返します。

クロック方式のバリエーション

GCLOCK: 一般化したクロック方式。
CLOCK-Pro: 最近ページアウトされたページの情報も利用する方式。
WSCLOCK: エージングアルゴリズムと組み合わせて使用される方式。
CAR: 自律的にパラメータを調整する、LRUよりも高性能なアルゴリズム。

LRU (Least Recently Used)

LRUアルゴリズムは、最も長い間使われていないページを置換するアルゴリズムです。理論的にはOPTに近い性能を発揮しますが、実装コストが高いという欠点があります。

LRU方式のバリエーション

LRU-K: LRUの時間局所性を改善した方式。LRU-2とも呼ばれる。
ARC: LRUとLFUを組み合わせ、シーケンシャルアクセスに強いアルゴリズム。

ランダム

ランダムアルゴリズムは、ページをランダムに選択して置換するアルゴリズムです。一見非効率に思えますが、特定の条件下ではFIFOやLRUよりも良い性能を発揮することがあります。

NFU (Not Frequently Used)

NFUアルゴリズムは、各ページにカウンタを用意し、クロック割り込みごとに参照されたページをカウントアップし、最もカウンタの小さいページを置換するというものです。

エージング

エージングアルゴリズムは、NFUを改良したもので、参照頻度に加えて時間経過を考慮します。参照カウンタを右シフトし、最新の参照に重みを置くことで、より実用的なページ置換を実現します。

参照ビットを持たないハードウェアでの技法

一部のハードウェアでは、ページごとの参照ビットを持たないため、Secondary Page Cachingなどのテクニックが使用されます。これは、ワーキングセットから除かれたページを一時的にリストに保持し、ソフトフォールトの発生を検出しつつ、効率的なページ置換を行うものです。

ワーキングセット

ワーキングセットは、ある期間中にプロセスが使用するページの集合であり、ページ置換アルゴリズムだけでなく、中期スケジューリングにも利用される概念です。

まとめ

ページ置換アルゴリズムは、仮想記憶システムにおいて重要な役割を果たします。様々なアルゴリズムが存在し、それぞれの特徴を理解し、システムの要件に合わせて適切なアルゴリズムを選択することが重要です。また、ハードウェアやソフトウェアの進化に伴い、新たな課題や要求が生まれているため、継続的な研究開発が求められます。

もう一度検索