這些行是否在無鎖隊列中不是必需的？

下面是使用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

這些行是否在無鎖隊列中不是必需的？

回答

相關問題