जैसा कि आपने शायद अनुमान लगाया था, यह लेख लॉक-फ्री कतारों के बारे में है।

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

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

क्लासिक लाइनअप

एक क्लासिक कतार एक सूची है (कोई फर्क नहीं पड़ता, बस जुड़ा हुआ या दोगुना जुड़ा हुआ) दो सिरों के साथ - एक सिर और एक पूंछ। सिर से पढ़ें, पूंछ में लिखें।

क्लासिक (1996) लॉक-फ्री कतार एल्गोरिदम को माइकल एंड स्कॉट एल्गोरिथम माना जाता है।
हमेशा की तरह, libcds लाइब्रेरी से कोड की एक शीट प्रदान की जाती है, अगर इसमें प्रश्न में एल्गोरिथ्म का कार्यान्वयन होता है, एक संक्षिप्त (अनुकूलित) रूप में। पूर्ण कोड - cds::intrusive::MSQueue देखें cds::intrusive::MSQueue । टिप्पणियाँ कोड द्वारा डाली जाती हैं, मैंने कोशिश की ताकि वे बहुत उबाऊ न हों।

 bool enqueue( value_type& val ) { /* Implementation detail:    node_type  value_type -                 ,  node_traits::to_node_ptr -   static_cast<node_type *>( &val ) */ node_type * pNew = node_traits::to_node_ptr( val ) ; typename gc::Guard guard; // , , Hazard Pointer // Back-off  (template- ) back_off bkoff; node_type * t; //    lock-free, ,     ... while ( true ) { /*  m_pTail,                  (delete)  */ t = guard.protect( m_pTail, node_to_value() ); node_type * pNext = t->m_pNext.load( memory_model::memory_order_acquire); /*  :  ,  m_pTail     ,  ,      .     */ if ( pNext != nullptr ) { // !    //(  )    m_pTail.compare_exchange_weak( t, pNext, std::memory_order_release, std::memory_order_relaxed); /*    ,   CAS   CAS  — , m_pTail -    ,    . */ continue ; } node_type * tmp = nullptr; if ( t->m_pNext.compare_exchange_strong( tmp, pNew, std::memory_order_release, std::memory_order_relaxed )) { //      . break ; } /*      — CAS  .  ,  -    .   —    ,       —   back_off */ bkoff(); } /* ,   —   ...  ,    -   —   ,     .         ,         */ ++m_ItemCounter ; /* ,     m_pTail.    ,     , —  ,   , . '!'   ,  dequeue */ m_pTail.compare_exchange_strong( t, pNew, std::memory_order_acq_rel, std::memory_order_relaxed ); /*     true. , , bounded queue,    false,   .    enqueue     */ return true; } value_type * dequeue() { node_type * pNext; back_off bkoff; //  dequeue   2 Hazard Pointer' typename gc::template GuardArray<2> guards; node_type * h; // ,    ... while ( true ) { //     m_pHead h = guards.protect( 0, m_pHead, node_to_value() ); //      pNext = guards.protect( 1, h->m_pNext, node_to_value() ); // : ,     , //  ?.. if ( m_pHead.load(std::memory_order_relaxed) != h ) { // , - -    ... //   continue; } /*   . ,            */ if ( pNext == nullptr ) return nullptr; //   /*    ,    Hazard Pointer'   —    ,     ( ) */ node_type * t = m_pTail.load(std::memory_order_acquire); if ( h == t ) { /* !    :  ,     ,     .    ... */ m_pTail.compare_exchange_strong( t, pNext, std::memory_order_release, std::memory_order_relaxed); //       - //      CAS continue; } //    —    //       if ( m_pHead.compare_exchange_strong( h, pNext, std::memory_order_release, std::memory_order_relaxed )) { //  —     break; } /*  ... , -  .    ,    */ bkoff() ; } //   -    , // .   enqueue --m_ItemCounter; //    '  h' dispose_node( h ); /* !!!     !   ,   []  ,  pNext     —    ! */ return pNext; } 

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


घुसपैठ बिंदु का निर्माण करते समय इस बिंदु को ध्यान में रखा जाना चाहिए - लौटा हुआ सूचक अभी भी कतार का हिस्सा है और केवल अगले dequeue पर हटाया जा सकता है।
दूसरे, एल्गोरिथ्म स्पष्ट रूप से मानता है कि पूंछ अंतिम तत्व को इंगित नहीं कर सकती है। जब भी हम पूंछ पढ़ते हैं, तो हम यह देखने के लिए m_pNext हैं कि उसमें अगला m_pNext तत्व है या नहीं। यदि यह पॉइंटर nullptr नहीं है - पूंछ जगह में नहीं है, तो इसे बढ़ावा देने की आवश्यकता है। यहां एक और खराबी है: ऐसा हो सकता है कि पूंछ सिर के सामने एक तत्व को इंगित करेगी (सिर और पूंछ का चौराहा)। इससे बचने के लिए, हम निहित m_pTail->m_pNext जाँच करते हैं: हम सिर को पढ़ते हैं, तत्व m_pHead->m_pNext को सिर के बगल में, सुनिश्चित करें कि pNext != nullptr , और फिर हमने देखा कि सिर पूंछ के बराबर है। इसलिए, पूंछ के पीछे कुछ है, क्योंकि वहाँ pNext , और पूंछ को आगे बढ़ने की आवश्यकता है। पारस्परिक सहायता (मदद) का एक विशिष्ट उदाहरण बहता है, जो लॉक-फ्री प्रोग्रामिंग में बहुत आम है।


2000 में, इस एल्गोरिथ्म का एक छोटा अनुकूलन प्रस्तावित किया गया था । यह नोट किया गया था कि MSQueue विधि में MSQueue एल्गोरिथ्म में, dequeue लूप के प्रत्येक पुनरावृत्ति पर dequeue जाता है , जो अति-विशिष्ट है: पूंछ को पढ़ने की आवश्यकता है (यह सत्यापित करने के लिए कि यह वास्तव में पूंछ है और अंतिम तत्व को इंगित करता है) जब केवल सिर सफलतापूर्वक अपडेट किया गया हो। इस प्रकार, हम कुछ प्रकार के भार के लिए m_pTail पर दबाव में कमी की उम्मीद कर सकते हैं। इस अनुकूलन को cds::intrusive::MoirQueue द्वारा libcds में दर्शाया गया है।

टोकरी कतार

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



प्रत्येक टोकरी वस्तुओं का एक अनियंत्रित संग्रह है। ऐसा लगता है कि इस परिभाषा के साथ, कतार की मुख्य संपत्ति, एफआईएफओ का उल्लंघन किया जाता है, अर्थात, कतार काफी कतार (अनुचित) नहीं बन जाती है। FIFO को बास्केट के लिए सम्मान दिया जाता है, लेकिन बास्केट में आइटम के लिए नहीं। यदि टोकरी को जोड़ने के लिए उपलब्धता अंतराल काफी छोटा है, तो आप इसमें तत्वों के विकार की उपेक्षा कर सकते हैं।
इस अंतराल की अवधि कैसे निर्धारित करें? और यह परिभाषित करने की आवश्यकता नहीं है, टोकरी क्यू के लेखकों का कहना है। MSQueue पर विचार करें। उच्च प्रतिस्पर्धा के साथ enqueue ऑपरेशन में, जब टेल चेंज सीएएस काम नहीं करता था, अर्थात, जहां बैक-ऑफ को MSQueue में कहा जाता है, हम यह निर्धारित नहीं कर सकते हैं कि तत्वों को कतार में जोड़ा जाएगा, क्योंकि वे एक ही समय में जोड़े जाते हैं। यह तार्किक टोकरी है। वास्तव में, यह पता चला है कि तार्किक टोकरियों का अमूर्तकरण एक तरह की बैक-ऑफ रणनीति है।
मैं समीक्षा लेखों में कोड के किलोमीटर को पढ़ने का प्रशंसक नहीं हूं, इसलिए मैंने कोड नहीं दिया। MSQueue उदाहरण के MSQueue का उपयोग करते MSQueue हमने पहले ही देखा है कि लॉक-फ्री कोड बहुत ही क्रिया है। cds::intrusive::BasketQueue कार्यान्वयन को देखना cds::intrusive::BasketQueue हैं, तो मैं cds::intrusive::BasketQueue लाइब्रेरी की cds::intrusive::BasketQueue क्लास, cds/intrusive/basket_queue.h । एल्गोरिथ्म की व्याख्या करने के लिए, मैं Nir Shavit & Co के काम से एक और तस्वीर उधार लूंगा:



1. थ्रेड्स ए, बी, सी कतार में आइटम जोड़ना चाहते हैं। वे देखते हैं कि पूंछ अपनी जगह पर है (और हमें याद है कि MSQueue पूंछ कतार में अंतिम तत्व का संकेत नहीं दे सकती है) और उसी समय इसे बदलने की कोशिश करें ।
2. स्ट्रीम ए विजेता से बाहर आया - एक नया तत्व जोड़ा। थ्रेड्स बी और सी हारे हुए हैं - उनकी पूंछ कैस असफल है, इसलिए वे दोनों पहले से पढ़े गए पुराने पूंछ मूल्य का उपयोग करके अपने आइटम को कार्ट में जोड़ना शुरू करते हैं।
3. स्ट्रीम बी इसके अतिरिक्त को पूरा करने वाला पहला था। इसी समय, थ्रेड डी भी enqueue कहता है और पूंछ को बदलकर सफलतापूर्वक अपना तत्व जोड़ता है।
4. स्ट्रीम सी भी सफलतापूर्वक पूरा करता है। हम देखते हैं कि उसने कहाँ जोड़ा - लाइन के बीच में! इसे जोड़ते समय, यह पुराने टेल पॉइंटर का उपयोग करता है जो कि इसके असफल कैस को निष्पादित करने से पहले ऑपरेशन में प्रवेश करते समय पढ़ता है।

यह ध्यान दिया जाना चाहिए कि इस तरह के जोड़ के साथ यह बहुत अच्छी तरह से हो सकता है कि तत्व कतार के सिर से पहले डाला जाएगा। उदाहरण के लिए, ऊपर चित्र 4 में C से पहले का तत्व: जबकि थ्रेड C, enqueue पर enqueue लगा रहा है, एक और धागा सी से पहले ही तत्व को हटा सकता है। इस स्थिति को रोकने के लिए, तार्किक विलोपन लागू करने का प्रस्ताव है, अर्थात् , एक विशेष रूप से हटाए गए तत्वों के साथ पहले हटाए गए तत्वों को चिह्नित करें। चूँकि यह आवश्यक है कि तत्व को ध्वज और सूचक को परमाणु रूप से पढ़ा जा सकता है, इसलिए हम इस ध्वज pNext तत्व के pNext सूचक pNext में संग्रहीत करेंगे। यह स्वीकार्य है, क्योंकि आधुनिक प्रणालियों में मेमोरी को कम से कम 4 बाइट्स द्वारा गठबंधन किया जाता है, इसलिए पॉइंटर के निचले 2 बिट्स हमेशा शून्य होंगे। इस प्रकार, हमने चिह्नित पॉइंटर्स तकनीक का आविष्कार किया, जिसका उपयोग लॉक-फ्री डेटा संरचनाओं में व्यापक रूप से किया जाता है। हम भविष्य में एक से अधिक बार इस तकनीक को पूरा करेंगे। तार्किक विलोपन को लागू करते हुए, अर्थात, CAS का उपयोग करके pNext के लो-ऑर्डर बिट को 1 पर pNext करना, हम सिर के सामने एक तत्व डालने की संभावना को समाप्त करते हैं - इन्सर्ट भी CAS द्वारा किया जाता है, और हटाए गए तत्व में पॉइंटर के लो-ऑर्डर बिट में 1 होता है, इसलिए CAS विफल हो जाएगा (बेशक, निश्चित रूप से) सम्मिलित करते समय, हम पूरे चिह्नित सूचक को नहीं लेते हैं, लेकिन केवल इसके सबसे महत्वपूर्ण बिट्स, वास्तविक पते वाले, हम शून्य से कम से कम महत्वपूर्ण बिट सेट करते हैं)।
और BasketQueue द्वारा प्रस्तुत अंतिम सुधार वस्तुओं का भौतिक निष्कासन है। यह देखा गया कि प्रत्येक सफल कॉल के साथ सिर को dequeue देने के लिए बदलना dequeue हो सकता है - कैस को वहां भी कहा जाता है, जो कि आप जानते हैं, काफी भारी है। इसलिए, हम सिर को तभी बदलेंगे जब कई तार्किक रूप से हटाए गए तत्व जमा हो libcds ( libcds कार्यान्वयन में डिफ़ॉल्ट रूप से libcds हैं)। या जब कतार खाली हो जाती है। आप कह सकते हैं कि BasketQueue में सिर हॉप्स के साथ बदलता है।

