HOME»基本情報技術者平成28年春期問題»午後問2
基本情報技術者過去問題 平成28年春期 午後問2
⇄問題文と設問を画面2分割で開く⇱問題PDF問2 ソフトウェア
リスト構造で管理されているセルとガーベジコレクタに関する次の記述を読んで，設問1，2に答えよ。
あるアプリケーションプログラム(以下，プログラムという)の実行環境では，プログラムからの要求によって，データ領域をセルとして提供する役割を担う供給源を実装している。プログラムは，使用中のセルをリストで管理している。
〔セルの構造とその管理方法〕
あるアプリケーションプログラム(以下，プログラムという)の実行環境では，プログラムからの要求によって，データ領域をセルとして提供する役割を担う供給源を実装している。プログラムは，使用中のセルをリストで管理している。
〔セルの構造とその管理方法〕
- 図1に示すように，セルの構造は，ガーベジコレクタ(以下，GCという)が使用するマークビットという1ビットのフラグ，別のセルヘのポインタ，及び固定長のデータ領域をもつ。マークビットの初期値は0である。ただし，以降の説明ではデータ領域を省略する。
- 図2に示すように，セルは，メモリ領域の中に連続して格納される。別のセルを指していないポインタには，NULL(終端記号)が格納されており，斜線を引いて表記している。
- 供給源の機能は次のとおりである。
- プログラムの実行開始時には，全てのセルは未使用セルとして，供給源が管理している。ここで，未使用セルのマークビットは0であり，ポインタにはNULLが格納されている。
- プログラムから取得要求があると，管理している未使用セルを提供する。
- プログラムは新たにセルが必要になると，供給源に要求を出し，未使用セルを受け取り，LIVEから始まるリスト(以下，LIVEリストという)に登録して使用する。LIVEリストに登録され，プログラムが使用している状態のセルをLIVEセルという。
- プログラムで不要になったセルは，LIVEリストから切り離すだけで，供給源には返却しない。この状態のセルをガーベジという。ガーベジのままでは使用することができない。LIVEセルがガーベジになる例を図3に示す。LIVEセルを実線，ガーベジを破線で表している。図3(a)では，LIVEからのポインタXはセルAを指しているが，プログラムの処理が進み，図3(b)では，セルCを指すようになった。このとき，セルAとセルBは，LIVEリストから切り離され，供給源の管理下の未使用セルでもなく，ガーベジになっている。
- プログラムからのセル取得要求が繰り返されると，供給源が管理する未使用セルが無くなってしまうことがある。このとき，プログラムが新たなセルを要求しても，供給源からセルを受け取ることができず，プログラムの実行が停止する。そこで，ガーベジを未使用セルにするGCが起動される。
設問1
GCは，LIVEからのポインタをたどることによって，全てのLIVEセルを特定することができる。また，メモリ領域を先頭から走査することによって，全てのセルを識別することができる。未使用セルが無くなった状態では，特定されたLIVEセル以外のセルは全てガーベジである。GCの処理方式の一つとして，マークアンドスイープという方式がある。この方式によるGC処理に関する次の 記述中の に入る正しい答えを，解答群の中から選べ。
〔マークアンドスイープ方式によるGC処理の説明〕
このGCの1回の作動で再び利用できるようになるガーベジの数はcと表せる。M に対する L の割合(L/M)を横軸に，単位時間当たりに再び利用できるようになるセルの数(GCの効率)を縦軸にとってグラフを描いた。GCの効率と L/M の関係を示すグラフの形として，最も適切なものはdである。
〔マークアンドスイープ方式によるGC処理の説明〕
- LIVEからのポインタをたどって到達できる全てのLIVEセルのマークビットを1にする。この処理をマーキングという。マーキング終了後のセルの状態の例を図4に示す。
- 次に，セルが格納されているメモリ領域中の全てのセルを重複が無いように走査し，各セルのマークビットの値を調べる。マークビットが0ならば，そのセルはガーベジであるので，供給源に未使用セルとして返却する。マークビットが1であれば0にする。以上の処理をスイープという。マーキング終了後で，スイープ開始前のメモリ領域の状態の例を図5に示す。
このGCの1回の作動で再び利用できるようになるガーベジの数はcと表せる。M に対する L の割合(L/M)を横軸に，単位時間当たりに再び利用できるようになるセルの数(GCの効率)を縦軸にとってグラフを描いた。GCの効率と L/M の関係を示すグラフの形として，最も適切なものはdである。
a，b，c に関する解答群
- L
- L－M
- M
- M＋L
- M－L
d に関する解答群
解答選択欄
- a:
- b:
- c:
- d:
解答
- a=ア
- b=ウ
- c=オ
- d=ウ
解説
〔aについて〕
マーキング処理ではLIVEセルをたどりマークビットを1にすることを繰り返します。処理の対象は「全てのLIVEセル」になるため、処理量はLIVEセルの数 L に比例します。
a＝ア：L
〔bについて〕
スイープ処理ではメモリ領域中の全てのセルを重複が無いように走査し，マークビットが0のセルは未使用セルとして供給源に返却、マークビットが1のセルはマークビットに0をセットします。処理の対象は「メモリ領域中の全てのセル」になるため、処理量はメモリ領域のセル数 M に比例します。
b＝ウ：M
〔cについて〕
GCは未使用セルが無くなったときに起動されるため、GC作動時のメモリ領域のセルは"LIVEセル"又は"ガーベジ"のいずれかの状態になっています。したがってメモリ領域内のセル数からLIVEセル数を減じた数が未使用セルとして供給源に返却されるセル数ということになります。
メモリ領域内のセル数＝M、LIVEセル数＝L なので、再利用可能となるガーベジ数を表す式は M－L となります。
c＝オ：M－L
〔dについて〕
GCの効率は、
再利用可能になるセルの数／単位時間当たりの処理量
で表すことができます。GCはマーキング処理とスイープ処理から成るため、その合計処理量はa、bより「L＋M」と表せます。また再利用可能になるセルの数はcにて「M－L」とわかっています。つまりGCの効率は、
(M－L)／(L＋M)
の式で表すことができます。この式とL／Mの関係を調べてみると以下の表のようになっていることがわかります。
表よりGCの効率はL／Mが上昇するに従って次第に減っていく関係にあることがわかります。したがって「ウ」のグラフが適切です。
e＝ウ
マーキング処理ではLIVEセルをたどりマークビットを1にすることを繰り返します。処理の対象は「全てのLIVEセル」になるため、処理量はLIVEセルの数 L に比例します。
a＝ア：L
〔bについて〕
スイープ処理ではメモリ領域中の全てのセルを重複が無いように走査し，マークビットが0のセルは未使用セルとして供給源に返却、マークビットが1のセルはマークビットに0をセットします。処理の対象は「メモリ領域中の全てのセル」になるため、処理量はメモリ領域のセル数 M に比例します。
b＝ウ：M
〔cについて〕
GCは未使用セルが無くなったときに起動されるため、GC作動時のメモリ領域のセルは"LIVEセル"又は"ガーベジ"のいずれかの状態になっています。したがってメモリ領域内のセル数からLIVEセル数を減じた数が未使用セルとして供給源に返却されるセル数ということになります。
メモリ領域内のセル数＝M、LIVEセル数＝L なので、再利用可能となるガーベジ数を表す式は M－L となります。
c＝オ：M－L
〔dについて〕
GCの効率は、
再利用可能になるセルの数／単位時間当たりの処理量
で表すことができます。GCはマーキング処理とスイープ処理から成るため、その合計処理量はa、bより「L＋M」と表せます。また再利用可能になるセルの数はcにて「M－L」とわかっています。つまりGCの効率は、
(M－L)／(L＋M)
の式で表すことができます。この式とL／Mの関係を調べてみると以下の表のようになっていることがわかります。
e＝ウ
設問2
プログラムの実行開始後，初めてGCが作動した。マーキング終了後の状態において，マークビットが1であるセルについての記述として正しい答えを，解答群の中から選べ。
解答群
- 供給源の管理下にある。
- プログラムが使用中である。
- プログラムの処理が進む過程で，LIVEリストから切り離された。
- マーキングに続いて行われるスイープで，供給源に返却されることがある。
解答選択欄
解答
- イ
解説
マーキング処理は、LIVEリストをたどって到達できるの全てのセルのマークビットを1にする操作です。LIVEリストに登録されているLIVEセルは「プログラムが使用している状態のセル」であると設問中に記述されています。
したがって「イ」が正解です。
したがって「イ」が正解です。
- 未使用セルの状態です。
- 正しい。
- ガーベジの状態です。
- スイープで供給源に返却されるセルはマークビットが0のセルです。