基本情報技術者試験 - 平成28年春期(科目B) - 問2
問題
リスト構造で管理されているセルとガーベジコレクタに関する次の記述を読んで,設問1,2に答えよ。
あるアプリケーションプログラム(以下,プログラムという)の実行環境では,プログラムからの要求によって,データ領域をセルとして提供する役割を担う供給源を実装している。プログラムは,使用中のセルをリストで管理している。
〔セルの構造とその管理方法〕
(1) 図1に示すように,セルの構造は,ガーベジコレクタ(以下,GCという)が使用するマークビットという1ビットのフラグ,別のセルへのポインタ,及び固定長のデータ領域をもつ。マークビットの初期値は0である。ただし,以降の説明ではデータ領域を省略する。

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

(3) 供給源の機能は次のとおりである。
① プログラムの実行開始時には,全てのセルは未使用セルとして,供給源が管理している。ここで,未使用セルのマークビットは0であり,ポインタにはNULLが格納されている。
② プログラムから取得要求があると,管理している未使用セルを提供する。
〔プログラムでのセルの使用方法〕
(1) プログラムは新たにセルが必要になると,供給源に要求を出し,未使用セルを受け取り,LIVEから始まるリスト(以下,LIVEリストという)に登録して使用する。LIVEリストに登録され,プログラムが使用している状態のセルをLIVEセルという。
(2) プログラムで不要になったセルは,LIVEリストから切り離すだけで,供給源には返却しない。この状態のセルをガーベジという。ガーベジのままでは使用することができない。LIVEセルがガーベジになる例を図3に示す。LIVEセルを実線,ガーベジを破線で表している。図3(a)では,LIVEからのポインタXはセルAを指しているが,プログラムの処理が進み,図3(b)では,セルCを指すようになった。このとき,セルAとセルBは,LIVEリストから切り離され,供給源の管理下の未使用セルでもなく,ガーベジになっている。

(3) プログラムからのセル取得要求が繰り返されると,供給源が管理する未使用セルが無くなってしまうことがある。このとき,プログラムが新たなセルを要求しても,供給源からセルを受け取ることができず,プログラムの実行が停止する。そこで,ガーベジを未使用セルにするGCが起動される。
設問1 GCは,LIVEからのポインタをたどることによって,全てのLIVEセルを特定することができる。また,メモリ領域を先頭から走査することによって,全てのセルを識別することができる。未使用セルが無くなった状態では,特定されたLIVEセル以外のセルは全てガーベジである。GCの処理方式の一つとして,マークアンドスイープという方式がある。この方式によるGC処理に関する次の記述中の[ ]に入る正しい答えを,解答群の中から選べ。
〔マークアンドスイープ方式によるGC処理の説明〕
(1) LIVEからのポインタをたどって到達できる全てのLIVEセルのマークビットを1にする。この処理をマーキングという。マーキング終了後のセルの状態の例を図4に示す。

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

GCが作動している間,プログラムの実行は一時中断される。中断の時間はマーキングの処理量とスイープの処理量に依存する。GCの対象となるメモリ領域のセルの数をM,GC開始時のLIVEセルの数をLとしたとき,マーキングの処理量は[ a ]に比例する。また,スイープの処理量は[ b ]に比例する。
このGCの1回の作動で再び利用できるようになるガーベジの数は[ c ]と表せる。Mに対するLの割合(L/M)を横軸に,単位時間当たりに再び利用できるようになるセルの数(GCの効率)を縦軸にとってグラフを描いた。GCの効率とL/Mの関係を示すグラフの形として,最も適切なものは[ d ]である。
aに関する解答群
bに関する解答群
cに関する解答群
dに関する解答群
設問2 プログラムの実行開始後,初めてGCが作動した。マーキング終了後の状態において,マークビットが1であるセルについての記述として正しい答えを,解答群の中から選べ。
解答群
あるアプリケーションプログラム(以下,プログラムという)の実行環境では,プログラムからの要求によって,データ領域をセルとして提供する役割を担う供給源を実装している。プログラムは,使用中のセルをリストで管理している。
〔セルの構造とその管理方法〕
(1) 図1に示すように,セルの構造は,ガーベジコレクタ(以下,GCという)が使用するマークビットという1ビットのフラグ,別のセルへのポインタ,及び固定長のデータ領域をもつ。マークビットの初期値は0である。ただし,以降の説明ではデータ領域を省略する。

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

(3) 供給源の機能は次のとおりである。
① プログラムの実行開始時には,全てのセルは未使用セルとして,供給源が管理している。ここで,未使用セルのマークビットは0であり,ポインタにはNULLが格納されている。
② プログラムから取得要求があると,管理している未使用セルを提供する。
〔プログラムでのセルの使用方法〕
(1) プログラムは新たにセルが必要になると,供給源に要求を出し,未使用セルを受け取り,LIVEから始まるリスト(以下,LIVEリストという)に登録して使用する。LIVEリストに登録され,プログラムが使用している状態のセルをLIVEセルという。
(2) プログラムで不要になったセルは,LIVEリストから切り離すだけで,供給源には返却しない。この状態のセルをガーベジという。ガーベジのままでは使用することができない。LIVEセルがガーベジになる例を図3に示す。LIVEセルを実線,ガーベジを破線で表している。図3(a)では,LIVEからのポインタXはセルAを指しているが,プログラムの処理が進み,図3(b)では,セルCを指すようになった。このとき,セルAとセルBは,LIVEリストから切り離され,供給源の管理下の未使用セルでもなく,ガーベジになっている。

