lock-free Queue
-
FlashBurn schrieb:
hustbaer schrieb:
für Lesen mit CAS braucht man natürlich gar keine Retry-Schleife, da hab ich Unsinn geschrieben. CAS liefert bei x86 ja die Werte zurück die vor dem eventuellen Tausch im Ziel gestanden haben. Ein einziges CAS(&target, 0, 0) reicht also. Bleibt trotzdem ineffizient, da CAS bekanntermassen viel langsamer ist als ein oder zwei normale Loads.
Das Problem mit CAS (in dem Zusammenhang mit paralleler Ausführung) ist, das du dir nur sicher sein kannst das der ganze Spaß auch atomar ist, wenn du ein Lock-Präfix davor setzt und nach den Infos die ich gefunden habe, wird grundsätzlich auch ein Lock-Write auf den Memorybus geschickt (auch wenn nichts geändert wird) und damit "zerstörst" du den Cacheinhalt in anderen CPUs. Zumal das Aktualisieren der Caches auch nicht unterschätzt werden sollte.
Ja, ich hab ja geschrieben "CAS bekanntermassen viel langsamer"
Hab was von 200~~400 Zyklen in Erinnerung (Mit lock Prefix auf nem Core 2 Quad ohne dass zwei Threads sich um die Cacheline streiten, also idealfall. Und die Zahl ist aus dem Gedächtnis, aber die Grössenordnung müsste hinkommen).Wobei... wer sagt denn dass der Load-Teil des CAS nicht auch ohne lock Prefix atomar ist? Müsste er IMO sein. Und ohne Lock Prefix sollte das durchaus akzeptabel schnell sein.
EDIT: man müsste natürlich einen Vergleichswert verwenden, der nie vorkommen kann, damit sicher gestellt ist, dass nie geschrieben wird. Und... ist
lockbeicmpxchg8bnicht sowieso implizit? Hmmm... /EDITHast du (oder jemand) denn eine Idee wie man das Problem, dass man auf nicht mehr vorhandenen Speicher zugreift, umgehen kann ohne das man Hazard-Pointers nutzt?
Ich nicht (jemand vielleicht schon
).D.h. der Teil wo man auf nichtmehr vorhandenen Speicher zugreift ist noch einfach: man gibt die Nodes halt nicht frei, sondern steckt sie in eine (per-thread) Free-List. Bloss ist es ja vermutlich genau so ein Problem, wenn sich der Inhalt einer Node (Next-Pointer) einfach so ändert, weil sie (u.U. in einer ganz anderen Liste) wiederverwendet wurde.
-
hustbaer schrieb:
Wobei... wer sagt denn dass der Load-Teil des CAS nicht auch ohne lock Prefix atomar ist? Müsste er IMO sein. Und ohne Lock Prefix sollte das durchaus akzeptabel schnell sein.
EDIT: man müsste natürlich einen Vergleichswert verwenden, der nie vorkommen kann, damit sicher gestellt ist, dass nie geschrieben wird. Und... ist lock bei cmpxchg8b nicht sowieso implizit? Hmmm... /EDIT
Das mit dem lock, da scheiden sich die Geister
Jeder sagt was anderes, aber ich kann es mir so erklären:XCHG ist immer "gelockt" und wenn du bei CMPXCHG kein LOCK verwendest dann ist nur der XCHG Teil atomar, verwendest du bei CMPXCHG LOCK, dann ist das CMP und der XCHG atomar!
Naja, ich hoffe ja noch das ich entweder eine Erleuchtung habe oder aber noch wirklich funktionierend Code finde.
-
Den Code muss ich mir nochmal richtig angucken und ändern. Denn beim Entfernen ist noch mind. 1 Fehler drin (ich packe ja in die leere Queue ein Dummy-Element, aber anstand beim Entfernen das erste wirkliche Element zu entfernen entferne ich jedes Mal das Dummy-Element und ändere aber den Head.ptr nicht
).Auch muss ich das Dummy-Element mit new erzeugen damit ich es überhaupt freigeben kann! Denn das wird ja gemacht damit immer ein Element in der Queue ist und Head/Tail nicht ins leere zeigen.
Das andere Problem bleibt aber, meiner Meinung nach, bestehen.
-
Also Hazard-Pointers sind eine Lösung um die Probleme mit dem Memory Management (wenn man keinen GC hat) zu lösen.
Am Bsp. der Queue ist ja das Problem, dass man eventuell einen Pointer dereferenziert (also liest) von einem Speicherbereich der schon wieder weg (im Sinne von geunmappt, dem OS zurückgegeben) ist und man eine Exception auslöst. Wenn ein Thread nicht unterbrochen werde kann solange er an der Queue arbeitet, sollte das Problem ja theoretisch nicht auftauchen können (da in dem speziellen Fall der Speicher auch nicht so schnell freigegeben wird, da dafür doch ein wenig Code von nöten ist (ca. 100 - 1000 Opcodes).
Also noch mal kurz, würde die Queue (mit dem Update-Tag wie im ersten Post ersichtlich) funktionieren, wenn man davon ausgeht das der Code nicht unterbrochen wird?
-
Noch eine Frage zu dem scheinbar "einfachen" lock-free Queue Algo wie er oft benutzt wird.
Mir ist (das glaube ich zumindest) eine Situation eingefallen, wo dieser Algo selbst mit einem Garbage-Collector schief gehen kann.
Das Problem ist immernoch, dass man einen Pointer dereferenziert, der auf Speicher zeigt, der nicht mehr vorhanden ist.
Wäre es, theoretisch, nicht möglich das ich die Adresse eines Queue-Elements in ein CPU Register lade, der Thread wird darauf unterbrochen (vom Scheduler) und ein anderer Thread löscht jetzt genau dieses Element (bzw. entfernt es aus der Liste). Da der Code, der unterbrochen wurde, in einem Thread mit sehr niedriger Priorität lief und dummerweise eine Weile nicht dran kommt, kommt der Garbage-Collector mal wieder zum Laufen, baut seinen Graphen auf (um festzustellen welche Objekte endgültig freigegeben werden können) und gibt das Element frei, weil die Adresse ja in einem CPU Register steht und nicht in einer Speichervariable.Auch wenn dieser Fall sehr unwahrscheinlich ist, ist er doch möglich und der Code damit, meiner Meinung nach, auch mit einen Garbage-Collector nicht sicher!
-
Der GC inspiziert normalerweise die Register (und Stacks) von laufenden Threads.
Und wenn nicht, dann ist der GC kaputt, nicht der Algorithmus.
-
hustbaer schrieb:
Der GC inspiziert normalerweise die Register (und Stacks) von laufenden Threads.
Wenn du mir noch verrätst wie er das macht (das mit den Registern)? Denn dazu müsste er an den KernelSpace-Stack ran (was nicht geht, ohne das der GC im KernelSpace läuft) und er müsste noch den genauen Aufbau des Stacks kennen (ohne den er nicht weiß was ein Register ist oder irgendetwas anderes).
-
Bei "managed" Sprachen geht es relativ einfach: bevor ein Thread den "managed" Mode verlässt, sorgt er einfach dafür, dass alle Referenzen auf Objekte die er in Registern hält vom GC gefunden werden können. Dazu reicht es z.B. schon wenn der Thread vor dem Wechsel alle Register auf den Stack pusht.
Und vor dem Wechsel zurück in den "managed" Mode prüft der Thread ob gerade eine Collection läuft, und wenn ja, legt er sich schlafen bis die Collection abgeschlossen ist.
(Threads werden normalerweise nur im "managed" Mode angehalten, Threads die gerade "unmanaged" laufen dürfen gerne weiter laufen)Wie ein GC für "unmanaged" Sprachen das macht weiss ich nicht. Eine Möglichkeit wäre einfach so lange zu warten, bis alle Threads wieder im Usermode laufen. Wobei das natürlich auch ein Problem ist, denn man hat ja oft genug Threads die sehr sehr lange im Kernelmode auf etwas warten - u.U. so lange bis das Programm beendet wird.
Bzw. ich bin mir nichtmal sicher ob es überhaupt ein Problem ist - werden die Usermode Registerwerte nicht beim Wechsel in den Kernelmode noch am Usermode-Stack abgelegt, und sind damit für den GC lesbar?
Was den Aufbau des Stacks angeht: GCs für "unmanaged" Sprachen sind meist nicht exakt sondern konservativ. D.h. der GC nimmt einfach bei allem was am Stack rumliegt an dass es eine Referenz bzw. ein "innerer Zeiger" ist.
Und bei "managed" Sprachen kann der GC wissen welche Teile des Stacks Referenzen sind und welche nicht - der JITer kann ja die dazu nötigen Daten in diverse Tabellen schreiben.
-
Das ist so ziemlich das was ich mir gedacht habe. Die Register werden auf dem KernelSpace-Stack gespeichert.
Die GC die ich z.B. für C++ kenne, sind halt konservativ und leaken im Endeffekt Speicher, aber wie es mit dieser Sache aussieht weiß ich gar nicht, müsste ich mal nachgucken, aber ich bezweifle, dass das bedacht wurde.
Heißt Managed-Sprache eigentlich grundsätzlich VM (JIT-Compiler)?
-
Ich verwende "managed" zumindest mit dieser Bedeutung.
