什么是"线性化"？

Question

那里的任何人都可以帮助我理解线性化是什么吗？我需要一个简单易懂的解释.我正在阅读Maruice Herilihy和Nir Shavit 的"多处理器编程艺术",并试图理解第3章"并发对象".

我知道一个方法是可线性化的,如果它有一个点,它似乎从其他线程的角度瞬间"生效".这是有道理的,但也有人说,线性化实际上是执行历史的一个属性.执行历史是可线性化的,为什么我关心它,以及它与可线性化的方法或对象有什么关系？

谢谢!

Answer 1

正如我在本文中解释的那样,一张图片值1000字.

第一个SELECT语句读取值50,而第二个SELECT读取值10,因为在两个读取操作之间执行写操作.

可线性化意味着即时进行修改,并且一旦写入注册表值,只要注册表不进行任何修改,任何后续读取操作都将找到相同的值.

如果您没有线性化可能会发生什么？

这一次,我们没有单一的注册表或单一的事实来源.我们的系统使用异步数据库复制,我们有一个主节点,它既可以读取也可以写入,而且一个Follower节点只用于读取操作.

由于复制是异步发生的,因此主节点行修改与Follower应用相同更改的时间之间存在延迟.

一个数据库连接将帐户余额从50更改为10并提交事务.紧接着,第二个事务从Follower节点读取,但由于复制不应用余额修改,因此读取值50.

因此,该系统不可线性化,因为变化似乎不是即时发生的.为了使该系统可线性化,我们需要使用同步复制,并且主节点UPDATE操作将不会完成,直到Follower节点也应用相同的修改.

Answer 2

如果单个对象被认为是可线性化的

(a)每种方法都是原子的.想象一下它们作为java同步方法,但更多下面.

(b)任何给定的线程/处理器最多可以有一个待处理的操作.

(c)操作必须在返回之前生效.对象将它们排入懒惰地执行它们是不可接受的.

现在,(a)可以放松得多.线性化要求该操作的效果是原子的.因此,无锁链接列表中的添加操作将在其执行中有一个点("线性化点"),之前没有添加该元素,之后元素肯定在.这比获取锁更好,因为锁可以无限期地阻止.

现在,当多个线程同时调用可线性化对象时,该对象的行为就像在某个线性序列中调用方法一样(因为原子性要求); 两个重叠的调用可以按任意顺序线性化.

并且因为在方法调用期间它们被迫产生效果(堆栈必须推/弹,集必须添加/删除等),所以可以使用众所周知的顺序规范方法(前后条件等)来推理对象. .

虽然我们处于这种状态,但线性化和顺序一致性之间的区别在于后者不需要(c).对于顺序一致的数据存储,方法不必立即生效.换句话说,方法调用仅仅是对操作的请求,而不是操作本身.在可线性化的对象中,方法调用是对操作的调用.可线性化的对象是顺序一致的,但不是相反的.

Answer 3

好吧,我想我可以简洁地回答这个问题.

当我们要告诉并发对象是否正确时,我们总是试图找到一种方法将部分顺序扩展到总顺序.

我们可以更容易地识别顺序对象是否正确.

首先,让我们把并发对象放在一边.我们稍后会讨论它.现在让我们考虑顺序历史H_S,顺序历史是一系列事件(即调用和响应),其中每个Invoke 由其相应的响应瞬间跟随.(好吧,"瞬间"可能会混淆,考虑执行单个 - 线程程序,当然每个Invoke和它的Response之间都有一个间隔,但是这些方法是逐个执行的.所以"瞬间"意味着没有其他的Invoke/Respone可以插入一对Invoke_i~Response_i)

H_S可能看起来像:

H_S : I1 R1 I2 R2 I3 R3 ... In Rn
(Ii means the i-th Invoke, and Ri means the i-th Response) 

很容易推断历史H_S的正确性,因为没有任何并发​​性,我们需要做的是检查执行是否与我们期望的一样(满足顺序规范的条件) .换句话说,是一个legel顺序历史.

好的,现实是我们正在使用并发程序.例如,我们在程序中运行两个线程A和B. 每次我们运行程序时,我们都会得到一个历史H_C(History_Concurrent)的执行.我们需要在H_S中将方法调用视为Ii~Ri.当然,线程A和线程B调用的方法调用之间必然存在很多重叠.但是每个事件(即Invokes和Responses)都有它的实时顺序.因此,A和B调用的所有方法的Invokes和Response可以映射到顺序,顺序可能如下所示:

H_C : IA1 IB1 RA1 RB1 IB2 IA2 RB2 RA2

这个顺序似乎很混乱,它只是每个方法调用的事件类型:

thread A:         IA1----------RA1               IA2-----------RA2
thread B:          |      IB1---|---RB1    IB2----|----RB2      |
                   |       |    |    |      |     |     |       |
                   |       |    |    |      |     |     |       |
real-time order:  IA1     IB1  RA1  RB1    IB2   IA2   RB2     RA2
                ------------------------------------------------------>time

我们得到了H_C.那么我们如何检查H_C的执行是否正确？我们可以按照规则将H_C 重新排序为H_RO:

规则: 如果一个方法调用m1在另一个m2之前,则m1必须在重新排序的序列中位于m2之前.(这意味着如果Ri在H_C中位于Ij前面,你必须保证Ri在重新排序的序列中仍然在Ij前面,我和j没有他们的命令,我们也可以使用a,b,c ...)我们说在这样的规则下H_C 等同于H_RO(history_reorder).

H_RO将有2个属性:

1. 它尊重程序顺序.
2. 它保留了实时行为.

在不违反上述规则的情况下重新排序H_C,我们可以获得一些连续历史(相当于H_C),例如:

H_S1: IA1 RA1 IB1 RB1 IB2 RB2 IA2 RA2
H_S2: IB1 RB1 IA1 RA1 IB2 RB2 IA2 RA2
H_S3: IB1 RB1 IA1 RA1 IA2 RA2 IB2 RB2
H_S4: IA1 RA1 IB1 RB1 IA2 RA2 IB2 RB2

但是,我们无法获得H_S5:

H_S5: IA1 RA1 IA2 RA2 IB1 RB1 IB2 RB2

因为IB1~RB1完全在H_C中的IA2~RA2之前,所以不能重新排序.

现在,有了这些连续的历史,我们如何确认我们的执行历史H_C是否正确？(我强调历史H_C,这意味着我们现在只关注历史H_C的正确性,而不是并发程序的正确性)

答案很简单,如果至少有一个连续历史是正确的(合法顺序历史符合顺序规范的条件),那么历史H_C是可线性化的,我们称合法H_S为H_C的线性化.并且H_C是正确的执行.换句话说,这是我们所期望的合法执行.如果你有并发编程的经验,你必须编写这样的程序,有时看起来很好但有时完全错误.

现在我们已经知道什么是并发程序执行的可线性化历史.那么并发程序本身呢？

线性化背后的基本思想是,每个并发历史在以下意义上与某些连续历史相同. [多处理器编程的艺术3.6.1:可线性化]("跟随意义"是我上面谈到的重新排序规则)

好的,参考可能有点困惑.这意味着,如果每个并发历史记录都具有线性化(法律顺序历史等同于它),则并发程序满足线性化条件.

现在,我们已经理解什么是线性化.如果我们说我们的并发程序是可线性化的,换句话说它具有线性化的特性.这意味着每次我们运行它时,历史都是可线性的(历史就是我们所期望的).

因此很明显,线性化是一种安全(正确性)属性.

然而,将所有并发历史重新排序为顺序历史以判断程序是否可线性化的方法仅在原理上是可能的.在实践中,我们面临着由两位数线程调用的方法调用.我们无法对它们的所有历史进行重新排序.我们甚至无法列出trival程序的所有并发历史记录.

显示并发对象实现可线性化的常用方法是为每个方法确定方法生效的线性化点.[多处理器编程的艺术3.5.1:线性化点]

我们将在"并发对象"的条件下讨论这个问题.它与上面基本相同.并发对象的实现具有一些访问并发对象的数据的方法.多线程将共享一个并发对象.因此,当他们通过调用对象的方法同时访问对象时,并发对象的实现者必须确保并发方法调用的正确性.

他将为每种方法确定线性化点.最重要的是要理解线性化点的含义."方法生效的地方"的陈述真的很难理解.我有一些例子:

首先,让我们看一个错误的案例:

//int i = 0; i is a global shared variable.
int inc_counter() {
    int j = i++;
    return j;
}

