問題
問82
ファイルを4冊まで置くことができる机で、A~Fの6冊のファイルを使って仕事をする。机上に5冊目のファイルを置きたいときは、机上の4冊のファイルのうち、最後に参照してから最も時間が経過しているファイルを引き出しにしまうことにする。ファイルをA, B, C, D, E, C, B, D, F, Bの順で机上に置いて参照するとき、最後に引き出しにしまうファイルはどれか。
- A
- B
- D
- E
[出典：ITパスポート試験 平成28年度春期 問82]
正解
正解は「エ」です。
解説
この問題は、LRU（Least Recently Used）というキャッシュアルゴリズムの考え方を応用したものです。机に置けるファイル数が限られている状況で、新しいファイルを追加する際に、どのファイルを捨てるべきかを判断する問題です。ここでは「最後に参照してから最も時間が経過しているファイルを引き出しにしまう」というルールが示されています。
机の容量が4冊なので、5冊目のファイルを置く際には、机上にある4冊のうち、一番長い間参照されていない（使われていない）ファイルを選んで捨てることになります。ファイルの参照順序と机の状態を追っていきましょう。
- A, B, C, D を順に置くと、机は [A, B, C, D] となり、満杯になります。参照順序はA→B→C→Dです。
- 次に E を置こうとします。机は満杯なので、何か1冊捨てる必要があります。この時点で最も長く参照されていないファイルは A です。したがって、Aを捨ててEを置きます。机の状態は [B, C, D, E] となります。参照順序はB→C→D→Eです。
- C を参照します。Cが使われたので、Cは新しくなります。机の状態は [B, D, E, C] となります。
- B を参照します。Bが使われたので、Bは新しくなります。机の状態は [D, E, C, B] となります。
- D を参照します。Dが使われたので、Dは新しくなります。机の状態は [E, C, B, D] となります。
- 次に F を置こうとします。机は満杯です。この時点で最も長く参照されていないファイルは E です。したがって、Eを捨ててFを置きます。机の状態は [C, B, D, F] となります。参照順序はC→B→D→Fです。
- 最後に B を参照します。Bが使われたので、Bは新しくなります。机の状態は [C, D, F, B] となります。 Fを置いた際に引き出しにしまわれたファイルは E です。したがって、正解はエのEとなります。
ア(A):
Aは、ファイルをEに置き換える際に一度引き出しにしまわれています。したがって、Fを置く際にはすでに机上には存在しません。
イ(B):
BはFを追加する時点では、最後に参照されたファイルではありませんが、最も時間が経過しているファイルでもありません。DやCの方がさらに古く参照されています。
ウ(D):
DはFを追加する時点では、最後に参照されたファイルではありませんが、最も時間が経過しているファイルでもありません。Cの方がDよりも古く参照されています。
難易度
この問題は、キャッシュ管理の基本的な考え方であるLRU（Least Recently Used）アルゴリズムを理解しているかを問うものです。具体的なシミュレーションが必要になりますが、問題文のルールが明確なため、一つずつ状況を追っていけば、初心者でも正解にたどり着くことが可能です。情報処理の基礎的な知識を問う良問であり、落ち着いて手順を踏めば難易度はそれほど高くありません。
用語補足
LRU (Least Recently Used)：
LRUは「最も最近使われていないもの」という意味で、コンピュータのキャッシュメモリ管理によく使われるアルゴリズムです。例えば、お気に入りの本を4冊だけ机に置いておける場合、新しい本を読もうとして机が満杯だったら、一番長い間読んでいない本を本棚に戻す、といったイメージです。
キャッシュアルゴリズム：
キャッシュアルゴリズムとは、限られた容量のキャッシュメモリに、どのデータを残し、どのデータを捨てるかを決定するルールや方式のことです。これにより、頻繁に使われるデータはキャッシュに残りやすくなり、システムの処理速度が向上します。
キャッシュメモリ：
キャッシュメモリは、CPUなどの処理速度の速い部品と、メインメモリなどの処理速度の遅い部品の間にある、少量で高速なメモリのことです。よく使うデータを一時的にここに保存しておくことで、毎回遅いメモリからデータを読み込む手間を省き、全体の処理を速くします。
データ参照：
データ参照とは、コンピュータがメモリやストレージから特定のデータを探し出して読み込む動作を指します。今回の問題では、ファイルA, B, Cなどを机に「置く」ことが、それらのファイルが参照されたことを意味します。
対策
この問題を解くためのポイントは、LRUアルゴリズムの動作を正確にシミュレーションすることです。机の容量（4冊）と参照順序を丁寧に記録し、新しいファイルが追加されるたびに「最も長く参照されていないファイル」を正しく特定して置き換えることが重要です。途中で参照されたファイルは「最近使われた」ものとして扱われるため、その順序も更新しながら追跡することで、ミスなく正解を導き出せます。
