2

.NETでコピーオンライトモデルを使用してスレッドセーフリストを作成する方法は?

以下は私の現在の実装ですが、スレッド化、メモリバリアなどについてたくさん読んだ後、ロックのないマルチスレッド化が関係する場合は注意が必要であることがわかりました。これが正しい実装であるかどうか、誰かがコメントできますか?

class CopyOnWriteList
{
    private List<string> list = new List<string>();

    private object listLock = new object();

    public void Add(string item)
    {
        lock (listLock)
        {
            list = new List<string>(list) { item };
        }
    }

    public void Remove(string item)
    {
        lock (listLock)
        {
            var tmpList = new List<string>(list);
            tmpList.Remove(item);
            list = tmpList;
        }
    }

    public bool Contains(string item)
    {
        return list.Contains(item);
    }

    public string Get(int index)
    {
        return list[index];
    }
}

編集

より具体的には、上記のコードはスレッドセーフですか、それとも何か追加する必要がありますか? また、最終的にすべてのスレッドで参照が変更されるのlistでしょうか? volatileまたは、リスト フィールドにキーワードを追加するか、Contains メソッドに参照へのアクセスとそのメソッドの呼び出しの間に Thread.MemoryBarrier を追加する必要がありますか?

たとえば、Java 実装は上記のコードのように見えますが、そのようなアプローチは .NET でもスレッドセーフですか?

そして、これは同じ質問ですが、Javaでもあります。

これに関連する別の質問があります。

4

3 に答える 3

0

Atomicity of variable referencesに従って、参照の割り当てがアトミックであるため、実装は正しいです。に追加volatileしlistます。

于 2013-06-28T15:26:57.637 に答える
0

あなたのアプローチは正しいように見えますが、データを保持するためにastring[]ではなく aを使用することをお勧めします。List<string>項目を追加するとき、結果のコレクションに含まれる項目の数が正確にわかっているため、正確に必要なサイズの新しい配列を作成できます。アイテムを削除するときは、list参照のコピーを取得して、コピーを作成する前にアイテムを検索できます。アイテムが存在しないことが判明した場合は、削除する必要はありません。存在する場合は、正確に必要なサイズの新しい配列を作成し、削除するアイテムの前後にあるすべてのアイテムを新しい配列にコピーできます。

考慮したいもう 1 つのことはint[1]、ロック フラグとして a を使用し、次のようなパターンを使用することです。

static string[] withAddedItem(string[] oldList, string dat)
{
  string[] result = new string[oldList.Length+1];      
  Array.Copy(oldList, result, oldList.Length);
  return result;
}
int Add(string dat) // Returns index of newly-added item
{
  string[] oldList, newList;
  if (listLock[0] == 0)
  {
    oldList  = list;
    newList = withAddedItem(oldList, dat);
    if (System.Threading.Interlocked.CompareExchange(list, newList, oldList) == oldList)
      return newList.Length;
  }
  System.Threading.Interlocked.Increment(listLock[0]);
  lock (listLock)
  {
    do
    {
      oldList  = list;
      newList = withAddedItem(oldList, dat);
    } while (System.Threading.Interlocked.CompareExchange(list, newList, oldList) != oldList);
  }
  System.Threading.Interlocked.Decrement(listLock[0]);
  return newList.Length;
}

書き込み競合がなければ、 はCompareExchangeロックを取得しなくても成功します。書き込み競合がある場合、書き込みはロックによってシリアル化されます。ここでのロックは、正確性を確保するために必要でも十分でもないことに注意してください。その目的は、書き込み競合が発生した場合のスラッシングを回避することです。スレッド #1 が最初の「if」テストを通過し、他の多くのスレッドが同時にリストを書き込んでロックの使用を開始しようとしている間に、タスクがタスク スイッチ アウトされる可能性があります。これが発生した場合、スレッド #1 は、独自のCompareExchange. このようなアクションの結果、lock-holding スレッドは新しい配列を作成するために時間を浪費する必要がありますが、そのような状況はめったに発生しないため、余分な配列コピーの時折のコストは問題になりません。

于 2013-10-04T18:03:27.130 に答える
0

はい、スレッドセーフです:

  1. Addとのコレクションの変更は別々のコレクションで行われるため、 /と/から/と/からRemove同じコレクションへの同時アクセスが回避されます。AddRemoveAddRemoveContainsGet

  2. 新しいコレクションの割り当ては、lockMonitor.Enter と のペアである 内で行われます。どちらもhereMonitor.Exitに記載されているように完全なメモリ バリアを実行します。つまり、ロック後にすべてのスレッドがフィールドの新しい値を監視する必要があります。list

于 2016-02-23T10:16:06.237 に答える