平成27年秋期試験午後問題 問11

午前試験免除制度対応!基本情報技術者試験のeラーニング【独習ゼミ】

問11 ソフトウェア開発(Java)

次のJavaプログラムの説明及びプログラムを読んで,設問に答えよ。
(Javaプログラムで使用するAPIの説明は,こちらを参照してください。)

〔プログラムの説明〕
 固定バイト長のブロック(以下,ブロックという)を単位としてデータを保管している装置(以下,ブロックデバイスという)に対し,ブロックのデータ(以下,ブロックデータという)へのアクセスを管理するプログラムである。図1に,プログラム構成の概要を示す。図中の四角はプログラムの構成要素を,矢印はブロックデータの流れを示す。ここで,このプログラムでは,ブロックデバイスからの読込みだけを考える。
pm11_1.png
 ブロックデバイス内の各ブロックは,インデックス値で指定する。最初のブロックのインデックス値は,0である。
 ブロックアクセッサは,アプリケーションから要求されたブロックデータを ブロックデバイスから取得して,アプリケーションに渡す役割をする。ブロックアクセッサはキャッシュを使用し,ブロックデバイスから取得したブロックデータをキャッシュする。アプリケーションから要求されたブロックデータがキャッシュされていれば,キャッシュから取得したブロックデータをアプリケーションに渡す。
 キャッシュは,FIFO(First In,First Out)とLRU(Least Recently Used)の2種類の管理方針に基づく実装が用意されていて,アプリケーションはどの実装を使用するかを指定する。
  • クラス BlockAccessor は,ブロックアクセッサを表す。
    1. コンストラクタは,ブロックデバイスをオープンし,引数で指定されたキャッシュの管理方針に基づくキャッシュを生成する。
    2. メソッド readBlock は,引数で指定されたインデックス値のブロックデータを返す。ブロックデータがキャッシュにあれば,それを返す。なければ,ブロックデバイスから取得し,キャッシュした後,そのブロックデータを返す。
  • クラス BlockDevice は,読取り専用のブロックデバイスを表す。実装は,バイト配列の配列であるフィールド blocks を使用し,ブロックデバイスを 仮想的に表す。ただし,ブロックデータの値は全て0である。
    1. 静的メソッド open は,ブロックデバイスのインスタンスを返す。
    2. メソッド getBlockSize は,ブロックのサイズをバイト数で返す。
    3. メソッド readBlock は,引数で指定されたインデックス値のブロックデータを引数で指定されたバッファに読み込む。
  • 抽象クラスCache は,ブロックアクセッサからキャッシュ機能を使用するためのクラスを表す。
    1. キャッシュの管理方針(FIFO及びLRU)を表す入れ子列挙 Cache.Policy を定義する。
    2. 静的メソッド createCache は,引数で指定されたキャッシュの管理方針と一致する実装クラスのインスタンスを生成して返す。
    3. 抽象メソッド getCachedBlockData は,引数で指定されたインデックス値のブロックデータがキャッシュされていれば,それを返す。キャッシュされていなければ,null を返す。
    4. 抽象メソッド cacheBlockData は,引数で指定されたインデックス値及びその値に対応するブロックデータをキャッシュする。キャッシュできるブロックデータ数が上限に達している場合は,管理方針に従ってキャッシュされているブロックデータを削除してから,指定されたブロックデータをキャッシュする。
  • 抽象クラス ListBasedCache は,リスト構造を使用して抽象クラス Cache の一部を実装する。キャッシュできるブロックデータ数の上限値は,フィールド CACHE_SIZE で表す。
    1. メソッド getCachedBlockData 及び cacheBlockData は,抽象クラス Cache で定義されている同名のメソッドを実装する。
    2. 抽象メソッド hit は,要求されたブロックデータがキャッシュ中に見つかったときに呼び出される。引数は,見つかったブロックデータとそのインデックス値の対(以下,キャッシュエントリという)である。
  • 入れ子クラス ListBasedCache.Entry は,キャッシュに格納するキャッシュエントリを表す。
    1. コンストラクタは,引数で指定されたインデックス値及びブロックデータをもつキャッシュエントリを生成する。
    2. メソッド getIndex 及び getBlockData は,それぞれインデックス値及びブロックデータを返す。
  • 入れ子クラス ListBasedCache.Fifo は,キャッシュエントリの管理をFIFOで行う。
    1. メソッド hit は,無操作である。
  • 入れ子クラス ListBasedCache.Lru は,キャッシュエントリの管理をLRUで行う。
    1. メソッド hit は,指定されたキャッシュエントリをリストの先頭に移動する。
 なお,上記コンストラクタやメソッドを呼び出すときの引数に誤りはないものとする。
