本文へ移動

基本情報技術者試験 · 学習ガイド

2010年度 春期 午後の問題・解答解説

旧制度の午前・午後と、2023年度以降の科目A・科目Bの公開問題を区別しています。現在の試験対策では現行シラバスと科目Bの形式を確認してください。公開問題は本試験の全出題を網羅する資料ではありません。

2010年度 春期 午後の概要
30:00

問題番号から選ぶ

キャッシュメモリの管理と置換アルゴリズム(FIFOおよびLRU)

ハードウェア · キャッシュメモリ / 置換アルゴリズム / FIFO / LRU / ライトバック

主記憶とキャッシュメモリ間のデータ転送に関する記述を読み、設問1・2に答えよ。 主記憶は1ブロック100語に分割され、先頭番地順にブロック番号が割り当てられている。データキャッシュは3つのバッファ(バッファ1〜3)から成り、それぞれ対応するディレクトリ(ブロック番号、順位、フラグ)を持つ。フラグは読み込み時に0、CPUによる書込み(STORE命令)時に1となる。 プログラム領域の命令列に従って処理を実行したときのディレクトリ部の変化について、設問1ではFIFO(最も古くから存在するブロックを追い出す方式)、設問2ではLRU(参照されていない時間が最も長いブロックを追い出す方式)に基づく各空欄の値を求めよ。

ア
設問1: 0 / 設問2: ブロック番号41, フラグ0
イ
設問1: 41 / 設問2: ブロック番号41, フラグ1
ウ
設問1: 42 / 設問2: ブロック番号42, フラグ0
エ
設問1: 43 / 設問2: ブロック番号42, フラグ1
オ
設問1: 44 / 設問2: ブロック番号43, フラグ0
カ
設問1: 45 / 設問2: ブロック番号43, フラグ1
キ
設問2: ブロック番号44, フラグ0
ク
設問2: ブロック番号44, フラグ1
ケ
設問2: ブロック番号45, フラグ0
コ
設問2: ブロック番号45, フラグ1
解答・解説を表示

解答

設問1: a=カ, b=エ, c=ウ; 設問2: d=イ, e=ク, f=ウ

解説

まず要点:キャッシュは容量が限られるので、あふれたときにどのブロックを追い出すかを決める規則が必要です。FIFO(先に入ったものから追い出す方式)は、入った順番だけで追い出しを決めます。LRU(最後に使われてから最も長くたつものを追い出す方式)は、使われた時刻を記録して決めます。書き換えたデータには変更フラグ(ダーティビット)を立て、追い出すときに主記憶へ書き戻します。

解き方

  1. プログラムの各命令が参照するメモリアドレスから、対応するブロック番号(41〜45)と操作の種類(LOADかSTOREか)を読み取る。
  2. 設問1ではFIFOの規則に従い、空きバッファへの割当てと、順位1(最も古い)ブロックの追い出しおよび順位の更新を追いかけて各バッファの中身を求める。
  3. 設問2ではLRUの規則に従い、参照のたびに順序を更新し、ミス時には最も長く参照されていないブロック(順位1)を置換対象としてフラグの変化も追跡する。

小問ごとの答え

小問 設問1 a:カ
1000番地のLOAD命令は番地4400(ブロック番号45)を参照します。初期状態ではキャッシュは空なのでミスが発生し、空きバッファの中で最も番号が小さいバッファ1にブロック45が読み込まれます。したがってaは45(カ)となります。
小問 設問1 b:エ
FIFO方式における1006番地のSTORE命令実行直後のディレクトリ1のブロック番号です。1004番地で最も古いブロック45(バッファ1)が追い出されてブロック43が読み込まれた後、1006番地ではバッファ2が追い出されるため、バッファ1のブロック43はそのまま残ります。よってbは43(エ)です。
小問 設問1 c:ウ
1006番地直後のディレクトリ3のブロック番号です。1003番地でバッファ3にブロック42が格納された後、1004番地ではバッファ1、1006番地ではバッファ2が置き換え対象となるため、バッファ3にはブロック42が残っています。よってcは42(ウ)です。
小問 設問2 d:イ
LRU方式の1回目ループで1006番地を実行した直後のディレクトリ2の状態です。1005番地でブロック41に対するSTORE命令が実行されフラグが1に変わり、最も最近参照された状態となっています。1006番地の参照(ブロック44)では最も長く参照されていないブロック42(バッファ3)が置き換えられるため、ディレクトリ2はブロック番号41、フラグ1(イ)のまま変化しません。
小問 設問2 e:ク
2回目ループの1002番地実行直後のディレクトリ3の状態です。1回目の1006番地でバッファ3にブロック44がSTORE命令により書き込まれたためフラグは1となっています。2回目の1002番地ではブロック41が参照(ヒット)されるのみでバッファ3は更新されないため、ブロック番号44、フラグ1(ク)となります。
小問 設問2 f:ウ
2回目ループの1003番地(ブロック42のLOAD)実行直後のディレクトリ1の状態です。直前の参照履歴から最も長く参照されていないのは1回目ループの1004番地以降参照のないブロック43(バッファ1)です。そのためバッファ1にブロック42がLOAD命令で読み込まれ、フラグは0に初期化されます。よってブロック番号42、フラグ0(ウ)となります。

覚えるポイント

  • STORE命令の実行時はキャッシュ内のフラグ(ダーティビット)が1になる。
  • FIFOは入った順序で追い出し、LRUは最後に使われた時刻が最も古いものを追い出す。

間違えやすいところ

  • LOAD命令でもフラグが1になると勘違いして、フラグの値を誤る。
  • LRUの追跡で、ヒットしたときに参照順位が最新に更新されるのを見落とす。

出題の前提:平成22年度春期基本情報技術者試験午後問1の出題条件および解答例

出典:IPA『2010年度 春期 午後』
公式問題冊子 p.5 ↗(www.ipa.go.jp) / 公式問題冊子 p.6 ↗(www.ipa.go.jp) / 公式問題冊子 p.7 ↗(www.ipa.go.jp) / 公式問題冊子 p.8 ↗(www.ipa.go.jp) / 公式問題冊子 p.9 ↗(www.ipa.go.jp) / 公式問題冊子 p.10 ↗(www.ipa.go.jp) / 公式問題冊子 p.11 ↗(www.ipa.go.jp)

2010年度 春期 午後

参照した公式資料

IPAが公開した2010年度 春期 午後の問題・解答資料です。