FIFOとLRUでページ置換回数が変わる理由
基本情報技術者試験 平成29年度春期 午前 問19 ／ ソフトウェア › オペレーティングシステム
過去問にチャレンジ
仮想記憶方式のコンピュータにおいて，実記憶に割り当てられるページ数は3とし，追い出すページを選ぶアルゴリズムは，FIFOとLRUの二つを考える。あるタスクのページのアクセス順序が 1，3，2，1，4，5，2，3，4，5 のとき，ページを置き換える回数の組合せとして，適切なものはどれか。
- ア
FIFO：3，LRU：2
- イ
FIFO：3，LRU：6
- ウ
FIFO：4，LRU：3
- エ
FIFO：5，LRU：4
会話形式の解説
講師まず、空き枠への読込みと、枠が埋まった後の置換えを分けて数えましょう。
受験者最初の1、3、2は枠に入れるだけなので、置換えはまだ0回ですね。
講師その通りです。FIFOは先に読み込んだページから追い出します。4番目の1は枠にあるので、読込み順は変わりません。
受験者すると、次の4で1を、5で3を追い出しますね。
講師はい。その後の2は枠にあるので置換えません。次の3で2を追い出し、最後の4と5も枠にあります。FIFOは計3回です。
受験者LRUでは、4番目の1を参照したことが追い出す順番に影響しますか。
講師影響します。LRUは最後に使ってから最も時間がたったページを追い出します。1を参照した直後は、古い順に3、2、1です。
受験者だから次の4では、最も古い3を追い出すのですね。
講師はい。続く5では2を、次の2では1を追い出します。この時点でLRUは3回です。
受験者後半の3、4、5も、そのたびに枠にないページになりますね。
講師その通りです。順に4、5、2を追い出すので、さらに3回、計6回になります。
受験者FIFOが3回、LRUが6回の組合せを選びます。FIFOが3回でもLRUが2回の組合せは違いますね。
講師はい。FIFOが4回や5回の組合せも、後半の2、4、5への参照がヒットすることと合いません。LRUが3回や4回の組合せも、後半の置換えを数え切れていません。枠の中身と古い順を一つずつ書くと確実です。
まとめ
最初の1、3、2は空き枠に読み込むだけなので、置換えには数えません。FIFOでは読込み順を保ち、4、5、3への参照で計3回置き換えます。LRUでは参照のたびに最終使用順を更新し、4、5、2、3、4、5への参照で計6回置き換えます。したがって、正解はイです。
解答・解説
正解はイです
この問題のテーマ
実記憶のページ枠が3つのとき、同じアクセス順序をFIFOとLRUで処理すると、ページの置換えが何回起きるかを数える問題です。
解き方の考え方
最初の1、3、2の参照では空き枠に読み込むだけなので、置換えには数えません。4番目以降の参照について、そのページが実記憶にあればヒット、なければ1ページを追い出して置換え1回と数えます。FIFOは読み込まれた順だけで追い出すページを決めるので、ヒットしても順序は変わりません。LRUは参照のたびに最終使用順を更新し、最後に使ってから最も時間がたったページを追い出します。
FIFOでは、4番目の1はヒットです。4で1を、5で3を追い出します。次の2はヒットで、3で2を追い出し、その後の4と5はヒットです。置換えは3回になります。
LRUでは、4番目の1がヒットになり、古い順は3、2、1に変わります。4で3を、5で2を、2で1を、3で4を、4で5を、5で2を追い出します。置換えは6回です。
したがって、FIFOが3回、LRUが6回の組合せになります。
選択肢ごとの解説
- ×ア FIFO：3，LRU：2「FIFO：3，LRU：2」の組合せは、FIFOの3回は手順の結果と合っています。しかしLRUでは、4番目の1の後は参照のたびに枠にないページを読み込むことになり、置換えは6回です。2回とはならないので不適切です。
- ○イ FIFO：3，LRU：6「FIFO：3，LRU：6」の組合せは、FIFOでは4、5、3の参照で置換えが起き、LRUでは4、5、2、3、4、5の参照で置換えが起きるという結果と一致します。したがって、これが正解です。
- ×ウ FIFO：4，LRU：3「FIFO：4，LRU：3」の組合せは、手順の結果と合いません。FIFOでは2、4、5の参照がヒットになるため置換えは3回で、4回にはなりません。LRUも3回ではなく6回です。
- ×エ FIFO：5，LRU：4「FIFO：5，LRU：4」の組合せも、どちらの値も手順の結果と合いません。実際はFIFOが3回、LRUが6回です。
補足
LRUのほうが一般に効率がよいと言われますが、この問題のアクセス順序では、LRUの置換え回数がFIFOより多くなります。どちらのアルゴリズムが有利かは、アクセスの並び方によって変わります。
POINT
- 枠が空いている間の読込みは、置換えの回数に数えません。
- FIFOは読み込まれた順で追い出すページを決め、参照されても順序は変わりません。
- LRUは参照のたびに最終使用順を更新し、最後の使用から最も時間がたったページを追い出します。
- 枠の中身と古い順を1参照ずつ表に書き出すと、数え間違いを防げます。