वाली बहु-प्रोग्रामिंग: ताला मुक्त ढेर

Question

मेरी आगामी समवर्ती सिस्टम परीक्षा के लिए preperation में, मैं पाठ्य पुस्तक "बहु प्रोग्रामिंग की कला" से कुछ सवाल पूरा करने के लिए कोशिश कर रहा हूँ। एक सवाल मुझे गुस्सा दिलाना है:

व्यायाम 129: यह मतलब है दोनों धक्का और हमारे LockFreeStack वस्तु में पॉप के लिए एक ही साझा backoff वस्तु उपयोग कैसे करें? EliminationBackOffStack में अंतरिक्ष और समय में हम बैकऑफ कैसे बना सकते हैं?

यह सवाल कीड़े मुझे क्योंकि पहली बात यह है कि मेरे दिमाग में आता है कि यह मतलब नहीं है करता है क्योंकि सभी एक backoff वस्तु एक प्रक्रिया इंतजार करना है, तो क्यों इसे साझा नहीं है? प्रश्न का दूसरा भाग मुझे पूरी तरह से बढ़ाता है और किसी भी मदद का स्वागत है।

LockFreeStack के लिए कोड:

public class LockFreeStack<T> { 

    AtomicReference<Node> top = new AtomicReference<Node>(null); 

    static final int MIN_DELAY = ...; 
    static final int MAX_DELAY = ...; 
    Backoff backoff = new Backoff(MIN_DELAY, MAX_DELAY); 

    protected boolean tryPush(Node node) { 
     Node oldTop = top.get(); 
     node.next = oldTop; 
     return(top.compareAndSet(oldTop, node)); 
    } 

    public void push(T value) { 
     Node node = new Node(value); 
     while (true) { 
      if (tryPush(node)) { 
       return; 
      } else { 
       backoff.backoff(); 
      } 
     } 
    } 

Answer 1

सुनिश्चित नहीं हैं कि अगर मेरे ramblings के किसी भी मदद लेकिन मैं "पोस्ट" बटन वैसे भी प्रेस की जाती है।

जवाब backoff() के कार्यान्वयन पर निर्भर करता है। चूंकि यहां सिंक्रनाइज़ेशन से बचने का लक्ष्य है, इसलिए कोई स्थानीय संग्रहण नहीं होगा - शायद ThreadLocal में कुछ। यदि बैकऑफ एल्गोरिदम एक यादृच्छिकता का उपयोग करता है तो उसे पुन: अनुक्रमित करने की आवश्यकता होगी। तो सबसे अधिक संभावना आप सक्षमpop और push के बीच साझा करने के लिए कर रहे हैं - अब आप करना चाहते हैं। चूंकि पुश और पॉप दोनों top संदर्भ को बदलने की कोशिश कर रहे हैं, तो बैकऑफ ने लगातार थ्रेड को काफी अलग संख्या देने के लिए अच्छा होगा। पुश या पॉप के आसपास और अधिक विवाद है? क्या हमें एक या दूसरी विधि के साथ अधिक आक्रामक रूप से समर्थन करने की आवश्यकता है? यदि यह एक सामान्य ढेर है तो आप नहीं जान पाएंगे।

कैसे backoff "पुनर्गठन" किया जा सकता है के संदर्भ में, मैं भी यकीन नहीं है। क्या आप बैकऑफ समय पर वापस थ्रोटल करने का मौका के रूप में सफल पुश या पॉप का उपयोग कर सकते हैं? यादृच्छिक बैकऑफ के बीच अंतर के बारे में ThreadLocal द्वारा अनुक्रमित अनुक्रम में बनाम प्राइम संख्याओं की प्रतीक्षा कैसे होती है?

Answer 2

एक सिंक्रनाइज़ेशन स्टैंड पॉइंट से पहले प्रश्न के करीब, मेरा मानना ​​है कि यह धक्का और पॉप दोनों के लिए उसी BackOff ऑब्जेक्ट को अनुमति देने के लिए समझ में आता है। इस वर्ग के कार्यान्वयन के बावजूद। इसका कारण यह है कि यदि हमारे पास ढेर है तो हमें स्टैक पर वस्तुओं को हटाने और जोड़ने के दौरान एक सतत स्थिति बनाए रखना चाहिए। हालांकि, हम केवल एक peek (पहले तत्व या ढेर के शीर्ष को देख रहे थे) की तुलना में हम एक से अधिक BackOff ऑब्जेक्ट देख सकते थे क्योंकि पाठ को डेटा स्रोत पर लॉक नहीं करना चाहिए। दूसरे प्रश्न को उस वर्ग के लिए कोड पोस्ट करने की आवश्यकता होगी।

Answer 3

एक backoff का उपयोग करते हुए इस स्थिति में मार खत्म हो गया है।

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

public void push(T value) { 
    Node node = new Node(value); 
    while (!tryPush(node)) 
     backoff.backoff(); 
} 

IMHO:

public void push(T value) { 
    Node node = new Node(value); 
    while (!tryPush(node)); 
}