8

現在、コピー オン ライト セットの実装を検討しており、それがスレッド セーフであることを確認したいと考えています。そうでない可能性がある唯一の方法は、コンパイラーが特定のメソッド内でステートメントを並べ替えることが許可されている場合であると確信しています。たとえば、Removeメソッドは次のようになります。

public bool Remove(T item)
{
    var newHashSet = new HashSet<T>(hashSet);
    var removed = newHashSet.Remove(item);
    hashSet = newHashSet;
    return removed;
}

hashSet が次のように定義されている場所

private volatile HashSet<T> hashSet;

だから私の質問は、 hashSet がメンバー変数への書き込みの前に新しいセットで発生するvolatileことを意味するのでしょうか? Removeそうでない場合、削除が行われる前に他のスレッドがセットを参照する可能性があります。

本番環境でこれに関する問題は実際に見たことがありませんが、安全であることが保証されていることを確認したいだけです.

アップデート

より具体的には、を取得する別の方法がありますIEnumerator。

public IEnumerator<T> GetEnumerator()
{
    return hashSet.GetEnumerator();
}

したがって、より具体的な質問は次のとおりです。返されたものが削除からIEnumerator決してスローしないという保証はありますか?ConcurrentModificationException

更新 2

申し訳ありませんが、回答はすべて複数のライターからのスレッドセーフに対処しています。良い点が挙げられていますが、それは私がここで見つけようとしているものではありません. コンパイラが操作を次のように並べ替えることができるかどうかを知りたいですRemove。

    var newHashSet = new HashSet<T>(hashSet);
    hashSet = newHashSet;                  // swapped
    var removed = newHashSet.Remove(item); // swapped
    return removed;

これが可能である場合、割り当てられたGetEnumerator後、削除される前にスレッドが呼び出すことができることを意味し、列挙中にコレクションが変更される可能性があります。hashSetitem

Joe Duffy には、次のようなブログ記事があります。

ロード時に揮発性とは、ACQUIRE を意味し、それ以上でもそれ以下でもありません。(もちろん、ループ外で巻き上げを許可しないなど、追加のコンパイラー最適化制限がありますが、ここでは MM の側面に焦点を当てましょう。) ACQUIRE の標準的な定義は、後続のメモリ操作が ACQUIRE 命令の前に移動しない可能性があることです。たとえば、{ ld.acq X, ld Y } が与えられた場合、ld Y は ld.acq X の前に発生することはできません。たとえば、{ ld X, ld.acq Y } の場合、ld.acq Y は実際に ld X の前に発生する可能性があります。これが実際に発生する唯一のプロセッサ Microsoft .NET コードが現在実行されているのは IA64 ですが、これは注目すべき領域です。 CLR の MM は、ほとんどのマシンよりも弱いです。次に、.NET 上のすべてのストアは RELEASE です (揮発性に関係なく、つまり、揮発性は jitted コードの観点からノーオペレーションです)。RELEASE の標準的な定義は、以前のメモリ操作は RELEASE 操作の後に移動できないというものです。たとえば、{ st X, st.rel Y } が与えられた場合、st.rel Y は st X の前に発生することはできません。たとえば、{ st.rel X, ld Y } が与えられた場合、ld Y は st.rel X の前に移動できます。

私がこれを読む方法は、 への呼び出しにnewHashSet.Removeは が必要でld newHashSetあり、 への書き込みにhashSetは が必要であるということst.rel newHashSetです。上記の RELEASE の定義から、ストア RELEASE の後にロードを移動することはできないため、ステートメントを並べ替えることができません。私の解釈が正しいことを確認してください。

4

3 に答える 3

3

Interlocked.Exchangeの使用を検討してください- 順序付けが保証されるか、Interlocked.CompareExchangeの副次的な利点として、コレクションへの同時書き込みを検出 (および潜在的に回復) できるようになります。明らかに、追加レベルの同期が追加されるため、現在のコードとは異なりますが、理由を説明するのは簡単です。

public bool Remove(T item) 
{ 
    var old = hashSet;
    var newHashSet = new HashSet<T>(old); 
    var removed = newHashSet.Remove(item); 
    var current = Interlocked.CompareExchange(ref hashSet, newHashSet, old);
    if (current != old)
    {
       // failed... throw or retry...
    }
    return removed; 
}

volatile hashSetそして、この場合 でも必要になると思います。

于 2012-07-06T07:53:09.697 に答える
1

編集：

Removeの呼び出し（およびその他のコレクションの変更）に対する外部ロックの存在を明確にしていただきありがとうございます。

RELEASEセマンティクスのため、変数への値が割り当てられるhashSetまで、新しい値をに格納することはありません（以降は移動できないため）。removedst removedst.rel hashSet

したがって、の「スナップショット」動作はGetEnumerator、少なくとも、同様の方法で実装されたRemoveおよびその他のミューテーターに関しては意図したとおりに機能します。

于 2012-07-10T19:39:58.793 に答える
0

私は C# について話すことはできませんが、C では volatile は原則として、変数の内容がいつでも変更される可能性があることを示しているだけです。コンパイラや CPU の並べ替えに関する制約はありません。得られるのは、キャッシュされたバージョンを信頼するのではなく、コンパイラ/CPU が常にメモリから値を読み取ることだけです。

ただし、最近の MSVC (およびおそらく C#) では、volatile の読み取りはロードのメモリ バリアとして機能し、書き込みはストアのメモリ バリアとして機能します。たとえば、すべてのロードが完了するまで CPU が停止し、ロードがこれを回避することはありません。揮発性読み取りの下で並べ替えられます (ただし、後で独立した読み込みがメモリ バリアの上に移動する場合があります)。CPU は、ストアが完了するまで停止し、ストアは揮発性書き込みの下で並べ替えられることによってこれを回避できません (ただし、後で独立した書き込みがメモリ バリアの上に移動する可能性はあります)。

1 つのスレッドだけが特定の変数を書き込んでいる (ただし多くのスレッドが読み取りを行っている) 場合、正しい操作に必要なのはメモリ バリアだけです。複数のスレッドが特定の変数に書き込む可能性がある場合、アトミック操作を使用する必要があります。CPU の設計では、基本的に書き込み時に競合状態が発生し、書き込みが失われる可能性があるためです。

于 2012-07-06T09:16:06.123 に答える