オペレーティング システムでページ置換に使用される WSClock アルゴリズムについて質問があります。
私が理解している限り、WSClock は両方のワーキング セットの機能を組み合わせています (ページが最後の T 時間間隔で参照された場合、ページは WS にあるため、最後の参照時間は R&M ビットを使用して各ページに保存されます)。クロック アルゴリズム (ページ フレーム テーブルは循環リストとして格納されます。ページ フォールトが発生すると、ワーキング セットに存在しないページを検索するためにリストが走査されます)。
各ページ参照で、HW はその R ビットを 1 に設定します。ある時間間隔で、OS はすべてのページの R ビットを 0 にリセットします。
ページ フォールトが発生すると、アルゴリズムはリストを走査し、ページごとに次の処理を実行します。
1) If R == 1 : set R = 0, set t = process_t, go further
2) Else if R == 0 and (t - process_t) <= T, go further
3) Else if R == 0 and (t - process_t) > T
1) If M = 1 - set page for writing to disk, go further
2) If M = 0 - this is our victim, evict
If there are no pages for immediate evict are found - traverse until a disk write for any marked page is finished, then evict.
If there are no pages scheduled for a disk write - take the one which was referenced to the most time ago.
アルゴリズムは、次の 1 つの点を除いて、私にとっては問題ないように見えます。
ページが最後に参照された時間は、1 回だけ変更されます。このページが参照された後にページ フォールトが発生した場合 (R = 1)、OS がまだ R ビットを 0 にリセットしていない場合 (R = 0)。私が理解しているように、最後に使用された時間は、パフォーマンスの向上につながるアプローチによってのみ概算されます。
したがって、プロセスの WS に間違いなく存在する非常に頻繁に使用されるページの場合は、すべて問題ありません。それらの参照頻度は、OS リセット イベントの頻度よりも高くなっています。
しかし、かなり頻繁に参照される不運なページがいくつかあるはずですが、残念ながら、これらの参照の後にページ フォールトは発生しません。しかし、ページ フォールトが発生すると、それらは参照されていないように見えるほど不運でもありますが、実際にはそうではありません。
したがって、私が見たところ、OS はページ フォールト イベント中にのみワーキング セットのスナップショットを取得しているように見えます。これらのスナップショットは、R ビットのリセットとページ フォールトの間の時間間隔で参照されるページのワーキング セットを表します。
それが実際の作業セットの適切な近似である理由は何ですか?
R ビットがリセットされる時間間隔の値によって、近似の品質 (したがって、アルゴリズムの有効性) が決まりますか?
したがって、この値は、上で述べたこれらの不運なページのほとんどをキャッチできるほど低すぎてはいけませんが、実際にはワーキング セットにまだないページをキャッチできないほど大きすぎてはいけませんか?