(3) プログラムからのセル取得要求が繰り返されると,供給源が管理する未使用セルが無くなってしまうことがある。このとき,プログラムが新たなセルを要求しても,供給源からセルを受け取ることができず,プログラムの実行が停止する。そこで,ガーベジを未使用セルにするGCが起動される。
設問1 GCは,LIVEからのポインタをたどることによって,全てのLIVEセルを特定することができる。また,メモリ領域を先頭から走査することによって,全てのセルを識別することができる。未使用セルが無くなった状態では,特定されたLIVEセル以外のセルは全てガーベジである。GCの処理方式の一つとして,マークアンドスイープという方式がある。この方式によるGC処理に関する次の記述中の[ ]に入る正しい答えを,解答群の中から選べ。
〔マークアンドスイープ方式によるGC処理の説明〕
(1) LIVEからのポインタをたどって到達できる全てのLIVEセルのマークビットを1にする。この処理をマーキングという。マーキング終了後のセルの状態の例を図4に示す。

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

GCが作動している間,プログラムの実行は一時中断される。中断の時間はマーキングの処理量とスイープの処理量に依存する。GCの対象となるメモリ領域のセルの数をM,GC開始時のLIVEセルの数をLとしたとき,マーキングの処理量は[ a ]に比例する。また,スイープの処理量は[ b ]に比例する。
このGCの1回の作動で再び利用できるようになるガーベジの数は[ c ]と表せる。Mに対するLの割合(L/M)を横軸に,単位時間当たりに再び利用できるようになるセルの数(GCの効率)を縦軸にとってグラフを描いた。GCの効率とL/Mの関係を示すグラフの形として,最も適切なものは[ d ]である。
aに関する解答群
| ア | L |
|---|---|
| イ | L-M |
| ウ | M |
| エ | M+L |
| オ | M-L |
bに関する解答群
| ア | L |
|---|---|
| イ | L-M |
| ウ | M |
| エ | M+L |
| オ | M-L |
cに関する解答群
| ア | L |
|---|---|
| イ | L-M |
| ウ | M |
| エ | M+L |
| オ | M-L |
dに関する解答群
| ア | ![]() |
|---|---|
| イ | ![]() |
| ウ | ![]() |
| エ | ![]() |
設問2 プログラムの実行開始後,初めてGCが作動した。マーキング終了後の状態において,マークビットが1であるセルについての記述として正しい答えを,解答群の中から選べ。
解答群
| ア | 供給源の管理下にある。 |
|---|---|
| イ | プログラムが使用中である。 |
| ウ | プログラムの処理が進む過程で,LIVEリストから切り離された。 |
| エ | マーキングに続いて行われるスイープで,供給源に返却されることがある。 |
正解と解説
正解設問1 (a)ア (b)ウ (c)オ (d)ウ 設問2 イ
分野テクノロジ系 › コンピュータシステム › ソフトウェア › オペレーティングシステム




解説
プログラムが使い終わったメモリ(ガーベジ=ゴミ)を回収して再利用できるようにする仕組みを,ガーベジコレクタ(GC)といいます。この問題では「マークアンドスイープ」という方式を扱っています。■ マークアンドスイープ方式の流れ
■ 設問1 空欄a,b(処理量)
マーキングでは,使用中のセルだけをたどるので,処理量はLIVEセルの数Lに比例します。空欄aは「ア」です。スイープでは,メモリ領域の全てのセルを1つずつ調べるので,処理量は全セル数Mに比例します。空欄bは「ウ」です。
■ 設問1 空欄c(回収できるガーベジの数)
GCは未使用セルが無くなったときに起動されるので,その時点では「使用中のセル(L個)」以外は全てガーベジです。したがって回収できる数はM-Lとなり,「オ」が正解です。■ 設問1 空欄d(GCの効率のグラフ)
GCの効率は「回収できるセルの数÷かかる時間」と考えられます。かかる時間はマーキングとスイープの合計なので,L+Mに比例します。したがって,効率はおおよそ(M-L)÷(M+L)に比例します。ここでx=L/Mとおいて分母分子をMで割ると,(1-x)÷(1+x)になります。
- x=0(使用中のセルがほぼ無い)のとき:1÷1=1で最大になります。
- x=1(全セルが使用中)のとき:0÷2=0になります。
xが大きくなるにつれて効率は下がり続け,その下がり方は最初が急で次第に緩やかになる曲線です。この形に合うのは「ウ」です。直感的には,「使用中のセルが多いほど,手間をかけても回収できるゴミが少ないので効率が悪い」ということです。
■ 設問2 マークビットが1のセル
マーキングでは,LIVEからたどれるセル,つまりプログラムが使用中のセルにだけ1を付けます。したがって「イ」が正解です。