इन सभी अनुकूलन को अत्यधिक प्रतिस्पर्धी स्थिति में क्लासिक लॉक-फ्री कतार के प्रदर्शन को बेहतर बनाने के लिए डिज़ाइन किया गया है।

आशावादी दृष्टिकोण

2004 में, Nir Shavit और Edya Ladan Mozes ने MSQueue अनुकूलन के लिए एक और दृष्टिकोण प्रस्तावित किया, जिसे उन्होंने आशावादी कहा।

उन्होंने देखा कि माइकल और स्कॉट के एल्गोरिथ्म में, dequeue ऑपरेशन के लिए केवल एक कैस की आवश्यकता होती है, जबकि enqueue दो की enqueue (दाईं ओर का आंकड़ा देखें)।

एन्क्यू में यह दूसरी कैस हल्के भार के तहत भी प्रदर्शन को काफी प्रभावित कर सकता है - आधुनिक प्रोसेसर में कैस काफी मुश्किल ऑपरेशन है। क्या उससे छुटकारा पाने का कोई रास्ता है?
गौर कीजिए कि MSQueue::enqueue में दो CAS कहां से आए। पहला CAS नए तत्व को पूंछ से बांधता है - pTail->pNext को संशोधित करता है। दूसरा - पूंछ को ही बढ़ावा देता है। क्या pNext फ़ील्ड को एक साधारण परमाणु रिकॉर्ड के साथ बदला pNext , और CAS के साथ नहीं? हां, अगर हमारी एकल लिंक्ड सूची की दिशा अलग होगी - सिर से पूंछ तक नहीं, लेकिन इसके विपरीत - हम परमाणु स्टोर ( pNew->pNext = pTail ) का उपयोग pNew->pNext = pTail सेट करने के लिए कर pNew->pNext , और फिर pTail बदल pTail । लेकिन अगर हम दिशा बदलते हैं, तो हम एक dequeue कैसे बना सकते हैं? pHead->pNext अब नहीं होगा - सूची की दिशा बदल गई है।
आशावादी लाइनअप के लेखकों ने एक डबल लिंक की गई सूची का उपयोग करने का सुझाव दिया।

