线性化和可串行化之间的区别

本文介绍了线性化和可串行化之间的区别的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 29岁程序员，3月因学历无情被辞！ 我对Java编程的线性化和可串行性感到困惑。能否请您通过示例解释这些差异或提供一个好的参考。I am really confused with linearizability and serializability w.r.t Java programming. Can you please explain the difference between these with an example or provide a good reference.推荐答案两者的中心区别在于可序列化是全局属性;整个经营/交易历史的财产。 可线性化是本地属性;单个操作/事务的属性。另一个区别是线性化包括实时的概念，可序列化不包含：操作的线性化点必须位于其调用和响应时间之间。 （参见Tim Harris： Transactional Memory，2ed 。参见Herlihy的幻灯片来自多处理器编程的艺术，关于可线性化的部分，它们是可在此处获取，以获取一些示例和证明。The central distinction between the two is that serializability is a global property; a property of an entire history of operations/transactions. Linearizability is a local property; a property of a single operation/transaction. Another distinction is that linearizability includes a notion of real-time, which serializability does not: the linearization point of an operation must lie between its invocation and response times. (See Tim Harris: Transactional Memory, 2ed. See Herlihy's slides from The Art of Multiprocessor Programming, the section on Linearizability, which are available here, for some examples and proofs.两个属性都针对相同的目标：顺序一致性。来自Herlihy的论文：Both properties are aimed at the same goal: sequential consistency. From Herlihy's paper: ...线性化可视为严格的特殊情况可串行化，其中事务被限制为由应用于单个对象的单个操作组成。然而，这种单一操作限制具有深远的实际和正式结果，使线性化计算与其可序列化对应物具有不同的风格。一个直接的实际结果是，适用于可串行化的并发控制机制通常不适用于线性化，因为它们会引入不必要的开销并对并发性施加不必要的限制。...Linearizability can be viewed as a special case of strict serializability where transactions are restricted to consist of a single operation applied to a single object. Nevertheless, this single-operation restriction has far-reaching practical and formal consequences, giving linearizable computations a different flavor from their serializable counterparts. An immediate practical consequence is that concurrency control mechanisms appropriate for serializability are typically inappropriate for linearizability because they introduce unnecessary overhead and place unnecessary restrictions on concurrency. 参考文献： Harris，Tim，James Larus和Ravi Rajwar：交易记忆，2ed 。计算机体系结构综合讲座。 Morgn& Claypool，2010。ISBN 9781608452354. URL： http：//www.morganclaypool。 com / doi / abs / 10.2200 / S00272ED1V01Y201006CAC011？journalCode = cacReferences:Harris, Tim, James Larus, and Ravi Rajwar: Transactional Memory, 2ed. Synthesis Lectures on Computer Architecture. Morgn & Claypool, 2010. ISBN 9781608452354. URL: http://www.morganclaypool.com/doi/abs/10.2200/S00272ED1V01Y201006CAC011?journalCode=cac Herlihy，Maurice和Jeanette Wing：线性化：正确性条件对于并发对象。 ACM Trans。 PROG。郎。和系统。卷。 1990年7月12日第3期，第463-492页。 URL http://www.cs.brown.edu /~mph/HerlihyW90/p463-herlihy.pdfHerlihy, Maurice and Jeanette Wing: Linearizability: A Correctness Condition for Concurrent Objects. ACM Trans. Prog. Lang. and Sys. Vol. 12, No. 3, July 1990, Pages 463-492. URLhttp://www.cs.brown.edu/~mph/HerlihyW90/p463-herlihy.pdf Papadimitriou，Christos：并发数据库更新的可串行性 。 Journal of the ACM Vol 26. No 4. October 1979，pp 631-653。 URL http://publications.csail.mit。 edu / lcs / pubs / pdf / MIT-LCS-TR-210.pdfPapadimitriou, Christos: The Serializability of Concurrent Database Updates. Journal of the ACM Vol 26. No 4. October 1979, pp 631-653. URL http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-210.pdf Herlihy，Maurice和Nir Shavit： The多处理器编程的艺术。 Elsevier，2008。ISBN 978-0-12-370591-4。网址： http://www.elsevier.com/wps/find /bookdescription.cws_home/714091/description#description 关于线性化的PPT幻灯片在这里： http://pub.ist.ac.at/courses/ppc10/slides/Linearizability.pptxHerlihy, Maurice and Nir Shavit: The Art of Multiprocessor Programming. Elsevier, 2008. ISBN 978-0-12-370591-4. URL: http://www.elsevier.com/wps/find/bookdescription.cws_home/714091/description#description PPT slides on linearizability are here: http://pub.ist.ac.at/courses/ppc10/slides/Linearizability.pptx Attiya，Hagit和Jennifer Welch：顺序一致性与线性化。 ACM Transactions on Computer Systems Vol。 1994年5月12日第2期，第91-122页。网址 http：// citeseerx。 ist.psu.edu/viewdoc/download?doi=10.1.1.133.4969&rep=rep1&type=pdfAttiya, Hagit and Jennifer Welch: Sequential Consistency versus Linearizability. ACM Transactions on Computer Systems Vol. 12, No. 2, May 1994, Pages 91-122. URL http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.133.4969&rep=rep1&type=pdf如果您真的关心这一点，请阅读介绍定义的论文。对于线性化，这是 可线性化：并发对象的正确性条件，Herlihy和Wing 。它很密集，但值得关注。请注意，在软件事务存储器社区中，线性化是否是正确的目标/属性是一个悬而未决的问题。If you really care about this, read the paper that introduced the definitions. For linearizability, that's Linearizability: A Correctness Condition for Concurrent Objects, Herlihy and Wing. It's dense, but worth the attention. Note that in the software transactional memory community, it's an open question whether linearizability is the right goal / property to aim for. 可串行性是关于一系列操作的结果/系统可表示为所有操作的特定排序（就好像执行以特定顺序执行......）。线性化是系统中单个操作子集的属性......如果操作/操作集在其他操作中看起来好像它们发生在相对于其他操作的（逻辑）时间的特定时刻，则它们是可线性化的。这里的规范论文是 Papadimitriou， The并发数据库更新的可序列化 。Serializability is about the outcome of a collection of operations/the "system" being expressible as a specific ordering ("as if execution took place in a specific order...") of all the operations. Linearizability is a property of a single subset of operations in the system... an operation/set of operations are linearizable if they appear to the other operations as if they occurred at a specific instant in (logical) time with respect to the others. The canonical paper here is Papadimitriou, The Serializability of Concurrent Database Updates.当您考虑可线性化时，请考虑原子操作。一组（一组）操作在它们（看起来）相对于系统的其他部分原子地发生时是可线性化的。一个常见的表述是提供每个操作在其调用和响应之间即时生效的错觉。 线性化的表述是由于 Herlihy ，强调这是一个本地属性，与其他类型的顺序一致性属性，如可序列化是全局的。Think "atomic operation" when you're thinking about "linearizable." A (set of) operations are linearizable when they (appear to) occur atomically with respect to other parts of the system. A common formulation is "provide the illusion that each operation takes effect instantaneously between its invocation and response." The formulation of linearizability is due to Herlihy, which emphasizes that this is a local property, vs. other kinds of sequential consistency properties like "serializability" which are global. 这篇关于线性化和可串行化之间的区别的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！ 上岸，阿里云！