ページ置換アルゴリズムとワーキングセット
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2007/06/22 17:15 UTC 版)
「ワーキングセット」の記事における「ページ置換アルゴリズムとワーキングセット」の解説
ページ置換アルゴリズムは従来、システムの全物理ページを対象としていた。しかし、メモリ容量の増大に伴ってそのようなアルゴリズムは効率が悪くなってきた。例えば、NRU(Not Recently Used)アルゴリズムをシステム全体で行う場合、二針時計アルゴリズムなどが使われていた。これはページの参照フラグをクリアする針と参照があったかどうかを確認する針が円形に並んだ物理ページを順次チェックしていくアルゴリズムである。二つの針を進める実装方法としては、一定間隔(例えば1秒に1回)で所定のページ数だけクリア/チェックを行うのが一般的である。しかし、メモリ容量が大きくなるにつれて、全物理ページをチェックするのに非常に長い時間がかかるようになってきた。針を進める速度を速めるとカーネルが長時間連続動作することになるため、システムの応答性が悪くなる。また、二つの針の間隔を広げると参照フラグがクリアされたままの物理ページが少なくなってしまい、これも効率が悪い。 以上のような経緯で、システム全体ではなく何らかの分割をした形でページ置換を行う必要が生じたのである。このためにワーキングセットに基づいたプロセス単位のページ置換が一般化するようになった。ワーキングセットを確定する手法としてはページ置換アルゴリズムにある各種アルゴリズムが使われている。いずれにしてもワーキングセットに基づいたページ置換は参照の局所性を根拠とするものである。
※この「ページ置換アルゴリズムとワーキングセット」の解説は、「ワーキングセット」の解説の一部です。
「ページ置換アルゴリズムとワーキングセット」を含む「ワーキングセット」の記事については、「ワーキングセット」の概要を参照ください。
- ページ置換アルゴリズムとワーキングセットのページへのリンク
