問85
頻出度★☆☆
ファイルを4冊だけ置くことができる机で，A～Fの6冊のファイルを使って仕事をする。机上に5冊目のファイルを置きたいとき，机上の4冊のファイルのうち，最後に参照してから最も時間が経過しているファイルを引き出しにしまうことにする。 ファイルがA，B，C，D，B，A，E，A，B，Fの順で必要になった場合，最後に引き出しにしまうファイルはどれか。
平成21年度 春期 ITパスポート試験 問85
テクノロジ系ソフトウェア › オペレーティングシステム
这道题的解析和你的作答记录。
解説
問 85
错误ア
A 在第 6 次和第 8 次又被参照，因此在进行收起判定的第 7 次和第 10 次这两个时点，它的最后参照时刻都比较新，不会被赶出去。在这个参照序列中，A 是一次也没有被收进抽屉的文件。
错误イ
B 在第 5 次和第 9 次又被参照，因此在第 7 次时点比 C、D 更新，在第 10 次时点则是最近被参照的文件。在这个参照序列中，B 一次也没有被收进抽屉。
- ウ
正解 这张桌子的规则是“最多只能放 4 本，想放第 5 本时，就把自最后一次参照以来经过时间最长（即最久没有使用）的文件收进抽屉”，这正是 LRU（Least Recently Used，最近最少使用）方式本身。按 A、B、C、D、B、A、E、A、B、F 的顺序依次追踪如下。 第 1 次 A / 第 2 次 B / 第 3 次 C / 第 4 次 D —— 此时桌上是 A、B、C、D 共 4 本，已经放满。 第 5 次 B：已经在桌上，因此无需收起，只是 B 的参照时刻更新为最新。 第 6 次 A：同样在桌上，因此不发生收起，A 的参照时刻更新为最新。 第 7 次 E：桌上没有。此时各文件的最后参照时刻是 C 为第 3 次、D 为第 4 次、B 为第 5 次、A 为第 6 次，最早的是 C → 把 C 收起。桌上为 A、B、D、E。 第 8 次 A：在桌上，不发生收起，A 的参照时刻更新为最新。 第 9 次 B：在桌上，不发生收起，B 的参照时刻更新为最新。 第 10 次 F：桌上没有。此时各文件的最后参照时刻是 D 为第 4 次、E 为第 7 次、A 为第 8 次、B 为第 9 次，最早的是 D → 把 D 收起。桌上为 A、B、E、F。 因此收进抽屉的顺序是 C→D，最后收进抽屉的文件是 D，正确答案为 ウ。
错误エ
E 是在第 7 次替换 C 而放到桌上的文件，到第 10 次时点它的最后参照是第 7 次，比 D（最后参照是第 4 次）更新，不会被赶出去。在这个参照序列中，E 是一次也没有被收进抽屉的文件。
ここがポイント
- “把自最后一次参照以来经过时间最长的赶出去”= LRU（Least Recently Used，最近最少使用）方式。它是虚拟存储的页面置换和缓存替换中使用的代表性算法，注意不要与按放入顺序赶出的 FIFO 混淆。
- 追踪 LRU 的诀窍是：每次参照都要把该文件的最后参照时刻更新为最新。参照已经在桌上（内存中）的文件时不会发生收起，但其他文件会因此相对变旧，下一个被赶出去的对象也会随之改变。
用語