LRUのページ置換

LRU 方式で主記憶（3ページ分）の中身を1回ずつ追い，ヒット（H）とミス（M）の回数を数える問題です。

主記憶にあれば H 秒で読めます（ヒット）。なければ外部記憶から M 秒かけて読み，主記憶に入れます（ミス）。

主記憶がいっぱいの時は，いちばん長く使われていないページを追い出します。中身は「古い→新しい」の順に書きます。

• 2：ミス。［2］
• 1：ミス。［2，1］
• 1：ヒット。［2，1］
• 2：ヒット。2 が最新になり［1，2］
• 3：ミス。空きがあるので［1，2，3］
• 4：ミス。いっぱいなので最も古い 1 を追い出し［2，3，4］
• 1：ミス。最も古い 2 を追い出し［3，4，1］
• 3：ヒット。［4，1，3］
• 4：ヒット。［1，3，4］
• ミスは 5 回，ヒットは 4 回なので，総アクセス時間は 5M＋4H。答えは ③（5M＋4H）

④（4M＋5H）：7番目の 1 をヒットと数えた値です。1 は 6番目で追い出されているのでミスです。

• LRU：最も長く使われていないページを追い出す方式
• ヒットしたページも「最新」に並べ直す。これを忘れると追い出す順を間違える
• 参照のたびに主記憶の中身を書き出すと数えまちがえない