pm11_2.png

設問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=
  • b=
  • c=
  • d=
  • e=
  • f=
  • g=

解説

aについて〕
getBlockSize は、ブロックのサイズをバイト数で返すメソッドです。〔プログラム 2〕で変数 blocks は、
byte[][] blocks = new byte[100][512]
と定義されており、2次元配列を使って512バイトの領域を100ブロック分確保しています。
pm11_3.png
各ブロックのサイズは512ですので、100ブロックのうちの1つの要素に対してlengthを呼び出せば、ブロックのサイズを取得できます。blocks[0]~blocks[99]のどれでも結果は同じです。

「ア」はブロックのサイズ(大きさ)ではなくブロックの数(要素数)が返されてしまうので誤り、角括弧"[ ]"内を空にしてよいのは宣言または配列生成式だけであり、配列へアクセスする際にはインデックスを指定しなければならないので他の選択肢も誤りです。

a=ウ:blocks[0]

bについて〕
空欄部分にはメソッド createCache の戻り値の型が入ります。実際に createCache を呼び出している〔プログラム1〕を確認すると、戻り値を受け取る変数 cache はCache型として定義されています。したがって正解の候補は、戻り値の型として Cache を指定している「ア」「イ」に絞られます。「イ」の"<>"(ダイアモンド演算子)と"?"を用いた宣言はジェネリクス(総称型)を指定する際に渡せるクラスに制限を付けるときに使いますが、クラス Cache はジェネリクスではないので、不適切な指定です。したがって「ア」が適切です。

実際にreturn文で返しているのは、クラス ListBasedCache の子クラスですが、クラス Cache はこれらのクラスの上位クラスですので、どちらも Cache として扱うことができます。

b=ア:Cache

cについて〕
〔プログラムの説明〕(3)③に以下の説明があります。

「抽象メソッド getCachedBlockData は,引数で指定されたインデックス値のブロックデータがキャッシュされていれば,それを返す。キャッシュされていなければ,null を返す」

IF文内では当該キャッシュエントリのブロックデータを返しているため、IF文の条件式は、引数 index で与えられたインデックス値をもつキャッシュエントリが見つかったときにだけ真を返すようになっていなければなりません。

for文で操作対象となっている entries は入れ子クラス Entry を要素とするList型(ArrayList型)です。クラス Entry は index と blockData という2つのフィールドを持っているので、entries の構造は以下のようになっています。
pm11_5.png
クラス Entry のメソッド getIndex は、自身が保持する index の値(ブロックのインデックス値)を返します。したがって、entry.getIndex() の値と引数 index の値が一致すれば求めるキャッシュエントリが見つかったと判断できます。よって、[c]には「==」が入ります。

※入れ子クラスは、一般的に内部クラスまたはインナークラスと言いますが、ここでは問題文の表現に合わせてあります。

c=エ:==

dについて〕
〔プログラムの説明〕(3)④に以下の説明があります。

「抽象メソッド cacheBlockData は,引数で指定されたインデックス値及びその値に対応するブロックデータをキャッシュする。キャッシュできるブロックデータ数が上限に達している場合は,管理方針に従ってキャッシュされているブロックデータを削除してから,指定されたブロックデータをキャッシュする」

IF文内では remove によって要素を削除しているので、条件式としてはキャッシュできるブロックデータ数が上限に達している場合に真となる式が入ります。(4)の説明に「キャッシュできるブロックデータ数の上限値は,フィールド CACHE_SIZE で表す」とあるように、上限値は定数 CACHE_SIZE に格納されています。よって、entries.size() が返すリストの要素数と CACHE_SIZE が一致していれば、キャッシュ内のブロックデータ数が上限に達していると判断できます。よって、[d]には「entries.size() == CACHE_SIZE」が入ります。

