Wie setzen Sie Software Transactional Memory?

Question

Im Hinblick auf die tatsächlichen niedrigen Niveau atomarer Befehle und Speicher Zäunen (ich nehme an sie gewöhnt sind), wie implementieren Sie STM?

Der Teil, der mir mysteriös ist, dass einige beliebigen Teil des Codes gegeben, Sie brauchen eine Möglichkeit, danach zurück zu gehen und festzustellen, ob die Werte in jedem Schritt verwendeten gültig waren. Wie machen Sie das, und wie tun Sie es effizient? Dies scheint auch darauf hin, dass wie jede andere ‚Verriegelung‘ Lösung, die Sie Ihre kritischen Abschnitte so klein wie möglich halten wollen (die Wahrscheinlichkeit eines Konflikts zu verringern), habe ich recht?

Auch kann STM einfach erkennen „ein anderer Thread diesen Bereich eingegeben, während die Berechnung ausgeführt wurde, also die Berechnung ist ungültig“ oder kann es tatsächlich erkennen, ob clobbered Werte verwendet wurden (und damit von Glück manchmal zwei Threads ausführen können die gleiche kritische Abschnitt gleichzeitig ohne Notwendigkeit für ein Rollback)?

Answer 1

Die einfachste Antwort ist „es kommt“. Es gibt Unmengen von radikal verschiedene Implementierungen in so ziemlich jede Art und Weise arbeiten sich vorstellen kann.

  

Der Teil, der mir mysteriös ist, dass einige beliebigen Teil des Codes gegeben, Sie brauchen eine Möglichkeit, darauf zurück zu gehen und festzustellen, ob die Werte in jedem Schritt verwendeten gültig waren. Wie machen Sie das, und wie tun Sie es effizient?

Eine Lösung ist Versionierung zu verwenden. Jedes Mal, wenn ein Objekt geändert wird, wird die Versionsnummer aktualisiert. Während die Transaktion ausgeführt wird, bestätigen Sie jede Version des zugegriffen Objekt, und wenn die Transaktion festgeschrieben wird, überprüfen Sie, dass die Objekte noch gültig. Diese Validierung kann ein einfacher Integer-Vergleich (wenn transaction_start_version >= object_version, das Objekt gültig ist), so kann es ziemlich effizient durchgeführt werden.

  

Dies scheint auch darauf hin, dass wie jede andere ‚Verriegelung‘ Lösung, die Sie Ihre kritischen Abschnitte so klein wie möglich halten wollen (die Wahrscheinlichkeit eines Konflikts zu verringern), habe ich recht?

Sehr wahrscheinlich. Ich denke, einige Implementierungen haben die Route der Annahme / erfordert gegangen alles eine Transaktion zu sein, aber ja, in den meisten Implementierungen Transaktionen sind speziell Teile des Codes markiert, und je länger eine Transaktion ausgeführt wird, desto größer die Möglichkeit eines Konflikts, die Transaktionen führen kann zurück zu rollen.

  

Auch kann STM einfach erkennen „ein anderer Thread diesen Bereich eingegeben, während die Berechnung ausgeführt wurde, also die Berechnung ist ungültig“ oder kann es tatsächlich erkennen, ob clobbered Werte verwendet wurden (und damit von Glück manchmal zwei Threads ausführen können die gleiche kritische Abschnitt gleichzeitig ohne Notwendigkeit für ein Rollback)?

Letzteres. Denken Sie daran, dass die Idee in TM zu schützen, ist Daten , anstatt Code .

Verschiedene Codepfade können die gleiche Variable in verschiedenen Transaktionen zugreifen. Dies muss durch das TM-System erfasst werden. Es gibt keinen wirklichen Begriff von „diesem Bereich“, da dieser auf Code bezieht, anstatt Daten. Das TM-System kümmert sich nicht darum, welcher Code ausgeführt wird, es verfolgt, welche Daten geändert werden. Auf diese Weise ist es durchaus von kritischen Abschnitten unterscheidet (den Code schützen, anstatt Daten)

Answer 2

Einige Papiere können wirklich schwierig zu lesen, aber zwei, die sind sehr klar und prägnant sind:

Transactional Locking II, Dave Dice, Ori Shalev, Nir Shavit , die beschreibt, die „TL2“ STM-Algorithmus in Bezug auf jede beliebige Sprache.

Deuce: Nichtinvasive Software Transactional Memory in Java, Guy Korland, Nir Shavit, Pascal Felber die erklärt eine Ladezeit Klasse Transformator, der in in-Memory-Klassen regelmäßig Java-Klassen transformiert, die zusätzliche Bytecode haben STM zu tun. Dies ist relevant für die Frage, wie das Papier erklärt, wie Code ohne STM kann mechanisch in Code umgewandelt werden, die STM in jeder OO Sprache tun.

Der Deuce Rahmen können Sie Plugin den eigentlichen Algorithmus Sie verwenden möchten; einschließlich des TL2-Algorithmus. Als Deuce Rahmen ist Java die folgende Diskussion Java-Terminologie verwendet, aber nur unter der Annahme, dass Sie in einer OO-Sprache schreiben.

Im Folgenden wird die TL2 Ansatz skizzieren. Die Papiere haben Links zu alternativen Ansätzen, aber das Studium eines Algorithmus beantwortet viele Fragen.

  

Wie implementieren Sie STM? Der Teil, der mir mysteriös ist, dass einige beliebigen Teil des Codes gegeben, Sie brauchen eine Möglichkeit, darauf zurück zu gehen und festzustellen, ob die Werte in jedem Schritt verwendeten gültig waren.

Eine kurze Antwort für wie TL2 tut STM „Buchhaltung“ ist und dann nur Schreibsperren unter Verwendung von Zeit zu begehen. Lesen Sie das Papier für die feinen Details aber ein Brett Pinsel Kontur ist wie folgt. Jede Eigenschaft, die Sie im ursprünglichen Code verwenden können, würde einen Getter und Setter haben. In dem transformierten Code gäbe es auch eine Versionsnummer der Immobilie und zusätzlicher Code hinzugefügt, um die Getter und Setter. Sie müssen die Version Aufzeichnung jedes Attribut, das Sie innerhalb der Transaktion zu lesen, wie die Transaktion „Read-Set“. Sie können dies tun, jeder Getter fügen Sie die Version des Attributs, indem er in einen Thread LinkedList gesehen. Sie müssen auch in einem Thread die Schreibvorgänge als „Schreib-Set“ puffern, bis Sie zu begehen. Beachten Sie, dass die Getter-Methoden einen Threadschreibfestgelegten Wert für ein bestimmtes Feld überprüfen und zurückkommen müssen, wenn Sie eine haben. So können Sie Ihre uncommitted schreibt in Ihrem sehen liest aber kein anderer Thread sie sehen wird, bis Sie zu begehen.

Zur Zeit verpflichten nehmen Sie Schreibsperren gegen jedes Attribut, das Sie im Begriff sind, zu schreiben. Während haben Sie die Sperren Sie überprüfen, dass Ihre Lese-Satz noch gültig ist; dass die Attribute, die Sie in Ihrer Transaktion nicht gelesen haben auf eine höhere Version durch eine andere Transaktion aktualisiert. Wenn ja, dann Ihre Geschäftslogik nicht gültig sein kann, wie Sie inkonsistent haben liest, so dass Sie die gesamte Transaktion rückgängig zu machen brauchen. Wenn die letzten Prüfungen bestanden werden dann begehen Sie durch Ihre Schreib Satz Spülung, stoßen die Versionen dieser Attribute, lassen Sie die Schreibsperren und endgültig klar sowohl die Schreib gesetzt und schreib gesetzt Threadlisten.

Das Papier erklärt, dass der Algorithmus frühzeitig abbrechen, wenn es erkennt, dass ein Attribut gelesen wird geschrieben wurde, da die tx gestartet. Das Papier hat ein paar nette Tricks Nurlesetransaktionen zu beschleunigen. Es hat sogar einen Trick, um herauszufinden, welche Blöcke sind schreibgeschützt und welche Lese- und Schreibberechtigung. Jeder, der ein Interesse an solchen Dingen ausdrücken sollte wirklich die beiden Papiere genießen.

Der Deuce Rahmen oben in dem Papier zeigt, wie alle durch die Injektion von neuem Java-Bytecode in Ihre Klassen zur Ladezeit Ihrer Getter und Setter ändern. Andere Sprachen können einen speziellen Compiler oder Prä-Prozessor haben, die die gleiche mechanische Transformation von normalen Code in STM aktiviert Code auszuführen. Insbesondere mit Deuce können Ihren Quellcode Objekte einfache Getter Setter Paare haben aber transformierte Klassen zur Laufzeit haben Getter Setter angereichert, die das tun, Bücherwurm.

Die Umwandlung regulären Code into STM-Code (insbesondere zur Laufzeit) ist interessant, aber wenn Sie tatsächlich benötigen, um eine STM aktiviert Datenstruktur schreiben Sie eine magische Sauce nicht brauchen. Statt nur eine Ref Klasse mit einem get() und einem set(x) schaffen und jede einzelne Beziehung zwischen der Datenstruktur Objekte aus Ref Griffe aus machen. Im get und set Ihre Ref Klasse können Sie die Threadbook tun. Dann können Sie eine einfache Version von „TL2“ oder einem anderen Algorithmus implementieren, die auch für Ihre Datenstrukturen und Ihre Gleichzeitigkeit von im Vergleich zu Schreib lesen funktioniert.

  

Dies scheint auch, dass vorschlagen wie jede andere ‚Verriegelung‘   Lösung, die Sie möchten, dass Ihre kritischen Abschnitte so klein wie möglich halten   (Die Wahrscheinlichkeit eines Konflikts zu verringern), habe ich recht?

