Matzにっき

_ [生活]睡眠

東京行きですっかりくたびれたか、異常に眠る。午前中はずっと寝ていた。 が、おかげで風邪引きかかっていたような気がしていたのが、直ったような。

_ [言語]GCとスレッド

スクリプト言語におけるGCの課題は、大量live objectとスレッド対応であると述べたが、 今回はスレッド対応の難しさについて考察する。

複数のスレッドが存在する環境でGCを行う場合に面倒なのは同期と排他制御だ。

そもそも、あるオブジェクトが死んでいる(プログラム終了まで使われることはない)かどうかは、 機械的には判定できない。そこで、どこからも参照されていないことを近似として用いているわけだが、 「どこからも参照されていない」かどうかを判定することも、それほど簡単ではない。

reference countを除くGC手法では、rootと呼ばれる「生きていることが分かっているオブジェクト」から始めて、 リンクをたどることで到達可能なオブジェクトを「生きている」と判定している。 生きているオブジェクト以外のオブジェクトはすなわち「死んでいる」わけだ。 ところが、GCがスキャンしている最中にほかのスレッドがオブジェクトの中身を書き換えてしまうと、 正確にスキャンできない。死んだはずのオブジェクトを生きていると判定するのは別に実害はないが、 生きているオブジェクトを死んでいると判定するのは非常にまずい。

これを避けるにはふたつの方法が知られている。

• GCが始まったら他のスレッドを全部止める
• 他のスレッドが書き換えたオブジェクト(を含むページ)にマークをつけ、スキャンをやりなおす

前者は簡単だが、GCのために毎回スレッドが全部止まってしまうようでは、処理効率が下がってしまい、 せっかくのスレッドの意味がなくなりかねない。多くの実装ではスレッドに「止まれ」と命令しても 次の「停止できる場所」に到達するまでは止まってくれないので、待ち合わせが必要になるし、 GCは思ったより頻繁に起きるものだし。

後者は オブジェクトのスキャンをやりなおしている間にまたマークがつけられてしまうと いつまでたっても回収が行えないことを考えると、実装が複雑になってしまう。 マークにpage protectionのような方法を使うと移植性が下がってしまうし。

そこで、世代別GCでminor collectionではスレッド間の協調なしに オブジェクトの回収ができるアルゴリズムがあれば、 スレッド環境下でも性能が維持できるのではないかと考えたのだが(まだ続く)。

あー、でもスクリプト言語では性能はあまり問題にならないと自分で書いたのだったな。