HOME»応用情報技術者試験掲示板»平成23年特別 午前問21について再投稿
投稿する

[1168] 平成23年特別 午前問21について再投稿

 ぽちさん(No.1) 
先日、”平成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回になります。
2018.06.10 20:26
 ぽちさん(No.2) 
設問と順序が前後しますが、先日は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回になります。
2018.06.10 21:08

返信投稿用フォーム

スパム防止のためにスレッド作成日から30日経過したスレッドへの書込みはできません。
© 2010-2024 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop