Weiß jemand, ob es in Haskell eine Lock-Free-Programmierung gibt? Ich bin sowohl an der Frage interessiert, ob die geeigneten Low-Level-Primitive verfügbar sind, als auch an (sofern vorhanden) Informationen darüber, was im Hinblick auf die Verwendung von diesen zum Aufbau funktionierender größerer Systeme im reinen funktionalen Kontext funktioniert. (Ich habe noch nie eine Lock-Free-Programmierung in einem reinen funktionalen Kontext gemacht.) Zum Beispiel, wie ich es verstehe, sind die Control.Concurrent.Chan-Kanäle auf MVars aufgebaut, die (wie ich die Dinge verstehe) Locks verwenden-- -könnte man grundsätzlich Versionen des Chan-Primitivs erstellen, die intern frei von Sperren sind? Wie viel Leistungssteigerung könnte man hoffen?
Ich würde auch sagen, dass ich mit der Existenz von TVaren vertraut bin, aber verstehe ihre interne Implementierung nicht - ich habe mir vorgenommen zu verstehen, dass sie meistens frei von Sperren sind, aber ich bin mir nicht sicher, ob sie völlig frei von Sperren sind. Also wären auch Informationen über die interne Umsetzung von TVaren hilfreich!
( Dieser Thread bietet einige Diskussionen, aber ich frage mich, ob es irgendetwas gibt aktueller / umfassender.)
Nicht nur, dass ein MVar Sperren verwendet, es ist eine Sperre Abstraktion. Soweit ich mich erinnere, sind einzelne STM-Primitive optimistisch, aber es gibt Locks, die an verschiedenen Stellen in der STM-Implementierung verwendet werden. Denken Sie nur an den handlichen Reim: "Wenn es blockieren kann, dann hüten Sie sich vor Schlössern."
Für echte Lock-Free-Programmierung möchten Sie IORefs direkt zusammen mit atomicModifyIORef verwenden.
Bearbeiten: in Bezug auf schwarze Löcher, wie ich mich erinnere die Umsetzung ist frei von Sperren, aber ich kann nicht für die Details bürgen. Der Mechanismus wird in "Laufzeitunterstützung für Multicore-Haskell" beschrieben: Ссылка
Aber diese Implementierung hat einige Verbesserungen erfahren, denke ich, wie in Simon Marlows 2010 Haskell Implementors Workshop-Vortrag "Scheduling Lazy Evaluation on Multicore" beschrieben: Ссылка . Die Folien sind leider offline, aber das Video sollte trotzdem funktionieren.
Lock-free-Programmierung ist in Haskell trivial. Die einfachste Möglichkeit, ein gemeinsames Datenelement zu verwenden, das von vielen Threads geändert werden muss, besteht darin, mit einem normalen Haskell-Typ (Liste, Map, Vielleicht, was immer Sie benötigen) zu beginnen und es in ein IORef zu platzieren. Sobald Sie dies getan haben, haben Sie die Möglichkeit, atomicModifyIORef zu verwenden, um Änderungen an Ort und Stelle vorzunehmen, die garantiert im Handumdrehen erfolgen.
%Vor%Der Grund dafür ist, dass ein Zeiger auf den Think gespeichert wird, der das Ergebnis innerhalb des IORefs schließlich auswertet, und wenn ein Thread aus dem IORef liest, erhalten sie den Thunk und evaluieren so viel von der Struktur, wie sie benötigt . Da alle Threads dieses gleiche Thunk lesen können, wird es nur einmal ausgewertet (und wenn es mehr als einmal ausgewertet wird, hat es garantiert immer das gleiche Ergebnis, so dass gleichzeitige Bewertungen in Ordnung sind). Ich glaube, das ist richtig, aber ich bin froh, dass es korrigiert wurde.
Die Botschaft von diesem Beispiel ist, dass diese Art von Abstraktion nur leicht in einer reinen Sprache implementiert werden kann, wo sich der Wert der Dinge niemals ändert (außer natürlich, wenn sie es tun, mit Typen wie IORef, MVars und den STM-Typen) ). Die Kopie über die Schreibweise von Haskells Datenstrukturen bedeutet, dass geänderte Strukturen viele Daten mit der ursprünglichen Struktur teilen können, während sie nur alles zuweisen, was neu für die Struktur ist.
Ich glaube nicht, dass ich sehr gut erklärt habe, wie das funktioniert, aber ich werde morgen zurückkommen und meine Antwort klären.
Weitere Informationen finden Sie in den Folien zum Vortrag Multicore Programmierung in Haskell von Simon Marlow von Microsoft Research (und einer der wichtigsten GHC-Implementierer).
Tags und Links haskell