समवर्ती डेटा संरचना
कंप्यूटर विज्ञान में, a समवर्ती डेटा संरचना है जिसके द्वारा एक्सेस के लिए डेटा को स्टोर करने और व्यवस्थित करने की विशेष विधि का उपयोग किया जाता हैं, कंप्यूटर पर एकाधिक कंप्यूटिंग थ्रेड (कंप्यूटर विज्ञान) (या प्रक्रिया (कंप्यूटिंग) उत्पन्न होती हैं।
ऐतिहासिक रूप से, ऐसी डेटा संरचनाओं का उपयोग यूनिप्रोसेसर पर किया जाता था।
ऑपरेटिंग सिस्टम वाली मशीनें जो एकाधिक का समर्थन करती हैं, इसके लिए कंप्यूटिंग थ्रेड्स (या प्रक्रिया (कंप्यूटिंग)) के लिए थ्रेड्स के संचालन की बहुसंकेतन /इंटरलीविंग शब्द संगामिति (कंप्यूटर विज्ञान) ने अधिकृत कर लिया हैं।
ऑपरेटिंग सिस्टम द्वारा डेटा प्रोसेसर कभी नहीं प्रोसेस होता हैं जबकि दो ऑपरेशन प्रस्तुत किए जाते हैं जो डेटा के साथ एक्सेस करती थी।
आज मल्टीप्रोसेसर के रूप में कंप्यूटर आर्किटेक्चर प्रदान करता है, समानांतर कंप्यूटिंग प्रमुख कंप्यूटिंग प्लेटफॉर्म बन जाती है (जिसके माध्यम से बहु-कोर प्रोसेसर का प्रसार होता हैं), इस प्रकार मुख्य रूप से डेटा संरचनाओं के लिए खड़े होते हैं जिन्हें एकाधिक द्वारा एक्सेस किया जाता है, थ्रेड्स जो वास्तव में डेटा के साथ एक्सेस करते हैं, क्योंकि वे विभिन्न प्रोसेसरों पर चलते हैं जो दूसरे के साथ संवाद करते हैं। समवर्ती डेटा संरचना (कभी-कभी 'साझा डेटा संरचना भी कही जाती है) जिसको सामान्यतः अमूर्त भंडारण में रहने के लिए माना जाता है, इस पर्यावरण को जिसे साझा स्मृति संरचना कहा जाता है, चूंकि यह एक प्रकार की मेमोरी हो सकती है, भौतिक रूप से इसे कसकर युग्मित किया जाता हैं और या फिर इसे एक भंडारण मॉड्यूल के वितरित संग्रह के रूप में लागू किया जाता हैं।
मूल सिद्धांत
समवर्ती डेटा संरचनाएं में उपयोग के लिए अभिप्रेत सम्मिलित होते हैं, जिसे समानांतर या वितरित कंप्यूटिंग वातावरण से भिन्न माना जाता हैं
अनुक्रमिक डेटा संरचनाएं, यूनी-प्रोसेसर पर उपयोग के लिए इसे अग्रेषिक किया जाता हैं।
मशीन को इस अभिप्राय में[1] विशेष रूप से, अनुक्रमिक वातावरण में डेटा संरचना के गुणों को निर्दिष्ट करने के लिए उपयोग किया जाता हैं और जाँचा जाता है कि वे सुरक्षा गुण प्रदान करके सही ढंग से लागू किये जा रहे है। इस प्रकार समवर्ती वातावरण में विनिर्देशन का भी वर्णन करना चाहिए, तथा जीवंतता गुण जो कार्यान्वयन प्रदान करना चाहिए। इसके सुरक्षा गुण सामान्यतः रहते हैं जिससे किसी प्रकार की हानी नहीं होती हैं, जबकि इसके सजीवता गुण बताते हैं कि इस अनुक्रम में कुछ न कुछ अच्छा होता रहता है। इस प्रकार इन गुणों को व्यक्त किया जा सकता है, उदाहरण के लिए, रैखिक लौकिक तर्क का उपयोग करना इत्यादि।
लाइवनेस आवश्यकताओं के प्रकार डेटा संरचना को परिभाषित करते हैं। विधि (कंप्यूटर विज्ञान) कॉल अवरुद्ध करना (कंप्यूटिंग) या गैर-अवरुद्ध एल्गोरिदम या नॉन-ब्लॉकिंग प्रकार की हो सकती है। ये मुख्य रूप से डेटा संरचनाएं नहीं होती हैं, इस प्रकार से सीमित, और संयोजनों को अनुमति दी जा सकती हैं। जहां कुछ मेथड कॉल ब्लॉक हो जाती हैं और अन्य नॉन-ब्लॉकि रहती हैं हैं, (उदाहरण के लिए जावा समवर्ती सॉफ्टवेयर में ये लाईब्रेरी पायी जाती हैं)।
समवर्ती डेटा संरचनाओं के सुरक्षा गुणों को उनका अधिकार करना चाहिए, व्यवहारिक रूप से इन विधियों के कई संभावित अंतःक्रियाओं को अलग-अलग प्रकारों से काॅल किया जाता है। इस प्रकार यह बिल्कुल सत्य है कि कैसे वर्चुअल डेटा संरचनाओं को निर्दिष्ट करने के लिए सहजता से ज्ञान युक्त अनुक्रमिक सेटिंग के रूप में व्यवहार करते हैं जिसमें कोई इंटरलीविंग नहीं होती हैं।
इसलिए इसके सुरक्षा गुणों पर वाद विवाद करने के लिए कई मुख्य धारा के दृष्टिकोण से समवर्ती डेटा संरचना (जैसे क्रमबद्धता, रैखिकता, अनुक्रमिक स्थिरता, और शांत संगति[1] संरचना गुण निर्दिष्ट किए जाते हैं जिसे क्रमिक रूप से इसके अनुक्रमिक को संग्रह करने के उद्देश्य से समवर्ती निष्पादन के साथ मैप किया जाता हैं।
इस प्रकार की सुरक्षा और जीवंतता गुणों की गारंटी देने के लिए, समवर्ती डेटा संरचनाओं को सामान्यतः थ्रेड्स को अनुमति देनी चाहिए, जिसके परिणामस्वरूप सहज सहमति (कंप्यूटर विज्ञान) तक पहुँच जाए और इसके फलस्वरूप उनके साथ डेटा एक्सेस और संशोधन का अनुरोध करने में सफल हो सके। यह प्रक्रिया ऐसे समझौते का समर्थन करती हैं, जिसमें समवर्ती डेटा संरचनाएं लागू की जाती हैं, विशेषतः तुल्यकालन संचालन का उपयोग करना सम्भव हो जाता हैं (इसके लिए तुल्यकालन (कंप्यूटर विज्ञान)#Process_synchronization को देख सकते हैं)।
आधुनिक बहु पर उपलब्ध होने वाले जो कई धागों को सहज सहमति तक पहुंचने की अनुमति देता है। स्पिनलॉक का उपयोग करके या बिना ताले के अवरुद्ध विधि से यह सहज सहमति प्राप्त कर सकता हैं, जिस स्थिति में यह गैर-अवरुद्ध एल्गोरिथम का उपयोग करता हैं। गैर-अवरुद्ध या भौतिक रूप से इसे प्रदर्शित किया जाता हैं, इस प्रकार समवर्ती डेटा संरचनाओं के डिजाइन के सिद्धांत को ग्रंथसूची संबंधी संदर्भ में दर्शाया जा सकता हैं।
डिजाइन और कार्यान्वयन
समवर्ती डेटा संरचनाओं को डिजाइन करना अधिक कठिन है, और उनके अनुक्रमिक समकक्षों की तुलना में सही होने के रूप में सत्यापित करने के लिए इसका उपयोग होता हैं।
इस अतिरिक्त कठिनाई का प्राथमिक स्रोत संगामिति होती है, इस तथ्य से धागे को पूरी तरह से अतुल्यकालिक माना जाना चाहिए: जिससे कि वे ऑपरेटिंग सिस्टम प्रीमेशन, पृष्ठ दोषों के अधीन कार्य करते हैं, इस प्रकार इसे बाधित किया जाता हैं।
आज की मशीनों में प्रोसेसर का लेआउट और मेमोरी में डेटा के लेआउट पर संचार भार को मल्टीप्रोसेसर आर्किटेक्चर के विभिन्न तत्व प्रदर्शन से प्रभावित करते हैं। इसके अतिरिक्त, शुद्धता और प्रदर्शन के बीच तनाव रहते है जिससे एल्गोरिथम संवर्द्धन के प्रदर्शन में सुधार हो सकता हैं, अधिकांशतः इसे डिजाइन करना और डेटा संरचना कार्यान्वयन के लिए सही प्रकार से सत्यापित करना अधिक कठिन होता है।[2] इसके प्रदर्शन के लिए महत्वपूर्ण माप मापनीयता है, जिसे कार्यान्वयन की गति से प्राप्त किया जाता है। इस प्रकार से गति बढ़ाने के बारे में उपायों के बारे में सोचा जाता है, जिसे प्रभावी रूप से एप्लिकेशन के उद्देश्य से उस मशीन का उपयोग कर रहा होता है जिस पर वह रन होता है। P प्रोसेसर वाली मशीन पर, स्पीडअप प्रोसेसर पर संरचना निष्पादन समय का P प्रोसेसर पर इसके निष्पादन समय का अनुपात निर्धारित होता हैं। आदर्श रूप से, हम रैखिक गति चाहते हैं: हम इसे प्राप्त करना चाहेंगे तथा P प्रोसेसर का उपयोग करते समय P को स्पीडअप करते हैं। इस प्रकार डेटा संरचनाएं जिसकी स्पीडअप P के साथ बढ़ती जाती हैं जिसे स्केलेबल कहा जाता है। समवर्ती डेटा संरचना के प्रदर्शन को किस सीमा तक बढ़ाता हैं, इसे आमदहीज नियम के रूप में ज्ञात सूत्र द्वारा प्रदर्शित किया जाता है और इसके अधिक परिष्कृत संस्करण जैसे कि गुस्ताफ़सन का नियम का उपयोग किया जाता हैं।
समवर्ती डेटा संरचनाओं के प्रदर्शन के साथ महत्वपूर्ण विवाद स्मृति विवाद के स्तर पर निर्भर रहता हैं: यातायात में और स्मृति से के रूप में ओवरहेड को कई थ्रेड्स के साथ उपयोग करने का प्रयास करने के परिणाम स्वरूपप स्मृति में स्थान देने के लिए उपयोग किया जाता हैं। इस प्रकार कार्यान्वयन को इसके अवरुद्ध करने के साथ यह समस्या सबसे गंभीर है जिसमें लॉक मेमोरी के एक्सेस को नियंत्रित करता है। जिसेके लिए लॉक प्राप्त करने पश्चात थ्रेड को बार-बार संशोधित करने के प्रयास से उपयोग किया जाता हैं। कैश सुसंगतता के लिए कैश-सुसंगत को मल्टीप्रोसेसर (एक जिसमें प्रोसेसर होते हैं, स्थानीय कैश जो उन्हें रखने के लिए हार्डवेयर द्वारा अपडेट किए जाते हैं, जिसमें संग्रहीत नवीनतम मूल्यों के अनुरूप) इसका परिणाम लंबे समय तक होता है, जिसके स्थान को संशोधित करने के प्रत्येक प्रयास के लिए प्रतीक्षा समय और इससे जुड़े अतिरिक्त मेमोरी ट्रैफ़िक द्वारा लॉक प्राप्त करने के असफल प्रयास को बढ़ा दिया जाता हैं।
यह भी देखें
- जावा संगामिति (JSR 166)
- जावा समवर्ती मानचित्र
संदर्भ
- ↑ 1.0 1.1 Mark Moir; Nir Shavit (2007). "Concurrent Data Structures" (PDF). In Dinesh Metha; Sartaj Sahni (eds.). Handbook of Data Structures and Applications. Chapman and Hall/CRC Press. pp. 47-14–47-30. Archived from the original (PDF) on 2011-04-01.
- ↑ Gramoli, V. (2015). "More than you ever wanted to know about synchronization: Synchrobench, measuring the impact of the synchronization on concurrent algorithms" (PDF). Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. ACM. pp. 1–10. Archived from the original (PDF) on 10 April 2015.
अग्रिम पठन
- Nancy Lynch "Distributed Computing"
- Hagit Attiya and Jennifer Welch "Distributed Computing: Fundamentals, Simulations And Advanced Topics, 2nd Ed"
- Doug Lea, "Concurrent Programming in Java: Design Principles and Patterns"
- Maurice Herlihy and Nir Shavit, "The Art of Multiprocessor Programming"
- Mattson, Sanders, and Massingil "Patterns for Parallel Programming"
बाहरी संबंध
- Multithreaded data structures for parallel computing, Part 1 (Designing concurrent data structures) by Arpan Sen
- Multithreaded data structures for parallel computing: Part 2 (Designing concurrent data structures without mutexes) by Arpan Sen
- libcds – C++ library of lock-free containers and safe memory reclamation schema
- Synchrobench – C/C++ and Java libraries and benchmarks of lock-free, lock-based, TM-based and RCU/COW-based data structures.
