アルゴリズムは、LRUとLFUを組み合わせたアルゴリズムで、最近キャッシュから消されたページの履歴を保持するように拡張し、その情報を使って、かつてキャッシュされていたけれど今はキャッシュから消されているという情報を元に、LRUとLFUの配分を動的に自動的に調整する。シーケンシャルなページアクセスに強い。よって行われた[14]。ランダム[編集]ランダム置換アルゴリズムはランダムにページを選んで置換する。おかしな話と思われるかもしれないが、このアルゴリズムはある状況では役に立つ。グローバルなLRU予測をしているが、LRUの性能が悪くなったことを検出するとランダム置換に切り替えるようになっている。プロセッサもランダム置換方式を採用していた[15]。Used)[編集]NFU(頻繁には使われていない)ページ置換アルゴリズムも、カウンタを必要とするが、この場合は各ページが初期値ゼロのカウンタを持つ。結果としてカウンタはそのページがどれだけ頻繁にアクセスされているかを示すことになる。したがって、最もカウンタの値の小さいページを必要に応じてスワップアウトする。主な問題点は、使用回数だけで頻度を求めているために、どれだけ本当に頻繁かがわからないことである。したがって、マルチパスコンパイラの動作を考えてみると、最初のパスで頻繁にアクセスしたメモリは次のパスではアクセスされないにも関わらず、全体的に使用回数で見れば最初のパスでアクセスしていたページの方が多いために、二回目のパスで実際に使用しているページがスワップアウトされてしまうことになる。なると性能は低下する。うれしいことに、これに似ているがもっとよいアルゴリズムがある(エージング)。アルゴリズムを改良したもので、ページを使用した時間間隔を考慮するようにしたものである。ページ毎のカウンタを単純にインクリメントする代わりに、時間に応じて参照に重み付けをする。ページの参照カウンタは右シフト(2で割るのと同じ)してからカウントアップされる。これを見てもわかる通り、最近の参照に対応した値は大きく、過去に遡るほど値が小さくなる。これにより参照回数がすくなくても最近参照されたページが高い優先順位を持つことになる。したがって、置換が必要なら、このカウンタ値が小さいページを選択する。エージングは違うことに注意されたい。32回だったりする)。前であっても、カウンタはゼロになってしまう。ぶんの履歴があればスワップアウトすべきページを決定するには十分である。参照ビットを持たないハードウェアでの技法[編集]これまで解説してきた技法の多くは、各ページに対応した参照ビットが存在することを前提としている。中にはそのようなビットを持たないハードウェアもあり、その場合に効率的にページ置換を行うにはテクニックを要する。知られた例として、VMSの動作するVAXがある。ワーキングセットから除かれたページはすぐには削除されず、一時的に2つのリストのいずれかに置かれる。ARMアーキテクチャでのLinuxカーネル実装でも参照ビットのない状況に対処している。この場合、参照ビットも更新ビットもないプロセッサ本来のページテーブルと、それらのビットを含めたページテーブルを用意する。それらのビットのエミュレーションはページフォールト処理で行う。参照ビットをクリアしたとき、ページフォールトを確実に発生させなければならないので、プロセッサ本来のページテーブルを同時に書き換える。ワーキングセットから除くページの選択は基本的にランダムになされるが、即座に書き換えられて使われるわけではないので、プロセスが再びそのページを参照し、ソフトフォールトを発生することもある。似た機構を提供し、全体として先述のセカンドチャンスと似たような効率となる。ワーキングセット[編集]詳細は「ワーキングセット」を参照プロセスのワーキングセットは、ある期間中にそのプロセスが使うと予想されるページの集合である。「ワーキングセットモデル」は厳密にはページ置換アルゴリズムではなく、一種の中期スケジューラである。2012年2月19日閲覧。(日時は個人設定で未設定ならばUTC)。表示-継承ライセンスの下で利用可能です。追加の条件が適用される場合があります。詳細は利用規約を参照してください。開発者Cookieに関する声明モバイルビュ。