Thema: Locking innerhalb des Kernels

[rizor]

Ich habe eben ein Paper über Hazard Pointer gelesen und die sollen sehr viel performanter sein als Spinlocks sein.  Das kann ich mir nur schwer vorstellen, da man je immer doppelt nachschauen muss, oder?  Ein Vorteil ist halt der Garbage Collector, der sich um gelöscht Objekte kümmert. Aber kann es sein, dass man die Verwaltung der Pointer trotzdem durch Locking sichern muss? Mir fällt zumindest keine andere Möglichkeit ein.  Sicher sind die auf jeden Fall. da du ja immer weißt, wer gerade Zugriff auf ein Objekt hat.

[bluecode]

Ich glaube das war so, das jeder Pointer, durch nen "Counter" (weil der immer nur um eins erhöht wird) "geschützt" wird und das Problem war, das wenn die Zeit zw. 2 Zugriffen eines Threads zu lange ist, dass dann das Objekt freigegeben werden kann und durch nen anderen Thread wieder alloziert wird und dann der Counter zufällig den selben Wert hat wie der Thread der nun nach längerer Zeit wieder darauf zugreift, aber das Objekt ist jetzt nicht mehr das gleiche.

Korrekt. Aber ich sags nochmal: Das hat NICHTS mit dem Algorithmus den ich meinte zu tun. Was wiedermal bestätigt, dass man über einen konkreten Algorithmus reden sollte und nicht allgemein über irgendwas undefiniertes. Bei meinem Algorithmus von oben hat der reference-counter nur einen Overflow (was ja erst das Problem auslöst), wenn man ca. 4Mrd Leute hat, die eine Reference auf den Cache halten.

Wovon du hingegen sprichst, ist nicht wirklich reference-counting (wird aber so bezeichnet), sondern eine Art Versionierung bei der der Counter angibt, welche Version des Zeigers man gerade hat. Wenn man den Zeiger verändert, zählt man die Version hoch und alle anderen stellen dann fest, dass sie eine alte Version haben (obwohl eventuell der Zeiger vollkommen gleich ist). Dabei wird aber immer um 1 hochgezählt (und niemals runter), d.h. ein Overflow ist realistisch, aber es ist wohl extrem unwahrscheinlich, dass genau 4Mrd. Änderungen an diesem Zeiger zwischen meinem Snapshot und meinem Überprüfen (zu welchem Zweck auch immer) sind und zusätzlich noch der eigentliche Zeiger genau zu dem Zeitpunkt gleich. Der einzige Nachteil ist wie gesagt, dass man zum Ändern einen DoppelCAS braucht, was es auf x64 teilweise nicht gibt, damit man den Pointer+Counter atomar ändert. Aber ich sags nochmal: Von der Art reference-counting habe ich NICHT geredet und die Art sollte man besser durch hazard pointer ersetzen.
Übrigens kann man mit der Art reference-counting das Objekt nicht vollständig freigeben, weil andere noch auf der Referenz rumnudeln könnten (und auf den Counter vertrauen können müssen), d.h. sie Lösen zwar das ABA-Problem, aber man kann trotzdem nicht freigeben. Hazard pointer dagegen lösen beide Probleme.

und auch ob sie theoretisch 100% sicher sind

ja, das kann ich mit 100%iger Sicherheit sagen bzw. so sicher wie man sich sein kann, wenn man das für eine Queue bereits in einem Theorembeweiser selbst gezeigt hat und einen Beweis in selbigen für einen Stack kennt.

ob die performancemäßig [...] besser oder schlechter sind als Reference-Counting

Besser, im speziellen ist das DoppelCAS unschön.
Nachteil ist halt (im Vergleich zu der Art von reference-counting die ich bezogen auf Caches genannt habe) dass man nicht sobald wie möglich freigeben kann, sondern immer ein paar Referenzen hält und dann mehrere auf einmal freigibt (sonst kommt man nicht auf O(1) amortisiert fürs freigeben).

Ich habe eben ein Paper über Hazard Pointer gelesen und die sollen sehr viel performanter sein als Spinlocks sein.

Die meisten lockfreien Algorithmen skalieren massiv besser als Algorithmen mit Locks (zumindest sagen das alle Performancegraphen die ich dazu in Papern gesehen habe). Im speziellen hat man auch keine Probleme mit priority inversion, Deadlocks oder ein Problem falls ein anderer Thread der einen Lock hält abkackt, das sollte man auch nicht unterschätzen. Und sie skalieren besser, weil andere währenddessen ihre Aktion abarbeiten können, was bei einem Spinlock offensichtlich nicht geht. Auch wenn jeder einzelne Thread ein paar atomare Reads mehr macht.

Aber kann es sein, dass man die Verwaltung der Pointer trotzdem durch Locking sichern muss?

