問 題
ページング方式の仮想記憶を用いるコンピュータにおいて、実記憶のページ枠数が不足した場合に追い出すページを選択するアルゴリズムとして、次の二つの方式を想定する。
FIFO：実記憶への読み込みが最も古いページを選択する。
LRU ：最後のアクセスが最も古いページを選択する。
ある特定のタスクを実行する場合、ページのアクセス順は次のとおりである。
1、2、4、3、5、2、1、4
このとき、仮想記憶の追い出すページを選択するアルゴリズムとして FIFO 方式を用いた場合、6 回のページ読み込みが発生した。同じ条件で、追い出すページを選択するアルゴリズムとして LRU 方式を用いた場合のページ読み込み回数として最も妥当なのはどれか。なお、初期状態では実記憶にはどのページも読み込まれていないものとする。
1．4 回
2．5 回
3．6 回
4．7 回
5．8 回
解 説
【実記憶領域 及び ページのイメージ】
実記憶領域はメインメモリに対応します。メインメモリは「作業机」のイメージを持つとわかりやすいです。ある特定のタスクは「宿題」のイメージです。
宿題をするために教科書を見たり、ノートを見たりしたいので、どんどん机に本棚からいろんなものを広げて置いていきます。「教科書」や「ノート」に対応するのが、タスクを実行する時にアクセスする「ページ１」、「ページ２」… です。
【ページ枠の個数について】
机がそれほど大きくないと、いくつかのものを広げた時に机がいっぱいになります。何個ものを広げることができるかが「ページ枠」です。
ページ枠いっぱいにものを広げた後で、さらにものを広げたい時に何を机からどかすかという問題があります。「FIFO：First In、 First Out」という考え方では「一番古くに机に置いたもの」をどかします。
1,2,4,3,5,2,1,4 という順番で ものを机に広げていく場合、もしも机にものを５個以上のせることができれば、1 回もものをどかす必要はありません。1 ~ 5 まで全て机におけるからです。 そこで机にものを４個までしか乗せることができないとします。以下のようなイメージです。
FIFO であれば、本問のタスクを実行する際に、以下のように机上のものが変化していきます。
「ページ読み込み回数」とは「ものを取って机に置く回数」です。上の流れで 6 回です。そのためページ枠は 4 個とわかります。
【LRU 方式の場合のページ読み込み回数】
後は同条件において LRU 方式だとどうなるかを考えると、ページ読み込み回数は FIFO の時より１回増えて７回です。「3,4,2,1」で次に 「5」を置く際に「1 をどかして 5 を置く」所は変わらないのですが、次に「1 」を置く時にどかすのが「4」になります。すると最後の 4 を読む時にもう１回机からものをどかすことになります。
以上より、正解は 4 です。
コメント