基本情報技術者試験の過去問と解説
[TOP] [午前分野別] [午後分野別] [キーワード索引] [令和元年秋午前] [令和元年秋午後]

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

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

 

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

 

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

 


図1 セルの構造

 

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

 


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

 

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

 

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

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

 


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

 

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

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

 

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

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


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

 

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

 


図5 スイープ開始前のメモリ領域の状態の例

 

 GC が作動している間,プログラムの実行は一時中断される。中断の時間はマーキングの処理量と スイープの処理量に依存する。GC の対象となるメモリ領域のセルの数を M, GC 開始時の LIVE セルの数を L としたとき, マーキングの処理量は に比例する。 また,スイープの処理量は に比例する。
 この GC の1回の作動で再び利用できるようになるガーベジの数は と表せる。M に対する L の割合(L/M)を横軸に, 単位時間当たりに再び利用できるようになるセルの数(GC の効率)を縦軸にとってグラフを 描いた。GC の効率と L/M の関係を示すグラフの形として,最も適切なものは である。

 

a 〜 c に関する解答群 ア L       イ L−M       ウ M

エ M+L       オ M−L

 

d に関する解答群
解答 a ←クリックすると正解が表示されます

解答 b ←クリックすると正解が表示されます

解答 c ←クリックすると正解が表示されます

解答 d ←クリックすると正解が表示されます

基本情報技術者試験


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

 

解答群 ア 供給源の管理下にある。

イ プログラムが使用中である。

ウ プログラムの処理が進む過程で,LIVE リストから切り離された。

エ マーキングに続いて行われるスイープで,供給源に返却されることがある。

解答 ←クリックすると正解が表示されます

[←前の問題] [次の問題→] [問題一覧表] [分野別] [基本情報技術者試験TOP ]