Différence entre linéarisation et sérialisabilité

Question

Je suis vraiment confus avec la linéarisation et la sérialisabilité en programmation Java. Pouvez-vous s'il vous plaît expliquer la différence entre ceux-ci avec un exemple ou fournir une bonne référence.

Answer 1

La distinction principale entre les deux est que serializability est un mondial de la propriété; la propriété d'un ensemble de l'historique des opérations. Linearizability est une propriété locale; une propriété d'une seule opération ou la transaction. Une autre distinction est que linearizability inclut une notion de temps réel, qui serializability n': la linéarisation point de fonctionnement doit se situer entre son invocation et les temps de réponse. (Voir Tim Harris: la Mémoire Transactionnelle, 2ed. Voir Herlihy de diapositives à partir de l'Art de La Programmation Multiprocesseur, la section sur les Linearizability, qui sont disponibles ici, pour certains exemples et des preuves.

Les deux propriétés sont en visant le même objectif: cohérence séquentielle. De Herlihy du papier:

Beaucoup de travail sur les bases de données et distribué les systèmes utilise serializability [40] comme la base de la justesse de la condition de simultanée des calculs.l Dans ce modèle, une transaction est un fil de le contrôle qui s'applique à une suite finie des opérations primitives à un ensemble de les objets partagés avec d'autres des transactions". Une histoire est sérialisable si c'est équivalent à l'une dans laquelle les transactions semblent exécuter de manière séquentielle, c'est à dire, sans l'entrelacement. (Partielles) priorité l'ordre peut être défini sur non-cumul des paires de transactions dans la manière évidente. Une histoire est strictement sérialisable si l' des transactions de l'ordre dans le séquentiel l'histoire est compatible avec leur ordre de priorité...

...Linearizability peut être considérée comme une cas particulier de la stricte serializability où les transactions sont limitées à consister en une seule opération appliquée à un seul objet. Néanmoins, cette une seule opération de restriction a de loin la pratique formelle et les conséquences, en donnant linearizable les calculs une saveur différente à partir de leur serializable homologues. Un immédiate conséquence pratique est cette simultanéité des mécanismes de contrôle approprié pour serializability sont généralement inapproprié pour linearizability parce qu'ils introduisent inutile de frais généraux et de la place les restrictions inutiles sur la simultanéité.

Références:

• Harris, Tim, James Larus, et Ravi Rajwar: la Mémoire Transactionnelle, 2ed. Synthèse des Conférences sur l'Architecture de l'Ordinateur. Morgn & Claypool, 2010. ISBN 9781608452354. URL: http://www.morganclaypool.com/doi/abs/10.2200/S00272ED1V01Y201006CAC011?journalCode=cac

• Herlihy, Maurice et Jeanette Aile: Linearizability: Une Exactitude Condition Simultanée des Objets. ACM Trans. Prog. Lang. et Sys. Vol. 12, N ° 3, Juillet 1990, Pages 463-492. URL http://www.cs.brown.edu/~h/HerlihyW90/p463-herlihy.pdf

• Papadimitriou, Christos: Le Serializability de Base de données Simultanées Mises à jour. Journal de l'ACM, Vol 26. N ° 4. Octobre 1979, pp 631-653. URL http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-210.pdf

• Herlihy, Maurice et Nir Shavit: l'Art de La Programmation Multiprocesseur. Elsevier, 2008. ISBN 978-0-12-370591-4. URL: http://www.elsevier.com/wps/find/bookdescription.cws_home/714091/description#description PPT diapositives sur linearizability sont ici: http://pub.ist.ac.at/courses/ppc10/slides/Linearizability.pptx

• Attiya, Hagit et Jennifer Welch: Cohérence Séquentielle contre Linearizability. ACM Transactions sur des Systèmes Informatiques Vol. 12, N ° 2, Mai 1994, Pages 91-122. URL http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.133.4969&rep=rep1&type=pdf

Plus De Détails:

Si vous tenez vraiment à ce sujet, lire le journal, qui a introduit les définitions. Pour linearizability, c'est Linearizability: Une Exactitude Condition Simultanée des Objets, Herlihy et de l'Aile. C'est dense, mais qui mérite l'attention. Notez que dans le logiciel de la mémoire transactionnelle de la communauté, c'est une question ouverte de savoir si linearizability est le droit objectif / propriété de viser.

Serializability est le résultat d'un ensemble d'opérations/le "système" d'être exprimable comme une commande ("comme si l'exécution a eu lieu dans un ordre précis...") de toutes les opérations. Linearizability est une propriété d'un seul sous-ensemble des opérations dans le système... une opération ou ensemble d'opérations sont linearizable si elles apparaissent à d'autres activités comme si elles se sont produites à un instant spécifique dans le (logique) de temps par rapport aux autres. L'canonique papier ici est Papadimitriou, Le Serializability de Base de données Simultanées Mises à jour.

Penser "opération atomique" lorsque vous pensez à la "linearizable." Un (ensemble de) opérations sont linearizable quand ils (semblent) se produisent de manière atomique à l'égard des autres parties du système. Une formulation commune est de "fournir l'illusion que chaque opération prend effet instantanément entre l'appel et la réponse." La formulation de linearizability est due à Herlihy, qui souligne que c'est une propriété locale, par rapport à d'autres types de cohérence séquentielle des propriétés comme "sérialisation; qui sont mondiaux.

Answer 2

Voir @andersoj réponse à une description claire de la différence entre serializability et linearizability.

Ce n'est qu'indirectement Java programmation simultanée. En général, un tel programme Java n'a pas besoin d'avoir un serializable ou linearizable l'histoire. Dans le cas qui n', serializability est généralement suffisant pour un programme (Java ou autre) de la "décision correcte", bien que des problèmes particuliers pourraient exiger la plus forte linearizability de la propriété. Mais de toute façon, c'est le problème qui détermine l'exactitude des exigences, pas de Java.

Answer 3

Vérifiez les explications de Wikipedia:

http://en.wikipedia.org/wiki/Linearizability#Linearizability_versus_serializability

Cela peut également être un peu déroutant, car nous utilisons également le terme sérialiser pour faire référence à la conversion d'une classe en flux de données pour le stockage ou la transmission réseau.