令和元年度 III-4

解説

この問題で問われていること

ルート(局所変数)から参照をたどって到達できないレコードを、ごみとして回収されるものとして選ぶ問題。

解き方

① マーク・アンド・スイープ=局所変数(ルート)から矢印をたどれるものに印を付け、印のないものを回収する
② 局所変数から 'a'、'd'、'g' に届く。'd'から'e'と'g'へ。'a'・'e'・'g'からは矢印なし → 印あり: a,d,e,g。回収: b,c,f('b'→'d'、'c'→'f'、'f'→'c'の矢印があっても、ルートから届かない)
③ ③

正解が正しい理由

マーク・アンド・スイープでは、ルート(使用されている局所変数)から参照をたどって到達できるレコードに印を付け(マーク)、印のないレコードを回収する(スイープ)。局所変数は'a'、'd'、'g'を参照し、'd'はさらに'e'と'g'を参照する。到達可能なのは'a'、'd'、'e'、'g'で、'b'、'c'、'f'はルートから到達できない('c'と'f'は互いに参照しているが、循環参照でも到達できなければ回収される)。したがって③が正しい。

各選択肢について

• ① 'b'だけでなく、ルートから到達できない'c'と'f'も回収される。
• ② 'e'と'g'は局所変数や'd'から参照されており、回収されない。
• ③ ルートから到達できない'b'、'c'、'f'で、これが正答。
• ④ 'e'は'd'から参照されており、回収されない。
• ⑤ 到達できないレコード('b'、'c'、'f')があるので、回収されるレコードはある。

覚えるべきポイント

マーク・アンド・スイープはルートからの到達可能性で判断するので、循環参照していても到達できなければ回収される(参照カウント方式ではこれを回収できない)。