कुछ समय पहले, मैंने फैसला किया कि मैं .NET में मल्टीथ्रेडिंग के काम के बारे में अधिक जानकारी जानना चाहता हूं और मैंने अतीत में इस पर ध्यान नहीं दिया। इस विषय पर बहुत जानकारी है (मैंने
"सी # पुस्तक के इस भाग को संक्षेप में" एक प्रारंभिक बिंदु के रूप में चुना है), लेकिन जैसा कि यह निकला, संसाधनों का केवल एक छोटा सा हिस्सा विस्तार से कुछ समझाने की कोशिश करता है।
प्रत्येक मास्टर को अपने उपकरणों को जानना चाहिए, और संग्रह से अधिक बार क्या उपयोग किया जा सकता है? इसलिए, मैंने मल्टीथ्रेडेड संग्रहों का एक छोटा सा अवलोकन करने का निर्णय लिया और
समवर्ती छाया के साथ शुरू किया (एक सरसरी समीक्षा पहले ही
यहां देखी जा चुकी
है , लेकिन उनमें से बहुत कम हैं)। सामान्य तौर पर, मुझे कुछ आश्चर्य हुआ कि अभी तक .NET के लिए ऐसा कोई लेख नहीं था (लेकिन
जावा के लिए
पर्याप्त है)।
तो चलिए चलते हैं।
यदि आप पहले से ही शब्दकोश से परिचित हैं, तो आप अगले अनुभाग को छोड़ सकते हैं।
शब्दकोश <TKey, TValue> क्या है?
शब्दकोश मानक
हैशटेबल का कार्यान्वयन है।
निम्नलिखित कार्य यहाँ दिलचस्प हैं:
प्रारंभ
प्रारंभ या तो निर्माण के दौरान होता है (यदि संग्रह का प्रारंभिक आकार स्थानांतरित किया जाता है) या जब पहला तत्व जोड़ा जाता है, और निकटतम प्राइम संख्या को आकार (3) के रूप में चुना जाएगा। इस स्थिति में, 2 आंतरिक संग्रह बनाए जाते हैं -
int [] बाल्टियाँ और
प्रविष्टि [] प्रविष्टियाँ । पहले में दूसरे संग्रह में तत्वों के सूचकांकों को शामिल किया जाएगा, और यह बदले में, इस रूप में स्वयं तत्वों को समाहित करेगा:
private struct Entry { public int hashCode; public int next; public TKey key; public TValue value; }
आइटम जोड़ना
एक तत्व जोड़ते समय, इसकी कुंजी के हैश कोड की गणना की जाती है और फिर टोकरी सूचकांक जिसमें इसे संग्रह में जोड़ा जाएगा modulo:
int bucketNum = (hashcode & 0x7fffffff) % capacity;
यह कुछ इस तरह दिखेगा:
फिर यह जांच की जाती है कि क्या संग्रह में पहले से ही ऐसी कोई कुंजी है, यदि ऐसा है, तो ऐड ऑपरेशन एक अपवाद को फेंक देगा, और इंडेक्स द्वारा असाइनमेंट बस तत्व को एक नए के साथ बदल देगा। यदि शब्दकोश का अधिकतम आकार पहुंच गया है, तो विस्तार होता है (निकटतम प्राइम संख्या द्वारा एक नया आकार चुना जाता है)।
ऑपरेशन की जटिलता, क्रमशः ओ (एन) है।
यदि कोई टकराव होता है (यानी, बकेटनेट इंडेक्स के साथ टोकरी में पहले से ही एक तत्व है), तो नए तत्व को संग्रह में जोड़ा जाता है, इसका सूचकांक टोकरी में संग्रहीत किया जाता है, और पुराने तत्व का सूचकांक इसके अगले क्षेत्र में होता है।
इस प्रकार, हम एक
यूनिडायरेक्शनल लिंक्ड सूची प्राप्त करते हैं। इस टकराव रिज़ॉल्यूशन तंत्र को
चेनिंग कहा जाता है। यदि किसी तत्व को जोड़ने पर टकरावों की संख्या बड़ी है (वर्तमान संस्करण में 100 से अधिक), तो जब संग्रह का
विस्तार किया जाता है , तो एक
री-हैश ऑपरेशन
होता है , जिसके पहले एक नया हैश कोड जनरेटर बेतरतीब ढंग से चुना जाता है।
टकराव की स्थिति में O (1) या O (n) जोड़ने की कठिनाई।
आइटम हटाएं
तत्वों को हटाते समय, हम इसकी सामग्री को डिफ़ॉल्ट मानों के साथ अधिलेखित कर देते हैं, यदि आवश्यक हो, तो अन्य तत्वों के अगले बिंदुओं को बदल सकते हैं, और इस तत्व के सूचकांक को फ्रीलास्ट आंतरिक क्षेत्र में संग्रहीत करते हैं, और अगले क्षेत्र में पुराना मूल्य। इस प्रकार, एक नया तत्व जोड़ते समय, हम ऐसी मुक्त कोशिकाओं का पुन: उपयोग कर सकते हैं:
टकराव की स्थिति में कठिनाई फिर से ओ (1) या ओ (एन) है।
अन्य
यह भी ध्यान देने योग्य है 2 अंक:
1) शब्दकोश की सफाई करते समय, इसका आंतरिक आकार नहीं बदलता है। यही है, संभवतः, आप बस जगह बर्बाद कर रहे हैं।
2) GetEnumerator बस एंट्रेस संग्रह (O (1) जटिलता) पर एक पुनरावृत्ति देता है। यदि आपने केवल तत्व जोड़े हैं, तो वे उसी क्रम में वापस आएंगे। हालांकि, यदि आपने तत्वों को हटा दिया है और नए जोड़े हैं, तो क्रम तदनुसार बदल जाएगा, इसलिए आपको इस पर भरोसा नहीं करना चाहिए (विशेषकर चूंकि यह फ्रेमवर्क के भविष्य के संस्करणों में बदल सकता है)।
तो क्या समवर्ती के बारे में?
ऐसा लगता है कि थ्रेड सुरक्षा सुनिश्चित करने के लिए माथे में 2 समाधान हैं - सभी एक्सेस को ताले में डिक्शनरी में लपेटें या उनमें अपने सभी तरीकों को लपेटें। हालांकि, स्पष्ट कारणों के लिए, यह समाधान धीमा होगा - लॉक द्वारा जोड़ा गया विलंब, और 1 थ्रेड पर प्रतिबंध जो संग्रह के साथ काम कर सकता है, प्रदर्शन को नहीं जोड़ता है।
Microsoft बेहतर तरीके से गया और डिक्शनरी में कुछ बदलाव हुए हैं। तो, शब्दकोश और इसके बास्केट की आंतरिक संरचना के लिए धन्यवाद, विधि का उपयोग करके, उन पर अवरुद्ध किया जाता है
private void GetBucketAndLockNo(int hashcode, out int bucketNo, out int lockNo, int bucketCount, int lockCount) { bucketNo = (hashcode & 0x7fffffff) % bucketCount; lockNo = bucketNo % lockCount; }
इसी समय, एक नियमित शब्दकोश इस योजना के साथ काम नहीं कर सका, क्योंकि सभी बास्केट एक ही प्रविष्टि सरणी का उपयोग करते हैं, इसलिए बास्केट एक नियमित एकल लिंक की गई सूची बन गई है:
वाष्पशील प्रवेश [] m_buckets (गैर-अवरोधन प्रदान करने के लिए क्षेत्र को वॉलेटेल घोषित किया गया है) एक स्थिति में सिंक्रनाइज़ेशन जब एक धागा कुछ ऑपरेशन करने की कोशिश कर रहा है, और इस पल में दूसरा संग्रह का आकार बदलता है)।
परिणामस्वरूप, टोकरियाँ इस तरह दिखने लगीं:
लॉकनो एक नए सरणी में एक इंडेक्स है जिसमें सिंक्रोनाइज़ेशन ऑब्जेक्ट -
ऑब्जेक्ट [] m_locks है । इसका उपयोग एक ही समय में विभिन्न थ्रेड्स को अलग-अलग बास्केट बदलने की अनुमति देता है। इस संग्रह का आकार पैरामीटर
ConcurrencyLevel पर निर्भर करता है जिसे कंस्ट्रक्टर के माध्यम से सेट किया जा सकता है। यह थ्रेड्स की अनुमानित संख्या निर्धारित करता है जो संग्रह के साथ एक साथ काम करेगा (डिफ़ॉल्ट रूप से, यह प्रोसेसर की संख्या * 4 है)। यह मान जितना अधिक होगा, ऑपरेशन लिखना उतना ही आसान होगा, लेकिन यह बहुत अधिक महंगा ऑपरेशन भी बन जाएगा, जिसमें संपूर्ण संग्रह (
Resize, ToArray, Count, IsEmpty, Keys, Values, CopyTo, Clear ) को पूर्ण रूप से अवरुद्ध करने की आवश्यकता होती है। यह पैरामीटर यह भी निर्धारित करता है कि संग्रह के कितने तत्व एक लॉक पर आते हैं (इस संग्रह के आकार के लिए टोकरियों की संख्या के अनुपात के रूप में) और जब आवश्यक से अधिक तत्व होते हैं, तो संग्रह का विस्तार होता है, क्योंकि अन्यथा तत्व की खोज O (1) नहीं होती है, लेकिन O (n) लिंक की गई सूचियों को ट्रेस करके। संग्रह के प्रारंभिक एक्सटेंशन की संख्या को थोड़ा कम करने के लिए, शब्दकोश का प्रारंभिक आकार अब 3 नहीं है, बल्कि 31 है।
सभी परिचालनों ने फार्म लिया:
void ChangeBacket(TKey key) { while (true) { Node[] buckets = m_buckets; int bucketNo, lockNo; GetBucketAndLockNo(m_comparer.GetHashCode(key), out bucketNo, out lockNo, buckets.Length); lock (m_locks[lockNo]) { if (buckets != m_buckets) {
एक नया तत्व जोड़ते समय, आपको यह निर्धारित करने के लिए पूरी लिंक की गई सूची के चारों ओर जाना होगा कि क्या पहले से ही ऐसी कुंजी है और यदि नहीं, तो इसे जोड़ें। इसी तरह, जब हटाते हैं - पहले आपको हटाए जाने वाले नोड को खोजने की आवश्यकता होती है।
हालांकि, कुछ ऑपरेशनों के लिए, सिद्धांत रूप में लॉकिंग आवश्यक नहीं है - ये
ट्राइगेटवैल्यू, गेटइन्यूमर, कॉन्टेंसेके और इंडेक्सिंग हैं । क्यों? क्योंकि टोक़ के आकार में सभी परिवर्तन इस तथ्य के कारण दिखाई देते हैं कि क्षेत्र अस्थिर है, तत्वों को जोड़ने या बदलने के लिए एक नया तत्व उत्पन्न होता है और पुराने को बदल दिया जाता है, और विलोपन केवल अगले नोड के साथ सूचक को प्रतिस्थापित करके होता है।
अन्य
1) एक नियमित शब्दकोश के विपरीत,
क्लियर विधि को कॉल करने से संग्रह का आकार डिफ़ॉल्ट मान पर रीसेट हो जाता है।
2)
GetEnumerator - विधि कॉल के बाद किसी अन्य थ्रेड द्वारा किए गए मामले में पुराने मान वापस कर सकते हैं और पुनरावृत्तिकर्ता ने इस तत्व को कैसे पारित किया। शुरुआत में उल्लिखित लेख में, यह ध्यान दिया गया था कि
शब्दकोश का उपयोग करना बेहतर है। चयन (x => x.Value) .ToArray () शब्दकोश की तुलना में ।Values.ToArray ()
और यह पूरी तरह से सच नहीं है - "बेहतर" के बजाय "तेज" होना चाहिए - ताले की अनुपस्थिति के कारण, लेकिन हमें यह ध्यान रखना चाहिए कि ये दृष्टिकोण अलग-अलग डेटा वापस
कर सकते हैं।
आपका ध्यान देने के लिए धन्यवाद।
लेख का इस्तेमाल किया:
1.
.NET शब्दकोश2.
समवर्ती संग्रह के अंदर: समवर्ती3.
समवर्ती संग्रह4. .NET रिफलेक्टर