ConcurrentLinkedQueue $ नोड हटाने के बाद ढेर में रहता है()

Question

मेरे पास एक बहुप्रचारित ऐप लिखना और एक ConcurrentLinkedQueue पढ़ना है, जिसे अवधारणात्मक रूप से किसी सूची/तालिका में प्रविष्टियों के लिए उपयोग किया जाता है। मैंने मूल रूप से इसके लिए एक ConcurrentHashMap का उपयोग किया, जो अच्छी तरह से काम किया। आदेश प्रविष्टियों को ट्रैक करने की आवश्यकता की एक नई आवश्यकता में आया, इसलिए कुछ स्थितियों के आधार पर उन्हें सबसे पुराने क्रम में हटा दिया जा सकता था। ConcurrentLinkedQueue एक अच्छा विकल्प प्रतीत होता है, और कार्यात्मक रूप से यह अच्छी तरह से काम करता है।

स्मृति में एक कॉन्फ़िगर करने योग्य प्रविष्टियां स्मृति में आयोजित की जाती हैं, और जब सीमा तक पहुंचने पर नई प्रविष्टि की पेशकश की जाती है, तो कतार को हटाए जा सकने वाले किसी के लिए सबसे पुराने क्रम में खोजा जाता है। कुछ प्रविष्टियों को सिस्टम द्वारा हटाया नहीं जाना चाहिए और ग्राहक बातचीत की प्रतीक्षा करें।

ऐसा प्रतीत होता है कि मेरे पास होने वाली कतार के सामने एक प्रविष्टि है, जो 100K प्रविष्टियां पहले हुई थी। कतार में कॉन्फ़िगर की गई प्रविष्टियों (आकार() == 100) की सीमित संख्या प्रतीत होती है, लेकिन जब प्रोफाइलिंग हो रही है, तो मैंने पाया कि स्मृति में ~ 100K ConcurrentLinkedQueue $ नोड ऑब्जेक्ट्स थे। यह डिज़ाइन द्वारा प्रतीत होता है, केवल ConcurrentLinkedQueue के स्रोत पर चमक रहा है, एक निकालने केवल ऑब्जेक्ट को संग्रहीत करने के संदर्भ को हटा देता है लेकिन पुनरावृत्ति के लिए लिंक्ड सूची को छोड़ देता है।

अंततः मेरा प्रश्न: क्या इस प्रकृति के संग्रह को संभालने के लिए एक "बेहतर" आलसी तरीका है? मुझे ConcurrentLinkedQueue की गति पसंद है, मैं इस मामले में असंभव रिसाव को बर्दाश्त नहीं कर सकता। यदि नहीं, ऐसा लगता है कि मुझे ऑर्डर ट्रैक करने के लिए दूसरी संरचना बनाना होगा और एक ही समस्या हो सकती है, साथ ही सिंक्रनाइज़ेशन चिंता भी हो सकती है।

Answer 1

वास्तव में यहां क्या हो रहा है यह है कि निकाली विधि लिंकिंग संदर्भ को बाहर निकालने के लिए एक मतदान थ्रेड तैयार करती है।

ConcurrentLinkedQueue एक गैर अवरुद्ध धागा सुरक्षित कतार कार्यान्वयन है। हालांकि जब आप क्यूई से नोड को मतदान करने का प्रयास करते हैं तो यह दो कार्य प्रक्रिया है। सबसे पहले आप मान को शून्य करते हैं तो आप संदर्भ को रद्द कर देते हैं। एक सीएएस ऑपरेशन एक एकल परमाणु कार्य है जो एक सर्वेक्षण के लिए immidiate संकल्प की पेशकश नहीं करेगा।

क्या होता है जब आप मतदान करते हैं कि सफल होने वाला पहला धागा नोड और शून्य के मूल्य को प्राप्त करेगा, तो वह धागा संदर्भ को रद्द करने का प्रयास करेगा। यह संभव है कि एक और धागा आ जाएगा और कतार से मतदान करने की कोशिश करेगा। यह सुनिश्चित करने के लिए कि इस कतार में एक अवरुद्ध संपत्ति है (जो एक थ्रेड की विफलता किसी अन्य धागे की विफलता का कारण नहीं बनती है) कि नया इनकमिंग थ्रेड देखेगा कि क्या मान शून्य है, अगर यह शून्य है कि थ्रेड संदर्भ को रद्द कर देगा और कोशिश करेगा फिर से मतदान()।

तो आप यहां क्या देख रहे हैं यह है कि निकालना धागा संदर्भ को रद्द करने के लिए बस कोई नया मतदान थ्रेड तैयार कर रहा है। एक गैर अवरुद्ध निकालने के कार्य को प्राप्त करने का प्रयास करना मुझे लगता है कि लगभग असंभव है क्योंकि इसके लिए तीन परमाणु कार्यों की आवश्यकता होगी। मूल्य के नल ने नोड को संदर्भित करने के लिए शून्य संदर्भ दिया, और आखिरकार उस नोड्स माता-पिता से इसके उत्तराधिकारी के नए संदर्भ।

अपने अंतिम प्रश्न का उत्तर देने के लिए। कतार के गैर अवरुद्ध राज्य को हटाने और बनाए रखने के लिए असुरक्षितता का कोई बेहतर तरीका नहीं है। कम से कम इस बिंदु पर है। एक बार प्रोसेसर 2 और 3 तरीके से आवरण शुरू कर देते हैं तो यह संभव है।

Answer 2

कतार का मुख्य अर्थशास्त्र जोड़/मतदान है। यदि आप मतदान()पर ConcurrentLinkedQueue पर उपयोग करते हैं, तो इसे साफ़ किया जाएगा जैसा इसे करना चाहिए। आपके विवरण के आधार पर, मतदान() आपको पुरानी प्रविष्टि को हटाने देना चाहिए। के बजाय इसका उपयोग क्यों न करें()?

Answer 3

1.6 के लिए स्रोत कोड देख रहे हैं।0_2 9, ऐसा लगता है कि सीएलक्यू के इटरेटर को नल वस्तुओं के साथ नोड्स को हटाने का प्रयास करने के लिए संशोधित किया गया था। बजाय:

p = p.getNext(); 

कोड है:

Node<E> next = succ(p); 
if (pred != null && next != null) 
    pred.casNext(p, next); 
p = next; 

इस बग के लिए ठीक के हिस्से के रूप में जोड़ा गया है: http://bugs.sun.com/view_bug.do?bug_id=6785442

दरअसल जब मैं निम्नलिखित की कोशिश मैं के साथ एक OOME मिल पुराना संस्करण लेकिन नए के साथ नहीं:

Queue<Integer> queue = new ConcurrentLinkedQueue<Integer>(); 
for (int i=0; i<10000; i++) 
{ 
    for (int j=0; j<100000; j++) 
    { 
     queue.add(j); 
    } 
    boolean start = true; 
    for (Iterator<Integer> iter = queue.iterator(); iter.hasNext();) 
    { 
     iter.next(); 
     if (!start) 
      iter.remove(); 
     start = false; 
    } 
    System.out.println(i); 
}