Ich habe versucht, die Serialisierbarkeit und Linearisierbarkeit im Kontext des Software-Transaktionsspeichers zu erfassen. Ich denke jedoch, dass beide Begriffe allgemein auf das Transaktionsgedächtnis angewendet werden können.

An dieser Stelle verstehe ich beide Themen wie folgt.

Serialisierbarkeit

Serialisierbarkeit ist eine globale Eigenschaft. Es ist eine Korrektheitseigenschaft von Transaktionen. Bei bestimmten kProzessen, bei denen jeweils eine Transaktion Tkgleichzeitig ausgeführt wird, stellt die Serialisierbarkeit sicher, dass eine Folge von Transaktionen nacheinander (dh nacheinander) ausgeführt werden kann , sodass das Endergebnis mit den gleichzeitig ausgeführten Transaktionen übereinstimmt. Es gibt also eine Permutation der Liste (T1, T2,..,Tk), die eine Liste von Transaktionen definiert, die nacheinander ausgeführt werden können.

Diese Eigenschaft macht für mich vollkommen Sinn und ich denke, meine Definition ist korrekt. Ich habe diese Definition auf den Text in "Die Kunst der Multiprozessor-Programmierung" von Herlihy und Shavit gestützt.

Linearisierbarkeit

Die Linearisierbarkeit ist eine lokale Eigenschaft gleichzeitiger Objekte (z. B. eine Instanz einer Klasse, die von Threads gemeinsam genutzt wird). Die Linearisierbarkeit stellt sicher, dass, wenn zwei Prozesse jeweils einen Serien-Op-Methodenaufruf (z. B. queueoder dequeueauf einer QueueInstanz) für dieses gemeinsam genutzte Objekt ausführen, eine sequentielle Reihenfolge dieser Methodenaufrufe vorliegt, bei der die Programmreihenfolge (die Reihenfolge, in der der Programmierer sie geschrieben hat) nicht unbedingt beibehalten wird down), aber jeder Methodenaufruf scheint sofort zu erfolgen (dh Aufruf und Antwort folgen direkt aufeinander), während das Ergebnis jedes Methodenaufrufs einzeln und folglich das Objekt seinen Status beibehält.

Frage

Nach einem "On the correctness of TM"Artikel von Guerraoui und Kapalka ist dies die Definition der Linearisierbarkeit im Kontext von TM:

.. Eine Sicherheitseigenschaft zur Beschreibung gemeinsam genutzter Objekte wird manchmal als korrektes Kriterium für TM verwendet. In der TM-Terminologie bedeutet Linearisierbarkeit, dass jede Transaktion intuitiv so aussehen sollte, als ob sie zu einem bestimmten Zeitpunkt während ihrer Lebensdauer stattgefunden hätte.

Diese Definition scheint mir nur der Serialisierbarkeit zu ähneln. Das Papier definiert die Serialisierbarkeit jedoch wie folgt:

.. ist eine der am häufigsten benötigten Eigenschaften einer Datenbanktransaktion. Grob gesagt ist ein Verlauf H von Transaktionen (dh die Reihenfolge aller Operationen, die von allen Transaktionen in einer bestimmten Ausführung ausgeführt werden) serialisierbar, wenn alle festgeschriebenen Transaktionen in H dieselben Operationen ausgeben und dieselben Antworten erhalten wie in einem sequentiellen Verlauf S, der besteht nur der festgeschriebenen Transaktionen in H. (Eine sequentielle Historie ist eine ohne Parallelität zwischen den Transaktionen).

Diese Definition scheint jedoch zu implizieren, dass man Anweisungen aus Transaktionen so umordnen kann, dass sie verschachtelt sind. (Dh ordnen Sie die Anweisungen so um, dass nicht alle Anweisungen einer Transaktion Tnacheinander in angezeigt werden H).

---

