and*_*soj 60
两者之间的区别在于可串行化是一种全球性的属性; 整个经营/交易历史的财产. 线性化是一种本地属性 ; 单个操作/事务的属性.另一个区别是线性化包括实时概念,可序列化不包括:操作的线性化点必须位于其调用和响应时间之间.(参见Tim Harris:Transactional Memory,2ed.参见Herlihy的"多处理器编程艺术"中的幻灯片,关于可线性化的部分,可在此处获得一些示例和证明.
这两个属性都针对相同的目标:顺序一致性.来自Herlihy的论文:
在数据库和分布式系统上的大量工作使用可序列化作为并发计算的基本正确性条件.在此模型中,事务是一个控制线程,它将有限的基本操作序列应用于与其他事务共享的一组对象.如果历史记录等同于事务似乎按顺序执行,即没有交错,则历史记录是可序列化的.可以以明显的方式在非重叠的事务对上定义(部分)优先顺序.如果顺序历史记录中的事务顺序与其优先顺序兼容,则历史记录是严格可序列化的...
...线性化可以被视为严格可串行化的特殊情况,其中事务被限制为由应用于单个对象的单个操作组成.然而,这种单一操作限制具有深远的实际和正式结果,使线性化计算与其可序列化对应物具有不同的风格.一个直接的实际结果是,适用于可串行化的并发控制机制通常不适用于线性化,因为它们会引入不必要的开销并对并发性施加不必要的限制.
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.郎.和系统.卷.1990年7月12日第3期,第463-492页.URL http://www.cs.brown.edu/~mph/HerlihyW90/p463-herlihy.pdf
Papadimitriou,Christos: 并发数据库更新的可序列化.Journal of the ACM Vol 26. No 4. May 1979,pp 631-653.URL http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-210.pdf
Herlihy,Maurice和Nir Shavit:多处理器编程的艺术.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.pptx
Attiya,Hagit和Jennifer Welch:顺序一致性与线性化.ACM Transactions on Computer Systems Vol.1994年5月12日第2期,第91-122页.URL http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.133.4969&rep=rep1&type=pdf
如果您真的关心这一点,请阅读介绍定义的论文.对于线性化,这是线性化:并发对象,Herlihy和Wing的正确性条件.它很密集,但值得关注.请注意,在软件事务存储器社区中,线性化是否是正确的目标/属性是一个悬而未决的问题.
可序列化是关于操作集合的结果/"系统"可表示为所有操作的特定排序("就好像执行以特定顺序执行......").线性化是系统中单个操作子集的属性......如果操作/操作集在其他操作中看起来好像它们是在(逻辑)时间相对于其他操作的特定时刻发生的,则它们是可线性化的.这里的规范论文是Papadimitriou,并发数据库更新的可串行性.
当您考虑"可线性化"时,请考虑"原子操作".一组(一组)操作在它们(看起来)相对于系统的其他部分原子地发生时是可线性化的.一个常见的表述是"提供每个操作在其调用和响应之间即时生效的错觉".线性化的公式是由于Herlihy,它强调这是一个局部属性,而不是其他类型的顺序一致性属性,如全局的"可序列化".
| 归档时间： |
|
| 查看次数： |
12602 次 |
| 最近记录： |