総視聴再生時間43万分以上(2017年5月13日現在)の動画で基本情報技術者試験の過去問&キーワード解説!スキマ時間に動画!〜これじょIT〜

PR広告

平成28年度春 基本情報技術者試験午後 過去問2 ソフトウェア 設問1 合格率アップ!動画付き解説

TOP :

問2 ソフトウェア

リスト構造で管理されているセルとガーベジコレクタに関する次の記述を読んで、設問1、2に答えよ。

 あるアプリケーションプログラム(以下、プログラムという)の実行環境では、プログラムからの要求によって、データ領域をセルとして提供する役割を担う供給源を実装している。プログラムは、使用中のセルをリストで管理している。

〔セルの構造とその管理方法〕

(1) 図1に示すように、セルの構造は、ガーベジコレクタ(以下、GCという)が使用するマークビットという1ビットのフラグ、別のセルヘのポインタ、及び固定長のデータ領域をもつ。マークビットの初期値は0である。ただし、以降の説明ではデータ領域を省略する。

平成28年度春応用情報技術者試験午問2 ソフトウェア 合格率アップ!動画解説!

(2) 図2に示すように、セルは、メモリ領域の中に連続して格納される。別のセルを指していないポインタには、NULL(終端記号)が格納されており、斜線を引いて表記している。

平成28年度春応用情報技術者試験午問2 ソフトウェア 合格率アップ!動画解説!

(3) 供給源の機能は次のとおりである。

① プログラムの実行開始時には、全てのセルは未使用セルとして、供給源が管理している。ここで、未使用セルのマークビットは0であり、ポインタにはNULLが格納されている。

② プログラムから取得要求があると、管理している未使用セルを提供する。

〔プログラムでのセルの使用方法〕

(1) プログラムは新たにセルが必要になると、供給源に要求を出し、未使用セルを受け取り、LIVEから始まるリスト(以下、LIVEリストという)に登録して使用する。LIVEリストに登録され、プログラムが使用している状態のセルをLIVEセルという。

(2) プログラムで不要になったセルは、LIVEリストから切り離すだけで、供給源には返却しない。この状態のセルをガーベジという。ガーベジのままでは使用することができない。LIVEセルがガーベジになる例を図3に示す。LIVEセルを実線、ガーベジを破線で表している。図3(a)では、LIVEからのポインタXはセルAを指しているが、プログラムの処理が進み、図3(b)では、セルCを指すようになった。このとき、セルAとセルBは、LIVEリストから切り離され、供給源の管理下の未使用セルでもなく、ガーベジになっている。

平成28年度春応用情報技術者試験午問2 ソフトウェア 合格率アップ!動画解説!

プログラムからのセル取得要求が繰り返されると、供給源が管理する未使用セルが無くなってしまうことがある。このとき、プログラムが新たなセルを要求しても、供給源からセルを受け取ることができず、プログラムの実行が停止する。そこで、ガーベジを未使用セルにするGCが起動される。

設問1

GCは、LIVEからのポインタをたどることによって、全てのLIVEセルを特定することができる。また、メモリ領域を先頭から走査することによって、全てのセルを識別することができる。未使用セルが無くなった状態では、特定されたLIVEセル以外のセルは全てガーベジである。GCの処理方式の一つとして、マークアンドスイープという方式がある。この方式によるGC処理に関する次の 記述中の に入る正しい答えを、解答群の中から選べ。

〔マークアンドスイープ方式によるGC処理の説明〕

(1) LIVEからのポインタをたどって到達できる全てのLIVEセルのマークビットを1にする。この処理をマーキングという。マーキング終了後のセルの状態の例を図4に示す。

平成28年度春応用情報技術者試験午問2 ソフトウェア 合格率アップ!動画解説!

次に、セルが格納されているメモリ領域中の全てのセルを重複が無いように走査し、各セルのマークビットの値を調べる。マークビットが0ならば、そのセルはガーベジであるので、供給源に未使用セルとして返却する。マークビットが1であれば0にする。以上の処理をスイープという。マーキング終了後で、スイープ開始前のメモリ領域の状態の例を図5に示す。

