मल्टीथ्रेडेड लिंक्ड सूची ट्रैवर्सल

Question

ऑब्जेक्ट्स (सी ++) की एक (दोगुनी) लिंक की गई सूची को देखते हुए, मेरे पास एक ऑपरेशन है जिसे मैं प्रत्येक ऑब्जेक्ट पर प्रदर्शन करने के लिए बहुप्रचार पसंद करूंगा। ऑपरेशन की लागत प्रत्येक वस्तु के लिए समान नहीं है। लिंक्ड सूची विभिन्न कारणों से वस्तुओं के इस सेट के लिए पसंदीदा भंडारण है। प्रत्येक ऑब्जेक्ट में पहला तत्व अगली ऑब्जेक्ट पर पॉइंटर है; दूसरा तत्व सूची में पिछली वस्तु है।

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

अनुकूलन के लिए मेरा अगला दृष्टिकोण मेरी लिंक्ड सूची में तत्वों की सरणी बनाने/पुन: उपयोग करने को समाप्त करने का प्रयास करना है। हालांकि, मैं इस "लीप-मेंढक" दृष्टिकोण को जारी रखना चाहता हूं और किसी भी तरह से कुछ अनौपचारिक दिनचर्या का उपयोग करना चाहता हूं जिसे "इंटरलाक्ड कॉम्परेयर डिफरेंस" कहा जा सकता है - परमाणु रूप से एनयूएलएल (सूची के अंत) के खिलाफ तुलना करने के लिए और सशर्त रूप से dereference & स्टोर, dereferenced मूल्य को वापस लौटना ।

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

विचार? धन्यवाद!

Answer 1

गंभीर वर्ग वास्तव में भारी वजन नहीं हैं। मान लीजिए कि वे लॉक को जल्दी से प्राप्त कर सकते हैं वे एक स्पिन लॉक की तरह कार्य करते हैं।

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

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

Answer 2

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

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

हालांकि, नीचे की रेखा स्पष्ट रूप से स्पष्ट है। अपनी समस्या सेट को जानें और प्रत्येक थ्रेड को अपने वर्तमान नोड के साथ पूरा करने के बारे में बताएं।

Answer 3

मूल रूप से, जितनी जल्दी हो सके सूची के माध्यम से चलाने के लिए, आपके पास कुछ चीजें टालने के लिए हैं;

• लॉक टकराव। यहां तक ​​कि स्पिन ताले के साथ, हर लूप पुनरावृत्ति काम करने के लिए एक मौका अवसर है।
• मेमोरी बाधाएं। हर बार जब आप परमाणु ऑपरेशन करते हैं, तो एक स्मृति बाधा आपके निष्पादन को रोक देगा।
• अनावश्यक काम, जैसे काम करने के लिए सूची स्कैन करना।

मुझे आपके पढ़ने के साथ सहमत होना होगा और स्पिन ताले के पक्ष लेना होगा।

आप पॉइंटर को अस्थिर सूचक में सूची के शीर्ष पर डाल देते हैं।

बदले में प्रत्येक थ्रेड;

• स्पिन ताला
• अगली सूची प्रविष्टि के लिए सूचक में एक अस्थायी
• अपडेट सूचक का मूल्य बचाता
• विज्ञप्ति spinlock ले जाता है।

यह अस्थायी द्वारा इंगित प्रविष्टि पर काम करना शुरू कर सकता है।

इसमें प्रति-प्रवेश लॉक का उपयोग करके सूची के माध्यम से खोज करने के कुछ फायदे हैं;

• यदि प्रति आइटम काम पूरा करने में कोई छोटा समय नहीं लगता है, तो आपके पास सूचक को अद्यतन करने की छोटी अवधि के लिए बहुत कम टकराव होंगे।
• टकराव को छोड़कर, आपके पास प्रत्येक सूची आइटम के लिए केवल 2 मेमोरी बाधाएं होंगी, एक लॉक के लिए, एक अनलॉक के लिए।
• नया कार्य आइटम प्राप्त करने के लिए सूची की कोई स्कैनिंग नहीं, बस "कतार" से कार्य प्राप्त करें।

Answer 4

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

प्रत्येक धागा करना होगा:

1. प्रारंभ के सिर से ही सूची traversing।
2. प्रत्येक सूची नोड के लिए जांच करें कि उसके अगले सूचक का निचला बिट सेट है या नहीं।
3. यदि बिट गेटो सेट किया गया है 7.
4. (next | 1) के साथ सूची नोड के अगले सूचक की तुलना करें और स्वैप करें।
5. यदि तुलना करें और स्वैप विफल हो गया 7।
6. ऑब्जेक्ट को संसाधित करें।
7. अगले नोड और गोटो में ले जाएँ 2.

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

इस तरह धागे को wait-free fashion में अवरुद्ध या व्यस्त कताई के बिना सूची से ऑब्जेक्ट प्राप्त होंगे।