問82
頻出度★★☆
ファイルを4冊まで置くことができる机で，A～Fの6冊のファイルを使って仕事をする。机上に5冊目のファイルを置きたいときは，机上の4冊のファイルのうち，最後に参照してから最も時間が経過しているファイルを引き出しにしまうことにする。ファイルをA，B，C，D，E，C，B，D，F，Bの順で机上に置いて参照するとき，最後に引き出しにしまうファイルはどれか。
平成28年度 春期 ITパスポート試験 問82
テクノロジ系コンピュータ構成要素 › メモリ
This question's explanation and your answers so far.
解説
問 82
Incorrectア
A is the file put away into the drawer first, when the 5th file E is placed; it is the “first” eviction, not the “last.” The question asks for the file put away last, so this is wrong.
Incorrectイ
B is referenced multiple times — 2nd, 7th, and 10th in the sequence — so it is always kept in a “just referenced” state. It stays on the desk to the end and is never put away into the drawer, so this is wrong.
Incorrectウ
D is referenced at the 4th and 8th positions, so its recency is refreshed and it stays on the desk to the end. It is not evicted, so this is wrong.
- エ
正解 This desk works by the LRU (Least Recently Used) method: it evicts the file that has gone the longest time since it was last referenced. Trace the reference order A, B, C, D, E, C, B, D, F, B. First A, B, C, D fill the desk (4 files). When you place the 5th file E, among A, B, C, D on the desk the one referenced longest ago is A, so you put A away into the drawer (1st eviction = A). The following C, B, D are all already on the desk; referencing them only makes them newer, so no eviction occurs. Next, when you place F, the desk holds E, C, B, D, and among these the oldest last-reference is E, so you put E away (2nd eviction = E). The final B is also already on the desk, so no eviction. Only two files are put away into the drawer, A then E, and the last of these is E. Therefore エ (E) is correct.
ここがポイント
- Tracing how the LRU (Least Recently Used = replace the item unused for the longest time) method operates. When full, it evicts the element whose last reference is the oldest, while referencing an existing element treats that element as the most recent.
- The same replacement method is a representative algorithm also used in cache memory replacement control, and the question tests whether you can correctly update the recency of references.
用語