线性化与可串行化的区别

我对Java编程的线性化和可串行化感到困惑。 你可以用一个例子来解释这些差异吗?或者提供一个很好的参考。

两者的核心区别在于可串行性是一个全球性的属性, 整个操作/交易历史的财产。 线性化是一个本地特性 ; 单一经营/交易的财产。 另一个区别是,线性化包括一个实时的概念,这个可序列化不是:操作的线性化点必须在它的调用和响应时间之间。 (参见Tim Harris: Transactional Memory,2ed 。参见Herlihy的“多处理器编程的艺术”中的幻灯片,有关线性化的一节 , 可以在这里find一些例子和certificate。

两个属性的目的都是一致的。 从Herlihy的论文:

对数据库和分布式系统的大量工作使用可串行化作为并发计算的基本正确性条件。 在这个模型中,一个事务是一个控制线程,将一个有限的基本操作序列应用于与其他事务共享的一组对象。 历史是可序列化的,如果它相当于事务看起来顺序执行的历史,即没有交织。 一个(部分)优先顺序可以用明显的方式在非重叠的事务对上定义。 如果顺序历史logging中的交易顺序与其优先顺序一致,则历史logging是严格可序列化的。

…线性化可以被看作是严格的可串行化的一个特殊情况,在这种情况下事务被限制为由一个单一的操作组成的一个对象。 然而,这种单一操作的限制具有深远的实际和正式的后果,使得可线性化的计算与其可序列化的计算具有不同的风味。 直接的实际结果是适合于可串行化的并发控制机制通常对于线性化是不合适的,因为它们引入了不必要的开销,并且对并发设置了不必要的限制。

参考文献:

  • Harris,Tim,James Larus和Ravi Rajwar: 交易记忆,2ed 。 计算机体系结构综合讲座。 Morgn&Claypool,2010 ISBN 9781608452354. URL: http : //www.morganclaypool.com/doi/abs/10.2200/S00272ED1V01Y201006CAC011? journalCode=cac

  • Herlihy,Maurice和Jeanette Wing: 线性化:并发对象的正确性条件 。 ACM Trans。 PROG。 郎。 和系统。 卷。 第12卷,第3号,1990年7月,第463-492页。 URL http://www.cs.brown.edu/~mph/HerlihyW90/p463-herlihy.pdf

  • Papadimitriou,Christos: 并发数据库更新的可串行化 。 “ACM杂志”第26卷,第4期,1979年10月,第631-653页。 URL lcs/pubs/pdf/MIT-LCS-TR-210.pdf

  • Herlihy,Maurice和Nir Shavit: 多处理器编程的艺术 。 Elsevier,2008年ISBN 978-0-12-370591-4。 URL: http : //www.elsevier.com/wps/find/bookdescription.cws_home/714091/description#description线性化PPT幻灯片在这里: http : //pub.ist.ac.at/courses/ppc10/slides/ Linearizability.pptx

  • Attiya,Hagit和Jennifer Welch: 序贯一致性与线性化 。 ACM计算机系统交易卷。 第12卷,第2期,1994年5月,第91-122页。 urlhttp://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.133.4969&rep=rep1&type=pdf

更多细节:

如果你真的关心这个,请阅读介绍定义的文章。 为了线性化,这就是线性化:并发对象 ,Herlihy和Wing的正确性条件 。 它很密集,但值得关注。 请注意,在软件事务内存社区,线性化是否是正确的目标/财产目标是一个悬而未决的问题。

可序列化是关于操作集合的结果/“系统”可以表示为所有操作的特定顺序(“好像执行发生在特定顺序中…”)。 线性化是系统中单个操作子集的一个属性。如果一个操作/一组操作对于其他操作来说似乎是线性化的,就像它们发生在(逻辑)时间相对于其他操作的特定时刻一样。 这里的规范文件是Papadimitriou, 并发数据库更新的可序列化

当你想到“可线性化”的时候,请思考“primefaces操作”。 一组(一组)操作在它们(似乎)相对于系统的其他部分以primefaces方式出现时是可线性化的。 一个共同的表述是“提供幻想,每个操作在其调用和响应之间立即生效”。 线性化的制定是由于Herlihy强调这是一个局部性质,而其他types的序贯一致性特性如“可序列化”是全球性的。

Peter Bailis在这里有一个很好的解释:

  • 线性化与可序列化

“用简单的英语来说,在线性化的情况下,写入应该是瞬间的,不准确的是,一旦写入完成,所有后来的读取(其中”稍后“由挂钟开始时间定义)应该返回该写入的值或稍后写入,一旦读取返回一个特定的值,所有后来的读取应该返回该值或稍后写入的值。

“可序列化是关于事务或一个或多个对一个或多个对象的一组操作的保证,它保证对多个项目执行一组事务(通常包含读写操作)相当于一些串行执行(总计订购)交易“。

请参阅@ andersoj的答案,以清楚地描述可串行性和线性化之间的区别。

这只是与Java并发编程间接相关的。 一般而言,并发Java程序不需要具有可序列化或可线性化的历史logging。 在这种情况下,可序列化对于“正确性”程序(Java或其他)通常是足够的,但是特定的问题可能需要更强的线性化属性。 但无论哪种方式,决定正确性要求的问题 ,不是Java。

检查维基百科的解释:

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

这也可能有点令人困惑,因为我们也使用术语“序列化”来指将类转换为数据stream用于存储或networking传输。