एक समस्या है: कैस पर दोहरी रूप से जुड़ी लॉक-फ्री सूची के लिए प्रभावी एल्गोरिदम अभी तक ज्ञात नहीं है। एल्गोरिदम को DCAS ( दो अलग-अलग मेमोरी सेल पर CAS) के लिए जाना जाता है, लेकिन हार्डवेयर में DCAS का कोई अवतार नहीं है। CAS पर MCAS (M असंबद्ध स्मृति कोशिकाओं पर CAS) का अनुकरण करने के लिए ज्ञात एल्गोरिथ्म, लेकिन यह अक्षम है (2M + 1 CAS की आवश्यकता है) और बल्कि सैद्धांतिक हित है।
लेखकों ने इस समाधान का प्रस्ताव दिया: सूची में पूंछ से सिर तक की कड़ी (अगला, वह कतार जो कतार के लिए आवश्यक नहीं है , लेकिन इस लिंक की शुरूआत आपको enqueue में पहली कैस से छुटकारा पाने की अनुमति देती है) हमेशा संगत होगी। लेकिन प्रतिक्रिया - सिर से पूंछ तक, सबसे महत्वपूर्ण, प्रचलित - पूरी तरह से सुसंगत नहीं हो सकती है, अर्थात इसका उल्लंघन स्वीकार्य है। यदि हमें ऐसा उल्लंघन लगता है, तो हम हमेशा अगली कड़ी का पालन करके सही सूची को पुनर्स्थापित कर सकते हैं। इस तरह के उल्लंघन का पता कैसे लगाया जाए? बहुत ही सरल: pHead->prev->next != pHead । यदि यह असमानता dequeue में पाई जाती है dequeue सहायक प्रक्रिया fix_list :

 void fix_list( node_type * pTail, node_type * pHead ) { // pTail  pHead   Hazard Pointer' node_type * pCurNode; node_type * pCurNodeNext; typename gc::template GuardArray<2> guards; pCurNode = pTail; while ( pCurNode != pHead ) { //     pCurNodeNext = guards.protect(0, pCurNode->m_pNext, node_to_value() ); if ( pHead != m_pHead.load(std::memory_order_relaxed) ) break; pCurNodeNext->m_pPrev.store( pCurNode, std::memory_order_release ); guards.assign( 1, node_traits::to_value_ptr( pCurNode = pCurNodeNext )); } } 

[ cds::intrusive::OptimisticQueue से cds::intrusive::OptimisticQueue लाइब्रेरी का cds::intrusive::OptimisticQueue क्लास]
fix_list पूंछ से सिर तक कतार के माध्यम से चलता है साथ ही स्पष्ट रूप से सही pNext लिंक और pPrev को सही करता है।
सिर से पूंछ की सूची (मौजूदा संकेत) का उल्लंघन संभवतः एक भारी भार के बजाय देरी के कारण होता है। देरी एक ऑपरेटिंग सिस्टम या एक बाधा द्वारा एक धागा बाहर भीड़ रहे हैं। OptimisticQueue::enqueue पर विचार करें OptimisticQueue::enqueue :

 bool enqueue( value_type& val ) { node_type * pNew = node_traits::to_node_ptr( val ); typename gc::template GuardArray<2> guards; back_off bkoff; guards.assign( 1, &val ); node_type * pTail = guards.protect( 0, m_pTail, node_to_value()); while( true ) { //    —     pNew->m_pNext.store( pTail, std::memory_order_release ); //    if ( m_pTail.compare_exchange_strong( pTail, pNew, std::memory_order_release, std::memory_order_relaxed )) { /*    —    .      ().   pTail     (dequeue)   (    ,   pTail    Hazard Pointer' , , ) */ pTail->m_pPrev.store( pNew, std::memory_order_release ); break ; // Enqueue done! } /* CAS  — pTail  (   CAS  C++11:     !)   pTail Hazard Pointer' */ guards.assign( 0, node_traits::to_value_ptr( pTail )); // High contention -  bkoff(); } return true; } 

यह पता चला है कि हम आशावादी हैं: हम pPrev सूची (हमारे लिए सबसे महत्वपूर्ण) का निर्माण कर रहे हैं, सफलता पर भरोसा कर रहे हैं। और अगर बाद में हम प्रत्यक्ष और रिवर्स सूची के बीच एक बेमेल पाते हैं - ठीक है, तो आपको सामंजस्य बिठाने ( fix_list चलाने) पर समय बिताना होगा।
तो नीचे की रेखा क्या है? enqueue और dequeue दोनों के पास अब ठीक एक कैस है। मूल्य - एक सूची उल्लंघन का पता चलने पर fix_list लॉन्च करें। चाहे वह उच्च या निम्न हो, प्रयोग कहेगा।
कार्य कोड cds/intrusive.optimistic_queue.h , cds::intrusive::OptimisticQueue लाइब्रेरी के cds::intrusive::OptimisticQueue वर्ग में पाया जा सकता है।

प्रतीक्षा-मुक्त कतार

क्लासिक कतार के बारे में बातचीत को समाप्त करने के लिए, यह प्रतीक्षा-मुक्त कतार एल्गोरिदम का उल्लेख करने योग्य है।
प्रतीक्षा-मुक्त दूसरों के बीच सबसे कठोर आवश्यकता है। यह कहता है कि एल्गोरिथ्म का निष्पादन समय परिमित और अनुमानित होना चाहिए। व्यवहार में, प्रतीक्षा-मुक्त एल्गोरिदम अक्सर अपने कम कड़े समकक्षों - लॉक-फ़्री और बाधा-मुक्त - को कोड की जटिलता और संख्या में पार करते हुए प्रदर्शन के दौरान (आश्चर्यचकित!) अवर होते हैं ।
कई प्रतीक्षा-मुक्त एल्गोरिदम की संरचना बहुत मानक है: एक ऑपरेशन करने के बजाय (हमारे मामले में enqueue / dequeue ) वे पहले इसे घोषित करते हैं, - ऑपरेशन डिस्क्रिप्टर को कुछ सार्वजनिक साझा संग्रहण में तर्कों के साथ संग्रहीत करते हैं, - और फिर प्रतिस्पर्धी थ्रेड्स की मदद करना शुरू करते हैं: दृश्य रिपॉजिटरी में डिस्क्रिप्टर और उनके (डिस्क्रिप्टर) में जो लिखा गया है उसे निष्पादित करने का प्रयास करें। नतीजतन, भारी भार के तहत, कई धागे एक ही काम करते हैं, और उनमें से केवल एक विजेता होगा।
C ++ में इस तरह के एल्गोरिदम को लागू करने की कठिनाई मुख्य रूप से इस भंडारण को कैसे लागू करें और विवरणकर्ताओं के लिए मेमोरी आवंटन से कैसे छुटकारा पाएं।
libcds लाइब्रेरी में प्रतीक्षा-मुक्त कतार कार्यान्वयन नहीं है। लेखकों के लिए स्वयं अपने अध्ययन में इसके प्रदर्शन पर निराशाजनक डेटा प्रदान करते हैं।

परीक्षण के परिणाम

इस लेख में, मैंने तुलनात्मक परीक्षणों के लिए अपनी नापसंदगी को बदलने और उपरोक्त एल्गोरिदम के परीक्षण परिणामों को लाने का फैसला किया।
परीक्षण सिंथेटिक हैं, परीक्षण मशीन दोहरे प्रोसेसर डेबियन लिनक्स, इंटेल दोहरी एक्सोन X5670 2.93 गीगाहर्ट्ज, 6 कोर प्रति प्रोसेसर + हाइपरथ्रेडिंग, कुल 24 तार्किक प्रोसेसर हैं। परीक्षणों के समय, कार लगभग 90% मुक्त थी।
कंपाइलर GCC -O3 -march=native -mtune=native , ऑप्टिमाइज़ेशन -O3 -march=native -mtune=native ।
परीक्षणित कतारें cds::container नेमस्पेस, यानी घुसपैठ नहीं। इसका मतलब है कि प्रत्येक तत्व के लिए मेमोरी आवंटित की जाती है। हम mutex सिंक्रोनाइज़ेशन के साथ मानक कार्यान्वयन std::queue<T, std::deque<T>> और std::queue<T, std::deque<T>> std::queue<T, std::list<T>> साथ तुलना करेंगे। टाइप T एक दो-पूर्णांक संरचना है। सभी लॉक-फ्री कतारें हाजर्ड पॉइंटर पर आधारित हैं।

धीरज की परीक्षा

बहुत विशिष्ट परीक्षण। केवल 10 मिलियन enqueue/ dequeueजोड़े के संचालन। पहले भाग में, परीक्षण 10 मिलियन करता है enqueue, जिसमें 75% संचालन होता है - यह enqueue25% है - dequeue(जो कि पहले भाग में 10 मिलियन enqueueऔर 2.5 मिलियन - dequeue) है। dequeueकतार खाली होने तक दूसरा हिस्सा केवल 7.5 मिलियन गुना है।
इस परीक्षण के निर्माण में विचार यह था: आवंटन कैश के प्रभाव को कम करने के लिए, जब तक कि, निश्चित रूप से, आवंटनकर्ता के पास कैश हो।
पूर्ण डेटा - परीक्षण का नेतृत्व समय:

मैं क्या कह सकता हूं? पहली चीज जो आपकी आंख को पकड़ती है - सबसे तेज़ निकला जो अवरुद्ध है std::queue<T, std::deque<T>> । क्यों?मुझे लगता है कि पूरी चीज मेमोरी के साथ काम कर रही है: यह std::dequeएन तत्वों के ब्लॉक में मेमोरी आवंटित करता है, प्रत्येक तत्व के लिए नहीं। इससे पता चलता है कि परीक्षणों को आवंटनकर्ता के प्रभाव को पूरी तरह से बाहर करना चाहिए, क्योंकि यह काफी बड़ी देरी का परिचय देता है, और इसके अलावा, एक नियम के रूप में, इसके अंदर म्यूटेक्स है। खैर, libcdsसभी कंटेनरों के घुसपैठ वाले संस्करण हैं जो अपने तत्वों के लिए स्मृति आवंटित नहीं करते हैं, आपको उनके साथ परीक्षण का प्रयास करना चाहिए।
जैसा कि हमारी लॉक-फ्री कतारों के लिए है, यह स्पष्ट है कि उन सभी अनुकूलन जो हमने MSQueueउनके परिणामों के संबंध में माना था , हालांकि इतना बड़ा नहीं है।

निर्माता / उपभोक्ता परीक्षण

यह एक जीवन परीक्षण है लाइनअप के एन लेखक और एन पाठक हैं। कुल मिलाकर, क्रमशः 10 मिलियन लेखन कार्य किए जाते हैं, और 10 मिलियन रीड ऑपरेशन होते हैं। रेखांकन में, थ्रेड्स की संख्या पाठकों और लेखकों के लिए थ्रेड्स की संख्या का योग है।
पूर्ण डेटा - परीक्षण निष्पादन समय:

यहां लॉक-फ्री कतारें अधिक योग्य व्यवहार करती हैं। यह विजेता निकला OpimisticQueue, जिसका अर्थ है कि इसके डिजाइन में रखी गई सभी मान्यताओं का भुगतान किया गया।
यह परीक्षण वास्तविकता के करीब है - कतार में तत्वों का कोई सामूहिक संचय नहीं है, इसलिए आंतरिक आवंटनकर्ता अनुकूलन खेलने में आते हैं (मुझे ऐसा लगता है)। खैर, यह सब ठीक है, क्योंकि अंत में, कतार पागल संचय के लिए अभिप्रेत नहीं है, लेकिन गतिविधि के बफरिंग के लिए, और कतार की सामान्य स्थिति इसमें तत्वों की अनुपस्थिति है।

निष्कर्ष

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

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

जारी रखने के लिए ...