2

これは、スレッド セーフ キューの実装です。プッシュとポップはお互いをブロックしません。ただし、キューが空の場合、アイテムがプッシュされるまで pop は待機します。複数のプロデューサーとコンシューマーがキューを使用できます。何か問題があれば教えてください。

更新：回答に従って編集1）「キューがいっぱい」の状況の問題を解決しました。2) .NET4 にはBlockingCollection<T>andがありConcurrentQueue<T>ます。したがって、車輪を再発明する必要はありません（.NET4の場合）

public class CustomQueue<T> where T: class
{
    class Node
    {
        public Node()
        {
            Value = null;
            NextNode = null;
        }

        public Node(T value)
        {
            Value = value;
            NextNode = null;
        }

        public T Value;
        public Node NextNode;
    }

    object PushLocker = new object();
    object PopLocker = new object();
    Semaphore QueueSemaphore;
    volatile int PushIncrement;
    volatile int PopIncrement;
    int MaxItems;
    Node FirstNode;
    Node LastNode;

    public CustomQueue(int maxItems)
    {
        QueueSemaphore = new Semaphore(0, maxItems);
        MaxItems = maxItems;
        FirstNode = LastNode = new Node();
        PushIncrement = 0;
        PopIncrement = 0;
    }

    public int Size()
    {
        return PushIncrement - PopIncrement;
    }

    public bool Push(T value)
    {
        lock(PushLocker)
        {
            if((Size()) >= MaxItems)
            {
                lock(PopLocker)
                {
                    PushIncrement = PushIncrement - PopIncrement;
                    PopIncrement = 0;
                    return false;
                }
            }
            Node newNode = new Node(value);                
            LastNode.NextNode = newNode;
            LastNode = newNode;
            PushIncrement++;
            QueueSemaphore.Release();
            return true;
        }            
    }

    public T Pop()
    {
        QueueSemaphore.WaitOne();
        lock(PopLocker)
        {
            Node tempFirst = FirstNode;
            Node tempNext = FirstNode.NextNode;
            T value = tempNext.Value;
            tempNext.Value = null;
            FirstNode = tempNext;
            PopIncrement++;
            return value;
        }
    }
}
4

5 に答える 5

3

自己教育のためにこれを行っている場合は、素晴らしいです-そうでなければ、BlockingCollection<T>またはConcurrentQueue<T>良い代替手段です.

Popここで私が目にする問題の 1 つは、いったん開始すると中断する方法がないことです。オブジェクトが目覚めたときに待機していると想定します。終了時にこれをどのようにクリアしますか? （要素を含む）または（データがない場合）TryPopを返すA の方が良い場合は、キューが空になったら、待機中のスレッドに正常にシャットダウンするように通知できます。truefalse

于 2010-11-10T14:33:00.123 に答える
3

1.2 番目の Node コンストラクターを追加することを検討してください。

        public Node(T value)
        {
            Value = value;
        }

次に、クライアントコード：

            Node newNode = new Node();
            newNode.Value = value;

値を不変式として扱うことができます:

            Node newNode = new Node(value);

2.次に、パブリック フィールドを作成します。

        public T Value;
        public Node NextNode;

自動プロパティに:

        public T Value { get; private set; };
        public Node NextNode { get; set; };

そのため、クライアント コードの中断を最小限に抑えて、実装から使用法を抽象化し、事後に検証やその他の処理などを追加できます。

于 2010-11-10T14:34:42.943 に答える
3

一見するとうまく実装されているように見えます。異なるロックを使用することは常に危険信号です。そのため、 and の同時呼び出しを含むいくつかのエッジ ケースをよく調べたところ、安全に見えます。おそらく、ブロッキング キューのリンク リストの実装について自分自身を教育したのではないでしょうか? これが安全である理由は、参照元と参照元のみであるためです。そうしないと、トリック全体が崩壊してしまいます。PopPushLastNodePushFirstNodePop

現在私に突き出ている唯一のことは、からカウントを解放しようとすると、Semaphoreすでにいっぱいになっている場合に例外がスローされるため、それを防ぐ必要があることです。1そうしないと、リンクされたリストに余分なノードが作成され、キューに1）最大数を超えるアイテムがあり、2）ライブロックされます。

アップデート：

私はこれをもう少し考えました。メソッドでのそのRelease呼び出しは非常に問題になります。考えられる解決策は 1 つだけです。コンストラクターからパラメーターを削除し、セマフォが までカウントできるようにします。そうしないと、アプローチを根本的に変更する必要があり、その結果、現在の実装とはかけ離れたものになります。PushmaxItemsInt.MaxValue

1これは、あなたがすぐに理解するよりも難しいことに気付くと思います。

于 2010-11-10T15:06:09.277 に答える
2

.NET 4: Blocking Collection と Producer-Consumer Problemがある場合は、こちらを参照してください。

于 2010-11-10T14:32:42.060 に答える
0

私は不変オブジェクトのファンなので、以前の回答に代わる、少しクリーンだと思う代替案を次に示します。

public sealed class CustomQueue<T> where T : class
{
    private readonly object pushLocker = new object();
    private readonly object popLocker = new object();
    private readonly Semaphore queueSemaphore;
    private readonly int maxItems;
    private volatile int pushIncrement;
    private volatile int popIncrement;
    private Node firstNode = new Node();
    private Node lastNode;

    public CustomQueue(int maxItems)
    {
        this.maxItems = maxItems;
        this.lastNode = this.firstNode;
        this.queueSemaphore = new Semaphore(0, this.maxItems);
    }

    public int Size
    {
        get
        {
            return this.pushIncrement - this.popIncrement;
        }
    }

    public bool Push(T value)
    {
        lock (this.pushLocker)
        {
            if (this.Size >= this.maxItems)
            {
                lock (this.popLocker)
                {
                    this.pushIncrement = this.pushIncrement - this.popIncrement;
                    this.popIncrement = 0;
                    return false;
                }
            }

            Node newNode = new Node(value, this.lastNode.NextNode);

            this.lastNode = new Node(this.lastNode.Value, newNode);
            this.firstNode = new Node(null, newNode);
            this.pushIncrement++;
            this.queueSemaphore.Release();
            return true;
        }
    }

    public T Pop()
    {
        this.queueSemaphore.WaitOne();
        lock (this.popLocker)
        {
            Node tempNext = this.firstNode.NextNode;
            T value = tempNext.Value;

            this.firstNode = tempNext;
            this.popIncrement++;
            return value;
        }
    }

    private sealed class Node
    {
        private readonly T value;

        private readonly Node nextNode;

        public Node()
        {
        }

        public Node(T value, Node nextNode)
        {
            this.value = value;
            this.nextNode = nextNode;
        }

        public T Value
        {
            get
            {
                return this.value;
            }
        }

        public Node NextNode
        {
            get
            {
                return this.nextNode;
            }
        }
    }
}
于 2010-11-11T15:11:11.767 に答える