TL2 hat eine kritische Phase in dem Halt der Schreibsperren dann Endkontrolle tun und schreibt die ohne Verständnis für die Anwendung Business-Logik zu begreifen, einfach und zu optimieren. Wenn Sie jede Zahl eine einzigartige Eigenschaft zuweisen können Sie trivialer Deadlock vermeiden durch Schleusen in aufsteigender Reihenfolge nehmen. Es ist wichtig zu beachten, dass alle Ihre Business-Logik spekulativ angenommen getan wird, dass die Kontrollen verpflichten passieren. Sie halten keine Sperren, während Sie beliebig langsam Geschäftslogik tun. Sie können mehrere Web-Service-Lookups oder langsame Datenbankaufrufe tun, und Sie werden alle Sperren nicht dauern, bis die begehen. Klar, dass die Profis werden das Heck aus dem allgemeinen kritischen Abschnitt zu stimmen.

Das Papier macht deutlich, dass der Algorithmus häufiger wird Abbruch, dass die spezifische Business-Logik erfordert. Der generische Algorithmus weiß nicht, ob bestimmte Dirty Reads nicht die tatsächliche Schreib Ergebnis auswirken würde. Handwritten Logik, die die eigentliche Business-Logik versteht besondere Fälle wissen konnte, wenn ein Rollback nicht für einen bestimmten Sätze von Dirty Reads benötigt wird. Wenn Sie jedoch eine Menge Code schreiben müssen und eine Anwendung, bei der die Wahrscheinlichkeit des Zurücksetzens ist sehr gering ein allgemeiner mechanischer STM Ansatz zu weniger Fehlern führen kann und eine gute Leistung.

  

Auch kann STM einfach erkennen „eingegeben ein anderer Thread diesen Bereich während   die Berechnung ausgeführt wurde, also die Berechnung ist ungültig“   oder kann es tatsächlich erkennen, ob clobbered Werte verwendet wurden (und damit   von Glück kann manchmal zwei Threads denselben kritischen Abschnitt ausführen   gleichzeitig, ohne dass eine Rollback)?

Der TL2 Ansatz wie alle über die Daten gelesen oder nicht über den Code geschrieben, der es tut. Es ist das, was man bekommt, und eingestellt und das zählt; und ob ein anderer Thread auf die Zehen getreten, bevor Sie alle Schreibvorgänge spülen. Alles, was der Code erforderlich ist, ist, dass Sie eine begin(), commit() und rollback() in der Business-Logik, die Transaktion zu Beginn, Ende und abbrechen müssen. das kann auch generierten Code werden. Mit Java können Sie Ihre Methoden mit der @Transactional Anmerkung auf Methoden markieren dann Code generieren, welche wickeln Ihre Methode Anrufungen in einem try / catch / finally, dass sie den Beginn / Commit / Rollback als idiomic java. Deuce spritzt eine solche Logik bei Klasse Ladezeit.

Wieder einmal müssen Sie nicht so magische Sauce beginnen / Commit / Rollback in Ihrem eigenen STM-Datenstrukturen aktiviert. Sie können in allen, die direkt in Ihre Datenstruktur Logik-Code explizit und stellen Ihre eigenen explizit STM aktiviert Klassen in jeder OO-Sprache zu erstellen.

Answer 3

GHC 's STM-Implementierung in Abschnitt beschrieben wird, sechs von:

Composable Speichertransaktionen . Tim Harris, Simon Marlow, Simon Peyton Jones, Maurice Herlihy. PPoPP'05: ACM SIGPLAN Symposium über die Prinzipien und Praxis der Parallelprogrammierung, Chicago, Illinois, Juni 2005

Und Abschnitt fünf:

Transactional Memory mit Daten Invarianten . Tim Harris, Simon Peyton-Jones. März 2006 TRANSACT '06

Answer 4

Ich schlage vor, Sie diese Präsentation sehen: http: // www. infoq.com/presentations/Value-Identity-State-Rich-Hickey

In der zweiten Hälfte erklärt, wie Werte zu aktualisieren, ohne sie in einem undefinierten Zustand zu verlassen. Zum Beispiel - wenn Sie einen Baum, die Sie Sie in STM-Stil aktualisieren wollen nicht die vorherige Version überhaupt ändern. Lassen Sie uns sagen, dass tree ein Zeiger auf die Wurzel des Baumes ist. Das einzige, was Sie erstellen, ist die Knoten, die sich geändert (aber sie können in der ursprünglichen Schnappschuss des Baumes Knoten beziehen.

Dann haben Sie einen Vergleichs- und Swap auf dem tree Zeiger. Wenn es erfolgreich ist, wird dann jeder jetzt Ihren neuen Baum und die alten kann Garbage Collection sein. Wenn nicht, dann wiederholen Sie den Vorgang und der Baum einfach ist konstruiert Müll gesammelt.

Die große Idee ist, dass Sie brauchen nicht zu erkennen, ob jemand die tree geändert, bis Sie tauschen tatsächlich die neuen und alten Werte, so gibt es keine „Konflikte“ oder „clobbered Werte“ von der typischen Multi-Thread-Programmierung.

Answer 5

Wenn Sie mit .NET-Framework werden,

Sie können diesen experimentellen Besuche

• .NET 4.0 STM.Net
  
• .NET rockt Podcast auf STM.Net: Dana Groff und Yossi Levanoni Diskussion STM