Ich gehe davon aus, dass meine persönlichen obigen Definitionen korrekt sind. Meine eigentliche Frage ist, wie Linearisierbarkeit im Kontext des Transaktionsgedächtnisses definiert wird. Es macht keinen Sinn, über jeden Methodenaufruf (dh Lese- / Schreibvorgang) in einer Transaktion einzeln nachzudenken, da dies die Semantik des Transaktionsspeichers brechen würde. Es wäre auch nicht sinnvoll, über zwei gleichzeitige Transaktionen ihre Verschachtelungen begründen zu müssen, da dies offensichtlich die Serialisierbarkeit beeinträchtigen würde. Bedeutet Linearisierbarkeit, dass einzelne Operationen innerhalb einer Transaktion neu angeordnet werden können? Wenn die Linearisierbarkeit eine stärkere Form der Serialisierbarkeit ist, sollte es keine Rolle spielen, in welcher Reihenfolge die Operationen innerhalb einer einzelnen Transaktion ausgeführt werden.

Kurz gesagt: Ist mein Verständnis von Serialisierbarkeit und Linearisierbarkeit zuallererst korrekt? Ich bin verwirrt, nachdem ich eine Vielzahl von Definitionen in verschiedenen Werken gelesen habe. Und zweitens, was bedeutet es, dass eine Reihe von Transaktionen linearisierbar ist?

Ich habe auch die Frage gelesen, die in den Kommentaren verlinkt war. Aber es hat mir meine spezifische Frage nicht erklärt.

Quellen

• SO Frage zum Thema (nicht explizit zu STM) /programming/4179587/difference-between-linearizability-and-serializability

• Eine informelle Erklärung zu den beiden http://www.bailis.org/blog/linearizability-versus-serializability/

• Originalpapier zur Serialisierbarkeit http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.92.2690&rep=rep1&type=pdf

• [1] Originalarbeit zur Linearisierbarkeit http://www.cs.toronto.edu/~christoff/files/Linearizability-ACorrectnessConditionForConcurrentObjects.pdf

Über Ihre Definitionen:

Die Grundidee der Serialisierbarkeit ( ) ist richtig. Es muss sich jedoch nicht auf die Annahme beschränken, dass : Jeder Prozess so viele Transaktionen ausgeben kann, wie er möchte.$\textsf{SR}$each (process) executes a transaction

Ihr Verständnis der Linearisierbarkeit ( ) ist völlig falsch. Erstens muss sowohl für als auch für Programmreihenfolge zwischen Transaktionen, die von einem einzelnen Prozess ausgegeben wurden, beibehalten werden. Darüber hinaus können Sie keine Vorgänge innerhalb einer Transaktion neu anordnen.$\textsf{LR}$$\textsf{SR}$$\textsf{LR}$

Erklärung von und :$\textsf{SR}$$\textsf{LR}$

Sowohl als auch erfordern, dass sich alle Transaktionen so verhalten, als ob sie in einer sequentiellen Reihenfolge , was bedeutet, dass in einer solchen sequentiellen Reihenfolge alle Operationen dieselben Werte und Endzustände der Datenbank zurückgeben ist dasselbe wie bei gleichzeitiger Ausführung der Transaktionen.$\textsf{SR}$$\textsf{LR}$$H$reads

Wie bereits erwähnt, muss sowohl für als auch für Programmreihenfolge zwischen Transaktionen, die von einem einzelnen Prozess ausgegeben wurden, beibehalten werden.$\textsf{SR}$$\textsf{LR}$

Das Obige gibt die Unterscheidung von . Jedoch erfordert weiter die sequentielle Reihenfolge die sogenannte Echtzeit (teilweise) , um zwischen den Transaktionen zu gehorchen: Wenn eine Transaktion Enden , bevor eine andere Transaktion beginnt , dann muss vor bestellt werden in .$\textsf{SR}$$\textsf{LR}$$H$$T_1$ $T_2$ $T_1$$T_2$$H$

Beachten Sie, dass die Echtzeitreihenfolge nicht erzwingt. Das heißt, ist stärker als .$\textsf{SR}$$\textsf{LR}$$\textsf{SR}$

Über globales Eigentum und lokales Eigentum:

Ich weiß nicht, ob als globale Eigenschaft bezeichnet wird (bitte geben Sie mir eine Referenz, wenn Sie sich sicher sind). Der Begriff "lokales Eigentum" hat jedoch eine besondere Bedeutung.$\textsf{SR}$

Eine Eigenschaft eines gleichzeitigen Systems wird als lokal bezeichnet, wenn das System als Ganzes erfüllt, wenn jedes einzelne Objekt erfüllt .$P$$P$$P$

Es ist bekannt, dass lokal ist [1], nicht.$\textsf{LR}$$\textsf{SR}$

