基本情報技術者 2015年 秋期 午後 問11
次のJavaプログラムの説明及びプログラムを読んで、設問に答えよ。
〔プログラムの説明〕
固定バイト長のブロック（以下、ブロックという）を単位としてデータを保管している装置（以下、ブロックデバイスという）に対し、ブロックのデータ（以下、ブロックデータという）へのアクセスを管理するプログラムである。図1に、プログラム構成の概要を示す。図中の四角はプログラムの構成要素を、矢印はブロックデータの流れを示す。ここで、このプログラムでは、ブロックデバイスからの読込みだけを考える。
ブロックデバイス内の各ブロックは、インデックス値で指定する。最初のブロックのインデックス値は、0である。
ブロックアクセッサは、アプリケーションから要求されたブロックデータをブロックデバイスから取得して、アプリケーションに渡す役割をする。ブロックアクセッサはキャッシュを使用し、ブロックデバイスから取得したブロックデータをキャッシュする。アプリケーションから要求されたブロックデータがキャッシュされていれば、キャッシュから取得したブロックデータをアプリケーションに渡す。
キャッシュは、FIFO (First In, First Out)とLRU (Least Recently Used)の2種類の管理方針に基づく実装が用意されていて、アプリケーションはどの実装を使用するかを指定する。
(1) クラスBlockAccessorは、ブロックアクセッサを表す。
① コンストラクタは、ブロックデバイスをオープンし、引数で指定されたキャッシュの管理方針に基づくキャッシュを生成する。
② メソッドreadBlockは、引数で指定されたインデックス値のブロックデータを返す。ブロックデータがキャッシュにあれば、それを返す。なければ、ブロックデバイスから取得し、キャッシュした後、そのブロックデータを返す。
(2) クラスBlockDeviceは、読取り専用のブロックデバイスを表す。実装は、バイト配列の配列であるフィールドblocksを使用し、ブロックデバイスを仮想的に表す。ただし、ブロックデータの値は全て0である。
① 静的メソッドopenは、ブロックデバイスのインスタンスを返す。
② メソッドgetBlockSizeは、ブロックのサイズをバイト数で返す。
③ メソッドreadBlockは、引数で指定されたインデックス値のブロックデータを引数で指定されたバッファに読み込む。
(3) 抽象クラスCacheは、ブロックアクセッサからキャッシュ機能を使用するためのクラスを表す。
① キャッシュの管理方針（FIFO及びLRU）を表す入れ子列挙Cache.Policyを定義する。
② 静的メソッドcreateCacheは、引数で指定されたキャッシュの管理方針と一致する実装クラスのインスタンスを生成して返す。
③ 抽象メソッドgetCachedBlockDataは、引数で指定されたインデックス値のブロックデータがキャッシュされていれば、それを返す。キャッシュされていなければ、nullを返す。
④ 抽象メソッドcacheBlockDataは、引数で指定されたインデックス値及びその値に対応するブロックデータをキャッシュする。キャッシュできるブロックデータ数が上限に達している場合は、管理方針に従ってキャッシュされているブロックデータを削除してから、指定されたブロックデータをキャッシュする。
(4) 抽象クラスListBasedCacheは、リスト構造を使用して抽象クラスCacheの一部を実装する。キャッシュできるブロックデータ数の上限値は、フィールドCACHE_SIZEで表す。
① メソッドgetCachedBlockData及びcacheBlockDataは、抽象クラスCacheで定義されている同名のメソッドを実装する。
② 抽象メソッドhitは、要求されたブロックデータがキャッシュ中に見つかったときに呼び出される。引数は、見つかったブロックデータとそのインデックス値の対（以下、キャッシュエントリという）である。
(5) 入れ子クラスListBasedCache.Entryは、キャッシュに格納するキャッシュエントリを表す。
① コンストラクタは、引数で指定されたインデックス値及びブロックデータをもつキャッシュエントリを生成する。
② メソッドgetIndex及びgetBlockDataは、それぞれインデックス値及びブロックデータを返す。
(6) 入れ子クラスListBasedCache.Fifoは、キャッシュエントリの管理をFIFOで行う。
① メソッドhitは、無操作である。
(7) 入れ子クラスListBasedCache.Lruは、キャッシュエントリの管理をLRUで行う。
① メソッドhitは、指定されたキャッシュエントリをリストの先頭に移動する。
なお、上記コンストラクタやメソッドを呼び出すときの引数に誤りはないものとする。
設問1：
問題文を見る プログラム中のに入れる正しい答えを、解答群の中から選べ。
aに関する解答群
ア：blocks
イ：blocks[]
ウ：blocks[0]
エ：blocks[][]
オ：blocks[0][]
カ：blocks[][0]
bに関する解答群
ア：Cache
イ：Cache<? extends Policy>
ウ：enum
エ：Policy
オ：Policy<? extends Cache>
カ：void
cに関する解答群
ア：!=
イ：<
ウ：<=
エ：==
オ：>
カ：>=
dに関する解答群
ア：!entries.isEmpty()
イ：entries.isEmpty()
ウ：entries.size() != CACHE_SIZE
エ：entries.size() != index
オ：entries.size() == CACHE_SIZE
カ：entries.size() == index
eに関する解答群
ア：CACHE_SIZE
イ：CACHE_SIZE - 1
ウ：CACHE_SIZE + 1
エ：index
オ：index - 1
カ：index + 1
fに関する解答群
ア：ArrayList
イ：ArrayList<Cache>
ウ：Cache
エ：List
オ：List<Cache>
カ：ListBasedCache
gに関する解答群
ア：0
イ：CACHE_SIZE - 1
ウ：entry
エ：entry.getIndex()
オ：entry.getIndex() - 1
カ：entry.getIndex() + 1
模範解答
a：ウ、b：ア、c：エ、d：オ、e：イ、f：カ、g：ウ
解説
解答の導き方
この問題では、ブロックデータを保存するキャッシュの処理を完成させます。キャッシュとは、一度読み込んだデータを一時的に保存し、次に必要になったときにすぐ取り出せるようにする場所です。
まず、プログラム全体では、要求されたブロックデータがキャッシュにあればそこから返し、なければブロックデバイスから読み込んでキャッシュに保存します。空欄は、それぞれこの流れやキャッシュの管理方法に合うように考えます。
a：ブロック1個分のサイズを求める
プログラム2では、blocksはバイト配列を並べた配列です。配列は、同じ種類の値を順番に並べて管理する入れ物です。宣言されているblocksの形は、ブロックが100個あり、それぞれが512バイトの配列です。
blocks[0]は、先頭のブロックのデータを表すバイト配列です。その配列のlengthを調べれば、ブロック1個分のバイト数が分かります。blocks全体のlengthではブロックの個数になってしまうため、aにはblocks[0]が入ります。
b：生成するキャッシュの戻り値の型を決める
プログラム3のcreateCacheは、管理方針がFIFOならFifoを、LRUならLruを生成して返します。FIFO（First In, First Out）は先に入れたものを先に削除する方法、LRU（Least Recently Used）は最も長く使われていないものを先に削除する方法です。
FifoとLruは、どちらもListBasedCacheを継承し、ListBasedCacheはCacheを継承する関係です。継承とは、あるクラスの機能を引き継いで別のクラスを作ることです。そのため、どちらのインスタンスも共通の親クラスであるCacheとして扱えます。createCacheの戻り値の型はCacheです。
c：要求されたブロックがキャッシュにあるか判定する
getCachedBlockDataは、リスト内のキャッシュエントリを順に調べます。キャッシュエントリは、ブロックのインデックス値とブロックデータを組にしたものです。
見つかったエントリのインデックス値が、要求されたindexと等しい場合に、そのブロックデータを返します。したがって、比較には等しいことを表す演算子を使います。等しくない場合に一致と判定すると、別のブロックのデータを返してしまいます。
d・e：キャッシュが満杯のとき、古いデータを削除する
キャッシュの上限はCACHE_SIZEで、値は20です。リストの要素数が上限と等しいときに、追加前の削除が必要です。したがって、dはentries.size() == CACHE_SIZEです。
一方、新しいエントリはentries.add(0, ...)によってリストの先頭に追加されます。FIFOでは、後から入ったものほど先頭にあり、最も古いものは末尾にあります。要素数が20のとき、末尾の位置はCACHE_SIZE - 1です。この位置の要素を削除するため、eにはCACHE_SIZE - 1が入ります。
f：FIFOとLRUの共通部分を継承する
ListBasedCacheは、リストを使った共通のキャッシュ処理をまとめた抽象クラスです。抽象クラスは、共通の処理をまとめ、具体的な種類のクラスに引き継がせるための土台です。
FifoとLruは、どちらもこの共通処理を使いながら、それぞれの管理方針に合わせたhitを実装します。したがって、両方のクラスが継承するのはListBasedCacheです。
g：LRUで、使われたエントリを先頭へ移す
LRUでは、要求されたデータが見つかったとき、そのエントリをリストの先頭へ移します。先頭に追加する前に、まずリストから見つかったエントリそのものを削除します。
そのため、entries.removeには、見つかったエントリを表す変数entryを渡します。entry.getIndex()はブロックのインデックス値であり、リスト内の位置を表す値ではありません。ここではリストの位置ではなく、該当するエントリを指定する必要があります。
誤りやすいポイント
-
aでblocks.lengthを選ぶ
blocks.lengthはブロックの個数です。ブロック1個分のサイズを求めるには、1個のブロックを表すblocks[0]のlengthを使います。 -
cで「等しくない」を選ぶ
キャッシュから返すのは、要求されたブロックとインデックス値が一致するデータです。 -
FIFOで先頭の要素を削除する
新しいエントリは先頭に追加されるため、最も古いエントリは末尾にあります。上限に達したときは末尾を削除します。 -
eでブロックのインデックス値を使う
eで指定するのは、ブロックの番号ではなくリスト内の位置です。CACHE_SIZE個の要素がある場合、末尾の位置はCACHE_SIZE - 1です。 -
gでentry.getIndex()を使う
ブロックのインデックス値と、リスト内での位置は別のものです。LRUでは、見つかったentryそのものをリストから削除します。
FAQ
Q: FIFOとLRUは、キャッシュにデータが見つかったときの動きがどう違いますか？
A: FIFOでは、見つかっても並び順を変えません。LRUでは、使われたデータを先頭へ移します。そのため、LRUでは末尾に最も長く使われていないデータが来るように管理できます。
A: FIFOでは、見つかっても並び順を変えません。LRUでは、使われたデータを先頭へ移します。そのため、LRUでは末尾に最も長く使われていないデータが来るように管理できます。
Q: createCacheの戻り値に、FifoやLruではなくCacheを使うのはなぜですか？
A: FifoとLruは、どちらもCacheを継承したクラスだからです。共通の型であるCacheを戻り値にすれば、管理方針がどちらでも同じ型として扱えます。
A: FifoとLruは、どちらもCacheを継承したクラスだからです。共通の型であるCacheを戻り値にすれば、管理方針がどちらでも同じ型として扱えます。
Q: キャッシュが満杯でなければ、既存のデータを削除しないのはなぜですか？
A: 上限に達するまでは追加できる空きがあるためです。上限に達した場合だけ、管理方針に従って古いデータを削除します。
A: 上限に達するまでは追加できる空きがあるためです。上限に達した場合だけ、管理方針に従って古いデータを削除します。
関連キーワード: キャッシュ、FIFO、LRU、配列、リスト構造、継承
