c＃効率的なスレッドセーフキューConcurrentQueue

C Efficient Thread Safety Queue Concurrentqueue

Enqueue、Dequeue、IsEmpty、キュー内の要素の数（カウント）を取得します。

まず、ConcurrentQueueの内部構造：

1.実装の原則

ご存知のとおり、一般的な非スレッドセーフキューには2つの実装があります。

1.配列を使用して実装された循環キュー。

2.リンクリストを使用して実装されたキュー。

まず、2つの方法の長所と短所を見てください。

.Net Farmeworkでの共通キューQueueの実装では、最初の方法を使用します。欠点は、キュースペースが不足している場合、拡張が実行されることです。拡張の主な実装は、元の長さが2倍の新しい配列を開き、元の配列のデータをコピーすることです。新しいアレイでは、拡張時に小さなメモリオーバーヘッドが発生することはなく、並行環境でのパフォーマンスへの影響を過小評価することはできません。もちろん、Queueのコンストラクターを呼び出すときに、デフォルトのスペースのサイズを指定できます。ただし、通常の状況では、データの量は予測できません。大きいものを選ぶと、スペースの無駄になります。小さいものを選択すると、メモリをコピーするためのオーバーヘッドが発生するため、拡張後にキューを拡張する必要があります。 TrimToSize（）メソッドは、未使用のメモリスペースを再利用するために呼び出されます。

リンクリストの2番目の実装は、スペースの浪費の問題を排除しますが、GCの圧力を高めます。キューに入ると、新しいノードが割り当てられます。キューがデキューされると、ノードは破棄されます。多数のデキュー操作の場合、この実装はあまり効率的ではありません。

上記の2つの実装を組み合わせることで、ConcurrentQueueは、複数のスレッドをサポートし、チームにチームを発行するときに、セグメント化されたストレージの概念を使用します（上の図を参照）。 ConcurrentQueueは、1つのセグメントのセグメント単位でメモリを割り当てます。内部には、デフォルトの長さが32の配列と、次のセグメントを実行するためのポインタが含まれています。開始セグメントと終了セグメントをそれぞれ指すヘッドポインタとテールポインタがあります。この構造は、オペレーティングシステムのセグメントメモリ管理とページメモリにいくぶん似ています。管理戦略）。この方法でメモリを割り当てると、GCの負荷が軽減されるだけでなく、呼び出し元はTrimToSize（）メソッドを使用してメモリを表示しません。 （メモリの特定のセグメントが空になると、GCはメモリのセグメントを再利用します）。

2.セグメント内部構造

実際、ConcurrentQueueの操作は、実際にはセグメントの操作です。

セグメントは、次のデータ構造を抽象化できます。

セグメント内の主なメソッド：

セグメントの内部は、配列によって実装される通常のキューと同等ですが、アトミック操作を使用してエンキューおよびデキュー操作のマルチスレッド競合の問題を防止し、ランダムな譲歩などの手法を使用してlivelock、および実装メカニズムとConcurrentStackはそれほど違いはありません。多くのTryAppendsの実装の詳細は、ソースコメントで非常に明確です。ここではこれ以上の説明はありません。

第二に、チームの運営

上の図に示すように、エンキュー操作は後続セグメントで実行されます。データがセグメントに失敗すると、最初にロールバック操作が実行され、成功するまで再試行されます。ここで失敗する理由（tail.Append（item）はfalseを返します。1つだけは、セグメント内のスペースが十分でない場合、新しいセグメントが割り当てられ、その間にセグメントに入る要素が失敗するためです。

第三に、チーム運営

上図に示すように、チームが失敗すると、チームのように巻き戻すのではなく、falseを返します。チームが失敗する理由は、キュー内のすべての要素が空になると、チームがブール値を返すように設計されているためです。値の関数。

第四に、それが空であるかどうかを判断します（IsEmpty）

全体的な判断は、O（1）の複雑さです。 3つの主な状況があります。

1.ヘッドノード（セグメント）がnullではなく、falseを返します

2.ヘッドノードが空で、次のノードも空でtrueを返します

3.ヘッドノードは空で、次のノードは空ではなく、falseを返します。これは、キューが拡張されていることを示しているため、拡張が再度判断を完了するまで待つ必要があります。

5、キュー内の要素の数を取得します（カウント）

ヘッドノードの低い位置とテールノードの高い位置を見つけます。キュー内の現在のセグメントのインデックスが各セグメントに記録されるため、キュー全体の要素数を簡単に見つけることができます。

ConcurrentStackと同様に、Microsoftの公式ドキュメントとコメントでも、キューが空かどうかを判断するには、Count == 0をカウントする代わりに、IsEmpty属性を使用することが示されています。理由は、GetHeadTailPositionsがヘッドノードとテールノードの位置を検索するためです。大量のデータを登録およびデキューするプロセス。ヘッドノードとテールノードの位置を決定するために継続的にループするための時間のかかる操作。キューが空であるかどうかを判断するか、IsEmpty属性を使用します。