这些行是否在无锁队列中不是必需的？

下面是使用compareAndSet来自无锁队列一些代码（在Java中）：这些行是否在无锁队列中不是必需的？

public void enq(T value) { 
    Node newNode = new Node(value); 
    while(true) { 
     Node last = tail.get(); 
     Node next = last.next.get(); 

     if(last != tail.get()) 
      continue; //???  

     if (next != null) { //improve tail 
      tail.compareAndSet(last, next); 
      continue; 
     } 

     if (last.next.compareAndSet(null, newNode)) { //update last node 
      tail.compareAndSet(last, newNode); //update tail 
      return; 
     } 
    } 
} 

public T deq() throws EmptyException { 
    while(true) { 
     Node first = head.get(); 
     Node last = tail.get(); 
     Node next = first.next.get(); 

     if(first != head.get()) 
      continue; //??? 

     if(first == last) { 
      if (next == null) 
       throw new EmptyException(); 

      tail.compareAndSet(last, next); 
      continue; 
     } 

     T value = next.value; 
     if (head.compareAnsdSet(first, next)) { 
      return value; 
     } 
    } 
}

（头部和尾部是队列的成员）

在这两个DEQ和ENQ功能，第一次检查似乎对我没有必要。（那些评论“???”）我怀疑它只是为了某种优化。

我在这里错过了什么吗？这些检查会影响代码的正确性吗？

（代码是从“的多处理器编程艺术”拍摄，虽然我没有重构代码风格有较少的嵌套如果和别人的，同时保持代码的等价物）

来源

2011-03-23 Shiroko

他们似乎在检查局部变量是否已经被一致地设置，但是我会把它留给其他人来回答它们是否会影响代码的正确性。 – 2011-03-23 13:24:44

呀，因为它有垃圾收集，那些IFS只有真正的价值优化，它的有点大：与仅从内存中读取数据相比，CAS相当昂贵，因此确保数值在此期间未发生变化，从而降低后续CAS失败的几率，有助于减少CAS重试次数，这有助于表现。

您也可以将第一个==最后一个& &尾更新检查到head.CAS中，作为进一步的优化：只有当头被更新时，尾才会滞后，因此只有在CAS成功是有道理的。你也可以在那里移动tail.get，因为你在别的地方都不需要它。下面的示例代码。希望这可以帮助！

public T deq() throws EmptyException { 
while(true) { 
    Node first = head.get(); 
    Node next = first.next.get(); 

    if (first != head.get()) 
     continue; 

    if (next == null) { 
     throw new EmptyException(); 
    } 

    T value = next.value; 

    if (head.compareAndSet(first, next)) { 
     Node last = tail.get(); 

     if (first == last) { 
      tail.compareAndSet(last, next); 
     } 

     return value; 
    } 
}

}

来源

2011-03-23 13:43:13 llongi

不错，我学到了一些东西。谢谢。 – Jaydee 2011-03-25 09:50:08

他们是没有必要的，但出于性能原因，请注意检查发生时不使用原子操作。从MSDN

实施例成本：

内存屏障被测量为服用20-90个循环。
InterlockedIncrement测量为需要36-90个周期。
获取或释放关键部分测量为40-100个周期。
获取或释放互斥体测量为需要约750-2500个周期。

参考该特定的技术：

[鲁道夫&西格尔84]鲁道夫，L。和西格尔，Z.镝NAMIC分散缓存方案forMIMD并行处理器。 Invùroceedingsof theíúvúth周年研讨会上 COM-帕特架构，在Java 340 1页> 347，1984年

来源

2011-03-23 13:38:19

它的非阻塞链表算法。详细描述在JCP书（15.4.2。一个非阻塞链接列表）

来源

2011-03-25 09:21:43 yetanothercoder

这些行是否在无锁队列中不是必需的？

回答

相关问题