threadsicher Warteschlange in C ++ nicht blockierende?

StackOverflow https://stackoverflow.com/questions/1645326

  •  10-07-2019
  •  | 
  •  

Frage

Gibt es eine Thread-sichere, nicht-blockierende Warteschlange Klasse in C ++?

Wahrscheinlich eine grundlegende Frage, aber ich habe nicht C ++ für eine lange Zeit zu tun ...

EDIT:. entfernt STL Anforderung

War es hilfreich?

Lösung

Angenommen, Ihre CPU verfügt über einen Doppelzeigerweiten Vergleichs- und swap (compxchg8b auf 486 oder höher, compxchg16b auf den meisten amd64 Maschinen [nicht vor einigen frühen Modellen von Intel]) ... Es gibt einen Algorithmus hier .

Update: Es ist nicht schwer, dies zu C ++ zu übersetzen, wenn Sie keine Angst haben, ein wenig Arbeit zu tun. : P

Dieser Algorithmus geht davon eine „Zeiger mit dem Tag“ Struktur, die wie folgt aussieht: 

// Be aware that copying this structure has to be done atomically...

template <class T>
struct pointer
{
   T *ptr;
   uintptr_t tag;
};

Dann möchten Sie die Anweisungen wickeln lock cmpxchg{8|16}b mit einigen Inline-asm ...

Vielleicht dann können Sie die Warteschlange Knoten wie folgt schreiben: 

template <class T>
struct queue_node
{
    T value;
    pointer<queue_node<T> > next;
};

Der Rest ist mehr oder weniger eine Transkription des Algorithmus I verknüpft ...

Andere Tipps

Da der aktuelle C ++ Standard nicht einmal die Existenz von Fäden erkennen, es ist mit Sicherheit nichts Thread-sicher in der STL oder einem anderen Teil der Standardbibliothek.

Dies scheint ein beliebtes Thema auf Dr. Dobb im vergangenen Jahr gewesen zu sein:

Sie müssen es selbst implementieren oder eine Bibliothek verwenden, es zu implementieren. Um es selbst zu tun, können Sie einen Blick auf diese haben:

einen Thread Implementierung -safe Queue mit Bedingungsvariablen

Kurze Antwort - nein. STL betrifft nicht selbst mit Concurrency (zumindest auf der Spezifikationsebene.) Strom C ++ Standard sagt nichts über Threads.
Sie können eine solche Warteschlange auf der STL leicht bauen und zwar steigern -. Nur wickeln std::queue und boost::mutex in Ihrer benutzerdefinierten Klasse

STL-Container sind nicht Thread-sicher, sollten Sie Ihre Behandlung für den gleichzeitigen Zugriff implementieren.
Es ist dieses Projekt (C ++), die gleichzeitige Zugriffe dienen soll: CPH STL
und Papier über .

Auch jetzt zu spät sein. Für die Zukunft, das ist eine gute Umsetzung der Lock-Free-Warteschlangen (in Thread-Sicherheit mit einigen Einschränkungen gebaut).

Multi-Produzent - Multi Verbraucher

http: // moodycamel. com / blog / 2014 / a-fast-Allzweck-Lock-Free-Queue-for-c ++

https://github.com/cameron314/concurrentqueue

Single Produzent - Single Verbraucher

http://moodycamel.com/blog/ 2013 / a-Fast-Lock-Free-Queue-for-c ++

https://github.com/cameron314/readerwriterqueue

Die derzeit inoffizielle Boost.Lockfree ist etwas zu prüfen. Ich benutze sowohl die FIFO und die Atomtypen.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top