ページ置換アルゴリズム

出典: フリー百科事典『ウィキペディア（Wikipedia）』

ページ置換アルゴリズム（ページちかんアルゴリズム）とは、メモリ管理としてページング方式を使用するコンピュータのオペレーティングシステムにおいて、空き物理ページが少ない状態で新たなページを割り当てなければならないときにどのページを「ページアウト（スワップアウト）」するかを決定する方法を意味する。これはページフォールトが発生したときに使用可能なフリーなページが存在しないときに発生する。厳密には発生条件はシステムの種類や設定によって異なるが、フリーなページが全く無い場合か、あらかじめ設定したしきい値よりもフリーなページ数が少ないときに発生する。

以前にページアウトすべきページとして選択され置換されたページに再度アクセスが発生したら、そのページをページインする必要がある。そして、これにはI/Oの完了を待たなければならない。この、ページインを待つ時間の累計が小さいほどページ置換アルゴリズムが優秀であると言える。ページ置換アルゴリズムはページへのアクセスに関するハードウェアからの限られた情報を見て、アルゴリズム自身にかかる時間とページインにかかる時間のバランスをとりつつ、ページミスのなるべく起きない置換をしなければならない。

ページ置換アルゴリズムはオンラインアルゴリズムの一種である。

目次 1 歴史 2 ローカルな置換とグローバルな置換 3 事前クリーニング 4 理論上最適なページ置換アルゴリズム 5 NRU（Not Recently Used） 6 FIFO（First-In First-Out） 7 セカンドチャンス 8 クロック 9 LRU（Least Recently Used） 9.1 LRU方式のバリエーション 10 ランダム 11 NFU（Not Frequently Used） 12 エージング 13 関連項目 14 参考文献 15 脚注

[編集] 歴史

置換アルゴリズムは1960年代から1970年代にかけて研究の重要テーマであり、議論が戦わされた。結果として洗練されたLRU推測手法とワーキングセットアルゴリズムが開発されたのである。以来、伝統的なアルゴリズムが前提としていた事柄の一部が否定され、ふたたび研究が行われるようになった。とりわけ、以下のようなハードウェアの動作の変化とユーザーレベルのソフトウェアの動作の変化がアルゴリズムを変えさせてきた。

• 一次記憶装置の容量はどんどん大きくなっている。主記憶が数ギガバイトということも珍しくない状態では、全メモリページを定期的にチェックするアルゴリズムはどんどん現実味を失いつつある。

• メモリ階層が高くなってきた。CPUのキャッシュミスは非常に性能にインパクトがあるため、上記の問題はさらに悪化する。

• ユーザーのソフトウェアでの参照の局所性は薄れてきた。オブジェクト指向プログラミングが多く使われるようになったことが原因のひとつである。この場合、小さな関数を数多く使用し、ツリー構造やハッシュテーブルなどの洗練されたデータ構造を使用する。これらは混沌としたメモリ参照パターンを示し、ガベージコレクションがひとたび起きればメモリ参照パターンは劇的に変化してしまう。

また、置換アルゴリズムへの要求もオペレーティングシステムのカーネルアーキテクチャの変化に伴って変わってきた。多くの最近のカーネルは仮想記憶とファイルシステムのキャッシュを統合的に管理している。したがって、置換アルゴリズムはページを選択するにあたって、ユーザプログラムの仮想アドレス空間とキャッシュされたファイルの両方を検討しなければならない。後者のページは特定の属性を持つ。例えば、ファイルキャッシュはロックされる可能性もあるし、ジャーナリングによってディスクへの書き込みを要求されている場合もある。さらに、ページ置換アルゴリズムの目標がメモリ待ちとなる時間を最小化することだとすれば、他のカーネル内サブシステムのメモリ確保要求についても関わっていかなければならない。結果として、最近のカーネル（Linux、FreeBSD、Solaris）では、ページ置換は仮想記憶サブシステムのレベルよりももっと基本的なカーネル内の汎用メモリアロケーション機構の一部となりつつある。

[編集] ローカルな置換とグローバルな置換

置換アルゴリズムは「ローカル」と「グローバル」に分けられる。あるプロセスがページフォールトを発生したとき、ローカルなページ置換アルゴリズムではそのプロセス（あるいはそのプロセスが属するメモリ・パーティションを共有するプロセスグループ）が現在使用しているページ群からページを選択して置換する。一方、グローバルなページ置換アルゴリズムではメモリ上の任意のページを選択する。

