1

MP/MCキューをロックフリーまたは待機フリーに書き込む方法に関するドキュメントを探しています。.Net4.0を使用しています。多くのC++コードが見つかりましたが、私はメモリモデルにあまり詳しくないため、C＃への移植中にいくつかのバグを導入する可能性があります。

4

3 に答える 3

3

考慮すべきオプションとして、DmitryVyukovによる制限付きMultipleProducerMultipleConsumerキューのアルゴリズムがあります。アルゴリズムを.NETに移植しました。ソースは、githubにあります。とても速いです。

エンキューアルゴリズム：

public bool TryEnqueue(object item)
{
    do
    {
        var buffer = _buffer; // prefetch the buffer pointer
        var pos = _enqueuePos; // fetch the current position where to enqueue the item
        var index = pos & _bufferMask; // precalculate the index in the buffer for that position
        var cell = buffer[index]; // fetch the cell by the index
        // If its sequence wasn't touched by other producers
        // and we can increment the enqueue position
        if (cell.Sequence == pos && Interlocked.CompareExchange(ref _enqueuePos, pos + 1, pos) == pos)
        {
            // write the item we want to enqueue
            Volatile.Write(ref buffer[index].Element, item);
            // bump the sequence
            buffer[index].Sequence = pos + 1;
            return true;
        }

        // If the queue is full we cannot enqueue and just return false
        if (cell.Sequence < pos)
        {
            return false;
        }

        // repeat the process if other producer managed to enqueue before us
    } while (true);
}

デキューアルゴリズム：

public bool TryDequeue(out object result)
{
    do
    {
        var buffer = _buffer; // prefetch the buffer pointer
        var bufferMask = _bufferMask; // prefetch the buffer mask
        var pos = _dequeuePos; // fetch the current position from where we can dequeue an item
        var index = pos & bufferMask; // precalculate the index in the buffer for that position
        var cell = buffer[index]; // fetch the cell by the index
        // If its sequence was changed by a producer and wasn't changed by other consumers
        // and we can increment the dequeue position
        if (cell.Sequence == pos + 1 && Interlocked.CompareExchange(ref _dequeuePos, pos + 1, pos) == pos)
        {
            // read the item
            result = Volatile.Read(ref cell.Element);
            // update for the next round of the buffer
            buffer[index] = new Cell(pos + bufferMask + 1, null);
            return true;
        }

        // If the queue is empty return false
        if (cell.Sequence < pos + 1)
        {
            result = default(object);
            return false;
        }

        // repeat the process if other consumer managed to dequeue before us
    } while (true);
}
于 2016-12-13T14:21:48.640 に答える
2

なぜロックフリーキューが必要だと思いますか？を使用してみましたかConcurrentQueue<T>、おそらくで囲まれていBlockingCollection<T>ますか？

マルチスレッドコードを書くのは難しいです。ロックフリーコードを書くことはさらに難しく、本当に必要な場合を除いて、自分で書くべきではありません。

于 2011-05-20T23:01:12.477 に答える
1

私が最初に行うのはConcurrentQueue<T>ですが、データストアをインターフェイスの背後に抽象化して、実装を簡単に変更できるようにすることができます。次に、典型的なシナリオのベンチマークを行い、どこで問題が発生するかを確認します。覚えておいてください：時期尚早の最適化はすべての悪の根源です。実装ではなく契約に関連付けられるようにシステムを設計してください。そうすれば、必要なすべての実装を最適化できます。

私はConcurrentQueue<T>ILSpyを見てみましたが、一見ロックフリーの実装のようです。まさにあなたが探しているものである可能性が高いです。

于 2011-05-20T23:51:34.490 に答える