找到错误很容易.我们可以将i ++翻译成:

#Pseudo-asm-code
Load   register, address of i
Add    register, 1
Store  register, address of i

所以两个线程可以执行一个"i ++"; 同时,我的结果似乎只增加了一次.我们可以得到这样一个H_C:

thread A:         IA1----------RA1(1)                  IA2------------RA2(3)
thread B:          |      IB1---|------RB1(1)    IB2----|----RB2(2)    |
                   |       |    |        |        |     |     |        |
                   |       |    |        |        |     |     |        |
real-time order:  IA1     IB1  RA1(1)  RB1(1)    IB2   IA2   RB2(2)   RA2(3)
                ---------------------------------------------------------->time

无论您尝试重新排序实时订单,都不能找到相当于H_C的legel顺序历史记录.

我们应该改写这个程序:

//int i = 0; i is a global shared variable.
int inc_counter(){
    //do some unrelated work, for example, play a popular song.
    lock(&lock);
    i++;
    int j = i;
    unlock(&lock);
    //do some unrelated work, for example, fetch a web page and print it to the screen.
    return j;
}

好的,inc_counter()的线性化点是什么？答案是整个批评部分.因为当很多线程反复调用inc_counter()时,临界区将以原子方式执行.并且它可以保证方法的正确性.方法的响应是全局i的增量值.考虑H_C如:

thread A:         IA1----------RA1(2)                 IA2-----------RA2(4)
thread B:          |      IB1---|-------RB1(1)    IB2--|----RB2(3)    |
                   |       |    |        |         |   |     |        |
                   |       |    |        |         |   |     |        |
real-time order:  IA1     IB1  RA1(2)  RB1(1)     IB2 IA2   RB2(3)   RA2(4)

显然,等效的顺序历史是合法的:

IB1 RB1(1) IA1 RA1(2) IB2 RB2(3) IA2 RA2(4)  //a legal sequential history

我们重新排序IB1~RB1和IA1~RA1,因为它们按实时顺序重叠,它们可以被重新排序.在H_C的情况下,我们可以推断首先输入IB1~RB1的临界区.

这个例子太简单了.让我们考虑另一个:

//top is the tio
void push(T val) {
    while (1) {
        Node * new_element = allocte(val);
        Node * next = top->next;
        new_element->next = next;
        if ( CAS(&top->next, next, new_element)) {  //Linearization point1
            //CAS success!
            //ok, we can do some other work, such as go shopping.
            return;
        }
        //CAS fail! retry!
    }
}

T pop() {
    while (1) {
        Node * next = top->next;
        Node * nextnext = next->next;
        if ( CAS(&top->next, next, nextnext)) { //Linearization point2
            //CAS succeed!
            //ok, let me take a rest.
            return next->value;
        }
        //CAS fail! retry!
    }
}

这是一个充满bug的无锁堆栈算法!但不要照顾细节.我只想显示push()和pop()的线性化点.我已经在评论中展示了它们.考虑很多线程反复调用push()和pop(),它们将在CAS步骤中进行排序.其他步骤似乎并不重要,因为无论它们同时执行,它们对堆栈的最终影响(精确的顶部变量)都是由于CAS步骤(线性化点)的顺序.如果我们可以确保线性化点确实有效,那么并发堆栈是正确的.H_C的图片太长了,但我们可以确认必须有一个与H_C相当的合法顺序.

因此,如果您正在实现并发对象,如何判断程序的正确性？您应该确定每个方法的线性化点并仔细思考(或甚至证明)它们将始终保持并发对象的不变量.然后,所有方法调用的部分顺序可以扩展到满足并发对象的顺序规范的至少一个合法的总顺序(事件的顺序历史).

然后你可以说你的并发对象是正确的.

Answer 4

可能是 Linearizability 与 Serializability 之间的混淆。

从这篇文章（P. Bailis）：

线性化是对单个对象的单一操作的保证 [...] 读取和写入操作的线性化是术语“原子一致性”的同义词，是吉尔伯特和林奇对 CAP 的证明中的“C”或“一致性”定理。

可串行化是对事务或对一个或多个对象的一个​​或多个操作组的保证。它保证在多个项目上执行一组事务（通常包含读和写操作）相当于事务的一些串行执行（总排序）[...] 串行化是传统的“I”或隔离，在酸中。