10

これは以前に尋ねられたことを知っています (そして私は調査を続けます) が、特定のリンクリスト機能をスレッドセーフな方法で作成する方法を知る必要があります。私の現在の問題は、リンクされたリスト内のすべての要素をループする 1 つのスレッドがあり、別のスレッドがこのリストの最後にさらに要素を追加する可能性があることです。1 つのスレッドが別の要素をリストに追加しようとしているときに、最初のスレッドがその要素を繰り返し処理している間に、例外が発生することがあります。

リストが現在反復処理中でビジー状態であることを示す変数 (ブール値フラグ) を追加することだけを考えていましたが、それを確認して 2 番目のスレッドで待機するにはどうすればよいでしょうか (最初のスレッドが実行されるので、待機しても問題ありません)。かなり早く）。これを行う唯一の方法は、このビジー フラグを常にチェックする while ループを使用することです。これは非常にばかげた考えであることに気付きました。何も役に立たないのに CPU が一生懸命働く原因になるからです。そして今、私はより良い洞察を求めるためにここにいます。ロックなどについて読んだことがありますが、私の場合は関係ないようですが、間違っているのでしょうか?

その間、私はインターネットを検索し続け、解決策が見つかったら投稿します。

編集:問題を解決するためにコードを投稿する必要があるかどうかを教えてください。ただし、より明確に説明しようとします。

そのため、処理が必要な要素を含むリンクリストを持つクラスがあります。関数呼び出しを介してこのリストを反復処理するスレッドが 1 つあります (「processElements」と呼びましょう)。非決定的な方法で処理する要素を追加する 2 番目のスレッドがあります。ただし、processElements の実行中にこの addElement 関数を呼び出そうとする場合があります。これは、要素が最初のスレッドによって繰り返されている間に、リンクされたリストに追加されていることを意味します。これは不可能であり、例外が発生します。これで解決することを願っています。

processElements メソッドの実行が完了するまで、生成する新しい要素を追加するスレッドが必要です。

  • この問題につまずく人へ。受け入れられた回答は、迅速で簡単な解決策を提供しますが、より包括的な回答については、以下のブライアン・ギデオンの回答を確認してください。これにより、より多くの洞察が得られます!
4

2 に答える 2

28

例外は、反復の途中でコレクションが変更された結果である可能性がありますIEnumerator。スレッドセーフを維持するために使用できるテクニックはほとんどありません。難しい順に紹介します。

すべてをロック

これは、スレッドセーフなデータ構造にアクセスするための最も簡単で簡単な方法です。このパターンは、読み取り操作と書き込み操作の数が等しく一致する場合にうまく機能します。

LinkedList<object> collection = new LinkedList<object>();

void Write()
{
  lock (collection)
  {
    collection.AddLast(GetSomeObject());
  }
}

void Read()
{
  lock (collection)
  {
    foreach (object item in collection)
    {
      DoSomething(item);
    }
  }
}

コピー読み取りパターン

これは少し複雑なパターンです。データ構造を読み取る前に、データ構造のコピーが作成されることに気付くでしょう。このパターンは、読み取り操作の数が書き込みの数に比べて少なく、コピーのペナルティが比較的小さい場合にうまく機能します。

LinkedList<object> collection = new LinkedList<object>();

void Write()
{
  lock (collection)
  {
    collection.AddLast(GetSomeObject());
  }
}

void Read()
{
  LinkedList<object> copy;
  lock (collection)
  {
    copy = new LinkedList<object>(collection);
  }
  foreach (object item in copy)
  {
    DoSomething(item);
  }
}

コピー - 変更 - スワップ パターン

最後に、最も複雑でエラーが発生しやすいパターンを示します。自分が何をしているのかを本当に理解していない限り、このパターンを使用することは実際にはお勧めしません。以下の内容から逸脱すると、問題が発生する可能性があります。これを台無しにするのは簡単です。実際、私は過去にうっかりこれを台無しにしてしまいました。すべての変更の前に、データ構造のコピーが作成されていることがわかります。次にコピーが変更され、最後に元の参照が新しいインスタンスと交換されます。基本的に、私たちは常にcollection不変であるかのように扱っています。このパターンは、書き込み操作の数が読み取りの数に比べて少なく、コピーのペナルティが比較的小さい場合にうまく機能します。