HINZUGEFÜGT: Über LR und Strict Serializability (SSR)

Wie von @Wandering Logic erwähnt, ist LR ursprünglich für Objekte definiert, nicht für Transaktionen. Zitiert aus [1] ；

Die Linearisierbarkeit kann als Sonderfall der strengen Serialisierbarkeit angesehen werden, bei der Transaktionen auf eine einzelne Operation beschränkt sind, die auf ein einzelnes Objekt angewendet wird.

Heutzutage haben jedoch viele Autoren für Transaktionen verwendet. Zum Beispiel verwendeten Shavit und Touitou in ihrer wegweisenden Arbeit [2] den Begriff für Transaktionen. Bei Verwendung für Transaktionen ist dasselbe wie .$\textsf{LR}$$\textsf{LR}$$\textsf{LR}$$\textsf{SSR}$

Danke @Wandering Logic für die Diskussionen .

---

[1] Linearisierbarkeit: Eine Korrektheitsbedingung für gleichzeitige Objekte . Von M. P. Herlihy und J. M. Wing. ACM Transactions on Programming Languages ​​and Systems. 3, Juli 1990.

[2] Software-Transaktionsspeicher . Von Nir Shavit und Dan Touitou. Distrib. Comput. (1997) 10: 99 & ndash; 116.

Ihre Definition der Serialisierbarkeit ist korrekt und entspricht der von Ihnen zitierten Definition von Guerraoui und Kapalka. Die Definition von Guerraoui und Kapalka erfordert, wie Ihre, dass alle Anweisungen in der Transaktion erscheinen, um ausgeführt und in der richtigen Reihenfolge ausgeführt zu werden. Das heißt: Das Endergebnis ist, als hätten Sie die Transaktionen atomar und in einer sequentiellen Reihenfolge ausgeführt. (Die Implementierung kann mit einem verrückten gleichzeitigen, parallelen Ausführungsschema außerhalb der Reihenfolge optimiert werden, aber das Ergebnis muss so aussehen, als hätten Sie alle Transaktionen in einer sequentiellen Reihenfolge und ohne Verschachtelung ausgeführt.)$T_k$

Die Serialisierbarkeit befasst sich mit dem Verhalten von Transaktionen, ohne die Prozesse oder Threads zu berücksichtigen, die diese Transaktionen ausgegeben haben. (In Ihrer Definition haben Sie genau so viele Prozesse wie Transaktionen, und jeder Prozess gibt genau eine Transaktion aus.)

Die Linearisierbarkeit berücksichtigt die Tatsache, dass jeder Thread mehrere Transaktionen ausgibt, und wir erwarten, dass diese Transaktionen in der Reihenfolge ausgeführt und abgeschlossen werden, in der wir sie aufgefordert haben.

Ein Transaktionsspeichersystem ist streng serialisierbar, wenn das Endergebnis einer Ausführung dasselbe ist, als ob die Transaktionen aller Prozesse atomar in einer sequentiellen Reihenfolge ausgeführt wurden und die von jedem einzelnen Prozess ausgegebenen Transaktionen in dieser Reihenfolge in der angegebenen Reihenfolge erscheinen das Programm dieses Prozesses.

(Dies ist die Definition der sequentiellen Konsistenz von Lamport, "So erstellen Sie einen Multiprozessor-Computer, der Multiprozessprogramme korrekt ausführt", IEEE T Comp 28 (9): 690-691, 1979 , jedoch geändert, um über Transaktionen anstelle von Speicheroperationen zu sprechen. Herlihy und Wing nennen diese Eigenschaft strenge Serialisierbarkeit .)

Das Originalpapier von Herlihy und Wing, das die Linearisierbarkeit definiert, befasste sich mit Operationen an Objekten, nicht mit Transaktionen. Das Folgende verbindet jedoch die beiden Konzepte:

Die Linearisierbarkeit kann als Sonderfall der strengen Serialisierbarkeit angesehen werden, bei der Transaktionen auf eine einzelne Operation beschränkt sind, die auf ein einzelnes Objekt angewendet wird.

(Herlihy, Maurice; Wing, Jeanette: Linearisierbarkeit: Eine Korrektheitsbedingung für gleichzeitige Objekte . ACM T. Prog. Lang. Und Sys. 12 (3): 463-492, 1990.)