【基本情報技術者試験平成28年春期午後】問題と解答

[TOP] [午前分野別] [午後分野別] [キーワード索引] [令和元年秋午前] [令和元年秋午後]

平成28年春期基本情報技術者午後問02

問02　　 ４問選択

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

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

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

図１　セルの構造

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

図２　メモリ領域の中に連続して格納されているセルのイメージ

(3) 供給源の機能は次のとおりである。 ① プログラムの実行開始時には，全てのセルは未使用セルとして，供給源が管理している。ここで，未使用セルのマークビットは 0 であり，ポインタには NULL が格納されている。
② プログラムから取得要求があると，管理している未使用セルを提供する。

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

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

図３　LIVE リストとガーベジの例

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

設問１

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

に入る正しい答えを，解答群の中から選べ。

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

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

図４　マーキング終了後のセルの状態の例

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