समवर्ती डेटा संरचना
कंप्यूटर विज्ञान में, एक समवर्ती डेटा संरचना है a द्वारा एक्सेस के लिए डेटा को स्टोर करने और व्यवस्थित करने का विशेष तरीका कंप्यूटर पर एकाधिक कंप्यूटिंग थ्रेड (कंप्यूटर विज्ञान) (या प्रक्रिया (कंप्यूटिंग))।
ऐतिहासिक रूप से, ऐसी डेटा संरचनाओं का उपयोग यूनिप्रोसेसर पर किया जाता था ऑपरेटिंग सिस्टम वाली मशीनें जो एकाधिक का समर्थन करती हैं कंप्यूटिंग थ्रेड्स (या प्रक्रिया (कंप्यूटिंग))। शब्द संगामिति (कंप्यूटर विज्ञान) ने कब्जा कर लिया थ्रेड्स के संचालन की बहुसंकेतन /इंटरलीविंग ऑपरेटिंग सिस्टम द्वारा डेटा, भले ही प्रोसेसर कभी नहीं दो ऑपरेशन जारी किए जो डेटा को एक साथ एक्सेस करते थे।
आज मल्टीप्रोसेसर के रूप में कंप्यूटर आर्किटेक्चर प्रदान करता है समानांतर कंप्यूटिंग प्रमुख कंप्यूटिंग प्लेटफॉर्म बन जाती है (के माध्यम से बहु-कोर प्रोसेसर का प्रसार), यह शब्द आ गया है मुख्य रूप से डेटा संरचनाओं के लिए खड़े होते हैं जिन्हें एकाधिक द्वारा एक्सेस किया जा सकता है थ्रेड्स जो वास्तव में डेटा को एक साथ एक्सेस कर सकते हैं क्योंकि वे विभिन्न प्रोसेसरों पर चलते हैं जो एक दूसरे के साथ संवाद करते हैं। समवर्ती डेटा संरचना (कभी-कभी 'साझा डेटा संरचना भी कहा जाता है) को आमतौर पर एक अमूर्त भंडारण में रहने के लिए माना जाता है पर्यावरण जिसे साझा स्मृति वास्तुकला कहा जाता है, हालांकि यह मेमोरी हो सकती है शारीरिक रूप से या तो एक कसकर युग्मित या ए के रूप में लागू किया गया भंडारण मॉड्यूल का वितरित संग्रह।
मूल सिद्धांत
समवर्ती डेटा संरचनाएं, में उपयोग के लिए अभिप्रेत हैं समानांतर या वितरित कंप्यूटिंग वातावरण, से भिन्न होते हैं
अनुक्रमिक डेटा संरचनाएं, एक यूनी-प्रोसेसर पर उपयोग के लिए अभिप्रेत हैं
मशीन, कई मायनों में।[1] सबसे विशेष रूप से, एक अनुक्रमिक वातावरण में one डेटा संरचना के गुणों को निर्दिष्ट करता है और जाँचता है कि वे सुरक्षा गुण प्रदान करके सही ढंग से लागू किया जाता है। में एक समवर्ती वातावरण, विनिर्देश का भी वर्णन करना चाहिए जीवंतता गुण जो एक कार्यान्वयन प्रदान करना चाहिए। सुरक्षा गुण आमतौर पर कहते हैं कि कुछ बुरा कभी नहीं होता, जबकि सजीवता गुण बताते हैं कि कुछ न कुछ अच्छा होता रहता है। इन गुणों को व्यक्त किया जा सकता है, उदाहरण के लिए, रैखिक लौकिक तर्क का उपयोग करना।
लाइवनेस आवश्यकताओं के प्रकार डेटा संरचना को परिभाषित करते हैं। विधि (कंप्यूटर विज्ञान) कॉल अवरुद्ध करना (कंप्यूटिंग) या गैर-अवरुद्ध एल्गोरिदम | नॉन-ब्लॉकिंग हो सकती है। डेटा संरचनाएं नहीं हैं एक या दूसरे प्रकार तक सीमित, और संयोजनों की अनुमति दे सकते हैं जहां कुछ मेथड कॉल ब्लॉक हो रहे हैं और अन्य नॉन-ब्लॉकिंग हैं (उदाहरण जावा समवर्ती सॉफ्टवेयर में पाए जा सकते हैं पुस्तकालय)।
समवर्ती डेटा संरचनाओं के सुरक्षा गुणों को उनका कब्जा करना चाहिए व्यवहार ने विधियों के कई संभावित अंतःक्रियाओं को दिया अलग-अलग धागों से पुकारा जाता है। यह बिल्कुल है कैसे अमूर्त डेटा संरचनाओं को निर्दिष्ट करने के लिए सहज ज्ञान युक्त एक अनुक्रमिक सेटिंग में व्यवहार करें जिसमें कोई इंटरलीविंग नहीं है। इसलिए, एक के सुरक्षा गुणों पर बहस करने के लिए कई मुख्यधारा के दृष्टिकोण समवर्ती डेटा संरचना (जैसे क्रमबद्धता, रैखिकता, अनुक्रमिक स्थिरता, और शांत संगति[1] संरचना गुण निर्दिष्ट करें क्रमिक रूप से, और इसके समवर्ती निष्पादन को मैप करें अनुक्रमिक का संग्रह।
सुरक्षा और जीवंतता गुणों की गारंटी देने के लिए, समवर्ती डेटा संरचनाओं को आमतौर पर (हालांकि हमेशा नहीं) थ्रेड्स को अनुमति देनी चाहिए परिणामों के अनुसार आम सहमति (कंप्यूटर विज्ञान) तक पहुँचें उनके एक साथ डेटा एक्सेस और संशोधन अनुरोध। को ऐसे समझौते का समर्थन करते हैं, समवर्ती डेटा संरचनाएं लागू की जाती हैं विशेष आदिम तुल्यकालन संचालन का उपयोग करना (देखें तुल्यकालन (कंप्यूटर विज्ञान)#Process_synchronization) आधुनिक बहु पर उपलब्ध है जो कई धागों को आम सहमति तक पहुंचने की अनुमति देता है। स्पिनलॉक का उपयोग करके या बिना ताले के अवरुद्ध तरीके से यह आम सहमति प्राप्त की जा सकती है, जिस स्थिति में यह गैर-अवरुद्ध एल्गोरिथम है। गैर-अवरुद्ध। चौड़ा शरीर होता है समवर्ती डेटा संरचनाओं के डिजाइन पर सिद्धांत (देखें ग्रंथसूची संबंधी संदर्भ)।
डिजाइन और कार्यान्वयन
समवर्ती डेटा संरचनाओं को डिजाइन करना काफी कठिन है और उनके अनुक्रमिक समकक्षों की तुलना में सही होने के रूप में सत्यापित करने के लिए।
इस अतिरिक्त कठिनाई का प्राथमिक स्रोत संगामिति है, इस तथ्य से बढ़ा है कि धागे को पूरी तरह से अतुल्यकालिक माना जाना चाहिए: वे ऑपरेटिंग सिस्टम प्रीमेशन, पृष्ठ दोषों के अधीन हैं, बाधित करता है, और इसी तरह।
आज की मशीनों पर, प्रोसेसर का लेआउट और मेमोरी, मेमोरी में डेटा का लेआउट, पर संचार भार मल्टीप्रोसेसर आर्किटेक्चर के विभिन्न तत्व प्रदर्शन को प्रभावित करते हैं। इसके अलावा, शुद्धता और प्रदर्शन के बीच एक तनाव है: एल्गोरिथम संवर्द्धन जो प्रदर्शन में सुधार करना चाहते हैं, अक्सर इसे डिजाइन करना और सही सत्यापित करना अधिक कठिन बना देता है डेटा संरचना कार्यान्वयन।[2] प्रदर्शन के लिए एक महत्वपूर्ण माप मापनीयता है, जिसे कार्यान्वयन की गति से प्राप्त किया जाता है। गति बढ़ाना कैसे का एक उपाय है प्रभावी रूप से एप्लिकेशन उस मशीन का उपयोग कर रहा है जो वह चला रहा है पर। पी प्रोसेसर वाली मशीन पर, स्पीडअप एक प्रोसेसर पर संरचना निष्पादन समय का पी प्रोसेसर पर इसके निष्पादन समय का अनुपात है। आदर्श रूप से, हम रैखिक गति चाहते हैं: हम एक हासिल करना चाहेंगे P प्रोसेसर का उपयोग करते समय P का स्पीडअप। डेटा संरचनाएं जिनकी स्पीडअप P के साथ बढ़ता है जिसे स्केलेबल कहा जाता है। एक समवर्ती डेटा संरचना के प्रदर्शन को किस हद तक बढ़ाया जा सकता है, इसे Amdahl's law के रूप में ज्ञात सूत्र द्वारा कैप्चर किया जाता है और इसके अधिक परिष्कृत संस्करण जैसे कि गुस्ताफ़सन का नियम।
समवर्ती डेटा संरचनाओं के प्रदर्शन के साथ एक महत्वपूर्ण मुद्दा स्मृति विवाद का स्तर है: यातायात में और स्मृति से एक के रूप में ओवरहेड कई थ्रेड्स का एक साथ उपयोग करने का प्रयास करने का परिणाम स्मृति में स्थान। कार्यान्वयन को अवरुद्ध करने के साथ यह समस्या सबसे गंभीर है जिसमें लॉक मेमोरी के एक्सेस को नियंत्रित करता है। के लिए लॉक प्राप्त करने के बाद, थ्रेड को बार-बार इसे संशोधित करने का प्रयास करना चाहिए जगह। कैश सुसंगतता पर|कैश-सुसंगत मल्टीप्रोसेसर (एक जिसमें प्रोसेसर होते हैं स्थानीय कैश जो उन्हें रखने के लिए हार्डवेयर द्वारा अपडेट किए जाते हैं संग्रहीत नवीनतम मूल्यों के अनुरूप) इसका परिणाम लंबे समय तक होता है स्थान को संशोधित करने के प्रत्येक प्रयास के लिए प्रतीक्षा समय, और है से जुड़े अतिरिक्त मेमोरी ट्रैफ़िक द्वारा बढ़ा दिया गया लॉक प्राप्त करने के असफल प्रयास।
यह भी देखें
- जावा संगामिति (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.