Wenn man ein Array fixer Größe (#Threads * #MaxHazardPointerProThread) dann auf jeden Fall nicht, da es ein Thread nur den eigenen Teil schreib und alle anderen Teile nur liest. Auch spielt es hier keine Rolle ob atomar gelesen wird oder nicht.
Für denn Fall, dass man das dynamisch vergrößern (zumindest was die Threadzahl angeht) behauptet Michaels, dass man es auch lockfrei hinbekommt. Darüber hab ich mir aber noch keine Gedanken gemacht ehrlich gesagt.

Aber wie ich schon einiges weiter oben sagte und FlashBurn zwei Posts weiter oben, kommt es bei der Art von Algorithmen _extrem_ auf die konkreten Details an. Im Speziellen sollte man _niemals_ die Reihenfolge von Reads/Writes auf globale Speicherzellen (die btw. von jedem Paper als atomar angenommen werden) auch nur ein bisschen ändern (auch wenn man meint, dass es korrekt wäre), kann ich aus eigener Erfahrung nur sagen

edit:

Meines Wissens nach gibt es dagegen nur 2 100%-tig sichere Abhilfen: zum einen ein richtiger atomarer Lock  [...]

Verstehe ich nicht. Ein CAS macht genau das?

aber soweit ich weiß sind viele von denen auf ein einigermaßen vorhersagbares zeitliches Verhalten des Code angewiesen

Das ist Humbug. Im Speziellen (siehe oben) hat es nichts mit der Zeit zu tun, sondern mit der Anzahl der Änderungen bei Versionierung/Reference-counting und wie oben gesagt, exakt ~4Mrd Änderungen und dann noch der gleiche Pointer ist einfach nur unwahrscheinlich.

[FlashBurn]

@bluecode

Unwahrscheinlich ist immer schön, aber d.h. trotzdem nicht unmöglich und solange nichts passiert ist es ja gut und schön, aber wenn was passiert, nicht so toll
Das Problem an unwahrscheinlich ist doch, das man einfach nicht an alles und alle Situationen denken kann (siehe Atomkraftwerke bzw. Sicherheit allgemein).

[bluecode]

Unwahrscheinlich ist immer schön, aber d.h. trotzdem nicht unmöglich und solange nichts passiert ist es ja gut und schön, aber wenn was passiert, nicht so toll

*sigh* Ich sags nochmal: Ich habe in dem Kontext an den du dachtest in keinster Weise reference-counting als Lösung vorgeschlagen und hab im Letzten Post auch klar gesagt, dass dafür hazard pointer unter anderem deswegen besser sind - wobei der eigentlich Grund ist, dass reference-counting es nicht ermöglicht die Dinge echt freizugeben und das benötigte DoppelCAS. Und bei dem Algorithmus den ich vorgeschlagen habe, hast du effektiv zu wenig speicher um 2^32 bzw. 2^64 Hazard pointer auf den Cache zu haben, insofern kann der referenzcounter da praktisch nicht overflowen.

[erik.vikinger]

Hallo,

Meines Wissens nach gibt es dagegen nur 2 100%-tig sichere Abhilfen: zum einen ein richtiger atomarer Lock  [...]

Verstehe ich nicht. Ein CAS macht genau das?

Mir ist klar das ein Doppel-CAS mit Objekt-Versionierung (ich nen das einfach mal so) normalerweise nicht so schnell überläuft das es zu Problemen kommen kann trotzdem ist es nicht zu absolut 100% sicher. Deswegen habe ich einen echten Lock für das Objekt vorgeschlagen (das XCHG war nur ein Beispiel, wer will darf dafür natürlich auch CMPXCHG benutzen).

aber soweit ich weiß sind viele von denen auf ein einigermaßen vorhersagbares zeitliches Verhalten des Code angewiesen

Das ist Humbug. Im Speziellen (siehe oben) hat es nichts mit der Zeit zu tun, sondern mit der Anzahl der Änderungen bei Versionierung/Reference-counting und wie oben gesagt, exakt ~4Mrd Änderungen und dann noch der gleiche Pointer ist einfach nur unwahrscheinlich.

Das mit dem unwahrscheinlich bestreite ich in keinster Weise trotzdem ist es auch eine Frage des zeitlichen Verhaltens, solange der zeitliche Abstand zwischen dem ersten Lesen und dem abschließenden CAS kürzer ist als es im schnellsten Fall dauert die 4Mrd Versionen zu durchlaufen ist alles okay aber wenn das aus irgendwelchen Gründen doch mal in den Bereich des möglichen kommen sollte besteht eben die theoretische Möglichkeit eines Fehlers, der eigentliche Pointer hat bei einem SLAB-Allocator wo immer wieder die selben Speicherstellen benutzt werden gar nicht mal einen so großen Wertebereich (der ist mit Sicherhheit eher zu treffen als die Version). Mir ist natürlich klar das die Möglichkeit auf einem 32Bit-System schon extrem theoretisch ist und auf einen 64Bit-System (falls dort dein Doppel-CAS existiert, was bei x86-64 ja zutrifft) erst recht.


Ich hab mir extra zwei mal die, im englischen Hazard-Pointer-Wiki-Artikel verlinkten, PDFs durchgelesen und ich muss ehrlich sagen das ich das nicht wirklich verstehe. Ich vermute mal das entweder mein Englisch oder mein Intellekt dafür nicht ausreichen, vermutlich aber beides.
Welchem Zweck dient das Zeug eigentlich? Gegen was genau sollen diese Hazard-Pointer eigentlich schützen?
Wenn ich das richtig verstanden habe durchsucht jeder Thread die kurzen und öffentlichen Eigen-Listen der anderen Threads. Aber schon dieser Suchvorgang kann doch bei einer recht großen Anzahl an Threads schon enorm CPU-Zeit kosten, IMHO auf jeden Fall sehr viel mehr als ein schlechter Lock-Mechanismus brauchen würde. Nebst dessen das auch dieses Suchen auf ein einigermaßen deterministisches zeitliches Verhalten angewiesen ist. Was ist wenn Thread B nach einem bestimten Pointer sucht der zur Zeit von Thread C benutzt wird, während dieser Suche gibt Thread C diesen frei und als Thread B mit der Suche zwischen Thread A und Thread C ist wird er unterbrochen (z.B. weil eine neue CPU-Frequenz angelegt werden soll) und Thread A kommt zum Zug und sucht ebenfalls nach diesem Pointer findest ihn nicht und trägt ihn in die eigene Liste ein und wenn dann Thread B wieder weiter sucht hat er den Pointer nirgends gesehen und trägt ihn ebenfalls in die eigene Liste ein und bearbeitet das Objekt zusammen mit Thread A also Crash. Oder hab ich da irgendetwas falsch verstanden?
Das nächste ist das ich nicht glaube das dieser Mechanismus mit einer wirklich großen Anzahl an Threads (>10000) gut skaliert. Der Suchaufwand wäre enorm und auch die lokale interne Liste (mit allen gefundenen Pointern) wäre bei allen Threads ebenfalls enorm. In die Gesamtgröße aller dieser internen Listen zusammen geht die Threadanzahl ja quadratisch ein. Klar kann man versuchen das mit Hash-Tabellen zu kompensieren aber die skallieren gar nicht oder die sind bei wenigen Threads zu dünn besetzt (also Speicherverschwendung) oder bei vielen Threads zu dicht besetzt (und wirken dann nicht mehr gescheit weil es zu viele False-Positive gibt).
Wenn jemand für diese Hazard-Pointer eine verständliche (und eventuell auch deutsche) Erklärung kennt wäre ich für einen entsprechenden Link ziemlich dankbar.


Grüße
Erik

[FlashBurn]

Ich glaube du verwechselst da was mit den Hazard-Pointern, die sind für Lock-Free Algos gedacht. Aber es ist nicht so das man dadurch einfach die Locks weglassen könnte, sondern sie sollen halt besser als Reference-Counting oder diese Atomic-Pointers (Versions-Pointers) sein.

Der Gedanke mit dem Skalieren ist gar nicht mal so verkehrt, aber seien wir ehrlich, ich denke nicht das die Performance von bisherigen Lock, Lock-Free oder Wait-Free (die ja eh performancemäßig schlecht sind) Algos in den Deminsionen irgendwas reißen können.
Wenn wir von 16 oder 32 Threads reden, sind ja anscheinend (da mein Mathe einfach zu schlecht ist, um es irgendwie beweisen zu können) Lock-Free Algos wesentlich besser, wieso sollten sie also bei >10000 Threads wieder schlechter werden? Zumal du bei einer solchen Thread Anzahl wahrscheinlich ganz andere Probleme hast.

[bluecode]

der ist mit Sicherhheit eher zu treffen als die Version

Du musst aber gerade beides treffen, damit ein CAS das scheitern sollte trotzdem gutgeht und die Datenstruktur damit kaputtmacht.

Gegen was genau sollen diese Hazard-Pointer eigentlich schützen?

Zum einen vor dem ABA-Problem, zum anderen sind sie dazu da, dass man überhaupt was (echt) freigeben kann und den Speicher für andere Zwecke nutzen kann. Außerdem natürlich das was FlashBurn sagt, für lockfreie Algorithmen.

Aber schon dieser Suchvorgang kann doch bei einer recht großen Anzahl an Threads schon enorm CPU-Zeit kosten, IMHO auf jeden Fall sehr viel mehr als ein schlechter Lock-Mechanismus brauchen würde.

Der Suchvorgang ist nur dazu da Speicher freizugeben, d.h. das kann man ne ganze Weile rausschieben. Und das wird auch in dem Paper gesagt, dass man wartet bis man zB 2 * #Threads * #HazardPointerProThread gesamelt hat, dann kann man auf jeden Fall die Hälfte freigeben, was dann O(1) pro Freigeben ergibt. Deswegen habe ich oben auch schon gesagt, dass es problematisch sein kann, da man bei vielen Threads ewig keinen Speicher freigibt.

Nebst dessen das auch dieses Suchen auf ein einigermaßen deterministisches zeitliches Verhalten angewiesen ist.

Nein.

Oder hab ich da irgendetwas falsch verstanden?

Ja, jeder versucht nur die Zeiger freizugeben die er aus der Datenstruktur entnommen hat. Stell dir zB eine Queue vor und jeder holt da einen Workitem raus. Da dabei nur einer einen bestimmten Workitem rausnimmt wird auch nur der versuchen diesen freizugeben.
edit: Der Algorithmus muss also klar vorgegeben haben, wem eine Referenz "gehört" (der darf sie dann auch Löschen), muss allerdings warten, bis alle anderen die Referenz nichtmehr Benutzen (was sie durch den Hazard pointer Record ja dem freigebenden Thread signalisieren). Und Benutzen heißt hier meist eher ein bisschen was anderes als man so intuitiv annehmen würde: zB bei der Queue bedeutet es, dass jemand noch einen Snapshot eines Zeigers für den (ehemaligen) Listenanfang der Queue hat, er aber noch nicht dazu gekommen ist, ein CAS für das echte dequeuen auszuführen (das dann sowieso scheitern wird, weil der Listenanfang ja bereits weitergezogen ist). Warum braucht er dazu überhaupt einen hazardpointer? Naja, er muss vor dem CAS die next-Referenz lesen (d.h. der andere darf nicht einfach deallozieren) und dann im CAS versuchen den momentanen Listenanfang gegen die next-Referenz einzutauschen.

Wie oben schon gesagt, kann ich nur wiederholen: Man kann bei solchen Sachen nicht einfach Methode X nehmen und blindlinks irgendwie einsetzen. Es hängt extrem stark vom konkreten Algorithmus ab, ob das dann überhaupt noch korrekt ist.

Das nächste ist das ich nicht glaube das dieser Mechanismus mit einer wirklich großen Anzahl an Threads (>10000) gut skaliert.

Und Locks machen das oder wie?
Erwartest du ernsthaft eine "Silberkugel" die alle Parallelitätsprobleme löst? Und dann auch noch so, dass jeder Idiot der 10000 Threads erzeugt ohne Probleme damit durchkommt?
Man müsste auch mal überlegen was genau mit Thread hier gemeint ist, es könnte sein, dass pro Kernelthread + Core (letzteres für Syscalls) ausreichend ist.

da mein Mathe einfach zu schlecht ist, um es irgendwie beweisen zu können

Was (reale) Performance angeht wüsste ich nicht, wie man da irgendwas auf Papier beweisen kann.

[FlashBurn]

Ich glaube wir sollten wirklich langsam mal einen Thread (wahrscheinlich besser einen Thread pro Datenstruktur) für Lock-freie Algos aufmachen. Damit man mal verschiedene Ansätze diskutieren kann (vorallem im Vergleich zu Locking und sehr feinem Locking) und die Infos mal irgendwo auch stehen. Denn das ist bisher mein Problem, das es scheinbar für ziemlich viele Probleme/Datenstrukturen Lock-freie Algos gibt, aber man keine Übersicht hat, welche es gibt und wie sie funktionieren.

Als Bsp. seien mal die Hazard-Pointers genannt, ist ja schön und gut, wenn man weiß wie die funktionieren, aber wie erik schon zurecht gefragt, wozu sind die gut und wo und wie verwendet man die und bringt es dann auch etwas.

Ich denke solche Themen dürften alle hier weiterhelfen.

Um aber mal allgemein zu bleiben, mir will die Sache mit der Zeit nicht aus dem Kopf gehen. Ich meine was passiert, wenn sich ein Thread einen Pointer holt und dann, aus welchem Grund auch immer, ne Weile nicht an die Reihe kommt und der Zufall es so will das der Pointer und die ihn schützende Struktur gleich sind, aber sich ganz andere Daten dahinter befinden?
Ein Lock kann das zuversichtlich verhindern, aber nicht wenn das Lock Bestandteil der Datenstruktur ist (Bsp. Queue wo man jedes Element lockt, auch beim Lesen -> RW-Lock).
Um auch nochmal erik´s Bsp aufzugreifen, auch wenn man das Freigeben bei Hazard-Pointern weit nach Hinten schiebt, kann die Situation auftreten (auch wenn sie erstmal nur theoretischer Natur ist), dass das Einfügen bzw. das Erstellen des Hazard-Pointers erst sehr lange nach dem Holen des Pointers passiert und der Pointer jetzt wieder dummerweise den selben Wert hat wie vorher (obwohl es sich um eine ganz andere Datenstruktur und Daten handelt). Geht das theoretisch?

[bluecode]

Um aber mal allgemein zu bleiben, mir will die Sache mit der Zeit nicht aus dem Kopf gehen. Ich meine was passiert, wenn sich ein Thread einen Pointer holt und dann, aus welchem Grund auch immer, ne Weile nicht an die Reihe kommt und der Zufall es so will das der Pointer und die ihn schützende Struktur gleich sind, aber sich ganz andere Daten dahinter befinden?

Das kann bei Hazard-Pointern eben nicht passieren. Du deallozierst den Pointer nur und er kann auch erst dann wiederverwendet werden bzw. wieder in der Datenstruktur vorkommen, wenn kein anderer Thread denselbigen hält.

Um auch nochmal erik´s Bsp aufzugreifen, auch wenn man das Freigeben bei Hazard-Pointern weit nach Hinten schiebt, kann die Situation auftreten (auch wenn sie erstmal nur theoretischer Natur ist), dass das Einfügen bzw. das Erstellen des Hazard-Pointers erst sehr lange nach dem Holen des Pointers passiert und der Pointer jetzt wieder dummerweise den selben Wert hat wie vorher (obwohl es sich um eine ganz andere Datenstruktur und Daten handelt). Geht das theoretisch?

Nein, du holst dir zuerst einen Snapshot des Pointers, packst den dann in deinen Hazardpointerrecord. Bevor du allerdings weitermachst überprüfst du nochmals ob der globale Pointer mit dem eigenen Snapshot übereinstimmt (das wird im Paper iirc als Validieren bezeichnet). Dadurch wird sichergestellt, dass zu dem Zeitpunkt zu dem der Thread den Hazardpointer in den Hazardpointerrecord geschrieben habe, dieser noch "in der Datenstruktur war" und noch niemand angefanngen hat ihn freizugeben (also auch noch nicht angefangen hat durch den Hazardpointerrecord zu laufen, um zu schauen ob andere diesen Pointer mitbenutzen).

[FlashBurn]

Nein, du holst dir zuerst einen Snapshot des Pointers, packst den dann in deinen Hazardpointerrecord. Bevor du allerdings weitermachst überprüfst du nochmals ob der globale Pointer mit dem eigenen Snapshot übereinstimmt

Und genau nach dem Holen des Snapshots wird der Thread pausiert, für eine so lange Zeit, die ausreicht damit der Speicher freigegeben werden kann und wieder alloziert wird.
Jetzt kommt der Thread wieder an die CPU und packt den Pointer in seinen Hazardpointerrecord und überprüft den Pointer nochmal und dummerweise ist der gleich, aber die Daten sind nicht mehr die die man dachte zu überprüfen.

Ist das theoretisch möglich?

[bluecode]

Verstehe ich nicht wirklich, denn du überprüfst mit dem Validieren ja nicht, ob die Datenstruktur noch gleich ist (so etwas würde ja erst zum ABA-Problem führen), sondern nur, dass der Zeiger nicht freigegeben ist (zum Zeitpunkt des Validierens dann, was ich vorher wohl anders gesagt habe). Und nach dem validieren weiß ich, dass er nicht freigegeben werden darf (=> Man greift nicht auf einen bereits freigegebenen Zeiger im weiteren zu) und damit auch, dass er nicht wiederverwendet wird (=> Man hat kein ABA-Problem, bezogen auf diesen Zeiger).

[erik.vikinger]

Hallo,

Ich glaube du verwechselst da was mit den Hazard-Pointern

Full ACK!
Ich hab auch immer noch nicht so ganz begriffen an welcher Stelle genau die eigentlich Sicherheit bringen sollen. Ein Szenario was ich glaube ich so langsam begriffen hab ist das Datenstrukturen niemals direkt modifiziert werden sondern nur kopiert und dabei modifiziert und zum Schluss passend eingehangen werden, hier kann es aber passieren das wenn mehrere Threads gleichzeitig das probieren das dieser Job doppelt so oft als nötig durchgeführt wird und dabei eine ziemliche Menge an Daten kopiert wird so das ich da (je nach Strukturgröße) kaum an einen echten Performancevorteil für die Lock-Free-Version glauben kann. Es kommt dabei zwar nicht mehr zu einem Dead-Lock aber eventuell zu einem gefühlten Live-Lock weil einige Threads sehr oft den selben Job immer wieder durchführen bis sie dann auch tatsächlich mal erfolgreich damit sind. Hier könnte ein kleine Schleife die versucht einen Lock zu bekommen und nach jedem Fehlversuch ein PAUSE macht eventuell deutlich schonender mit den globalen Ressourcen (Speicherbandbreite usw.) umgehen.

Ich schätze mal wir können uns hier auf ein "hängt von der gegebenen Situation ab" einigen.

Der Gedanke mit dem Skalieren ist gar nicht mal so verkehrt, aber seien wir ehrlich, ich denke nicht das die Performance von bisherigen Lock, Lock-Free oder Wait-Free (die ja eh performancemäßig schlecht sind) Algos in den Deminsionen irgendwas reißen können.

Was mir persönlich an diesen Hazard-Pointern nicht gefällt ist das die selber nicht gut skalieren. Man kann das zwar für eine im Voraus bekannte Anzahl an Threads recht gut implementieren (vom Speicherverbrauch bei vielen Threads mal abgesehen) aber wenn das eben nicht bekannt ist (und das trifft bei einem General-Purpose-OS IMHO immer zu) sind Hazard-Pointer wohl keine gute Wahl und werden in einer dynamischen Variante sicher auch kein O(1) mehr erreichen (oder höchstens mit irgendwelchen Randbedingungen die man in einer unvorhersehbaren General-Purpose-Umgebung eben nicht zusichern kann).

Wenn wir von 16 oder 32 Threads reden, sind ja anscheinend (da mein Mathe einfach zu schlecht ist, um es irgendwie beweisen zu können) Lock-Free Algos wesentlich besser, wieso sollten sie also bei >10000 Threads wieder schlechter werden?

Ich glaube gar nicht mal das es hierbei allzu sehr auf die Anzahl der Threads ansich ankommt sondern wohl eher darauf wie vorhersehbar oder dynamisch diese ist. Was mir als nächstes in dem PDF von diesem Michael nicht gefällt ist das er mit LL/SC einfach nur ein CAS emuliert, ich weiß ja nicht genau was für Beschränkungen PowerPC dem LL/SC-Pärchen auferlegt aber wenn diese nicht allzu extrem sind dann kann man damit sehr viel besseres bauen (falls man die Idee hinter LL/SC wirklich verstanden hat). Ich unterstelle daher einfach mal (ohne es zu beweisen, bitte widersprecht mir wenn ich mich irre) das die gezeigten Bench-Mark-Ergebnisse von keiner relevanten Bedeutung sind.

Zumal du bei einer solchen Thread Anzahl wahrscheinlich ganz andere Probleme hast.

Wieso? Wir haben doch hier auch schon darüber diskutiert das ein HTTP-Server der einfach forkt durchaus eine gute Performance bringen kann (und da war wimre von mehr als 10000 Prozessen die Rede), also zumindest das damalige Linux hat mit einer großen Anzahl an Prozessen keine Probleme bekommen und von einem modernen General-Purpose-OS erwarte ich auch keine Probleme mit einer entsprechenden Anzahl an Threads (ich könnte jetzt natürlich erzählen das es in einem 32Bit-Flat-Memory-System eventuell schwierig werden könnte entsprechend viele Stacks in den einen virtuellen Prozess-Adressraum zu quetschen aber das hatten wir ja schon mal ).

der ist mit Sicherhheit eher zu treffen als die Version

Du musst aber gerade beides treffen, damit ein CAS das scheitern sollte trotzdem gutgeht und die Datenstruktur damit kaputtmacht.

Weiß ich doch, ich wollte damit nur ausdrücken das wenn es in den Bereich des Möglichen kommt die Version zu treffen das dann der eigentliche Pointer auch keine so große Hürde mehr ist.

Der Suchvorgang ist nur dazu da Speicher freizugeben, d.h. das kann man ne ganze Weile rausschieben.
[....]
Deswegen habe ich oben auch schon gesagt, dass es problematisch sein kann, da man bei vielen Threads ewig keinen Speicher freigibt.

Aha, ich denke jetzt verstehe ich etwas besser. Der Speicherverbrauch ist dann aber das eigentliche Problem (was durch die exponentiell großen internen Listen in diesen Hazard-Pointern noch zusätzlich verstärkt wird) und in einer Umgebung mit einer dynamischen Anzahl an Threads könnte es dann eventuell zu einem Out-of-Memory kommen obwohl eigentlich genug Speicher da ist.

Nebst dessen das auch dieses Suchen auf ein einigermaßen deterministisches zeitliches Verhalten angewiesen ist.

Nein.

Und wie soll dann mein Szenario vom 12.08. Abends gelöst werden?

jeder versucht nur die Zeiger freizugeben die er aus der Datenstruktur entnommen hat. Stell dir zB eine Queue vor und jeder holt da einen Workitem raus. Da dabei nur einer einen bestimmten Workitem rausnimmt wird auch nur der versuchen diesen freizugeben.

Aber zum Entnehmen aus der Queue benötigt man dann ja doch wieder einen Lock oder einen weiteren Lock-Free-Algorithmus. Damit ist doch dann eigentlich die erforderliche Seriallisierung bereits erledigt oder meinst Du eine Single-Writer/Multiple-Reader-Situation?

Warum braucht er dazu überhaupt einen hazardpointer? Naja, er muss vor dem CAS die next-Referenz lesen (d.h. der andere darf nicht einfach deallozieren) und dann im CAS versuchen den momentanen Listenanfang gegen die next-Referenz einzutauschen.

Okay, ich glaub das hab ich verstanden. Trotzdem bin ich der Meinung das man das mit LL/SC sehr viel besser hinbekommen kann und das ganz ohne irgendwelche Listen usw. Ich vermute der Grund warum das in dem PDF vom Michael so schlecht performt ist darin zu suchen das er eben ein CAS nachbaut obwohl das mit dem Next-Pointer sich mit LL/SC auch direkt lösen lässt (sogar mit extremen Einschränken beim LL/SC-Pärchen).

Das nächste ist das ich nicht glaube das dieser Mechanismus mit einer wirklich großen Anzahl an Threads (>10000) gut skaliert.

Und Locks machen das oder wie?

Wenn jeder Thread eine andere Struktur locken und bearbeiten will dann schon (wenn jeder dieser Strukturen in einer anderen Cache-Line liegt dann gibt es nicht mal spürbare Performance-Probleme). Wenn alle durch ein Nadelöhr wollen (z.B. Anhängen an eine Queue) ist das natürlich was anderes aber das ist wohl sowieso kein Fall für Hazard-Pointer.

Erwartest du ernsthaft eine "Silberkugel" die alle Parallelitätsprobleme löst?

Natürlich nicht. Ich denke Hazard-Pointer können dann einen Vorteil bringen wenn es sich um wenige und vor allem um eine einigermaßen bekannte Anzahl an Threads handelt.

Und dann auch noch so, dass jeder Idiot der 10000 Threads erzeugt ohne Probleme damit durchkommt?

Ja, das schon. Erwartest Du da etwa Probleme?

Was (reale) Performance angeht wüsste ich nicht, wie man da irgendwas auf Papier beweisen kann.

Beweisen nicht aber plausibel erklären sollte möglich sein (unter der Voraussetzung das wir Computer als deterministische Systeme betrachten ).

Ich denke solche Themen dürften alle hier weiterhelfen.

Dem möchte ich mich ebenfalls anschließen.


Grüße
Erik

[FlashBurn]

Hier könnte ein kleine Schleife die versucht einen Lock zu bekommen und nach jedem Fehlversuch ein PAUSE macht eventuell deutlich schonender mit den globalen Ressourcen (Speicherbandbreite usw.) umgehen.

Das höre ich nicht zum ersten Mal, aber warum scheinen alle die Arbeiten dazu geschrieben haben zu einem anderen Ergebnis zu kommen? Bzw. wieso hört man aus der akademischen Welt nicht dass das absolut Unsinn ist?

Was mir als nächstes in dem PDF von diesem Michael nicht gefällt ist das er mit LL/SC einfach nur ein CAS emuliert

Da wären wir wieder schön bei den Problemen von portablen Code, er wollte eine Variante zeigen, die auf allen Architekturen läuft, die irgendeine Art und Weise von CAS kann und da man mit LL/SC CAS emulieren kann, aber nicht umgekehrt, hat er sich wohl dafür entschieden.

Wenn alle durch ein Nadelöhr wollen (z.B. Anhängen an eine Queue) ist das natürlich was anderes aber das ist wohl sowieso kein Fall für Hazard-Pointer.

Nur dieser Fall ist interessant, weil ansonsten hat man weder mit der einen Varianten, noch mit der anderen ein Problem (außer das Locking bei einzelnen Threads schneller ist als Lock-Free) und genau dieser Fall ist ein Fall für Lock-Free Algos und damit Hazard-Pointers.

So um nochmal eins festzuhalten, ich habe im Moment ein Problem wie man bei Lock-Free Algos z.B. das Iterieren durch eine Liste machen können soll und davon ausgehen können soll, das die Daten auch in Ordnung sind. Also wer macht mal nen Thread dazu auf

[Svenska]

Ich habe das Gefühl, dass ihr hier Skalierbarkeit und Performance verwürfelt... ob Hazard-Pointer oder Locks besser skalieren, sagt nämlich nichts darüber aus, was von beidem besser performt.

Beispiel: Der Ansatz des Giant Lock funktioniert prima, ist einfach und ist verdammt schnell für Uniprozessorsysteme (da sind die Locks immer frei). Auch bei 2..4 CPUs ist er gut, aber bei 64+ CPUs ist er halt scheiße.

Der Webserver skaliert besser, wenn er fork() benutzt, als wenn er poll() benutzt. Das sagt wiederum nichts über die absolute Performance aus und es stand dabei, dass sämtliche getesteten Betriebssysteme (einschl. Linux) während des Vernichtens der Prozesse nicht mehr reagieren; auch das hat interessante Konsequenzen unter Last.

So, jetzt könnt ihr bei dem Thema weitermachen. Ich halte fein granulierte Locks für eine gute Möglichkeit, weil ich sie (im Gegensatz zu den anderen hier genannten Methoden) verstehe.

Gruß,
Svenska

[erik.vikinger]

Hallo,

Das höre ich nicht zum ersten Mal, aber warum scheinen alle die Arbeiten dazu geschrieben haben zu einem anderen Ergebnis zu kommen? Bzw. wieso hört man aus der akademischen Welt nicht dass das absolut Unsinn ist?

Das wüste ich auch gerne mal, ich hab in der letzten Zeit auch mal etwas gesucht und einiges positives über Lock-Free gefunden, z.T. auch mit ansprechenden BenchMark-Ergebnissen drin. Das Problem ist das ich nur selten wirklich sagen kann ob da nicht eventuell die Gegenseite schlechter gemacht wird als sie ist (womit ich definitiv keine Absicht sondern aller höchstens Unkenntnis unterstellen möchte).

Da wären wir wieder schön bei den Problemen von portablen Code, er wollte eine Variante zeigen, die auf allen Architekturen läuft, die irgendeine Art und Weise von CAS kann und da man mit LL/SC CAS emulieren kann, aber nicht umgekehrt, hat er sich wohl dafür entschieden.

Wenn er sich für CAS entscheidet dann soll er auch eine Plattform nehmen die das nativ anbietet. Ein ordentlich implementierter CAS-Befehl ist mit Sicherheit schneller als zwei unabhängige LL/SC-Befehle (dafür sind letztere deutlich Leistungsfähiger so das man mit einem passenden SW-Algorithmus hier wieder schneller ist, bei ansonsten vergleichbarer Plattformperformance wie Speicherbandbreite/latenz usw., nebst dessen das LL/SC sicherer ist weil prinzipbedingt kein ABA-Problem o.ä. auftreten kann). Das Argument mit dem portablen Code lass ich auch nicht durchgehen da LL/SC gerade in der besseren RISC-Welt (Alpha / ARM / MIPS / PowerPC / SPARC / ...) recht verbreitet ist. Das ist so als würde ich aus Kompatibilität zur rollenden Fortbewegung das manuelle Fahrrad wählen und ignorieren das es motorisierte Autos gibt.

Ich habe das Gefühl, dass ihr hier Skalierbarkeit und Performance verwürfelt...

Sicherlich etwas, ja. Aber woher bekommt man da mal belastbare BenchMark-Ergebnisse?

Ich halte fein granulierte Locks für eine gute Möglichkeit, weil ich sie (im Gegensatz zu den anderen hier genannten Methoden) verstehe.

Da bist Du nicht der einzigste.
Gerade das ist auch ein sehr wichtiges Argument. Dinge die der Programmierer nicht so richtig verstanden hat sind eventueller etwas verbugter oder nur suboptimal umgesetzt.


Grüße
Erik

[FlashBurn]

Beispiel: Der Ansatz des Giant Lock funktioniert prima, ist einfach und ist verdammt schnell für Uniprozessorsysteme (da sind die Locks immer frei). Auch bei 2..4 CPUs ist er gut

Du meinst also der Giant Lock (vorallem wenn ich da zwangsläufig an Linux = monolith denke) ist auch noch bei 2 bis 4 CPUs gut? Das kann ich einfach nicht glauben. Allerdings sollten wir erstmal klären, was genau meinst du mit Giant Lock? Einen Lock der im Endeffekt den gesamten Kernel schützt?

Würde ich den bei mir verwenden, würde schon das Initialisieren des Kernels linear pro CPU ansteigen und bei nem monolithen dürfte es noch schlechter sein als bei nem MikroKernel (zwecks das die ganzen Subsysteme außerhalb des Kernels liegen und erstmal nicht direkt davon betroffen sind).

Das Argument mit dem portablen Code lass ich auch nicht durchgehen da LL/SC gerade in der besseren RISC-Welt (Alpha / ARM / MIPS / PowerPC / SPARC / ...) recht verbreitet ist. Das ist so als würde ich aus Kompatibilität zur rollenden Fortbewegung das manuelle Fahrrad wählen und ignorieren das es motorisierte Autos gibt.

Das war erstmal nur eine Vermutung meinerseits, aber gucke dir doch Android an, was man da zwecks Portabilität gemacht hat (ich sag nur VM).

[bluecode]

@erik: Ich glaube dir zu antworten, verschiebe ich auf einen Eintrag im Wiki, den ich hoffentlich irgendwann Mitte/Ende der Woche anfange. Aber ich bin mir ziemlich sicher, dass du nicht weißt, was die Definition von lockfrei ist, was wohl das erste sein wird, was in den Eintrag kommt.

So um nochmal eins festzuhalten, ich habe im Moment ein Problem wie man bei Lock-Free Algos z.B. das Iterieren durch eine Liste machen können soll und davon ausgehen können soll, das die Daten auch in Ordnung sind.

Wie ich oben schonmal versucht habe zu sagen, es ist wichtig, dass man zuerstmal genau spezifiziert was eine Operation (nach außen hin) leisten soll. "Iterieren durch eine Liste" ist aber genau eine Implementierung und keine Spezifikation eines Interfaces. Ist das was du suchst eine Menge, die folgendes unterstützt:
* set::contains(x): Gibt true zurück, falls die Menge x enthält
* set::insert(x): Fügt x hinzu falls es noch nicht in der Menge ist
* set::remove(x): Entfernt x, falls es in der Menge ist
Wie man diese Datenstruktur implementiert, kann man auch Michaels entnehmen (solange die Elemente eine totale Ordnung haben): Er benutzt dazu eine geordnete, einfach verkettete Liste. Die muss er natürlich auch durchlaufen, um ein Element zu finden. Das Problem ist jetzt, dass man nicht einfach dieses Durchlaufen der Liste in einem anderen Kontext verwenden kann.
Warum? Weil es doch überhaupt nicht klar ist, was das bedeuten soll, wenn sich die Liste vor und hinter "mir" verändert während ich durchlaufe. Ein ganz einfach Beispiel (das vollkommen unabhängig davon ist wie man es implementiert, es hängt nur davon ab, dass andere parallel etwas an der Datenstruktur machen dürfen): Es soll eine Methode implementiert werden, die alle Werte dieses Sets aufsammelt. Nehmen wir an ich bin eine Weile durch die Liste gelaufen und hab mir die Elemente gemerkt. Jetzt fügt jemand (irgendwo) hinter mir ein Element x ein und jemand anders löscht anschließend (irgendwo) vor mir ein Element y. Ich laufe jetzt weiter und stelle fest in meiner Menge ist weder x noch y. Jetzt natürlich die Masterfrage: Gab es überhaupt einen Zeitpunkt während meiner Operation, bei der weder x noch y in der Menge war? Nein, anfangs war y in der Menge, dann kam x dazu, dann wurde y entfernt und x blieb. Das heißt es gibt keinen atomaren Zeitpunkt, bei dem die Operation "ausgeführt wurde" (d.h. sie ist nicht linearisierbar, eine der wichtigsten Korrektheitsbegriffe für lockfreie Algorithmen und das zweite was in den Artikel kommt). Wenn du mit so wenig Semantik glücklich werden kannst, dann prima. Andernfalls musst du ganz klar definieren was die Operation tun soll.
Das andere ist: Es reicht auch nicht aus zu spezifizieren was eine der Operationen machen soll, sondern man muss vorher klären was man alles an Operationen unterstützen will. Beispiel: Ich will das Iterieren von vorhin, aber niemand darf löschen oder was hinzufügen. Dann ist wohl offensichtlich wie man das hinkriegt, der Erkenntnisgewinn ist allerdings gleich 0 (d'uh).

edit: Was ich damit sagen will ist auch, dass wenn ich dazu einen Eintrag verfassen soll, dass man dann Beweisen muss warum etwas korrekt ist (und bezogen auf was überhaupt, siehe Linearisierbarkeit oben) und man muss natürlich auch Beweisen das etwas lockfrei ist. Wenn ihr darin Interesse habt und Feedback gebt, kann ich da gerne anfangen, aber sonst würde ich das lassen.

Ich wollte noch was zu LL/SC sagen: Soweit ich weiß kann man die nicht verschachteln (also auf mehrere Speicheradressen gleichzeitig anwenden), was man aber braucht für andere Algorithmen. Und es löst nur das ABA-Problem, nicht aber das Problem, dass man gerne Speicher freigeben würde.

ROFLMAO, das war mein leetster Beitrag 

[FlashBurn]

Ich sehe schon, das mit den Lock-Free Algos wird ne harte Nuss

So mir ist jetzt aber noch ein Grund eingefallen warum sie besser (im Sinne von Schneller und Skalieren) sein könnten (ich hoffe es doch). Auch wenn das Thema hier Locking im Kernel ist, kann man im UserSpace nicht mal einfach die Ints ausmachen (womit dann Spinlocks sehr teuer werden können). Sprich man hat die Wahl ob man ne Spinlock nimmt, die kann aber unter Umständen die ganze Zeit des Threads durch sinnloses spinnen verschwenden (selbst wenn man nach einigem Warten abgibt oder gleich abgibt, kommt als Zeit, noch die Threadwechsel dazu), man kann auch nen Mutex nehmen, aber das erfordert wiederrum den Eintritt in den Kernel und wieder zwei Threadwechsel (einen zum Thread hin, der gerade die Mutex hat und einen wieder zurück zum Thread, der versucht hat die Mutex zu bekommen). Bei Lock-Free Algos kann aber jeder Thread fortschritte machen, egal ob gerade ein anderer Thread auch versucht etwas zu ändern. Sprich der worst-case, nämlich Thread A hat alles soweit das er die Datenstruktur ändern will und wird unterbrochen und Thread B kommt an die Reihe und will auch etwas ändern, bei einer Spinlock und der Mutex muss er warten bis Thread A fertig ist, aber bei einem Lock-Free Algo kann Thread B einfach ganz normal sein Ding durchziehen, ohne das er von Thread A behindert/ausgebremst wird. Spinning im UserSpace ist sogar richtig gefährlich, weil es ja sein kann das Thread A den Lock hat und Thread B eine viel höhere Priorität hat, damit wird Thread A unterbrochen und Thread B blockiert beim Spinnen die Freigabe des Locks.

@bluecode

Ich, und ich denke auch erik, bin sehr darin interessiert. Ich muss aber ehrlich zugeben, ich habe irgendwie nichts von dem was du geschrieben hast wirklich verstanden

[bluecode]

Bei Lock-Free Algos kann aber jeder Thread fortschritte machen [...]

Das stimmt so nicht ganz. Man kann nicht isoliert auf jeden Thread sagen dass dieser Fortschritt macht (im Sinne von "er kommt seinem Ziel näher"), sondern man kann nur sagen, dass immer wieder irgendein Thread seine Operation fertig ausgeführt hat (Das ist quasi genau die Definition von lockfree). Das für sich genommen ist nicht unbedingt spannend, viel spannender ist, welche Ereignisse dabei nicht ausgeschlossen werden: Es wird nicht ausgeschlossen, dass ein Thread endlich oder unendlich lang nicht geschedult wird oder das er einfach abgebrochen wird. Es kann also per Definition keinen Deadlock, Livelock oder Priority Inversion geben. Und im Prinzip hat die Performance viel weniger mit dem Scheduler zu tun als bei Algorithmen mit Locks, insofern würde ich (im Ggs. zu erik) behaupten, dass in keinster Weise irgendwas vom zeitlichen Verhalten abhängt...

Ich muss aber ehrlich zugeben, ich habe irgendwie nichts von dem was du geschrieben hast wirklich verstanden

Auch nicht den letzten Beitrag von mir?

[FlashBurn]

Auch nicht den letzten Beitrag von mir?

Den meinte ich ja