क्या यह (लॉक-फ्री) कतार कार्यान्वयन थ्रेड-सेफ है?

Question

मैं जावा में लॉक-फ्री कतार कार्यान्वयन बनाने की कोशिश कर रहा हूं, मुख्य रूप से व्यक्तिगत शिक्षा के लिए। कतार एक सामान्य होना चाहिए, जो किसी भी पाठक और/या लेखकों को समवर्ती रूप से अनुमति देता है।

क्या आप इसकी समीक्षा करेंगे, और आपको कोई सुधार/समस्याएं मिलेंगी?

धन्यवाद।

import java.util.concurrent.atomic.AtomicReference; 

public class LockFreeQueue<T> { 
    private static class Node<E> { 
     E value; 
     volatile Node<E> next; 

     Node(E value) { 
      this.value = value; 
     } 
    } 

    private AtomicReference<Node<T>> head, tail; 

    public LockFreeQueue() { 
     // have both head and tail point to a dummy node 
     Node<T> dummyNode = new Node<T>(null); 
     head = new AtomicReference<Node<T>>(dummyNode); 
     tail = new AtomicReference<Node<T>>(dummyNode); 
    } 

    /** 
    * Puts an object at the end of the queue. 
    */ 
    public void putObject(T value) { 
     Node<T> newNode = new Node<T>(value); 
     Node<T> prevTailNode = tail.getAndSet(newNode); 
     prevTailNode.next = newNode; 
    } 

    /** 
    * Gets an object from the beginning of the queue. The object is removed 
    * from the queue. If there are no objects in the queue, returns null. 
    */ 
    public T getObject() { 
     Node<T> headNode, valueNode; 

     // move head node to the next node using atomic semantics 
     // as long as next node is not null 
     do { 
      headNode = head.get(); 
      valueNode = headNode.next; 
      // try until the whole loop executes pseudo-atomically 
      // (i.e. unaffected by modifications done by other threads) 
     } while (valueNode != null && !head.compareAndSet(headNode, valueNode)); 

     T value = (valueNode != null ? valueNode.value : null); 

     // release the value pointed to by head, keeping the head node dummy 
     if (valueNode != null) 
      valueNode.value = null; 

     return value; 
} 

Answer 1

कोड थ्रेड-सुरक्षित नहीं है। putObject(...) पर विचार करें: पहले पिछले नोड के next सूचक स्थापित किया गया है

public void putObject(T value) { 
    Node<T> newNode = new Node<T>(value); 
    Node<T> prevTailNode = tail.getAndSet(newNode); 
    prevTailNode.next = newNode; 
} 

2 बयान नए नोड कहते हैं। यह केवल तीसरे कथन में होता है। इस प्रकार, एक खिड़की है जिसमें nextnull है; यानी एक दौड़ की स्थिति।

यदि आपने इसे ठीक किया है, तो भी एक और कपटपूर्ण समस्या है। एक नोड ऑब्जेक्ट के लिए next फ़ील्ड पढ़ने वाला धागा आवश्यक उस मान को देख सकता है जो एक दूसरा धागा अभी लिखा है। यह जावा मेमोरी मॉडल का एक परिणाम है। इस मामले में, के लिए रास्ता सुनिश्चित कि निम्नलिखित हमेशा पढ़ने के लिए पहले लिखित मूल्य देखता है या तो है:

• घोषित nextvolatile, या
• होने के लिए दोनों पढ़ने और एक आदिम म्युटेक्स में लिख कर एक ही वस्तु पर।

संपादित करें: और अधिक विस्तार में getObject() और putObject() के लिए कोड को पढ़ने पर, मैं देख सकता है कि कुछ भी नहीं next के गैर शून्य मान बलों putObject में स्मृति को प्लावित हो सकता है, और कुछ भी नहीं बलों getObject मुख्य से next पढ़ने के लिए याद। तो getObject कोड next का गलत मान देख सकता है, जिससे यह कतार में वास्तव में एक तत्व होने पर null लौटाता है।

Answer 2

मैं अपने कोड के साथ केवल दो समस्याओं को देखने:

• एक स्मृति संचालन आदेश देने स्टीफन सी उल्लेख (next और valuevolatile की घोषणा के द्वारा हल किया जा सकता है) के साथ समस्या यह है (नोड: मूल्य एक ही समस्या है)

• दूसरा एक और सूक्ष्म है, और समेकन संबंधित नहीं है: getObject में किसी ऑब्जेक्ट को वापस करने के बाद, आप अभी भी अपना संदर्भ सिर से बनाए रखते हैं। यह एक स्मृति रिसाव का कारण बन सकता है।

अन्यथा एल्गोरिदम ठीक है। एक अस्पष्ट प्रदर्शन (उपरोक्त मान लिया गया है):

एल 1: tail कतार से कभी भी हटाया नहीं जा सकता है। ऐसा इसलिए होता है क्योंकि जब tail में कुछ संग्रहीत किया जाता है, तो इसमें next == null है।साथ ही, जब आप xxx.next (केवल putObject में) असाइन करते हैं, तो यह tail नहीं हो सकता है, क्योंकि GetAndSet की परमाणुता और अस्थिर लेखन और बाद में पढ़ने के बीच ऑर्डरिंग - मान लीजिए कि आप एक गैर-शून्य tail.next पढ़ते हैं, तो यह मान लिखा जाना चाहिए putObject और इसलिए होता है- इसके बाद की अंतिम पंक्ति। इसका मतलब यह है कि होता है- पिछली पंक्ति के बाद, जिसका अर्थ है कि हम जो मूल्य पढ़ रहे हैं वह tail से नहीं है।

इसका परिणाम यह है कि putObject में प्रत्येक ऑब्जेक्ट अंततः head से पहुंच योग्य होगा। ऐसा इसलिए है क्योंकि हम tail के बाद कनेक्ट हो रहे हैं, और इस नोड को केवल next पर नया नोड संदर्भ लिखने के बाद ही हटाया जा सकता है, जिसका अर्थ है कि नया नोड head से पहुंच योग्य है।

अतिरिक्त वस्तुओं को ऑपरेशन द्वारा putObject में क्रमशः आदेश दिया गया है।

अस्वीकृत वस्तुओं को compareAndSet परिचालनों के अनुसार getObject में क्रमशः आदेश दिया गया है।

getObject/putObject को अस्थिर क्षेत्र next लिखने/पढ़ने के अनुसार आदेश दिया जाता है।

Answer 3

मेरा मानना ​​है कि जब आप करने की कोशिश आप एक एनपीई मिलता था "मूल्य जारी ..." यदि आप

new LockFreeQueue<?>().getObject(); 

फोन के बाद से आप के खिलाफ की रक्षा के बावजूद, वहाँ valueNode पर किसी भी तुच्छता परीक्षण नहीं करते यह ऊपर

Answer 4

आप java.util.concurrent.ConcurrentLinkedQueue के कार्यान्वयन http://java.sun.com/j2se/1.5.0/docs/api/java/util/concurrent/ConcurrentLinkedQueue.html यह करता है काफी पर आप क्या