基本情報技術者試験の過去問と解説
[TOP] [午前分野別] [午後分野別] [キーワード索引] [令和元年秋午前] [令和元年秋午後]

平成27年 秋期 基本情報技術者 午後 問11
問11   Java

 次の Java プログラムの説明及びプログラムを読んで,設問に答えよ。

〔プログラムの説明〕

 固定バイト長のブロック(以下,ブロックという)を単位としてデータを保管している装置 (以下,ブロックデバイスという)に対し,ブロックのデータ(以下,ブロックデータという)への アクセスを管理するプログラムである。図1に,プログラム構成の概要を示す。 図中の四角はプログラムの構成要素を,矢印はブロックデータの流れを示す。 ここで,このプログラムでは,ブロックデバイスからの読込みだけを考える。


図1 プログラム構成の概要

 ブロックデバイス内の各ブロックは,インデックス値で指定する。 最初のブロックのインデックス値は,0である。

 ブロックアクセッサは,アプリケーションから要求されたブロックデータを ブロックデバイスから取得して,アプリケーションに渡す役割をする。 ブロックアクセッサはキャッシュを使用し,ブロックデバイスから 取得したブロックデータをキャッシュする。 アプリケーションから要求されたブロックデータがキャッシュされていれば, キャッシュから取得したブロックデータをアプリケーションに渡す。

 キャッシュは,FIFO(First In,First Out)と LRU(Least Recently Used)の2種類の 管理方針に基づく実装が用意されていて,アプリケーションはどの実装を使用するかを指定する。

(1) クラス BlockAccessor は,ブロックアクセッサを表す。

@ コンストラクタは,ブロックデバイスをオープンし,引数で指定されたキャッシュの 管理方針に基づくキャッシュを生成する。

A メソッド readBlock は,引数で指定されたインデックス値のブロックデータを返す。 ブロックデータがキャッシュにあれば,それを返す。なければ, ブロックデバイスから取得し,キャッシュした後,そのブロックデータを返す。

(2) クラス BlockDevice は,読取り専用のブロックデバイスを表す。実装は, バイト配列の配列であるフィールド blocks を使用し,ブロックデバイスを 仮想的に表す。ただし,ブロックデータの値は全て 0 である。 @ 静的メソッド open は,ブロックデバイスのインスタンスを返す。

A メソッド getBlockSize は,ブロックのサイズをバイト数で返す。

B メソッド readBlock は,引数で指定されたインデックス値のブロックデータを 引数で指定されたバッファに読み込む。

(3) 抽象クラス Cache は,ブロックアクセッサからキャッシュ機能を使用するためのクラスを表す。

@ キャッシュの管理方針(FIFO 及び LRU)を表す入れ子列挙 Cache.Policy を定義する。

A 静的メソッド createCache は,引数で指定されたキャッシュの管理方針と 一致する実装クラスのインスタンスを生成して返す。

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

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

(4) 抽象クラス ListBasedCache は, リスト構造を使用して抽象クラス Cache の一部を実装する。 キャッシュできるブロックデータ数の上限値は,フイールド CACHE_SIZE で表す。 @ メソッド getCachedBlockData 及び cacheBlockData は, 抽象クラス Cache で定義されている同名のメソッド を実装する。

A 抽象メソッド hit は,要求されたブロックデータがキャッシュ中に見つかったときに 呼び出される。引数は,見つかったブロックデータとそのインデックス値の対 (以下,キャッシュエントリという)である。

(5) 入れ子クラス ListBasedCache.Entry は,キャッシュに格納するキャッシュエントリを表す。 @ コンストラクタは,引数で指定されたインデックス値及びブロックデータを もつキャッシュエントリを生成する。

A メソッド getIndex 及び getBlockData は,それぞれインデックス値及びブロックデータを返す。

(6) 入れ子クラス ListBasedCache.Fifo は,キャッシュエントリの管理を FIFO で行う。 @ メソッド hit は,無操作である。 (7) 入れ子クラス ListBasedCache.Lru は,キャッシュエントリの管理を LRU で行う。 @ メソッド hit は,指定されたキャッシュエントリをリストの先頭に移動する。

 なお,上記コンストラクタやメソッドを呼び出すときの引数に誤りはないものとする。

〔プログラム1]

public class BlockAccessor {
   private final Cache cache;
   private final BlockDevice device;

   public BlockAccessor(Cache.Policy policy) {
      device = BlockDevice.open();
      cache = Cache.createCache(policy);
   }

   public byte[] readBlock(int index) {
      byte[] blookData = cache.getCachedBlockData(index);
      if (blockData == null) {
         blockData = new byte[device.getBlockSize()];
         device.readBlock(index, blockData);
         cache.cacheBlockData(index, blockData);
      }
      return blockData.clone();
   }
}
〔プログラム2〕
class BlockDevice {
   private final byte[][] blocks = new byte[1ØØ][512];

   static BlockDevice open() {
      return new BlockDevice();
   }

   int getBlockSize() {
      return  .length;
   }

   void readBlock(int index, byte[] buffer) {
      byte[] block = blocks[index];
      System.arraycopy(block, Ø, buffer, Ø, block.length);
   }
}
〔プログラム3〕
public abstract class Cache {
   public enum Policy {
      FIFO, LRU;
   }

   static  createCache(Policy policy) {
      switch (policy) {
      case FIFO:
         return new ListBasedCache.Fifo();
      case LRU:
         return new ListBasedCache.Lru();
      }
      throw new UnsupportedOperationException();
   }

   abstract byte[] getCachedBlockData(int index);
   abstract void cacheBlockData(int index, byte[] blockData);
}
〔プログラム4〕
import java.util.ArrayList;
import java.util.List;

abstract class ListBasedCache extends Cache {
   final List<Entry> entries = new ArrayList<Entry>();
   private static final int CACHE_SIZE = 2Ø;

   byte[] getCachedBlockData(int index) {
      for (Entry entry : entries) {
         if (entry.getIndex()  Index) {
            hit(entry);
            return entry.getBlockData();
         }
      }
      return null;
   }

   void cacheBlockData(int index, byte[] blockData) {
      if (  ) {
         entries.remove(  );
      }
     entries.add(Ø, new Entry(index, blockData));
   }

   abstract void hit(Entry entry);

   private static class Entry {
      private final int index;
      private final byte[] blockData;

      private Entry(int index, byte[] bLockData) {
         this.index = index;
         this.blockData = blockData;
      }

      int getIndex() { return index; }
      byte[] getBlockData() { return blockData; )
   }

   static class Fifo extends  {
      void hit(Entry entry) { }
   }

   static class Lru extends  {
      void hit(Entry entry) {
         entries.remove(  );
         entries.add(Ø, entry);
      }
   }
}
設問 プログラム中の に入れる正しい答えを,解答群の中から選べ。

a に関する解答群

ア blocks        イ blocks[]        ウ blocks[O]       
エ blocks[][]        オ blocks[Ø][]        カ blocks[][Ø]       

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 に関する解答群

ア Ø        イ CACHE_SIZE - 1        ウ entry       
エ entry.getIndex()        オ entry.getIndex() - 1        カ entry.getIndex() + 1       
解答 a ←クリックすると正解が表示されます

解答 b ←クリックすると正解が表示されます

解答 c ←クリックすると正解が表示されます

解答 d ←クリックすると正解が表示されます

解答 e ←クリックすると正解が表示されます

解答 f ←クリックすると正解が表示されます

解答 g ←クリックすると正解が表示されます


[←前の問題] [次の問題→] [問題一覧表] [分野別] [基本情報技術者試験TOP ]