TThreadedQueue vs ThreadedRingBuffer

[QuickAndDirty]

TThreadedQueue aus System.Generics.Collections
Führt bei jedem PushItem oder PopItem sowas hier durch

Delphi-Quellcode:

  TMonitor.Enter(FQueueLock); // ALLES WIRD GELOCKT
  try
    Result := wrSignaled;
    while (Result = wrSignaled) and (FQueueSize = Length(FQueue)) and not FShutDown do
      if not TMonitor.Wait(FQueueNotFull, FQueueLock, FPushTimeout) then
        Result := wrTimeout;

    if FShutDown or (Result <> wrSignaled) then
      Exit;

    FQueue[(FQueueOffset + FQueueSize) mod Length(FQueue)] := AItem;
    Inc(FQueueSize);
    Inc(FTotalItemsPushed);

  finally
    AQueueSize := FQueueSize;
    TMonitor.Exit(FQueueLock);
  end;

  TMonitor.Pulse(FQueueNotEmpty);

Wenn ich Queue als Ringpuffer umsetzen würde , müsste ich dann immer noch beides LOCKEN also READ und WRITE oder kann ich READ während des WRITE ungelockt lassen ?

Edit:
Ich sehe gerade DASS es sich bei TThreadedQueue um einen Ringbuffer handelt.
Warum wird jedesmal alles gelockt?

[Rollo62]

Zitat:

Zitat von QuickAndDirty (Beitrag 1545884)

Edit:
Ich sehe gerade DASS es sich bei TThreadedQueue um einen Ringbuffer handelt.
Warum wird jedesmal alles gelockt?

Ohne mir das angesehen zu haben, wie kommst Du darauf , dass eine Queue ein Ringbuffer ist?

Ich denke das Queue hat eine variable Größe/Kapazität, worauf auch diese Zeile hindeutet:

Delphi-Quellcode:

Inc(FQueueSize);

Bei einem Ringbuffer sollte es meiner Meinung nach eine feste Kapazität geben, die sich nicht vergrößert/verkleinert,
sondern überschrieben werden, wenn es über die Kapazität hinausgeht.

[QuickAndDirty]

Es ist ein Ringpuffer
FqueueSize minus fqueueOffset Ist die Länge der Schlange im Ringpuffer. FQueueSize hat vielleicht nicht ganz den richtigen Bezeichner! Length(FQueue) ist die größe des Ringpuffers.
FQueue ist ein Array = Der Puffer.
Der Schreib-Index des Ringpuffers wird wie folgt ermittelt

Code:

(FQueueOffset + FQueueSize) mod Length(FQueue)

FQueueSize modulo 10
ergibt indizes 0..9 in einem RING
FQueueSize = 1401
würde einen index 1 ergeben da 1401 modulo 10 gleich 1 ist!

man kann FQueueSize einfach immer hochzählen solange man den index über modulo ermittelt.

[himitsu]

Queue = FIFO (first in, first out)
Stack = LIFO (last in, first out)

Also ja Queue gleich entsprechend RingBuffer ... praktisch das gleiche Verhalten, also es unterscheidet sich nur die interne Speicherverwaltung.

Und da die TThreaded-Komponenten ja selbst das Threadsichere handhaben, kann man da meistens direkt auf Add/Remove/Push/Pop/... zugreifen, weil sie intern sich selbst absichern (wenn diese Methoden direkt oben public erreichbar sind)


Als Ringbuffer oder verkettete Liste hat es halt den Vorteil, dass beim Reinschieben oder Rausholen nicht der gesamte Listeninhalt verschoben werden muß.
(beim Stack geht ist Beides immer am Listenende und somit verschieben sich die vorherrigen Einträge nicht)

[Rollo62]

Zitat:

Zitat von himitsu (Beitrag 1545894)

Als Ringbuffer oder verkettete Liste hat es halt den Vorteil, dass beim Reinschieben oder Rausholen nicht der gesamte Listeninhalt verschoben werden muß.

Genau, der RingBuffer, so wie ich ihn verstehe, muss nur einmal seine Speicher-Kapazität allozieren und zeigt dann quasi nur mit Start- und Ende-Pointern auf den entsprechenden Abschnitt in seinem gesamten Speicherbereich, was den Zugriff theoretisch viel effizienter machen sollte, weil nie etwas hin- und herkopiert wird.
Dafür kann es aber auch einen Überlauf geben.

[QuickAndDirty]

Zitat:

Zitat von Rollo62 (Beitrag 1545899)

Genau, der RingBuffer, so wie ich ihn verstehe, muss nur einmal seine Speicher-Kapazität allozieren und zeigt dann quasi nur mit Start- und Ende-Pointern auf den entsprechenden Abschnitt in seinem gesamten Speicherbereich, was den Zugriff theoretisch viel effizienter machen sollte, weil nie etwas hin- und herkopiert wird.
Dafür kann es aber auch einen Überlauf geben.

TThreadedQueue macht das genau so.
Intern speichert es einen ReadPointer "FQueueOffset mod length(fQueue)" in form eines index auf ein Array und einen WritePointer "(FQueueOffset + fQueSize) mod length(fQueue)" ebenfalls als index auf das Array fQueue.

Zitat:

Zitat von himitsu (Beitrag 1545894)

Und da die TThreaded-Komponenten ja selbst das Threadsichere handhaben, kann man da meistens direkt auf Add/Remove/Push/Pop/... zugreifen, weil sie intern sich selbst absichern (wenn diese Methoden direkt oben public erreichbar sind)

Ich hatte halt nur irgendwie gehofft dass ein Ringspecher ohne Vollsperrung für threadsicherheit auskommen würde.
Vermutlich müsste es dafür ein Ringspeicher auf Basis einer Verkettetenliste sein?

[Stevie]

Zitat:

Zitat von QuickAndDirty (Beitrag 1545884)

Warum wird jedesmal alles gelockt?

Weil die RTL Entwickler wenig bis keine Erfahrung haben, lockfreie Datenstrukturen zu designen und zu implementieren.
Und das meine ich ausnahmsweise mal nicht despektierlich, das ist nämlich wirklich kein Zuckerschlecken sonst hätt ich sowas auch in Spring4D, aber davon lass ich lieber die Finger 8-)
Wenn du sowas benötigst, solltest du dich eher bei externen Bibliotheken umschauen, z.B. der OTL.

Übrigens, lockfrei ist auch nicht wirklich der heilige Gral, da gibt es noch weit mehr zu berücksichtigen.

[QuickAndDirty]

Ich habe drüber nachgedacht...
um es semi-Lockfrei zu halten müsste ich dafür sorgen das im Ringpuffer immer mindestesens zwei Einträge sind...also auch im leeren Ringpuffer müssten 2 dummy einträge sein...
Und dann könnte ich lesen und schreiben unabhängig von einander Locken... nur so zur sicherheit...aber das wäre effektiv so dass kein thread je auf das unlock warten müsste (Waitfree)...es sei denn es läuft etwas schief.

[QuickAndDirty]

Zitat:

Zitat von Stevie (Beitrag 1545912)

Wenn du sowas benötigst, solltest du dich eher bei externen Bibliotheken umschauen, z.B. der OTL.

Oh je.
Ist es das hier?

https://github.com/gabr42/OmniThread...kFreeQueue.pas

Verstehst du das?

Edit:
OK es gibt hier eine Erklärung
https://www.thedelphigeek.com/2010/0...-it-right.html