Prüfungsantrag: Thread sichere Warteschlange (parallel Push pop)

Question

Hier ist eine Implementierung einer Thread-sicher-Warteschlange. Die Push- und Pop nicht gegenseitig blockieren. Pop wird jedoch warten, bis ein Element gedrückt wird, wenn die Warteschlange leer ist. Mehrere Produzenten und Konsumenten können die Warteschlange verwenden. Bitte sagen Sie mir, wenn Sie irgendwelche Probleme zu sehen.

Update: Edited nach Antworten 1) gelöst, die Frage der „Warteschlange voll“ -Situation. 2) Es gibt BlockingCollection<T> und ConcurrentQueue<T> in .NET4. So gibt es keine Notwendigkeit, das Rad (für .NET4)

neu zu erfinden

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;
        }
    }
}

Answer 1

Es sieht aus wie eine gute Umsetzung auf einem Blick. verschiedene Schlösser zu verwenden ist immer eine rote Fahne zu mir, damit ich auf einen guten harten Blick nahm einig der Rand Fälle, in denen gleichzeitig Anrufe an Pop und Push und es scheint sicher. Ich vermute, Sie erzogen sich wahrscheinlich auf der verknüpften Liste Implemenation einer Sperr Warteschlange nicht wahr? Der Grund, warum dies sicher ist, weil man immer nur Referenz LastNode von Push und FirstNode von Pop sonst der ganze Trick auseinander fallen würde.

Das einzige, was jetzt bei mir herausragt, ist, dass, wenn Sie versuchen, eine Zählung freizugeben von einem Semaphore wird es eine Ausnahme auslösen, wenn es bereits voll ist, so dass Sie gegen das schützen möchten. ¹ Andernfalls werden Sie mit zusätzlichen Knoten in der verknüpften Liste und die Warteschlange 1) haben am Ende mehr als die maximale Anzahl der Elemente und 2) es Live-gesperrt wird erhalten.

Update:

gab ich diesen etwas mehr Gedanken. Der Release Aufruf in der Push Methode sein wird, sehr problematisch. Ich sehe nur eine mögliche Lösung. Entfernen Sie den maxItems Parameter aus dem Konstruktor und lassen Sie das Semaphore Int.MaxValue zu zählen. Andernfalls Sie gehen radikal zu haben, um Ihren Ansatz in einer Implementierung resultierenden zu ändern, die keine ist, wo die Nähe zu dem, was Sie im Moment haben.

¹ _{ich glaube, Sie werden feststellen, dass dies schwieriger sein wird als das, was Sie könnten sofort erkennen.}

Answer 2

1. Betrachten Sie einen zweiten Knoten Konstruktor hinzu:

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

dann Ihre Kundennummer ein:

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

kann den Wert als unveränderlich behandeln:

            Node newNode = new Node(value);

2. dann Ihre öffentlichen Bereichen machen:

        public T Value;
        public Node NextNode;

in Auto Eigenschaften:

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

So kann man abstrakt die Nutzung von der Implementierung und fügt Validierung, eine andere Verarbeitung usw. nach der Tat mit minimaler Unterbrechung Client-Code.

Answer 3

Wenn Sie dies tun für Selbsterziehung, groß - sonst BlockingCollection<T> oder ConcurrentQueue<T> sind gute Alternativen.

Ein Problem, das ich hier sehe, ist, dass es keine Möglichkeit, Interrupt Pop ist, sobald es beginnt - nimmt ein Objekt wartet, wenn er erwacht. Wie würden Sie diese nach unten auf Beendigung löschen? Ein TryPop, dass die Renditen true (mit einem Element) oder false (wenn keine Daten) besser sein könnte, dann könnte man Fäden Signal warten sauber herunterzufahren, sobald die Warteschlange leer ist.

Answer 4

Dieses Sehen Sie, wenn Sie .Net 4

• Wie ich ein Fan von unveränderlichen Objekten bin, hier ist eine Alternative zu meiner früheren Antwort, dass ich ein bisschen sauberen halten würde:

  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;
              }
          }
      }
  }
  

Answer 5

Wie ich ein Fan von unveränderlichen Objekten bin, hier ist eine Alternative zu meiner früheren Antwort, dass ich ein bisschen sauberen halten würde:

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;
            }
        }
    }
}

Answer 6

Answer 7

Answer 8