ページングアルゴリズム

OSがページアウトするページを決める際のアルゴリズムとしてLRUがある。
これは最も参照されていない期間が長いページをページアウトするアルゴリズムである。
しかしながら、すべてのページついて参照された時刻を記録して比較することは
あまりに大きなオーバーヘッドとなるため、近似的なアルゴリズムを用いることになる。
一つの考え方としてページに付加されたrefarence bitとdirty bitを利用する方法がある。

• • refarence bit

read時にsetされる。

• • dirty bit

更新時にsetされる。

これを利用した置換アルゴリズム

1.OSが定期的にrefarence bit とdirty bit をclearする。
2.ページング処理ではclearされているページを選ぶ