TrickDiary このページをアンテナに追加 RSSフィード Twitter

2009-09-12

[] 部分的なマーク・アンド・スイープ( Partial Mark and Sweep )の詳細について

昨晩、Twitter上で、循環参照問題*1を機械的に排除する方法について意見を求めたところ id:DigitalGhost さん( @DecimalBloat )から...

http://wiki.livedoor.jp/author_nari/d/GC/extend/Partial%20Mark%20and%20Sweep

...というものをご紹介頂いたのですが、「4.scan」の記述が非常に残念な状態になっています。

で、今日、たまたま id:DigitalGhost さんと名古屋でお会いすることになっていたので、これ幸いと id:DigitalGhost さんからその詳細を教えて頂きました。その際のメモを以下に残しておきます。

あるべき挙動のモデル

表記
表記説明
S1,S2,S3スタックからの参照
A,B,C,D循環参照を形成しているオブジェクト
X循環参照を形成しているオブジェクト群から参照されている外部のオブジェクト
吹き出しの数字それぞれのオブジェクトの被参照カウント
初期状態

f:id:wraith13:20090912220707p:image

スタックからの参照のひとつが切れるがまだ別のスタックからの参照が残っている状態

f:id:wraith13:20090912221159p:image

最後のスタックからの参照が切れる状態

f:id:wraith13:20090912221155p:image

循環参照オブジェクトが解放された状態

f:id:wraith13:20090912221146p:image

部分的なマーク・アンド・スイープ( Partial Mark and Sweep )での挙動

件のページと併せてご参照ください。

「4.scan」の記述が致命的なのは「4.scan」は実際には 「3. Mark Gray」と同様の「Mark Black」という操作と「whiten」操作をごっちゃに記述していることです。これらはそれぞれ...

Mark Black
Mark Gray と同様の操作を行なう。ただし非grayのオブジェクトをgrayに置き換えるのではなく、参照カウントが非0で且つgrayのオブジェクトをblackに置き換え、また参照カウントを -1 するのではなく代わりに +1 する。
Whiten
「Mark Black」を実施後、grayで且つ参照カウントが0のオブジェクトをwhiteにする。

...のようになります。*2


スタックからの参照のひとつが切れるがまだ別のスタックからの参照が残っている時の挙動

f:id:wraith13:20090912221159p:image:left

f:id:wraith13:20090912221435p:image


最後のスタックからの参照が切れた時の挙動

f:id:wraith13:20090912221155p:image:left

f:id:wraith13:20090912221430p:image


f:id:wraith13:20090912221146p:image

追記

微妙に解釈が間違っているようです。詳細はコメント欄を参照。

*1:スマートポインタを利用したシステムおいてプログラムからは一切アクセスされなくなったにも関わらず循環的に相互参照することで生き長らえてしまうオブジェクト群が発生する問題。リソースリークの一種。

*2:「Mark Black」も「Whiten」も便宜上そう勝手に呼称しているだけで正規のステップ名ではありません。

authorNariauthorNari 2009/09/15 14:04 wikiの作者です。
大変わかりやすい図で、素晴らしい解説だと思います。

さて、ご指摘の件ですが、確かに 4.scan はわかりづらいですね(汗)
この辺りは修正しておきます。すいません。。

しかし、ご指摘内容についてはちょっと理解しかねます。
まず、MarkBlackのあとにWhitenという処理は(このアルゴリズムでは)おこないません。
scanの時に一緒にやってしまいます。

この辺りは論文かRJGCを参照してもらうのがよいかと思います。
# オフレコですが今GC本を執筆中で、本が出版されたらそちらをご参照ください(とか宣伝してみる)

論文:Rafael D. Lins, Cyclic reference counting with lazy mark-scan,Information Processing Letters

wraith13wraith13 2009/09/19 01:59 レスが遅くなってすみません・・・また後でちゃんとしたレスします。m(_ _)m

wraith13wraith13 2009/09/23 19:16 随分と遅くなってしまいましたが・・・(汗


>しかし、ご指摘内容についてはちょっと理解しかねます。

最初は「4.scan」の部分を勝手な解釈で誤解とは言えそれなりに解釈していたのですが、そうではないことを id:DigitalGhost さんからご指摘頂きよく読み返したのですが、結局はぶっちゃけ「4.scan」の文章からは意味がよく理解できませんでした。すみません。(汗

# この手のアルゴリズムの解説は難しいですよね。アルゴリズムの雰囲気だけならともかく正確に伝えるためには図を多用しなければならなかったり、その図も理解しやすいようにいろいろ工夫しなければならなかったり。


>まず、MarkBlackのあとにWhitenという処理は(このアルゴリズムでは)おこないません。
>scanの時に一緒にやってしまいます。

Mark Black より先にやると余分に white にしてしまう箇所が出てくるのではないかと思いますが Mark Black によって結局の所 余分に white にしてしまった部分も black になるので問題ないとかそんな感じですかねぇ。


># オフレコですが今GC本を執筆中で、本が出版されたらそちらをご参照ください(とか宣伝してみる)

おおー、それは超期待です。今すぐにでも出版してください!
そもそものこのアルゴリズムの話題に至った理由が、プログラミング言語の自作をやってるとこでしてそのメモリ管理モデルの設計で循環参照問題をどうしたものかと悩んでいたのが始まりなものでそのような書籍があると非常に参考になります。

しかし、よくそんなニッチなテーマの書籍が企画を通りましたね。(^^;

# GC 系はどうしても RAII と相性がよくない(リソースのリリースタイミングが不定になる or 不必要に延長される)ので、いまはオーナーシップつき参照カウント方式スマートポインタ+ウィークポインタとかそんなモデルでいくつもりですが。
# 基本はウィークポインタを使うことで循環参照を回避し、ウィークポインタで回避されていない循環参照はオーナーシップを持っているオブジェクトが失われると同時に強制削除(強制削除される参照元の参照先は強制的に null にされる)する戦略。

authorNariauthorNari 2009/09/23 23:00 今すぐ出版できればいいのですが、それは難しそうですね(笑)。
プログラミング言語自作ですか!おー、それはすごい。
Wikiの方は暇になったら文章を直しておきます。
# 今はちょっと無理かもです(汗)

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/wraith13/20090912/1252762617