可线性化具有以下性质。参考文献［1］证明了可线性化具有局部（本地）性质。历史H 2是非可线性化的。可线性化可以看成是严格可串行化的一种特殊情况，即将事务限制在由单对象的单操作构成上。图11.1是可线性化执行序列的一个示例，这是一个4字节编址地址存储器，共有4个节点，分别记作X、Y、T、U。图11.1可线性化执行序列如同可串行化定义一样，可线性化的定义也依赖于操作与它们的执行序。......
2023-10-28
分布式数据库可线性化理论
【摘要】：下面先讨论学术界对可串行化理论的修正，即可线性化理论。维基百科[2]对可线性化的定义为：可线性化首先由Herlihy和Wing于1987年在介绍一致性模型时引入。因此，我们可以非形式化地给出可线性化的定义，如下。这个过程是非线性化的。为了实现线性化，要求对每个进程Pi使用自己的寄存器Ri。
数据复制，会造成一个数据（项）有多个副本，也产生了新的问题。多副本首先引发了数据一致性问题，而一致性讨论又源于数据修改事务的操作问题。现在，事务理论面临着挑战，首先是并发控制理论面临的挑战。下面先讨论学术界对可串行化理论的修正，即可线性化（linearizability）理论。
参考文献［5］中提出了可线性化的概念：并发计算是可线性化的，是指它在形式上“等价”于一个合法的顺序计算。
维基百科[2]对可线性化的定义为：可线性化首先由Herlihy和Wing于1987年在介绍一致性模型时引入。可线性化对原子性给出了更富限制性的定义，因为在诸如“an atomic operation is one which cannot be（or is not）interrupted by concurrent operations”里，关于操作的开始和结束通常是含糊的。
原子对象及其顺序定义：并行运行的一组操作一个接着一个发生，则不会出现不一致。可线性化保证所有操作观察到的系统具有不变性（invariants），也保留不变性，如果所有操作保留不变，则整个系统也不变。
因此，我们可以非形式化地给出可线性化的定义，如下。
并发系统由通过共享数据结构或对象的一组进程组成。并发系统的执行会产生一段历史（history），即一个已完成操作的有序序列。
历史H是对象上的一组线程或进程的调用（invocations）和响应（responses）。调用可以看成是操作的开始，响应看成是操作的结束。函数的调用有相应的响应。
顺序历史（sequential history）是指所有调用后直接跟着相应的响应，可把调用和响应看成是瞬时发生的。顺序历史是一个线性序列，但也是平凡的，因为没有实际上的并发。
●历史H是可线性化的，如果存在一个完成操作的线性序列满足H中的每个已完成操作，并在线性序列中有相对应的操作，这种一对一操作执行后返回的结果相同。
●线性序列中，操作op1在op2开始前（即调用前）完成（即响应），则在H中，操作op1也在op2开始前（即调用前）完成（即响应）。
换言之：
●线性序列的调用和响应重新排序，会产生一个顺序历史。
●按照对象的顺序性定义，顺序历史是正确的。
●在初始历史里，如果一个响应在一个调用之前，在重新排序的顺序历史中依然如此。
前两点和可串行化要求一样，最后一点是可线性化所独有的。
即使在单机形态的计算机环境中，对可线性化有要求的例子也很多，下面列举一些。
1.计数器
计数器是计算机中常用的一种数据结构，用来记录事件和事件发生的轨迹。计数器对象可以被多个进程存取，相关的两个操作如下。
（1）加1（increment）：计数器当前值加1后存入计数器，返回acknowledgement。
（2）读（read）：返回计数器的当前值，不作修改。
可以使用共享寄存器来实现这种计数器对象，下面来分析两类形态。
情况1：原生、非原子性实现。
加1（increment）：
●读寄存器R的当前值。
●读出的值加1。
●新值写回寄存器R。
读（read）：假设两个进程访问一个初始值为0的计数器对象，则
●进程1读寄存器的值，结果为0。(www.chuimin.cn)
●进程1将值加1（当前值变为1），但在写回寄存器前被挂起，同时进程2启动。
●进程2读寄存器的当前值，结果为0。
●进程2将值加1（此时值为1）。
●进程2将新值写回寄存器，寄存器值变成1。
●进程2结束，进程1继续运行，即进程1将1写入寄存器，覆盖进程2的更新结果。这个过程是非线性化的。
情况2：原子性实现。
为了实现线性化，要求对每个进程Pi使用自己的寄存器Ri。
加1（increment）：
●读寄存器Ri中的值。
●读出的值加1，获得新值。
●新值写回Ri。
读（read）：
●读寄存器R1，R2，…，Rn。
●返回所有寄存器的值的累加和。
这个系统的加1操作是线性化的。当然，这是一个普通的例子，真实情况会复杂得多。例如，读一个64位的内存，实际上是通过两次顺序读左右32位实现的。如果一个进程只读了前32位，而在读后32位前，后32位发生了变化，则读出的64位值变成混合值。因此，要小心处理，要能及时发现这类错误并纠正它。
2.比较/交换
许多系统提供原子性的比较/交换（compare-and-swap）指令，从内存位置读出值并与用户提供的期待值进行比较，如果匹配，就写入新值。
如果两个进程同时运行，一个执行比较/交换操作，另一个执行内存修改，失控时也不能保证其原子性。
3.封锁
封锁（locking）的算法如下。
●请求一个封锁，排除其他线程。
●读内存地址的值。
●读出的值加1。
●加1后的值写回原来的内存地址。
●释放封锁。
原子性要求在释放封锁前不准其他线程修改内存地址的值。但是，由于封锁之间的竞争，会发生失控，从而破坏原子性。
参考文献［1］中提出了顺序数据类型的概念和数据类型线性的叠加操作。
有关分布式数据库技术的文章
- 详细阅读
-
分布式数据库的可串行化理论及并发控制详细阅读
分布式数据库管理系统的并发控制是为了保证多用户分布环境下的数据库一致性。可串行化是涉及并发控制的一个重要理论。条件1表示调度涉及的域是一个由各个事务构成的集合。例9.2所示的是一个串行调度。下面我们讨论可串行化的问题。定义9.3 一个调度Sc是可串行的，当且仅当Sc冲突等价于一个串行调度，这种可串行化通常称为冲突等价可串......
2023-10-28
-
分布式数据库：面向对象可串行化实现详细阅读
前面讨论了面向对象数据库系统的事务管理，本节讨论并发控制的核心问题，即可串行化问题。由面向对象数据库系统的事务可知，这是学术界所说的开放嵌套事务。为此，我们提出了面向对象可串行化的思想。对象调度的面向对象可串行化给出了一个动作序列。我们把一个事务的系统调度称为是面向对象可串行化的，如果所有的对象调度都是面向对象可串行化的，那么所有的附加动作依赖关系不含冲突。如图15.10所示，将三个事务发送给对象En......
2023-10-28
-
保险理论创新：可保风险、普惠保险、生态保险详细阅读
近年来，保险理论创新不断发展，特别是关于可保风险、普惠保险、生态保险、保险经营和风险管理等方面的理论研究热度不断上升。因此，可保风险理论研究正在重新定义，强调经济性、合同性和社会公平，而不再局限于传统风险形态。......
2023-08-11
-
道可道，知止得不失-道可道详细阅读
始制有名，名亦既有，夫亦将知止，知止可以不殆。人为了治理建立了制度，确立了名分，名分已经有了，那也要知道适可而止，知道适可而止可以避免危害。过分的吝啬必定会付出更多，聚财过多而不施以济众，必会引起众怨，招致后患和损失。所以，知道满足就不会受到屈辱，知道适可而止，才不会遭到危险。他们不知足，更不知止，最后栽进了罪恶的泥潭。后赐和自尽，并给他定了20项罪名。从此退而不隐，强而不显。......
2023-12-06
-
可持续旅游指标与评价-旅游资源开发的可持续发详细阅读
1996年WTO提出了一套以十一个核心指标为主形成的可持续旅游指标体系，这十一个核心指标可归纳为三个复合指标。WTO的可持续旅游指标体系是迄今为止对旅游目的地可持续性评价的最成熟、最全面的方法，但该指标并未从总体上量化旅游目的地的可持续性。......
2023-11-16
-
自由的蓝天：道可道-道可道详细阅读
“人无法选择自然的故乡，但人可以选择心灵的故乡。”人们对外在的渴望和追求已经远远超越了对心灵的关注。过度重视那些物质的、有形的财富，反而会造成心灵的贫穷。当人类对心灵失去关注，就意味着人类对自身失去了关注。......
2023-12-06
-
大智若愚，道可道-道可道详细阅读
人皆知有用之用，而莫知无用之用也。凡此种种，皆是杨修的聪明触犯了曹操，他急于显示自己的有用之处，结果反被用处所害，这就是不懂得“无用之用”道理的教训。所以，“有之以为利，无之以为用。”老子则反其道而行之，他依据“有无相生”和“无用之用”的理论，提出君主应实行无为而治的说法。无为，有的时候恰恰是大为，无用，也可能是大用。......
2023-12-06
相关推荐