लॉकलेस कतार मतदान के लिए सबसे तेज़ रेस फ्री विधि क्या है?

Question

कहें कि हमारे पास एकल-निर्माता-थ्रेड एकल-उपभोक्ता-थ्रेड लॉकलेस कतार है, और निर्माता बिना किसी डेटा के उत्पादन के लंबे समय तक जा सकता है। जब कतार में कुछ भी नहीं है (बिजली की बचत के लिए और अन्य प्रक्रियाओं/धागे के लिए सीपीयू को मुक्त करने के लिए) उपभोक्ता धागे को नींद देना फायदेमंद होगा। यदि कतार लॉकलेस नहीं थी, तो इस समस्या को हल करने का सीधा तरीका है कि उत्पादन थ्रेड एक म्यूटेक्स को लॉक करें, अपना काम करें, एक कंडीशन वैरिएबल सिग्नल करें और अनलॉक करें, और रीडिंग थ्रेड के लिए म्यूटेक्स को लॉक करने के लिए, कंडीशन वैरिएबल पर प्रतीक्षा करें , इसे पढ़ना, फिर अनलॉक करें। लेकिन अगर हम एक लॉकलेस कतार का उपयोग कर रहे हैं, तो म्यूटेक्स का उपयोग करके वैसे ही एक ही तरीके से लॉकलेस कतार का उपयोग करने से प्राप्त होने वाले प्रदर्शन को खत्म कर दिया जाएगा।

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

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

क्या यह करने का सबसे अच्छा तरीका है? क्या विकल्प हैं?

नोट: द्वारा 'सबसे तेजी से' मैं वास्तव में ', सबसे तेजी से अधिक से अधिक कतार जाँच करने के लिए एक कोर समर्पित बिना' मतलब लेकिन उस शीर्षक में फिट नहीं होता, पी

एक वैकल्पिक: निष्पक्ष समाधान के साथ जाएं, लेकिन उपभोक्ता को कंडीशन वैरिएबल पर अधिकतम विलंबता के अनुरूप टाइमआउट के साथ प्रतीक्षा करें, जिसे आप कतार के माध्यम से यात्रा करने वाले आइटम के लिए सहन करने के इच्छुक हैं। यदि वांछित टाइमआउट काफी छोटा है, तो यह आपके ओएस के लिए न्यूनतम प्रतीक्षा समय से नीचे हो सकता है या फिर भी बहुत अधिक CPU का उपभोग कर सकता है।

Answer 1

मुझे लगता है कि आप Dr Dobbs article से लॉक-फ्री एकल-निर्माता सिंगल-उपभोक्ता कतार का उपयोग कर रहे हैं - या कुछ इसी तरह - इसलिए मैं वहां से शब्दावली का उपयोग करूंगा।

उस मामले में, पैरा में आपके द्वारा सुझाए गए जवाब शुरू होता है कि "AFAICT" अच्छा है, लेकिन मैं यह थोड़ा अनुकूलित किया जा सकता है लगता है:

• उपभोक्ता में - के रूप में आप कहते हैं, जब उपभोक्ता समाप्त हो गया है कतार और सो विचार कर रहा है (और उसके बाद ही), यह म्युटेक्स या तो
  • विज्ञप्ति म्युटेक्स ताले, कतार फिर से जाँच करता है, और फिर और, काम पर किया जाता है, अगर वहाँ कतार में एक नया आइटम था
  • या हालत परिवर्तनीय पर ब्लॉक (म्यूटेक्स को छोड़कर जब यह एक खाली खाली कतार खोजने के लिए जागता है, नेट urally)।
• निर्माता में:
  • पहले last की एक प्रति लेने के लिए, कॉल यह saved_last
  • हमेशा की तरह आइटम new_item जोड़ कर divider सूचक की एक प्रति लेने के लिए, यह saved_divider कहते हैं।
  • यदि saved_divider का मान new_item के बराबर है, तो जिस वस्तु को आपने अभी डाला है, तो आपकी वस्तु पहले से ही खाई जा चुकी है, और आपका काम पूरा हो गया है।
  • अन्यथा, यदि saved_divider का मान saved_last के बराबर नहीं है, तो आपको उपभोक्ता को जागने की आवश्यकता नहीं है। इसका कारण यह है:
    • एक समय सख्ती से करने के बाद आप अपने नए ऑब्जेक्ट जोड़ पर, आप जानते हैं कि divider अभी तक या तो new_item या saved_last
    • जब से तुम प्रविष्टि शुरू कर दिया पर पहुंच गया था, last केवल उन दो मानों पड़ा है
    • उपभोक्ता केवल तब ही बंद हो जाता है जब dividerlast
    • के कारण बराबर है इसलिए उपभोक्ता अभी भी जागृत होना चाहिए और सोने से पहले आपके नए आइटम तक पहुंच जाएगा।
  • अन्यथा म्यूटेक्स को लॉक करें, कन्वेयर को सिग्नल करें और फिर म्यूटेक्स को छोड़ दें। (प्राप्त करने म्युटेक्स यहाँ आप देख कतार खाली है, और वास्तव में condvar पर अवरुद्ध उपभोक्ता के बीच के समय में condar संकेत नहीं है सुनिश्चित करता है।)

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

उपरोक्त स्पष्टीकरण काफी शब्दशः है (क्योंकि मैं यह समझना चाहता हूं कि यह क्यों काम करता है, बजाय एल्गोरिदम क्या है), लेकिन इसके परिणामस्वरूप कोड काफी सरल होना चाहिए।

बेशक यह वास्तव में करने योग्य है कि यह बहुत सी चीजों पर निर्भर करेगा, और मैं आपको यह मापने के लिए प्रोत्साहित करता हूं कि प्रदर्शन आपके लिए महत्वपूर्ण है या नहीं। म्यूटेक्स/कोंडोर प्राइमेटिव्स के अच्छे कार्यान्वयन आंतरिक रूप से अधिकांश मामलों के लिए परमाणु संचालन का उपयोग करते हैं, इसलिए यदि आमतौर पर आवश्यकता होती है तो वे केवल कर्नेल कॉल (सबसे महंगी बिट!) बनाते हैं - यानी अगर ब्लॉक करने की आवश्यकता है, या निश्चित रूप से कुछ हैं धागे इंतजार कर रहे हैं - इसलिए म्यूटेक्स फ़ंक्शंस को कॉल न करके सहेजा गया समय केवल लाइब्रेरी कॉल के ओवरहेड तक ही हो सकता है।