d=オ:entries.size() == CACHE_SIZE
  • 「キャッシュしているブロックデータがある場合」という意味になるので不適切です。
  • 「キャッシュしているブロックデータがない場合」という意味になるので不適切です。
  • 「キャッシュしているブロックデータ数が上限と一致しない場合」という意味になり、まだ上限に達していないときでも削除することになってしまうので不適切です。
  • 引数 index はブロックデータのインデックス値です。リストの要素数との比較に用いるのは不適切です。
  • 正しい。
  • 「エ」と同様の理由で不適切です。
eについて〕
[d]と関連しますが、「管理方針に従ってキャッシュされているブロックデータを削除」に相当する部分です。

remove の直後にある
entries.add(0, new Entry(index, blockData));
の処理はリスト(キャッシュ)に要素(キャッシュエントリ)を追加する処理ですが、第1引数が0なので、要素の挿入は常にリストの先頭に対して行われることがわかります。add の仕様を見てみると、「指定された位置及びその後に既に要素がある場合は、それらの要素をシフトする」とあるので、要素を追加する度に既存要素が1つずつ後ろにシフトしていき、リストの中で最後に追加したデータが先頭、最初に追加した要素が末尾になっていることがわかります。

後の解説と関連しますが、FIFO、LRUのどちらの管理方針でも置換対象となるブロックデータはリストの末尾に位置しているので、リスト末尾のインデックス値である「CACHE_SIZE - 1」を指定して、当該要素を削除することになります(-1しているのはインデックス値は0始まりだからです)。

「ア」「ウ」は上限を超えるインデックスを指定していることになるので誤り、「エ」「オ」「カ」はキャッシュの削除が特定のインデックスではなく末尾に対して行われること、引数 index は追加しようとしているブロックデータのインデックスを表すことから誤りです。

e=イ:CACHE_SIZE - 1

fについて〕
空欄を含む入れ子クラス Fifo および Lru は、〔プログラム3〕で以下のように呼び出されています。
pm11_4.png
[b]に入る戻り値の型は Cache でしたから、return している Fifo および Lru のインスタンスは Cache の下位クラスでなければなりません。よって、正解の候補は「ウ」と「カ」に絞られます。このうち、「ウ」の Cache は抽象クラスなので、継承するためには抽象メソッド getCachedBlockData と cacheBlockData を実装する必要がありますが、クラス Fifo および Lru にはその記述がありません。したがって[f]に入るのは「ListBasedCache」しかありません。

f=カ:ListBasedCache

gについて〕
〔プログラムの説明〕(7)①には「メソッド hit は,指定されたキャッシュエントリをリストの先頭に移動する」とあります。LRU(Least Recently Used)は、置換対象の中で最も長い時間参照されていないものを置換対象とするアルゴリズムなので、キャッシュエントリが参照されたとき、そのキャッシュエントリを置換と最も遠い位置であるリストの先頭に移動させる必要があります。この移動のため、hit が呼ばれたときに参照された要素を削除し、先頭に追加する操作があります。

Java APIの説明を見ると、List型のメソッド remove は2種類あり引数の型によって動作が変わります。1つはリスト内でのインデックス値を指定するもの、もう一つはオブジェクト自体を指定して削除するものです。
public E remove(int index)
 リスト内の指定された位置にある要素を削除する。

public boolean remove(Object obj)
 指定された要素がこのリストにあれば,その最初の要素を削除する。
メソッド hit は、読込みが行われた entry を引数に呼び出されるので、remove の引数として entry を渡せば、当該キャッシュエントリの削除が可能です。

g=ウ:entry
  • 常にリストの先頭の要素が削除されてしまうので不適切です。
  • 常にリストの末尾の要素が削除されてしまうので不適切です。
  • 正しい。
  • ブロックデータのインデックス値とリスト内の位置は一致していないので、entry.getIndex() を値を削除位置として使うのは不適切です。
  • 「エ」と同様の理由で不適切です。
  • 「エ」と同様の理由で不適です。

Pagetop