参照カウント

問題

オブジェクトが使用されなくなったら破棄します。

コンテキスト

将来使用されないことが判明している場合、オブジェクトを破棄することが望ましいことがあります。参照カウントは、慎重に実行すれば並列プログラミングにも拡張できる一般的なシリアル・ソリューションです。

強制

• 参照の循環がある場合、その循環を明示的に解除しない限り、基本的な参照カウントでは十分ではありません。

• アトミックカウントはハードウェア的には比較的高コストです。

解決方法

スレッドセーフな参照カウントはシリアル参照カウントに似ていますが、インクリメント/デクリメントがアトミックに実行され、デクリメントと「カウントがゼロか?」のテストが、単一のアトミック操作で動作する必要がある点が異なります。次の例では、std::atomic<int> を使用してこれを実現します。

template<typename T> 
class counted { 
    std::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; 
    } 
};

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

--my_count; 
return my_count==0.// 誤り!

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

ポインターをアトミックにコピーして参照カウントをインクリメントする簡単な方法はありません。参照カウントが低すぎる場合、コピーとインクリメントの間にタイミングのギャップが生じ、別のスレッドがカウントをゼロに減らしてオブジェクトを削除する可能性があります。この問題に対処する方法は 2 つあり、「ハザードポインター」と「責任転嫁」です。詳細については、以下の参考資料を参照してください。

バリエーション

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

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

参考資料

D. Bacon and 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, and 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). 「責任転嫁」手法について説明します。