कुछ साल पहले, मेरे छोटे गेम प्रोजेक्ट पर काम करते समय, मुझे एक थ्रेड से दूसरे में संदेशों के हस्तांतरण को लागू करने की आवश्यकता थी। समाधान की तलाश में, एक गैर-अवरुद्ध कतार को लागू करने के लिए विचार आया।
कट के तहत विवरण।
समस्या का बयान।
2 धाराएँ हैं - लेखक (इसके बाद लेखक) और पाठक (पाठक)। ताले (म्यूटेक्स या अन्य अवरुद्ध तरीकों) का उपयोग न करके, लेखक को पाठक से संदेश भेजने के लिए एक कतार की आवश्यकता होती है।
कुछ विचार के बाद, हमें निम्नलिखित समाधान मिला: ताकि धागे एक-दूसरे के साथ हस्तक्षेप न करें, आपको दो-भाग वाली कतार का उपयोग करने की आवश्यकता है। एक भाग लेखक द्वारा और दूसरा पाठक द्वारा उपयोग किया जाता है। एल्गोरिथ्म इस प्रकार है:
- लेखक कतार के अपने हिस्से को संदेश लिखता है और पाठक की कतार की जाँच करता है। यदि यह खाली है, तो लेखक की बारी पाठक को दी जाती है, और लेखक के लिए एक नई कतार बनाई जाती है।
- पाठक कतार के अपने हिस्से की जांच करता है और यदि यह खाली नहीं है, तो इससे मान लेता है।
मैंने आरएसडीएन पर कार्यान्वयन निर्धारित किया है (लिंक लेख के अंत में दिया गया है), लेकिन कुछ चर्चा के बाद यह विषय थम गया। और अब मैं अपनी सर्वश्रेष्ठ प्रथाओं को यहां साझा करना चाहूंगा।
वास्तव में कोड:
#define LOCK_FREE_QUEUE2_USE_FLUSH 1 template <class TYPE> class LockFreeQueue2 { public: LockFreeQueue2(); ~LockFreeQueue2(); // void Enqueue(TYPE* data); // bool Dequeue(volatile TYPE*& data); #if LOCK_FREE_QUEUE2_USE_FLUSH // . bool Flush(); #else // void SetWriterFinished(); #endif private: volatile TYPE *readerTop; // TYPE *writerTop, *writerBottom; // #if LOCK_FREE_QUEUE2_USE_FLUSH == 0 volatile bool isWriterFinished; #endif }; template<class TYPE> LockFreeQueue2<TYPE>::LockFreeQueue2() { readerTop = writerTop = writerBottom = NULL; #if LOCK_FREE_QUEUE2_USE_FLUSH == 0 isWriterFinished = false; #endif } template<class TYPE> LockFreeQueue2<TYPE>::~LockFreeQueue2() { } template<class TYPE> void LockFreeQueue2<TYPE>::Enqueue(TYPE* data) { data->next = NULL; if (writerTop) // , { writerBottom->next = data; writerBottom = data; } else // { writerTop = writerBottom = data; } if (!readerTop) // , { readerTop = writerTop; writerTop = NULL; } } template<class TYPE> bool LockFreeQueue2<TYPE>::Dequeue(volatile TYPE*& data) { if (!readerTop) // { #if LOCK_FREE_QUEUE2_USE_FLUSH == 0 if (isWriterFinished && writerTop) // , { readerTop = writerTop; writerTop = NULL; } else #endif { return false; // } } // - data = readerTop; readerTop = readerTop->next; return true; } #if LOCK_FREE_QUEUE2_USE_FLUSH template<class TYPE> bool LockFreeQueue2<TYPE>::Flush() { if (!writerTop) return true; if (!readerTop) // { readerTop = writerTop; return true; } return false; } #else template<class TYPE> void LockFreeQueue2<TYPE>::SetWriterFinished() { isWriterFinished = true; } #endif
LOCK_FREE_QUEUE2_USE_FLUSH
परिभाषित का उपयोग लेखक के काम के अंत में दो अलग-अलग प्रकार के कतार व्यवहार को संकलित
करने के लिए किया जाता है। जब मान 1 होता है, तो राइटर को
फ्लश विधि को तब तक कॉल करना चाहिए जब तक वह रीडर को अपनी चैट कतार नहीं फेंकता। यदि मान 0 है, तो लेखक बस
isWriterFinished चर का मान
सही और सेट करने के लिए सेट करता है। पाठक स्वयं शेष को अंत में उठाएगा।
यह भी लगता है कि पाठक को काम खत्म करने के लिए एक ध्वज की आवश्यकता है ताकि लेखक हमेशा इंतजार न करे।
इस कार्यान्वयन के लिए, आप कुछ और सुविधाएँ जोड़ सकते हैं। उदाहरण के लिए, आप एक आइटम काउंटर जोड़ सकते हैं। यह कतार के प्रत्येक भाग के लिए अलग होना चाहिए, ताकि काउंटर चर तक एक साथ पहुंच न हो। इन काउंटरों का योग कतार में तत्वों की कुल संख्या होगी।
आप रीडर के लिए एक ईवेंट भी जोड़ सकते हैं, जिसके अनुसार वह तब जागेगा जब राइटर उसे अपना हिस्सा देगा। लेकिन सब कुछ इतना सरल नहीं है और एक साथ उपयोग की समस्याएं संभव हैं।
एक लेखक और कई पाठकों की स्थिति के लिए इस कतार का उपयोग नहीं किया जा सकता है, लेकिन आप प्रत्येक पाठक के लिए एक राउटर (डिस्पैचर) और एक कतार का उपयोग कर सकते हैं। राउटर में संदेश को जोड़ने के लिए राउटर को यह निर्धारित करना होगा कि पाठकों में से कौन सा। सबसे सरल मामले में, यह मानदंड कतार में तत्वों की न्यूनतम संख्या हो सकती है।
लेख प्रकाशित करने से पहले, मैंने इस विषय पर थोड़ा ध्यान दिया, लेकिन कुछ भी समान नहीं मिला। शायद मैं बुरी तरह से देख रहा था, इसलिए अगर मैंने एक साइकिल का आविष्कार किया, या यदि आपको कार्यान्वयन में त्रुटियां मिलती हैं, तो टिप्पणियों में लिखें।
RSDN में चर्चा के लिए
लिंक ।