object lockobj = new object();
volatile LinkedList<object> collection = new LinkedList<object>();

void Write()
{
  lock (lockobj)
  {
    var copy = new LinkedList<object>(collection);
    copy.AddLast(GetSomeObject());
    collection = copy;
  }
}

void Read()
{
  LinkedList<object> local = collection;
  foreach (object item in local)
  {
    DoSomething(item);
  }
}

アップデート：

そこで、コメント セクションで次の 2 つの質問をしました。

  • なぜ書き込み側ではlock(lockobj)なく？lock(collection)
  • なぜlocal = collection読み取り側で？

最初の質問に関しては、C# コンパイラがlock.

void Write()
{
  bool acquired = false;
  object temp = lockobj;
  try
  {
    Monitor.Enter(temp, ref acquired);
    var copy = new LinkedList<object>(collection);
    copy.AddLast(GetSomeObject());
    collection = copy;
  }
  finally
  {
    if (acquired) Monitor.Exit(temp);
  }
}

collectionこれで、ロック式として使用した場合に何がうまくいかないかを簡単に確認できることを願っています。

  • スレッド A が実行されobject temp = collectionます。
  • スレッド B が実行されcollection = copyます。
  • スレッド C が実行されobject temp = collectionます。
  • スレッド A は、元の参照でロックを取得します。
  • スレッド C は、新しい参照でロックを取得します。

明らかにこれは悲惨なことです！クリティカル セクションが複数回入力されるため、書き込みが失われます。

さて、2 番目の質問は少しトリッキーでした。上記で投稿したコードで必ずしもこれを行う必要はありません。でも、それはcollection一度しか使っていないからです。次のコードを考えてみましょう。

void Read()
{
  object x = collection.Last;
  // The collection may get swapped out right here.
  object y = collection.Last;
  if (x != y)
  {
    Console.WriteLine("It could happen!");
  }
}

ここでの問題はcollection、いつでも交換できることです。これは、見つけるのが非常に難しいバグです。これが、このパターンを実行するときに常に読み取り側でローカル参照を抽出する理由です。これにより、各読み取り操作で同じコレクションを使用していることを確認できます。

繰り返しますが、このような問題は非常に微妙なので、本当に必要でない限り、このパターンを使用することはお勧めしません。

于 2012-05-11T19:00:08.220 に答える
6

ロックを使用してリストへのアクセスを同期する方法の簡単な例を次に示します。

private readonly IList<string> elements = new List<string>();

public void ProcessElements()
{
    lock (this.elements)
    {
        foreach (string element in this.elements)
            ProcessElement(element);
    }
}

public void AddElement(string newElement)
{
    lock (this.elements)
    {
        this.elements.Add(element);
    }
}

lock(o)ステートメントとは、実行中のスレッドがオブジェクトの相互排他ロックを取得しo、ステートメント ブロックを実行し、最後にロックを解放する必要があることを意味しoます。o別のスレッドが (同じコード ブロックまたは他のコード ブロックに対して) 同時にロックを取得しようとすると、ロックが解放されるまでブロック (待機) します。

したがって、重要な点は、lock同期するすべてのステートメントに同じオブジェクトを使用することです。一貫性がある限り、使用する実際のオブジェクトは任意です。上記の例では、コレクションを読み取り専用として宣言しているため、ロックとして安全に使用できます。ただし、そうでない場合は、別のオブジェクトをロックする必要があります。

private IList<string> elements = new List<string>();

private readonly object syncLock = new object();

public void ProcessElements()
{
    lock (this.syncLock)
    {
        foreach (string element in this.elements)
            ProcessElement(element);
    }
}

public void AddElement(string newElement)
{
    lock (this.syncLock)
    {
        this.elements.Add(element);
    }
}
于 2012-05-11T18:48:17.577 に答える