ローカルなページ置換では、ある種のメモリ・パーティションが前提となっており、プロセスあるいはプロセスグループに対して割り当て可能なメモリページ数を決定している。最も一般的なパーティション手法としては「固定パーティション」とワーキングセットモデルに基づいた「バランスセット」アルゴリズムがある。ローカルなページ置換の利点はスケーラビリティが良いことである。各プロセスはページフォールトに独立して対処できるので、グローバルなデータ構造に必要以上に関わる必要がない。

[編集] 事前クリーニング

最も教科書的な置換アルゴリズムは、結果としてページを選択して返す。このページが変更されている場合（そのページを再利用する前に内容を二次記憶装置に書き戻す必要があることを意味する）、ページ内容をディスクなどに書き出して クリーンなページにしなければならない。初期の仮想記憶では、このクリーニング処理のオーバーヘッドは問題とはならなかった。というのは、当時のシステムでは全二重チャネルで二次記憶装置を接続していたため、ページインを並行して実行できたのである。最近の商用ハードウェアでは、全二重転送はサポートしていないため、クリーニングが問題となるのである。

これに対処するために、様々な事前クリーニングポリシーが実装された。事前クリーニングとは、間もなく再利用される予定の（内容を変更されている）ページについて I/O を開始する機構である。考え方は、次にページアウト対象として選ばれるページを事前にディスクに書き戻しておけば、実際にページアウト対象として選ばれたときにはI/Oをする必要がないということである。事前クリーニングは次に選択されるページが事前にわかることを前提としている。あまり積極的に行うと、選択されたときにはまたクリーニングが必要な状態になってI/Oバンド幅を浪費することになる。結局、スループットを優先するか、ターンアラウンドタイムを優先するかという選択になり、システムの性格によって最適な落とし所は変わってくる。

[編集] 理論上最適なページ置換アルゴリズム

理論上最適なページ置換アルゴリズム（OPT とか千里眼置換アルゴリズムとも呼ばれる）とは、以下のようなものである。ページをスワップインする必要が生じたとき、オペレーティングシステムが現在メモリ上にあるページを全て調べて、次にページが使われるまでの時間を測る。そして、OSは最も長い期間使われないページをスワップアウトする。たとえば、今後600万マイクロ秒の間使われないページをスワップアウトして、今後4000マイクロ秒間使われる予定のページに割り当てる。

しかし、このアルゴリズムを実際に（少なくとも汎用の）オペレーティングシステムに実装することは現実的ではない。ただし、実行されるソフトウェアが全て判っていて、それらのメモリ使用パターンも分析済みであるか、実行時に分析することが可能な場合は不可能ではない。とは言うものの、OPT に近い性能を示すアルゴリズムは存在する。あるソフトウェアを最初に動作させたときに、オペレーティングシステムが使われたページを全て記録する。そしてこのデータを使って二度目以降にそのソフトウェアを動作させるときに、このデータを使ってページ置換を行うのである。この手法は OPT に近い性能を保証するが、それは二度目の動作のときであり、初めて動作させるソフトウェアでは無効である。また、動作するたびにメモリ参照パターンが大きく変化するプログラムでは効果がない。

[編集] NRU（Not Recently Used）

NRU（最近使われていない）ページ置換アルゴリズムは、最近使われたページを残すことを主眼としたアルゴリズムである。このアルゴリズムは以下のように働く。ページが参照されたとき、そのページの参照ビットが立って参照があったことを示す。同様にページが変更（書き込み）された場合、変更ビットを立てる。これらビットのセットは通常ハードウェア（MMU）が行うが、ソフトウェアレベルで行うことも可能である。

そして、ある一定の時間間隔でクロック割り込みをトリガーとして全ページの参照ビットをクリアする。そうすると、その時間間隔内で参照されたページだけが参照ビットが立った状態になる。ページを置換する必要が生じたとき、オペレーティングシステムはページを四種類に分類する。

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

参照されていないのに変更されているページというのは矛盾しているように思われるが、これはカテゴリ3のページの参照ビットをクロック割り込みの際にクリアした場合に生じる。NRU アルゴリズムでは、単純にカテゴリ番号の小さい方のページを選択する。つまり、変更があるかどうかよりも参照があるかどうかを重視することに注意されたい。

[編集] FIFO（First-In First-Out）

FIFOページ置換アルゴリズムはオーバヘッドの少ないアルゴリズムのひとつで、OS内でちょっとした記録をとる。名前からもわかるとおり、プロセスに割り当てたページを割り当てた順番にキューに載せる。ページ置換が必要になったとき、キューの先頭のページ（最も古いページ）を選択する。FIFO構造はコストがかからないし簡単なのだが、実際のアプリケーションにこのアルゴリズムを適用すると性能は悪くなる。そのため、そのままの形で使われることはない。

FIFOページ置換アルゴリズムはVAXのVMS^[1]、Microsoft Windows NTシリーズで使われている。

