問82
頻出度★★☆
ファイルを4冊まで置くことができる机で，A～Fの6冊のファイルを使って仕事をする。机上に5冊目のファイルを置きたいときは，机上の4冊のファイルのうち，最後に参照してから最も時間が経過しているファイルを引き出しにしまうことにする。ファイルをA，B，C，D，E，C，B，D，F，Bの順で机上に置いて参照するとき，最後に引き出しにしまうファイルはどれか。
平成28年度 春期 ITパスポート試験 問82
テクノロジ系コンピュータ構成要素 › メモリ
この問題の解説と、これまでの解答の記録です。
解説
問 82
不正解ア
A は5冊目の E を置くときに最初に引き出しへしまわれるファイルであり、「最後」ではなく「最初」の追い出し。設問は最後にしまうファイルを問うているので誤り。
不正解イ
B は順序中で2番目・7番目・10番目と何度も参照され、常に「新しく参照された」状態に保たれる。最後まで机上に残り、一度も引き出しにしまわれないので誤り。
不正解ウ
D は4番目と8番目に参照されて新しさが更新され、最後まで机上に残る。追い出されないので誤り。
- エ
正解 この机は「最後に参照してから最も時間が経過したファイルを追い出す」＝LRU（Least Recently Used）方式で動く。参照順 A，B，C，D，E，C，B，D，F，B を追跡する。まず A，B，C，D で机は満杯（4冊）。5冊目 E を置くとき、机上 A・B・C・D のうち最も長く参照されていない A を引き出しへしまう（1回目の追い出し＝A）。続く C，B，D はいずれも既に机上にあり、参照によって新しくなるだけで追い出しは起きない。次に F を置くとき、机上は E・C・B・D で、この中で最後の参照が最も古いのは E なので E をしまう（2回目の追い出し＝E）。最後の B も既に机上なので追い出しなし。引き出しにしまったのは A→E の2回だけで、その「最後」は E。よって「エ（E）」が正しい。
ここがポイント
- LRU（Least Recently Used＝最も長く使われていないものを置き換える）方式の動作追跡。満杯時に「最後の参照が最も古い」要素を追い出し、既存要素の参照はその要素を最新扱いにする。
- 同じ置き換え方式は キャッシュメモリ の入れ替え制御でも用いられる代表的アルゴリズムで、参照の新旧を正しく更新できるかが問われる。
用語