LRU（Least Recently Used）方式のページ置き換えアルゴリズムは、基本情報技術者試験に出題されます。仮想記憶のページ置き換えアルゴリズムのひとつ。
実際にどうやって処理が進むのかを自分で手を動かして整理してみることが解く鍵。
LRUとは？
LRUはLeast Recently Usedの略。
- Least → 最も少ない
- Recently → 最近
- Used → 使われた
直訳すると、「最近使われた中で、最も少ないもの」となる。問題にLRU方式と指示がある場合、最近、一番使用されていないデータを置き換える ルールということ。
たとえば、3冊しか入らない本棚がある。新しく買った本を入れるときには、その時に一番読まれていない本を取り出す、というイメージ。さらに、一番古い本を改めて読むことで、その本は一番新しい本という扱いになる。
理解するには、「使った順」をしっかり追いかけるのがコツです。
例題
- 主記憶枠：3つ
- アクセス順番：A → B → C → D → B → E
LRUルールに従って、E アクセス時にどのページが追い出されるか？
手順まとめ
| アクセス順 | メモリの中身（古い順 → 新しい順） | コメント |
|---|---|---|
| A | A | フォールト（枠が空いている状態）、新規追加 |
| B | A, B | フォールト、新規追加 |
| C | A, B, C | フォールト、新規追加（3枠いっぱいになる） |
| D | B, C, D | A が LRU（追い出される） → 置き換え |
| B | C, D, B | B は存在している → 最新に更新 |
| E | D, B, E | C が LRU（追い出される） → 置き換え（ここ！） |
✅ 結果と学び
回答：ページ C が追い出される
手書きでもいいので、上記の表を書くと簡単ですね。
コメント