物理メモリーを、256 MB も(?)積んでいる機種のCPUは、恐らく 1GHzは
あると考えるのが妥当だという前提に立つと、1エントリの調査に x クロック
必要だとすると、

x * (100*65536)/(1024*1024*1024) = 0.006 x

これが、この処理が必要とする時間の全CPUパワーに対する比率になります。

x = 10 として、6%。

IA32だと、ページテーブルエントリのアクセスビットだけでなく、
ページディレクトリ・エントリのアクセスビットもあるので、そちらで
普段は「カリング」できるので、このアルゴリズムでも余り問題ないの
でしょうか？？

しかし、FLATモデルだと、複数のページディレクトリがあるので、そんな
ことで済まないような気も。