是一个没有线性化点的方法总是不能线性化？ [英] Is a method with no linearization points always not linearizable?

问题描述

如果你能明确地证明一个方法没有线性化点，那么它必然意味着该方法不是线性化的？

If you can definitely prove that a method has no linearization points, does it necessarily mean that that method is not linearizable? Also, as a sub question, how can you prove that a method has no linearizatioon points?

推荐答案

If you can definitely prove that a method has no linearization points, does it necessarily 
mean that that method is not linearizable? 

首先，线性化不是方法的属性，它是执行序列的属性。

Firstly, linearizability is not property of a method, it is property of execution sequence.

how can you prove that a method has no linearizatioon points?

这取决于执行顺序，我们是否能找到方法
的线性化点。

It depends on the execution sequence whether we are able to find linearization point for the method or not.

例如，对于FIFO队列上的线程A，我们有以下序列。 t1，t2，t3是时间
间隔。

For example, we have the below sequence, for thread A on a FIFO queue. t1, t2, t3 are time intervals.

A.enq（1） A.enq（2）  A.deq（1）

     t1         t2                t3

A.enq(1)   A.enq(2)   A.deq(1)
     t1          t2                t3

我们可以选择前两个enq方法的线性化点（lp）作为时间间隔t1和t2中的任何点，以及为t3中的任意点选择。我们选择的点是这些方法的lp。

We can choose linearization points(lp) for first two enq methods as any points in time interval t1 and t2 respectively, and for deq any point in t3. The points that we choose are lp for these methods.

现在，考虑一个错误的实现

Now, consider a faulty implementation

A.enq（1）   A.enq 2）   A.deq（2）

    t1          t2                 t3

A.enq(1)   A.enq(2)    A.deq(2)
    t1           t2                 t3

可线性允许lp尊重实时排序。因此，方法的lp应遵循时间排序，即t1 < t2 < t3。然而，由于我们的实施是不正确的，我们不能清楚地这样做。因此，我们不能找到方法A.deq（2）的线性化点，反过来我们的seq。

Linerizability allows lp to respect the real-time ordering. Therefore, lp of the methods should follow the time ordering i.e. t1 < t2 < t3. However, since our implementation is incorrect, we cannot clearly do this. Hence, we cannot find linearization point for the method A.deq(2), in turn our seq. too in not linerizable.

希望这有助于，如果你需要知道更多你可以阅读这本书：
http://www.amazon.com/Art-Multiprocessor-Programming-Maurice-Herlihy/dp/0123705916

Hope this helps, if you need to know more you can read this book: http://www.amazon.com/Art-Multiprocessor-Programming-Maurice-Herlihy/dp/0123705916

这篇关于是一个没有线性化点的方法总是不能线性化？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！