[編集] セカンドチャンス

これは、FIFOページ置換アルゴリズムを少し改善したものである。このアルゴリズムでもFIFOの先頭のページをまず調べるが、即座にスワップアウトするのではなく、参照ビットが立っているかどうかを調べる。もし立っていなかったら、そのページをスワップアウトする。さもなくば、そのページの参照ビットをクリアしてFIFOの最後尾につなぎ直す。この処理を繰り返すのである。もし、全てのページの参照ビットが立っていたら、元の先頭ページがFIFOの先頭に出てきた時点で、それをスワップアウトする（参照ビットがクリアされているため、元にもどったかどうかを判断する必要はない）。

セカンドチャンスが何をしているかと言えば、古いページの参照ビットを見てチャンスを一度あげるのである。

ページ置換が必要になったとき、キュー上の全ページを見て回る（しかもキューを操作し続ける）可能性があることに注意。大容量のメモリを持ち、応答性能を重視されるシステムでは予想外の遅延が生じる可能性がある。

[編集] クロック

クロックとは、FIFOをセカンドチャンスよりも効率化した方式で、ページを定期的にリストの後方に押しやる必要がなく、セカンドチャンスと同等の機能を実現するものである。クロックアルゴリズムではページを円環状のリストとして扱い、そのリスト上の最も古いページを指す「手」を使用する。ページフォールトが発生して空きがないとき、手が指している位置から参照ビットのチェックを行う。参照ビットが 0 なら、手の指しているページを再利用し、0 でないなら参照ビットをクリアして手をインクリメントする。そして、置換可能なページが見つかるまでこれを繰り返す^[2]。

[編集] LRU（Least Recently Used）

LRU（最も最近使われていない）ページ置換アルゴリズムは NRUと名前は似ているが、LRUでは短期間のページ使用履歴を保持している点が異なる。NRUではクロック割り込み間隔の使用/不使用で判断していた。LRU は、最近よく使われているページはその後の短時間でもよく使われるだろうという判断に基づいている。LRU は理論上は OPT に近い性能を発揮するはずだが、実際に実装するとコストがやや高い。このコストを抑える試みをした実装手法がいくつか存在している。

最もコストの高い手法はメモリ上の全ページを含むリンクリストを使う方法である。このリストの最後尾はLRUページであり、先頭は逆に最も最近使われているページである。この実装のコストはメモリ参照の度にリスト上のアイテムを移動させなければならない点であり、これには非常に時間がかかる。

別の方法は以下のようなハードウェアのサポートを必要とする。ハードウェアで 64ビットのカウンタを命令実行毎にカウントアップする。ページにアクセスがあったときは、その時点のカウンタの値をページに与える。ページを置換するとき、オペレーティングシステムは単純に最も小さなカウンタ値を持つページを選択する。ただし、現在のハードウェアにはそのような機構はないので、現実的ではない。

LRU アルゴリズムの重要な利点は、完全な統計分析を修正できる余地がある点である。たとえば、OPT アルゴリズムに比較して N回以上ページフォールトが多くなることはない、ということが証明されている。ここで、N は管理対象のページ数に比例した値である。

一方 LRU の欠点は、一般的な参照パターンで性能を低下させてしまう傾向があることである。たとえば、LRU 対象のページが N 個あったとして、あるアプリケーションが N + 1 ページにまたがる配列にアクセスしながらループしているとき、インデックスの進みと共にページフォールトが発生してしまう（つまり、配列が大きすぎるので必ずページ置換は必要だが、LRUを使うと次にアクセスするページが必ずページアウトされてしまう）。大きなループを使うのは一般的なので、このような場合に対応できるようにLRUを改善する試みは多く行われてきた。最も多い手法はループしてアクセスしているパターンを検出して、適した置換アルゴリズム（たとえば、MRU（Most Recently Used）に切り替えるのである。

[編集] LRU方式のバリエーション

1. LRU-K は、LRU における時間局所性を改善した方式。LRU-2 とも呼ばれる。LRU-1 は通常の LRU 方式を意味する。
2. ARC^[3] アルゴリズムは最近置換されたページの履歴を保持するよう拡張した LRU であり、その情報を使ってページ使用履歴の扱いを修正している。特にシーケンシャルなページアクセスに強い。他のアルゴリズムとの比較が Megiddo と Modha によって行われた^[4]。

[編集] ランダム

ランダム置換アルゴリズムはランダムにページを選んで置換する。おかしな話と思われるかもしれないが、このアルゴリズムはある状況では役に立つ。一般に FIFO よりも性能がよく、ループしたメモリ参照でも LRU より性能がよい。OS/390は グローバルなLRU予測をしているが、LRUの性能が悪くなったことを検出するとランダム置換に切り替えるようになっている。

