問85
頻出度★☆☆
ファイルを4冊だけ置くことができる机で，A～Fの6冊のファイルを使って仕事をする。机上に5冊目のファイルを置きたいとき，机上の4冊のファイルのうち，最後に参照してから最も時間が経過しているファイルを引き出しにしまうことにする。 ファイルがA，B，C，D，B，A，E，A，B，Fの順で必要になった場合，最後に引き出しにしまうファイルはどれか。
平成21年度 春期 ITパスポート試験 問85
テクノロジ系ソフトウェア › オペレーティングシステム
This question's explanation and your answers so far.
解説
問 85
Incorrectア
A is referenced again at the 6th and the 8th steps, so at both points where an eviction is decided (the 7th and the 10th) its last reference is recent and it is not pushed out. Throughout this reference sequence, A is a file that is never put into the drawer.
Incorrectイ
B is referenced again at the 5th and the 9th steps, so at the 7th step it is newer than C and D, and at the 10th step it is the most recently referenced file. Throughout this reference sequence, B is never put into the drawer.
- ウ
正解 The rule for this desk is “at most 4 files may be placed on it, and when you want to place a 5th one, you put away into the drawer the file that has gone the longest since it was last referenced (that is, the one unused for the longest time),” which is exactly the LRU (Least Recently Used) method itself. Tracing the reference sequence A, B, C, D, B, A, E, A, B, F in order gives the following. 1st A / 2nd B / 3rd C / 4th D — at this point the desk is full with the 4 files A, B, C, D. 5th, B: it is already on the desk, so nothing needs to be put away; only the reference time of B becomes the newest. 6th, A: likewise it is on the desk, so no file is put away, and the reference time of A becomes the newest. 7th, E: it is not on the desk. At this point the last reference times are the 3rd for C, the 4th for D, the 5th for B and the 6th for A, so the oldest is C → put C away. The desk holds A, B, D, E. 8th, A: it is on the desk, so no file is put away, and the reference time of A becomes the newest. 9th, B: it is on the desk, so no file is put away, and the reference time of B becomes the newest. 10th, F: it is not on the desk. At this point the last reference times are the 4th for D, the 7th for E, the 8th for A and the 9th for B, so the oldest is D → put D away. The desk holds A, B, E, F. Therefore the order in which files were put into the drawer is C→D, the last file put away is D, and the correct answer is ウ.
Incorrectエ
E is placed on the desk at the 7th step in place of C, and at the 10th step its last reference (the 7th) is newer than that of D (the 4th), so it is not pushed out. Throughout this reference sequence, E is a file that is never put into the drawer.
ここがポイント
- “Evict the one that has gone the longest since it was last referenced” = the LRU (Least Recently Used) method. It is a representative algorithm used for page replacement in virtual memory and for cache replacement; do not confuse it with FIFO, which evicts in the order items were put in.
- The trick to tracing LRU is to update that file's last-reference time to the newest value every time it is referenced. Referencing something already on the desk (in memory) causes no eviction, but the other files become relatively older as a result, which changes which one is evicted next.
用語