atomic_queue - Eine Thread-sichere und Lock-freie queue

[fat-lobyte]

Hallo!

Als ich letztens eine Aktuelle C++-Referenz durchgeblättert habe, entdeckte ich einen neuen Header, den ich noch nie gesehen hatte - <atomic>.
Dieser Header enthielt mystische Klassen und Funktionen, die anscheinend in Mehrsträngigen Programmen gebraucht werden können. Da dachte ich mir: das wär doch gelacht, wenn ich mich nicht damit auseinandersetzen könnte.

2 Wochen später möchte ich folgendes Präsentieren:
Eine Queue (First-in-first-out Datenstruktur), die ohne Mutexe auskommt und trotzdem threadsicher ist!
Das bedeutet, dass ihr eine Instanz dieser Queue zwischen verschiedenen Threads teilen könnt, die fröhlich und völlig unsynchronisiert draufschreiben und lesen können.
Wie das Möglich ist? Das Stichwort ist "atomics", das sind Variablen auf denen bestimmte Operationen als Unteilbar erscheinen. Kann man diese Operationen in geschickter Weise anordnen, kann man die Threadsicherheit garantieren, ohne auf Mutexe zurückgreifen zu müssen.
Wer sich mehr für Multithreading, Threadsicherheit und Atomics interessiert, dem sei folgender Artikel empfohlen: http://queue.acm.org/detail.cfm?id=2088916

Das Rückgrad der queue ist eine einfach verkettete Liste. Folgende Methoden sind public:

• push_back: Ein Objekt in die Queue kopieren oder hineinbewegen (move-construct)
• emplace_back: Ein objekt in der Queue erstellen
• pop_front: Ein objekt aus der Queue entfernen und zurückgeben lassen
• deallocate: Ein zurückgegebenes Objekt löschen
• size: Aktuelle, ungefähre Größe der Queue ermitteln.

Jedes Objekt, dass mit pop_front() erhalten wurde muss mit deallocate() wieder freigegeben werden.

Kompilieren tut das ganze mit:

• Clang >= 3.1, mit -stdlib=libc++
• GCC >= 4.7, mit -D_GLIBCXX_USE_SCHED_YIELD
• Visual Studio >= 2012 (_MSC_VER >= 1700), allerdings ohne emplace_back()

Einen aktuellen Schnappschuss des Codes habe ich hier angehängt, allerdings ist der Code mit einigen Tests, Makefiles und einem README auf https://github.com/fat-lobyte/atomic_queue verwaltet.

Bitte seht euch die Klasse an, probiert sie aus, verwendet sie, und stellt Fragen! Über konstruktives Feedback würde ich mich freuen!

mfg, fat-lobyte

[Xin]

Wird dringend Zeit, dass ich den GCC47 installiere...

[fat-lobyte]

Ich muss leider einen Rückruf starten, es sind doch noch Probleme aufgetaucht.

Code: Alles auswählen

        do {
            // Punkt 1
            if (!old_front) return nullptr; // nothing to pop
            new_front = old_front->next;
            // Punkt 2
        } while(!front_.compare_exchange_weak(old_front, new_front));

Dieser Code ist kaputt, aus zwei Gründen:
1.: Wenn Thread A die Funktion aufruft, bei Punkt 1 stehenbleibt, ein weiterer Thread B die Funktion aufruft, beendet und die node dann gelöscht wird, und Thread A weitergeführt wird, zeigt der old_front Zeiger auf gelöschten Speicher, wobei dann old_front->next abgefragt wird. Dieser Wert wird zwar nicht verwendet wenn die Node gelöscht wird (außer es Tritt das zweite Problem auf), allerdings ist das trotzdem "undefiniertes" Verhalten und nicht korrekt.

2.: Dieser Code verlässt sich darauf, dass eine neu erstellte Node nicht die gleiche Adresse haben kann wie eine bereits gelöschte. Dies ist nicht zwingend der Fall! Bleibt Thread A bei Punkt 2 stecken, und ruft Thread B die funktion auf und erstellt gleich darauf eine neue Node die zufällig die gleiche Adresse hat, glaubt die Funktion alles sein in Ordnung und schreibt dann den Wert der nächsten Node nach front_... Das zeigt dann allerdings ins Nirvana.

Übrigens ist Punkt 2 anscheinend ein bekanntes Problem: http://en.wikipedia.org/wiki/ABA_problem

Ich habe noch keine passende Lösung gefunden. Ich muss wohl nochmal ans Reißbrett.

ps.: Das ganze Thema ist echt verdammt schwierig für mich. Wer eine Herausforderung will, dem kann ich nur empfehlen eine Threadsichere&Lockfreie Datenstruktur zu schreiben

[Xin]

Das ganze Thema ist echt verdammt schwierig für mich. Wer eine Herausforderung will, dem kann ich nur empfehlen eine Threadsichere&Lockfreie Datenstruktur zu schreiben

Mit dem Thema beschäftigen sich schon Generationen von Informatikern.

Dass Du es so früh tust, kann aber dazu führen, dass Du damit irgendwann einen interessanten Erfolg erringen kannst.