MSDNのSimplePriorityQueueサンプルの重大なバグ

Question

同時プライオリティキューを使用する必要があり、MSDNのHow to: Add Bounding and Blocking Functionality to a CollectionチュートリアルのSimplePriorityQueue<TPriority, TValue>サンプルを適用することを検討していました。しかし、私は、そのサンプルが持つと思われるバグの重大さに驚いた。誰かがこれらの問題が本当に存在するかどうかを検証できますか？

1）レースハザードがArgumentException後者からスローさせることができるTryAddとToArray、間に存在します。 TryAddメソッドは、最初に項目を内部キューに追加してから、m_countカウンタをインクリメントします。一方、ToArrayは、最初にサイズm_countの新しい配列を初期化し、内部配列をこの配列にコピーします。 ToArrayが実行されているときにTryAddが呼び出された場合、ToArrayは、CopyToコールがArgumentExceptionをスローする原因となる、配列内のスペースを割り当てた以上のアイテムのコピーを試みる可能性があります。

private ConcurrentQueue<KeyValuePair<int, TValue>>[] _queues; 
private int m_count; 

// ... 

// IProducerConsumerCollection members 
public bool TryAdd(KeyValuePair<int, TValue> item) 
{ 
    _queues[item.Key].Enqueue(item); 
    Interlocked.Increment(ref m_count); 
    return true; 
}  

public int Count 
{ 
    get { return m_count; } 
} 

public KeyValuePair<int, TValue>[] ToArray() 
{ 
    KeyValuePair<int, TValue>[] result; 

    lock (_queues) 
    { 
     result = new KeyValuePair<int, TValue>[this.Count]; 
     // *** context switch here; new item gets added *** 
     int index = 0; 
     foreach (var q in _queues) 
     { 
      if (q.Count > 0) 
      { 
       q.CopyTo(result, index); // *** ArgumentException *** 
       index += q.Count; 
      } 
     } 
     return result; 
    } 
} 

2）別のレースの危険はGetEnumerator方法に存在します：内部キューへの更新の間の同期はありません。

public IEnumerator<KeyValuePair<int, TValue>> GetEnumerator() 
{ 
    for (int i = 0; i < priorityCount; i++) 
    { 
     foreach (var item in _queues[i]) 
      yield return item; 
    } 
} 

キューからアイテムを取り、インクリメント優先でそれを再追加し、次のコードスニペット、考えてみましょう：上記のスニペットを列挙して同時に実行された場合は、1が期待する

if (queue.TryTake(out item) && item.Key < maxPriority - 1) 
    queue.TryAdd(new KeyValuePair<int, string>(item.Key + 1, item.Value)) 

をアイテムは、元のアイテムまたは増分された優先度のいずれかで最大で1回表示されるか、場合によってはまったく表示されません。その商品がの2倍のの優先度で表示されるとは思わないでしょう。ただし、GetEnumeratorは内部キューを順番に反復処理するため、キュー全体でこのような順序の不一致を防ぎません。それは、任意のメモリフェンスなし共有m_countフィールドを読み取るため

3）パブリックCount性は、古くなった値を返すことができます。コンシューマが以下のような独自のメモリフェンスを生成しないループでこのプロパティにアクセスすると、他のスレッドによってアイテムがキューに追加されているにもかかわらず、無限ループに陥る可能性があります。

while (queue.Count == 0) 
{ } 

共有変数を読み取るときは、いくつかの他の記事で議論されたメモリフェンスの必要性：

• How to correctly read an Interlocked.Increment'ed int field?
• Reading an int that's updated by Interlocked on other threads
• Do concurrent interlocked and reads require a memory barrier or locking?

4） THER eは、_queuesアレイの初期化とSimplePriorityQueueコンストラクタの完了との間のメモリバリアではありません。競合の危険は、別のスレッドの外部消費者がTryAddと呼び出し、_queuesにアクセスしてからにアクセスすると発生する可能性があります（またはメモリキャッシュに完了したと表示されます）。これは、constructors and memory barriersの私の他の質問でさらに議論されています。

5）TryTakeとToArrayはlockキーワードの使用によって保護されています。不十分であることとは別に（上記で説明したバグのために）、これは並行コレクションの設計の全目的を破っています。その短所を考えると、内部の構造体を平文Queueにダウングレードし、どこにいてもロックを追加し、これを並行ではなくスレッドセーフな構造として扱うことが最善のアプローチだと思います。

Answer 1

私はそれがあなたのクラスをどのように使用するかによって決まると思います。自分自身をTryAddとTryTake（これは2つの主なものであるBlockingCollection<T>に依存しています）に制限した場合、問題はなく、非常に速いロックの最小優先度キューがあります。

Count、CopyTo、または他の方法のいずれかを使用して開始する場合は、あなたが指摘した問題を実行する可能性があります。