J
Hi! Danke, dass du dir die Zeit nimmst.
hustbaer schrieb:
Ich verstehe die Motivation ehrlich gesagt nicht ganz.
Normalerweise braucht man nachdem man eine Funktion aufgerufen hat das Ergebnis des Aufrufs (was u.U. auch nur der Umstand sein kann dass die Nebeneffekte des Funktionsaufrufs jetzt sichtbar sind).
Bei deiner Variante geht das nicht.
Allerdings. Wenn der Algorithmus vom Ergebnis des Aufrufs (oder seiner Nebeneffekte) abhängen würde, müsste man wieder eine Mutex benutzen, da der Code dann eh nichts sinnvolles machen kann, solange er die Funktion nicht aufrufen darf.
hustbaer schrieb:
Und ... was spricht jetzt wirklich gegen eine Mutex? "Mag ich nicht" ist doch wohl kein guter Grund.
Angenommen, der Code nach dem Funktionsaufruf würde nicht vom Ergebnis abhängen. In dem Moment wäre es schade, sich in den Mutex-Lock zu begeben, obwohl man eigentlich nur will, dass die Funktion überhaupt mal synchronisiert aufgerufen wird und man etwas anderes sinnvolles tun könnte.
Der primäre Anwendungsfall, wofür ich das machen will, ist für WinSock (mit seiner verbauten IOCP-API). Die zu synchronisierenden Funktionen sind z.B. WSASend, WSARecv (also Funktionen, die asynchrone Operationen initiieren). Laut Reference sind diese tatsächlich nicht threadsafe. Jetzt kann ich bei feinster Granulierung höchstens jedem Socket einen Mutex verpassen (wobei auf meinem System ein Mutex alleine schon 10 mal größer als ein Socket ist) und die Aufrufe pro Socket synchronisieren.
Ich will es aus purer Langeweile aber mal probieren, das ganze lockfrei hinzubekommen.
hustbaer schrieb:
ps: Die Implementierung der push_task Funktion ist für mich total wirr.
Hm, irgendwie schaffe ich es nicht, die Idee zu kommunizieren.
Dann mal grafisch:
|
|
V
+---+
| |<-+
| A | |
| |--+
+---+
Das bedeuetet: Ein Node (namens A) mit einem Next-Pointer, der auf sich selber zeigt, wobei auch der Tail-Pointer (von oben) auf den Node zeigt
Ausgangssituation:
|
|
V
+---+
| |<-+
| B | |
| |--+
+---+
Jetzt mache ich (abgekürzte) Diagramme für alle atomaren Schritte:
1.
|
V
+---+ +---+
| |<-+ | |
... -->| B | | | C |
| |--+ | |
+---+ +---+
Das ist Zeile 26, C wird der neue Tail. Dabei merkt er sich den alten Tail innerhalb von old_tail . Hier besteht eine Race Condition zwischen den Threads, aber das ist nicht schlimm, da sich jeder Thread den alten Tail merkt und nichts verloren geht.
2.
|
V
+---+ +---+
| | | |
... --->| B |--->| C |
| | | |
+---+ +---+
Das ist 28. Der Next-Pointer des Vorgängers wird umgebogen. Durch das exchange in Schritt 1 ist gewährleistet, dass nur 1 Thread das tun kann, also keine Race Condition. Da der Next-Pointer von B vorher auf sich selbst zeigte (oder der Tail selbst nullptr war), ist C nun der autorisierte "Funktionsaufrufer" (er hat quasi den Mutex akquiriert). Wiederrum wegen der obigen Begründung kann nur 1 Thread gleichzeitig autorisiert sein.
3.
Da der Thread jetzt autorisiert ist, kann er sicher den Task ausführen (Zeile 33). Andere Threads könnten in der Zwischenzeit auch Elemente an die Liste gepusht haben. Keiner von ihnen kann autorisiert sein, die Tasks zu starten, weshalb sie alle nicht in den äußeren if-Zweig von push_task gelangen. Wir merken anhand des Next-Pointers von C, der nicht länger auf 0 zeigen könnte, das neue Operationen anstehen.
|
V
+---+ +---+ +---+
| | | | | |
... --->| B |--->| C |--->| D |
| | | | | |
+---+ +---+ +---+
Wir möchten "den Mutex" nun wieder freigeben, indem wir C auf sich selber zeigen lassen (Zeile 34).
|
V
+---+ +---+ +---+
| | | |<-+ | |
... --->| B |--->| C | | | D |
| | | |--+ | |
+---+ +---+ +---+
5. Sofern der Next-Zeiger von C vorher auf 0 stand, ist kein neuer Node dazugekommen (d.h. alle anderen potentiell pushenden Threads befinden sich vor Zeile 28, welche mit Zeile 34 in synchronizes-with-Beziehung steht). Dann kann die Funktion verlassen werden. Ansonsten muss (wie im Diagramm gezeigt) auch der Task D ausgeführt werden (Schleifenablauf wiederholt sich). Das wird nun so lange gemacht, bis der Thread einen Next-Zeiger auf den selben Node zeigen lässt, der vorher auf 0 und nicht auf einen anderen Node zeigte. Da nur 1 Thread autorisiert ist, wird auch nur 1 Thread durch diese Schleife gehen und versuchen, den Next-Zeiger zu manipulieren. Alle anderen Threads belassen ihn bei nullptr .
Bei dieser Gelegenheit löscht er die ganzen alten anderen Nodes vor ihm, auf die nun niemand außer er selbst zugreifen könnte (Zeile 37).
|
V
+---+ +---+ +---+
| | | |<-+ | |<-+
... --->| B |--->| C | | | D | |
| | | |--+ | |--+
+---+ +---+ +---+
(del) (del)
Ich hoffe, jetzt ist die Idee etwas klarer. Gibt's einen Haken und wenn ja, wo?
