応用情報技術者 試験情報＆徹底解説

先日、”平成23年特別 午前問21の解説について[1163]”に返信し、
分かりづらいと思い削除したのですが、他に返信がないようですので、
再掲載いたします。[1163]には返信できなかったため、こちらに投稿します。

LRUでは
・ページイン
・読出し
・置換え（ページアウト及びページイン）
いずれかを行うと、
該当ページは最終参照時刻が更新されて、置換えの優先順が最下位になります。

アクセス順序1, 3, 2, 1, 4, 5, 2, 3, 4, 5のページ操作後の、
ページ(p1, p2, p3)のデータ及び置換えの優先順をトレースしてみます。

・初期状態：全ページ未参照
  (p1, p2, p3)＝(null, null, null)
  置換えの優先順位はp1＞p2＞p3 と考えます。

・アクセス[1]：p1に[1]をページイン
  (p1, p2, p3)＝([1], null, null)
  p1の最終参照時刻が更新され、置換えの優先順位はp2＞p3＞p1 になります。

・アクセス[3]：p2に[3]をページイン
  (p1, p2, p3)＝(1, [3], null)
  p2の最終参照時刻が更新され、置換えの優先順位はp3＞p1＞p2 になります。

・アクセス[2]：p3に[2]をページイン
  (p1, p2, p3)＝(1, 3, [2])
  p3の最終参照時刻が更新され、置換えの優先順位はp1＞p2＞p3 になります。

・アクセス[1]：p1の[1]を読出し
  (p1, p2, p3)＝([1], 3, 2)
  p1の最終参照時刻が更新され、置換えの優先順位はp2＞p3＞p1 になります。

・アクセス[4]：p2を、3→[4]に置換え
  (p1, p2, p3)＝(1, [4], 2)
  p2の最終参照時刻が更新され、置換えの優先順位はp3＞p1＞p2 になります。

・アクセス[5]：p3を、2→[5]に置換え
  (p1, p2, p3)＝(1, 4, [5])
  p3の最終参照時刻が更新され、置換えの優先順位はp1＞p2＞p3 になります。

・アクセス[2]：p1を、1→[2]に置換え
  (p1, p2, p3)＝([2], 4, 5)
  p1の最終参照時刻が更新され、置換えの優先順位はp2＞p3＞p1 になります。

・アクセス[3]：p2を、4→[3]に置換え
  (p1, p2, p3)＝(2, [3], 5)
  p2の最終参照時刻が更新され、置換えの優先順位はp3＞p1＞p2 になります。

・アクセス[4]：p3を、5→[4]に置換え
  (p1, p2, p3)＝(2, 3, [4])
  p3の最終参照時刻が更新され、置換えの優先順位はp1＞p2＞p3 になります。
  
・アクセス[5]：p1を、2→[5]に置換え
  (p1, p2, p3)＝([5], 3, 4)
  p1の最終参照時刻が更新され、置換えの優先順位はp2＞p3＞p1 になります。

以上、本問のLRUでの置換え回数は6回になります。

設問と順序が前後しますが、先日はLRUについてのみ返信し、
FIFOには触れていませんでしたので、FIFOでのトレースも投稿致します。

FIFOでは
・ページイン
・置換え（ページアウト及びページイン）
のいずれかを行うと、
該当ページはページイン時刻が更新されて、置換えの優先順が最下位になります。
FIFOでは読出しのみの場合、置換えの優先順は変わりません。

アクセス順序1, 3, 2, 1, 4, 5, 2, 3, 4, 5のページ操作後の、
ページ(p1, p2, p3)のデータ及び置換えの優先順をトレースしてみます。

・初期状態：全ページ未参照
  (p1, p2, p3)＝(null, null, null)
  置換えの優先順位はp1＞p2＞p3 と考えます。

・アクセス[1]：p1に[1]をページイン
  (p1, p2, p3)＝([1], null, null)
  p1のページイン時刻が更新され、置換えの優先順位はp2＞p3＞p1 になります。

・アクセス[3]：p2に[3]をページイン
  (p1, p2, p3)＝(1, [3], null)
  p2のページイン時刻が更新され、置換えの優先順位はp3＞p1＞p2 になります。

・アクセス[2]：p3に[2]をページイン
  (p1, p2, p3)＝(1, 3, [2])
  p3のページイン時刻が更新され、置換えの優先順位はp1＞p2＞p3 になります。

・アクセス[1]：p1の[1]を読出し
  (p1, p2, p3)＝(1, 3, 2)
  p1のページイン時刻は変わらず、置換えの優先順位はp1＞p2＞p3 のままです。
  
・アクセス[4]：p1を、1→[4]に置換え
  (p1, p2, p3)＝([4], 3, 2)
  p1のページイン時刻が更新され、置換えの優先順位はp2＞p3＞p1 になります。

・アクセス[5]：p2を、3→[5]に置換え
  (p1, p2, p3)＝(4, [5], 2)
  p2のページイン時刻が更新され、置換えの優先順位はp3＞p1＞p2 になります。

・アクセス[2]：p3の[2]を読出し
  (p1, p2, p3)＝(4, 5, 2)
  p3のページイン時刻は変わらず、置換えの優先順位はp3＞p1＞p2 のままです。

・アクセス[3]：p3を、2→[3]に置換え
  (p1, p2, p3)＝(4, 5, [3])
  p3のページイン時刻が更新され、置換えの優先順位はp1＞p2＞p3 になります。

・アクセス[4]：p1の[4]を読出し
  (p1, p2, p3)＝(4, 5, 3)
  p1のページイン時刻は変わらず、置換えの優先順位はp1＞p2＞p3 のままです。
  
・アクセス[5]：p2の[5]を読出し
  (p1, p2, p3)＝(4, 5, 3)
  p2のページイン時刻は変わらず、置換えの優先順位はp1＞p2＞p3 のままです。

以上、本問のFIFOでの置換え回数は3回になります。