参照カウント

問題

使用されなくなったオブジェクトを破棄する。

コンテキスト

多くの場合、オブジェクトが将来使用されないことが分かっているときは、オブジェクトを破棄することが望まれます。参照カウントは、注意深く行えば並列プログラミングに拡張できる一般的なシリアル・ソリューションです。

影響

ソリューション

スレッドセーフな参照カウントは、インクリメント/デクリメントがアトミックに行われ、デクリメントと「カウントがゼロかどうか」のテストを単一のアトミック操作として行う必要があることを除いて、シリアル参照カウントに似ています。次のサンプルはこのために tbb::atomic<int> を使用しています。

template<typename T>
class counted {
   tbb::atomic<int> my_count;
   T value;
public:
   // 単一の参照でオブジェクトを構築
   counted() {my_count=1;}
   // 参照を追加
   void add_ref() {++my_count;}
   // 参照を削除して最後の参照だった場合は true を返す
   bool remove_ref() {return ‐‐my_count==0;}
   // オブジェクトへの参照を取得
   T& get() {
       assert(my_count>0);
       return my_value;
   }
};

カウントがゼロかどうかをテストするために個別の読み取りを使用することは正しくありません。次のコードは remove_ref() メソッドの正しくない実装です。2 つのスレッドがデクリメントを実行して my_count の読み取りがどちらもゼロになった場合、2 つの呼び出し元はどちらも最後の参照を削除したと誤って伝えられます。

      ‐‐my_count;
      return my_count==0. // 間違い!

オブジェクトが削除される前にすべての保留中の書き込みが完了するように、デクリメントには release フェンスを用いる必要があります。

参照カウントが非常に小さな場合、コピーと参照カウントのインクリメントとの間にはタイミング的な問題があるため、アトミックにポインターをコピーしてその参照カウントをインクリメントする単純な方法はありません。このため、別のスレッドがカウントをデクリメントしてオブジェクトを削除することになります。この問題に対応するには、「ハザードポインター」と「pass the buck」の 2 つの方法があります。詳細は、下記の参考資料を参照してください。

バリエーション

アトミック・インクリメント/デクリメントは、通常のインクリメント/デクリメントより桁を大きくすることができますが、よりコストがかかります。冗長なインクリメント/デクリメント操作をなくすシリアル最適化は、アトミックな参照カウントでより重要になります。

ポインターが共有されず対象が共有される場合、重み付けされた参照カウントを使用してコストを減らすことができます。各ポインターに weight (重み) を関連付けます。参照カウントは、重みの合計です。ポインター x は、x と x' 間の元の重みを分割することにより、参照カウントを更新しないで、ポインター x' としてコピーすることができます。x の重みが小さくなりすぎて分割できない場合、最初に定数 W を参照カウントと x の重みに追加します。

参考資料

D. Bacon および V.T. Rajan、"Concurrent Cycle Collection in Reference Counted Systems" in Proc. European Conf. on Object-Oriented Programming (June 2001)。サイクルを収集する参照カウントに基づくガベージコレクターについて説明。

M. Michael、"Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects" in IEEE Transactions on Parallel and Distributed Systems (June 2004)。「ハザードポインター」手法について説明。

M. Herlihy、V. Luchangco、および M. Moir、"The Repeat Offender Problem: A Mechanism for Supporting Dynamic-Sized, Lock-Free Data Structures" in Proceedings of the 16th International Symposium on Distributed Computing (Oct. 2002)。「pass the buck」手法について説明。

親トピック: デザインパターン