基本情報技術者 2016年 春期 午後 問02
リスト構造で管理されているセルとガーベジコレクタに関する次の記述を読んで、設問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〜cに関する解答群
ア：L
イ：L − M
ウ：M
エ：M + L
オ：M − L
dに関する解答群
模範解答
a：ア、b：ウ、c：オ、d：ウ
解説
解答の導き方
この設問では、GC（Garbage Collector：不要になったセルを回収し、再利用できるようにする仕組み）の処理にかかる量と、回収できるセルの数を考えます。セルは、データを入れる一定の大きさの区画です。
a：マーキングの処理量
マーキングでは、本文に「LIVEからのポインタをたどって到達できる全てのLIVEセル」のマークビットを1にするとあります。ポインタは、別のセルの場所を示す情報です。
GC開始時のLIVEセルの数は です。LIVEセルをたどり、各セルをマーキングする処理の量は、LIVEセルの数に応じて増えます。したがって、マーキングの処理量は に比例します。aはアです。
b：スイープの処理量
スイープでは、本文に「メモリ領域中の全てのセル」を走査するとあります。LIVEセルだけでなく、ガーベジも含めて、メモリ領域にあるセルを一つずつ調べます。
セルの総数は なので、スイープの処理量は に比例します。bはウです。
c：再び利用できるようになるガーベジの数
GC開始時に未使用セルがないため、メモリ領域内のセルは、LIVEセルかガーベジのどちらかです。全体のセル数 からLIVEセルの数 を引けば、ガーベジの数が分かります。
スイープでは、マークビットが0のセルをガーベジとして供給源に返却します。このため、再び利用できるようになるガーベジの数は です。cはオです。
d：GCの効率と の関係
GCの処理にかかる量は、マーキングとスイープの合計なので、 に比例します。一方、再利用できるセルの数は です。したがって、GCの効率は、処理にかかる量に対する回収できるセルの数の割合で考えられます。
横軸の値を とすると、効率の変化は次の比で表せます。
が0から1に近づくと、回収できるガーベジが減るため、効率は下がります。また、 ではLIVEセルが全てを占め、回収できるガーベジがなくなるため、効率は0です。
この比は、はじめは大きく下がり、その後は下がり方がゆるやかになります。選択肢では、この形に当てはまるのはウです。
誤りやすいポイント
- マーキングとスイープの対象を混同しないようにします。マーキングはLIVEセルをたどる処理なので に比例し、スイープは全セルを調べる処理なので に比例します。
- 回収できるセルの数を と考えないようにします。LIVEセルは使用中のセルです。回収できるのは、全セル数からLIVEセル数を引いた です。
- 効率のグラフを直線と決めつけないようにします。効率は、回収できるセル数だけでなく、GCの処理にかかる量にも左右されます。
FAQ
Q: マーキング後に、LIVEセルのマークビットを0に戻すのはなぜですか？
A: 次回のGCでも、LIVEセルを改めてマーキングできるようにするためです。マークビットが前回の値のままだと、今回の処理でLIVEセルかどうかを判別しにくくなります。
A: 次回のGCでも、LIVEセルを改めてマーキングできるようにするためです。マークビットが前回の値のままだと、今回の処理でLIVEセルかどうかを判別しにくくなります。
Q: ガーベジは、LIVEリストから外れた時点で再利用できるのですか？
A: できません。問題文では、ガーベジは供給源に返却されていない状態です。GCがガーベジを見つけて供給源に返却することで、再利用できるようになります。
A: できません。問題文では、ガーベジは供給源に返却されていない状態です。GCがガーベジを見つけて供給源に返却することで、再利用できるようになります。
Q: が大きいほど、GCの効率は高くなりますか？
A: いいえ。 が大きいほどLIVEセルの割合が高く、回収できるガーベジは少なくなります。そのため、GCの効率は低くなります。
A: いいえ。 が大きいほどLIVEセルの割合が高く、回収できるガーベジは少なくなります。そのため、GCの効率は低くなります。
関連キーワード: ガーベジコレクション、マークアンドスイープ、ポインタ、メモリ管理、到達可能性
設問2：
問題文を見る プログラムの実行開始後、初めてGCが作動した。マーキング終了後の状態において、マークビットが1であるセルについての記述として正しい答えを、解答群の中から選べ。
解答群
ア：供給源の管理下にある。
イ：プログラムが使用中である。
ウ：プログラムの処理が進む過程で、LIVEリストから切り離された。
エ：マーキングに続いて行われるスイープで、供給源に返却されることがある。
模範解答
イ
解説
解答の導き方
この設問では、GC（Garbage Collector：不要になったセルを回収し、再利用できるようにする機能）の処理後に、マークビットが1のセルがどのような状態かを考えます。
まず、プログラムの実行開始時には、セルのマークビットはすべて0です。また、セルを使い始めても、最初のGCが動くまではマークビットは0のままです。設問では「初めてGCが作動した」とあるため、マーキングの前に、以前のGCによるマークが残っていることはありません。
GCのマーキングでは、LIVEリスト（プログラムが使用中のセルを管理するリスト）からポインタをたどり、到達できるセルにマークを付けます。マークビットを1にするのは、プログラムが使っているセルを、回収対象と区別するためです。図4でも、LIVEリストからたどれるセルはマークビットが1になり、セルAやセルBのようにLIVEリストからたどれないセルは0のままです。
このため、マークビットが1のセルは「プログラムが使用中である」と判断できます。選択肢ではイに当たります。
ほかの選択肢も確認します。
- アの「供給源の管理下にある」セルは、まだ使われていないセルです。実行開始時の未使用セルはマークビットが0なので、マークビットが1のセルとは状態が異なります。
- ウの「LIVEリストから切り離された」セルはガーベジです。LIVEリストからたどれなくなるため、マーキングされず、マークビットは0のままです。
- エのスイープは、メモリ領域を調べて、マーキングされなかったセルを供給源に返す処理です。マークビットが1のセルは使用中なので、返却対象ではありません。
誤りやすいポイント
- マークビットが1のセルを、回収対象と考えてしまうことがあります。1は「使用中のセルとしてマーキングされた」状態です。
- LIVEリストから外れたセルが、すぐ供給源に返ると思い込まないようにしましょう。問題文では、LIVEリストから切り離されたセルはガーベジになり、GCが回収するまでは再利用できません。
- マーキングとスイープの役割を混同しないことが大切です。マーキングでは使用中のセルを見つけ、スイープでは使用中としてマークされなかったセルを回収します。
FAQ
Q: マークビットが0なら、必ずガーベジですか？
A: マーク中の時点では、0は「LIVEリストからたどって確認できていない」状態です。この設問では初めてのGCで、供給源の未使用セルもない状況でGCが始まっています。そのため、使用中としてマークされなかったセルが回収対象になります。
A: マーク中の時点では、0は「LIVEリストからたどって確認できていない」状態です。この設問では初めてのGCで、供給源の未使用セルもない状況でGCが始まっています。そのため、使用中としてマークされなかったセルが回収対象になります。
Q: ポインタをたどってマーキングするのはなぜですか？
A: LIVEリストに直接登録されたセルだけでなく、そのセルから参照されているセルもプログラムが使う可能性があるためです。ポインタをたどることで、間接的に利用されているセルも回収しないようにできます。
A: LIVEリストに直接登録されたセルだけでなく、そのセルから参照されているセルもプログラムが使う可能性があるためです。ポインタをたどることで、間接的に利用されているセルも回収しないようにできます。
Q: スイープでは、どのセルが供給源に返されますか？
A: マークビットが1になっていないセルです。使用中として確認できなかったセルを供給源に返し、再利用できるようにします。
A: マークビットが1になっていないセルです。使用中として確認できなかったセルを供給源に返し、再利用できるようにします。
関連キーワード: ガーベジコレクション、マーク・スイープ方式、マークビット、ポインタ、到達可能性
