ページ置換：FIFO・LRU・最適置換

循環参照、OPTを押して、7回のフォールトがどのステップで起きるか確かめてください。次に、100ページを占める配列を1,000回繰り返し走査して合計を求めるプログラムを考えます。フレームは99個です。LRUとOPTでは、それぞれ何回フォールトするでしょう。フレームを100個にすると、何回になるでしょうか。

この問題をツールで開く

1. 画面の例では、最初の5回の参照でフォールトが起きます。4回で空のフレームが埋まり、5回目でページ置換が必要になります。その後のフォールトはステップ9と13。4回の参照ごとに起きるので、合計は5 + 2 = 7回です。

   $$5+2=7\text{faults: steps }1\text{–}5,9,13$$

2. n個のページを循環参照し、フレームがn − 1個あるとき、メモリにないページは常にひとつです。フォールトが起きた時点で、次の参照が最も遠いのは直前に参照したページ。再び参照されるのはn − 1回後です。ただし、最後の周回では、もう参照されないページをOPTが選ぶこともあります。このページを取り除いても、次のn − 2回で参照するページはすべてメモリに残っています。したがって、次のフォールトはn − 1回後に起きます。

   $$n-1\text{frames}:\text{one fault every}n-1\text{references}$$

3. 99フレームのLRUでページpのフォールトが起きたとき、メモリにはそれ以外のすべてのページがあります。最後に使ってから最も時間がたったのはp + 1、つまり次に参照するページです。よって100 × 1,000 = 100,000回の参照すべてでフォールトが起きます。画面の例で15回すべてがフォールトしたのと同じです。FIFOも同じページを取り除きます。

   $$\text{LRU}:100\times 1000=100000$$

4. OPTでは、最初の99回の参照でフレームが埋まります。100回目からは99回の参照ごとにフォールトが起き、参照回数でいうと100、199、298、…回目です。この部分のフォールト数は1 + ⌊(100,000 − 100) / 99⌋ = 1 + 1,009 = 1,010回。合計は99 + 1,010 = 1,109回です。一般式n + ⌊n(r − 1)/(n − 1)⌋に、n = 100、r = 1,000を代入した値になります。

   $$\text{OPT}:99+(1+\lfloor \frac{100000-100}{99}\rfloor )=99+1010=1109=n+\lfloor \frac{n(r-1)}{n-1}\rfloor$$

5. フレームを100個にすると、配列全体がメモリに収まります。どの方式でもフォールトは100回。各ページの初回参照でだけ起き、最初の周回が終われば、それ以降は起きません。

   $$F=100:100\text{faults}$$