-クラシック関数CompareExchange。
-SpinWait
-volatile（メモリバリアとして使用）
ConcurrentQueueは、リングバッファ構造に基づいています。
リングバッファ
リングバッファは、キューデータ構造（FIFO）の実装に最適です。
データの配列と2つのポインター-開始（開始）と終了（終了）に基づいています。
主に2つの操作があります。
- プッシュ -最後に追加します。 バッファに新しい要素を追加すると、終了カウンタが1増加し、新しい要素がその場所に書き込まれます。 配列の上限で「休止」した場合、終了値はリセットされ（配列の先頭に「移動」）、要素は配列の先頭に書き込まれ始めます。 終了インデックスが開始インデックスに達するまで書き込みが可能です。
- ポップ -最初にアイテムを選択します。 要素の選択は開始要素から行われ、終了に達するまで値が連続的に増加します。 サンプリングは、開始インデックスが終了インデックスに達するまで可能です。
ブロックリングバッファ
ConcurrentQueueは、従来のリングバッファーよりも少し複雑です。 その実装では、セグメント（セグメント）の概念が使用されます。 ConcurrentQueueは、（単方向の）セグメントのリンクリストで構成されます。 セグメントサイズは32です。
private class Segment { volatile VolatileBool[] m_state; volatile T[] m_array; volatile int m_low; volatile int m_high; volatile Segment m_next; }
最初に、ConcurrentQueueに1つのセグメントが作成されます
必要に応じて、新しいセグメントが右側に追加されます。
結果は、単方向のリンクリストです。 リンクリストの先頭はm_head、末尾はm_tailです。 制限事項：
- m_headセグメントでは、左側に空のセルのみを配置できます。
- m_tailセグメントの右側にのみ空のセルを含めることができます
- m_head = m_tailの場合、空のセルは左側と右側の両方にあります。
- セグメントでは、m_headとm_tailの間に空のセルは存在できません。
アイテムの追加（エンキュー）
以下は、要素をセグメントに追加するためのアルゴリズムの例です。
- M_highは1ずつ増加します
- インデックスm_highを使用して、新しい値がm_array配列に書き込まれます。
index = Interlocked.Increment(ref this.m_high); if (index <= 31) { m_array[index] = value; m_state[index].m_value = true; }
m_state-セルの状態の配列。trueの場合-要素はセルに書き込まれ、falseの場合-まだではありません。 実際、これは一種の「コミット」レコードです。 Interlocked.Incrementインデックスを増やしてからm_array [index] = valueの値を書き込む操作の間、別のスレッドが要素を読み取らないようにする必要があります。 次に、実行後にデータが読み込まれます。
while (!this.m_state[index].m_value) spinWait2.SpinOnce();
新しいセグメントの追加（Segment.Grow）
現在のセグメントのm_highが31になるとすぐに、現在のセグメントへの書き込みが停止され、新しいセグメントが作成されます（現在のセグメントは引き続き有効です）。
m_next = new ConcurrentQueue<T>.Segment(this.m_index + 1L, this.m_source); m_source.m_tail = this.m_next;
m_next-次のセグメントへのリンク
m_source.m_tail-セグメントのリストの最後のセグメントをリンクします。
要素の選択（TryDequeue）
キューからの要素の選択は、2つの基本的な機能に基づいています。
- Interlocked.CompareExchangeは、変数の値が比較値と等しい場合に変数の値を書き込むアトミック操作です。
public static extern int CompareExchange(ref int location1, int value, int comparand);
- MSDNのSpinWait
System.Threading.SpinWaitは軽量の同期タイプで、低レベルのシナリオで使用して、カーネルイベントに必要な高価なコンテキストスイッチとカーネル遷移を回避できます。 マルチコアコンピューターでは、リソースが長期間保持されないことが予想される場合、待機スレッドが数十または数百サイクルの間ユーザーモードでスピンしてから、リソースの取得を再試行する方が効率的です。 。 スピン後にリソースが使用可能になった場合、数千サイクルを節約できました。 リソースがまだ利用できない場合、数サイクルしか費やしておらず、カーネルベースの待機に入ることができます。 この回転して待機する組み合わせは、2フェーズ待機操作と呼ばれることもあります。
サンプル操作の近似アルゴリズム：
- m_lowを取得する
- CompareExchangeを使用してm_lowを1増やす
- m_lowが31より大きい場合-次のセグメントに進みます
- インデックスm_lowを持つ要素のコミット（m_state [low] .m_value）を待ちます。
SpinWait spinWait1 = new SpinWait(); int low = this.Low; if (Interlocked.CompareExchange(ref this.m_low, low + 1, low) == low) { SpinWait spinWait2 = new SpinWait(); while (!this.m_state[low].m_value) spinWait2.SpinOnce(); result = this.m_array[low];
カウントvs IsEmpty
IsEmptyコード：
ConcurrentQueue<T>.Segment segment = this.m_head; if (!segment.IsEmpty) return false; if (segment.Next == null) return true; SpinWait spinWait = new SpinWait(); for (; segment.IsEmpty; segment = this.m_head) { if (segment.Next == null) return true; spinWait.SpinOnce(); } return false;
つまり 実際、これは最初の空でないセグメントを見つけることです。 見つかった場合、キューは空ではありません。
カウントコード：
ConcurrentQueue<T>.Segment head; ConcurrentQueue<T>.Segment tail; int headLow; int tailHigh; this.GetHeadTailPositions(out head, out tail, out headLow, out tailHigh); if (head == tail) return tailHigh - headLow + 1; return 32 - headLow + 32 * (int) (tail.m_index - head.m_index - 1L) + (tailHigh + 1);
実際、最初と最後のセグメントを検索し、これら2つのセグメントに基づいて要素の数を計算します。
結論-カウント操作はIsEmptyよりも多くのプロセッサー時間を必要とします。
スナップショットとGetEnumerator
ConcurrentQueueフレームワークは、スナップショットテクノロジーをサポートして、要素の完全なセットを提供します。
整数データは以下を返します：
- トーアレイ
- ICollection.CopyTo
- Getenumerator
上記の演算子はロックなしでも機能し、カウンターを導入することで整合性が実現します。
volatile int m_numSnapshotTakers
キュー全体内-現在の時点でスナップショットを操作している操作の数。 つまり 完全な画像を取得する各操作では、次のコードを実装する必要があります。
Interlocked.Increment(ref this.m_numSnapshotTakers); try { ...// } finally { Interlocked.Decrement(ref this.m_numSnapshotTakers); }
これに加えて、デキュー操作のみが変更を「書き込む」ため、キュー要素へのリンクを削除する必要性のみをチェックします。
if (this.m_source.m_numSnapshotTakers <= 0) this.m_array[low] = default (T);