基本情報技術者 2011年 秋期 午前（科目A） 問11

キャッシュと主記憶の実効アクセス時間の順序付け【午前2 解説】

要点まとめ

• 結論→実効アクセス時間が短い順は A（主記憶15ns）→D（キャッシュ有りで実効18ns）→B（30ns）→C（48ns）で、したがって選択肢は イ が正解です。
• 根拠→キャッシュがある場合の実効アクセス時間は $EAT=T_c+(1-h)T_m$ で表され、各行の数値をこの式に代入して比較します。
• 差がつくポイント→キャッシュのアクセス時間 $T_c$ とヒット率 $h$ の組合せが重要で、ミス時にもキャッシュアクセス時間が加算される点を確実に理解してください。

正解の理由

よくある誤解

• 「ミス時は主記憶のみ見る」と考えてキャッシュアクセス時間を無視する誤り。ミスでも最初にキャッシュをチェックするためキャッシュ時間は加算されます。
• ヒット率を百分率のまま代入してしまう（例：60 をそのまま使う）。式では割合（0.6）で扱う必要があります。
• キャッシュの有無だけで比較して、キャッシュアクセス時間が大きい場合に逆に遅くなる可能性を見落とすこと。

解法ステップ

1. キャッシュ有無を確認し、キャッシュが無ければ EAT = 主記憶アクセス時間 とする。
2. キャッシュがある場合は式 $EAT=T_c+(1-h)T_m$ を使う（$h$ は 0〜1 の割合）。
3. 各行について数値を代入して EAT を求める。
4. 得られた EAT の小さい順に並べ、選択肢と照合する。

• A：キャッシュ無し → EAT = 15 ns
• B：キャッシュ無し → EAT = 30 ns
• C：$T_c=20,h=0.6,T_m=70$ → $20+(1-0.6)\times 70=20+28=48$ ns
• D：$T_c=10,h=0.9,T_m=80$ → $10+(1-0.9)\times 80=10+8=18$ ns

選択肢別の誤答解説

• ア: A, B, C, D
  誤りの理由は B(30) を A(15) の次としていますが、D(18) の方が B(30) より短いため順序が間違っています。
• イ: A, D, B, C ← 正解
  すべての実効アクセス時間を正しく計算して並べた順序です。
• ウ: C, D, A, B
  C を最短としていますが C の実効48nsは最長に近く、完全に逆の並びです。
• エ: D, C, A, B
  D を最短にしていますが A(15ns) の方が短いため誤りです。

補足コラム

• キャッシュが有効かどうかの簡単な判定条件は $T_c+(1-h)T_m<T_m$、すなわち $h>\frac{T_c}{T_m}$ です。Dなら閾値は $10/80=0.125$（12.5%）で与えられた90%は十分有効、Cは閾値 $20/70\approx 0.286$（28.6%）で与えられた60%も有効です。
• 実システムではタグチェックとデータ読出しの重なりや、複数レベルのキャッシュ、ライトポリシーによって EAT の評価が複雑になりますが、基本問題では上記の式で扱います。
• 小さな演習として、Pythonで同じ計算を自動化すると理解が深まります。

cases = {
    "A": {"cache": False, "Tm":15},
    "B": {"cache": False, "Tm":30},
    "C": {"cache": True,  "Tc":20, "h":0.6, "Tm":70},
    "D": {"cache": True,  "Tc":10, "h":0.9, "Tm":80},
}
def eat(info):
    if not info.get("cache", False):
        return info["Tm"]
    return info["Tc"] + (1-info["h"])*info["Tm"]

results = {k: eat(v) for k,v in cases.items()}
print(sorted(results.items(), key=lambda x: x[1]))
# [('A', 15.0), ('D', 18.0), ('B', 30.0), ('C', 48.0)]

FAQ