[編集] NFU（Not Frequently Used）

NFU（頻繁には使われていない）ページ置換アルゴリズムも、カウンタを必要とするが、この場合は各ページが初期値ゼロのカウンタを持つ。クロック割り込みの度に前回のクロック割り込み以降参照のあったページ全てのカウンタを 1 だけカウントアップする。結果としてカウンタはそのページがどれだけ頻繁にアクセスされているかを示すことになる。したがって、最もカウンタの値の小さいページを必要に応じてスワップアウトする。

NFU の主な問題点は、使用回数だけで頻度を求めているために、どれだけ本当に頻繁かがわからないことである。したがって、マルチパスコンパイラの動作を考えてみると、最初のパスで頻繁にアクセスしたメモリは次のパスではアクセスされないにも関わらず、全体的に使用回数で見れば最初のパスでアクセスしていたページの方が多いために、二回目のパスで実際に使用しているページがスワップアウトされてしまうことになる。そうなると性能は低下する。うれしいことに、これに似ているがもっとよいアルゴリズムがある（後述）。

[編集] エージング

エージング・アルゴリズムは NFU アルゴリズムを改良したもので、ページを使用した時間間隔を考慮するようにしたものである。ページ毎のカウンタを単純にインクリメントする代わりに、時間に応じて参照に重み付けをする。ページの参照カウンタは右シフト（2で割るのと同じ）してからカウントアップされる。たとえば、あるページのクロック割り込み 6回分の参照ビットが、1 → 0 → 0→ 1 → 1 → 0 だった場合、その参照カウンタは、10000000 → 01000000 → 00100000 → 10010000 → 11001000 → 01100100 のように変化する。これを見てもわかる通り、最近の参照に対応した値は大きく、過去に遡るほど値が小さくなる。これにより参照回数がすくなくても最近参照されたページが高い優先順位を持つことになる。したがって、置換が必要なら、このカウンタ値が小さいページを選択する。

LRU と エージングは違うことに注意されたい。エージングは限られたクロック割り込み回数ぶんしか参照履歴を持たない（そのプロセッサの整数のビット幅により、16回だったり 32回だったりする）。カウンタが8ビットの場合、9 tick（クロック割り込み間隔のこと）前に参照があっても 1000 tick 前であっても、カウンタはゼロになってしまう。一般に、最近の 16 tick ぶんの履歴があればスワップアウトすべきページを決定するには十分である。したがって、エージングは低コストで OPT に近い性能を発揮する。

[編集] 関連項目

• キャッシュアルゴリズム

[編集] 参考文献

• Aho, Denning and Ullman, Principles of Optimal Page Replacement, Journal of the ACM, Vol. 18, Issue 1,January 1971, pp 80-93
• Tanenbaum, Andrew S. Operating Systems: Design and Implementation (Second Edition). New Jersey: Prentice-Hall 1997.
• Tanenbaum, Andrew S. Modern Operating Systems (Second Edition). New Jersey: Prentice-Hall 2001. ページ置換アルゴリズムに関するオンラインの抜粋: Page Replacement Algorithms.
• Johnson and Shasha, 2Q: A Low Overhead High Performance Buffer Management Replacement AlgorithmPDF (1.01 MiB) abstract
• Gideon Glass and Pei Cao Adaptive-Page-Replacement-Based-on-Memory-Reference-Behavior. 拡張された形式で Technical Report 1338 at www.cs.wisc.edu にもある。
• Jongmin Kim and others, A Low-Overhead High-Performance Unified Buffer Management Scheme that Exploits Sequential and Looping ReferencesPDF (4.14 MiB), Usenix Symposium on Operating System Design and Implementation (OSDI'2000), San Diego, CA, October 17-21, 2000
• Sorav Bansal and Dharmendra S. Modha, CAR: Clock with Adaptive ReplacementPDF (212 KiB)
• Smaragdakis and others, EELRU: Simple and Effective Adaptive Page ReplacementPDF (1.55 MiB)
• Song Jiang and Xiaodong Zhang, LIRS: a Low Inter Reference recency Set replacementPDF (309 KiB), SIGMETRICS 2002
• Elizabeth J. O'Neil and others, The LRU-K page replacement algorithm for database disk bufferingPDF (1.17 MiB), ACM SIGMOD Conf., pp. 297–306, 1993.
• Y. Zhou and J.F. Philbin, The Multi-Queue Replacement Algorithm for Second-Level Buffer Caches, Proc. Usenix Ann. Tech. Conf. (Usenix 2001), pp. 91-104.

[編集] 脚注