平成28年度春応用情報技術者試験午問2 ソフトウェア 合格率アップ!動画解説!

 GCが作動している間、プログラムの実行は一時中断される。中断の時間はマーキングの処理量とスイープの処理量に依存する。GCの対象となるメモリ領域のセルの数を M、GC開始時のLIVEセルの数を L としたとき、マーキングの処理量はaに比例する。また、スイープの処理量はbに比例する。

 このGCの1回の作動で再び利用できるようになるガーベジの数はcと表せる。M に対する L の割合(L/M)を横軸に、単位時間当たりに再び利用できるようになるセルの数(GCの効率)を縦軸にとってグラフを描いた。GCの効率と L/M の関係を示すグラフの形として、最も適切なものはdである。

a、b、c に関する解答群

  1. L
  2. L-M
  3. M
  4. M+L
  5. M-L

d に関する解答群

平成28年度春応用情報技術者試験午問2 ソフトウェア 合格率アップ!動画解説!

設問1の解説

設問1はadの穴埋め問題です。答えは下記のようになります。

 GCが作動している間、プログラムの実行は一時中断される。中断の時間はマーキングの処理量とスイープの処理量に依存する。 GCの対象となるメモリ領域のセルの数を M、GC開始時のLIVEセルの数を L としたとき、 マーキングの処理量はLに比例する。また、スイープの処理量はMに比例する。

 このGCの1回の作動で再び利用できるようになるガーベジの数はM - Lと表せる。 M に対する L の割合(L/M)を横軸に、単位時間当たりに再び利用できるようになるセルの数(GCの効率)を縦軸にとってグラフを描いた。 GCの効率と L/M の関係を示すグラフの形として、最も適切なものはである。

aにはマーキングの処理量がはります。マーキングはLIVEポインタをたどって到達できる全てのLIVEセルのマークビットを1にすることなので、GC開始時のLIVEセルの数Lに比例します。従ってaには「L」が入ります!

bにはスイープの処理量がはります。スイープはGC対象の各セルをみるので、GCの対象となるメモリ領域のセルの数Mに比例します。従ってbには「M」が入ります!

GC1回の動作で、ガーベジできる数は、「各セルの数M」から「LIVEセルの数L」を引いた数「M - L」になるので、cには「M - L」が入ります!

マーキングの量が増えると、効率が悪くなります。「LIVEセルの数L」が「各セルの数M」の値と同じになる(1になる)とガーベジできません。従って「ウ」のようなグラフになります!

設問2

プログラムの実行開始後、初めてGCが作動した。マーキング終了後の状態において、マークビットが1であるセルについての記述として正しい答えを、解答群の中から選べ。

解答群

  1. 供給源の管理下にある。
  2. プログラムが使用中である。
  3. プログラムの処理が進む過程で、LIVEリストから切り離された。
  4. マーキングに続いて行われるスイープで、供給源に返却されることがある。

設問2の解説

正解は「イ プログラムが使用中である。」です!

設問の「プログラムの実行開始後、初めてGCが作動した。マーキング終了後」を考えます。

マーキングとは「LIVEからのポインタをたどって到着できる全てのLIVEセルのマークビット1にする」ことです。

これは「プログラムが使用中」のものに対してマークビットを1にするといえます。

正解は「イ プログラムが使用中である。」です!

TOP :

タグ: ,

PR広告

フェイスブックコメント

平成28年度秋 基本情報技術者試験 午後 テキスト・動画解説

平成28年度秋 基本情報技術者試験 午前 テキスト・動画解説

平成28年度春 基本情報技術者試験 午後 テキスト・動画解説

平成28年度春 基本情報技術者試験 午前 テキスト・動画解説

平成27年度秋 基本情報技術者試験 午後 テキスト・動画解説

平成27年度春 基本情報技術者試験 午後 テキスト・動画解説

平成27年度春 基本情報技術者試験 午前 テキスト・動画解説

平成26年度秋 基本情報技術者試験 午前 テキスト・動画解説

平成26年度春 基本情報技術者試験 午前 テキスト・動画解説