2

如果你可以肯定地证明一个方法没有线性化点，那是否一定意味着该方法不可线性化？另外，作为一个子问题，你如何证明一个方法没有线性化点？

4

3 回答 3

3

为了建立在上述答案的基础上，可以将一种方法描述为可线性化的。正如 djoker 提到的书中所引用的那样：http ://www.amazon.com/dp/0123705916/?tag=stackoverfl08-20

在第 69 页，练习 32，我们看到

在此处输入图像描述

应该注意的是 enq() 确实是一种方法，它被描述为可能是可线性化/不可线性化的。

证明存在可线性化的点归结为寻找是否存在可以破坏线性化的示例。如果你假设一个方法中的各种读/写内存操作是线性化的，然后通过矛盾证明这种假设会导致非线性化的情况，你可以声明前面提到的读/写操作不是一个有效的线性化点。

以下面的 enq()/deq() 方法为例，假设它们是标准队列实现的一部分，带有头/尾指针和后备数组“arr”：

public terribleQueue(){
  arr = new T[10];
  tail = 0;
  head = 0;
}

void enq(T x){
  int slot = tail;
  arr[slot] = x;
  tail = tail + 1;
}

T deq(){
  if( head == tail ) throw new EmptyQueueException();
  T temp = arr[head];
  head = head + 1;
  return temp;
}

在这个糟糕的实现中，我们可以很容易地证明，例如， enq 的第一行不是一个有效的线性化点，假设它是一个线性化点，然后找到一个显示其他情况的示例，如下所示：

以两个线程 A 和 B 以及示例历史为例：

A: enq( 1 )
A: slot = 0
B: enq( 2 )
B: slot = 0

（A 和 B 现在已经超过了它们的线性化点，因此我们不允许重新排序它们以适应我们的历史）

A: arr[0] = 1
B: arr[0] = 2
A: tail = 1
B: tail = 2

C: deq()
C: temp = arr[0] = 2
C: head = 1
C: return 2

现在我们看到，由于我们选择了线性化点（它固定了 A 和 B 的顺序），这个执行将不可能线性化，因为我们不能让 C 的 deq 返回 1，无论我们把它放在哪里。

有点啰嗦的答案，但我希望这会有所帮助

于 2015-10-07T01:31:37.467 回答
2 
如果你可以肯定地证明一个方法没有线性化点，它是否一定
意味着该方法不可线性化？

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

你怎么能证明一个方法没有线性化点？

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

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

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

我们可以将前两种 enq 方法的线性化点 (lp) 分别选择为时间间隔 t1 和 t2 中的任意点，而对于 deq 则选择 t3 中的任意点。我们选择的点是这些方法的 lp。

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

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

线性化允许 lp 尊重实时排序。因此，方法的 lp 应遵循时间顺序，即 t1 < t2 < t3。但是，由于我们的实现不正确，我们无法清楚地做到这一点。因此，我们无法找到方法 A.deq(2) 的线性化点，而我们的 seq。也不能衬里。

希望这会有所帮助，如果您需要了解更多信息，可以阅读本书： http ://www.amazon.com/Art-Multiprocessor-Programming-Maurice-Herlihy/dp/0123705916

于 2011-10-03T20:51:36.780 回答
0

这个答案基于我第一次阅读维基百科上的线性化，并试图通过发生前的关系将其映射到我对内存一致性的现有理解。所以我可能误解了这个概念。

如果你可以肯定地证明一个方法没有线性化点，那是否一定意味着该方法不可线性化？

可能存在这样一种情况，即共享的可变状态由多个线程同时操作，而没有任何同步或可见性帮助，并且仍然保持所有不变量而没有损坏的风险。

但是，这些情况非常罕见。

你怎么能证明一个方法没有线性化点？

据我了解线性化点，在这里我可能错了，它们是在线程之间建立关系之前发生的地方。如果一个方法（通过它依次调用的每个方法递归）没有建立这样的关系，那么我会断言它没有线性化点。

于 2009-09-03T21:06:40.137 回答