सॉफ़्टवेयर ट्रांसेक्शनल मेमोरी

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

प्रदर्शन

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

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

हालाँकि, व्यवहार में, एसटीएम सिस्टम को कम संख्या में प्रोसेसर (एप्लिकेशन के आधार पर 1 से 4) पर फाइन-ग्रेन्ड लॉक-आधारित सिस्टम की तुलना में प्रदर्शन में गिरावट का सामना करना पड़ता है। यह मुख्य रूप से लॉग को बनाए रखने से जुड़े ओवरहेड और लेनदेन करने में लगने वाले समय के कारण है। इस मामले में भी प्रदर्शन आम तौर पर दोगुने धीमे से अधिक खराब नहीं होता है। एसटीएम के अधिवक्ताओं का मानना ​​है कि यह जुर्माना एसटीएम के वैचारिक लाभों के कारण उचित है.

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

वैचारिक फायदे और नुकसान

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

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

इसके विपरीत, मेमोरी लेनदेन की अवधारणा बहुत सरल है, क्योंकि प्रत्येक लेनदेन को एकल-थ्रेडेड गणना के रूप में अलग से देखा जा सकता है। डेडलॉक और लाइवलॉक को या तो पूरी तरह से रोका जाता है या किसी बाहरी लेनदेन प्रबंधक द्वारा नियंत्रित किया जाता है; प्रोग्रामर को इसके बारे में चिंता करने की कोई आवश्यकता नहीं है। प्राथमिकता व्युत्क्रमण अभी भी एक मुद्दा हो सकता है, लेकिन उच्च-प्राथमिकता वाले लेनदेन उन परस्पर विरोधी निम्न प्राथमिकता वाले लेनदेन को निरस्त कर सकते हैं जो पहले से ही प्रतिबद्ध नहीं हैं।

दूसरी ओर, विफल लेनदेन को निरस्त करने की आवश्यकता भी लेनदेन के व्यवहार पर सीमाएं लगाती है: वे कोई भी ऐसा ऑपरेशन नहीं कर सकते हैं जिसे पूर्ववत नहीं किया जा सकता है, जिसमें अधिकांश I/O भी शामिल हैं। व्यवहार में ऐसी सीमाओं को आम तौर पर बफ़र्स बनाकर दूर किया जाता है जो अपरिवर्तनीय परिचालनों को कतारबद्ध करते हैं और उन्हें किसी भी लेनदेन के बाहर बाद में निष्पादित करते हैं। हास्केल (प्रोग्रामिंग भाषा) में, इस सीमा को टाइप सिस्टम द्वारा संकलन समय पर लागू किया जाता है।

कंपोज़ेबल ऑपरेशंस

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

<ब्लॉककोट> शायद सबसे मौलिक आपत्ति [...] यह है कि लॉक-आधारित प्रोग्राम रचना नहीं करते हैं: संयुक्त होने पर सही टुकड़े विफल हो सकते हैं। उदाहरण के लिए, थ्रेड-सुरक्षित डालने और हटाने के संचालन वाली हैश तालिका पर विचार करें। अब मान लीजिए कि हम तालिका t1 से एक आइटम A को हटाना चाहते हैं, और इसे तालिका t2 में सम्मिलित करना चाहते हैं; लेकिन मध्यवर्ती स्थिति (जिसमें किसी भी तालिका में आइटम शामिल नहीं है) अन्य थ्रेड्स को दिखाई नहीं देनी चाहिए। जब तक हैश तालिका का कार्यान्वयनकर्ता इस आवश्यकता का अनुमान नहीं लगाता, इस आवश्यकता को पूरा करने का कोई तरीका नहीं है। [...] संक्षेप में, जो ऑपरेशन व्यक्तिगत रूप से सही हैं (सम्मिलित करें, हटाएं) उन्हें बड़े सही ऑपरेशन में शामिल नहीं किया जा सकता है।
-टिम हैरिस एट अल., कंपोजेबल मेमोरी ट्रांजेक्शन्स, खंड 2: पृष्ठभूमि, पृष्ठ 2 </ब्लॉककोट>

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

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

यह योजना ग्लासगो हास्केल कंपाइलर में लागू की गई है।

प्रस्तावित भाषा समर्थन

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

// परमाणु रूप से दोगुनी लिंक की गई सूची में एक नोड डालें
 'परमाणु' {
     newNode->पिछला = नोड;
     newNode->अगला = नोड->अगला;
     नोड->अगला->पिछला = नयानोड;
     नोड->अगला = नयानोड;
 }

जब ब्लॉक का अंत हो जाता है, तो यदि संभव हो तो लेनदेन प्रतिबद्ध होता है, अन्यथा निरस्त कर दिया जाता है और पुनः प्रयास किया जाता है। (यह केवल एक वैचारिक उदाहरण है, सही कोड नहीं है। उदाहरण के लिए, यदि लेनदेन के दौरान सूची से नोड हटा दिया जाता है तो यह गलत व्यवहार करता है।)

सीसीआर एक गार्ड शर्त की भी अनुमति देता है, जो लेनदेन को तब तक इंतजार करने में सक्षम बनाता है जब तक कि उसे काम न करना पड़े:

 'परमाणु' (कतार आकार > 0) {
     आइटम को कतार से हटाएँ और उसका उपयोग करें
 }

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

 परमाणु {
     यदि (कतार आकार > 0) {
         आइटम को कतार से हटाएँ और उसका उपयोग करें
     } अन्य {
         पुन: प्रयास
     }
 }

लेन-देन में देर से गतिशील रूप से पुनः प्रयास करने की यह क्षमता प्रोग्रामिंग मॉडल को सरल बनाती है और नई संभावनाओं को खोलती है।

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

ट्रांजेक्शनल लॉकिंग

एसटीएम को लॉक-फ्री एल्गोरिदम के रूप में कार्यान्वित किया जा सकता है या यह लॉकिंग का उपयोग कर सकता है। लॉकिंग योजनाएं दो प्रकार की होती हैं: एनकाउंटर-टाइम लॉकिंग (एननल्स, साहा और हैरिस) में, मेमोरी राइटिंग पहले किसी दिए गए स्थान के लिए अस्थायी रूप से लॉक प्राप्त करके, सीधे मूल्य लिखकर और इसे पूर्ववत लॉग में लॉग करके किया जाता है। कमिट-टाइम लॉकिंग केवल कमिट चरण के दौरान मेमोरी स्थानों को लॉक करता है।

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

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

सीओ के साथ वांछित क्रमबद्धता संपत्ति केवल कालानुक्रमिक क्रम में लेनदेन करके प्राप्त की जाती है जो संबंधित लेनदेन के पूर्ववर्ती क्रम (संघर्षों में संचालन के कालानुक्रमिक आदेशों द्वारा निर्धारित) के साथ संगत है। सीओ को लागू करने के लिए प्रतिबद्धता आदेश के कुछ कार्यान्वयन#एक सामान्य स्थानीय सीओ एल्गोरिदम का उपयोग करने की आवश्यकता है। ऊपर उद्धृत पेटेंट सार पूर्व-निर्धारित प्रतिबद्ध आदेश के साथ एल्गोरिदम के सामान्य कार्यान्वयन का वर्णन करता है (यह वास्तविक समय की बाधाओं के साथ सीओ जेनेरिक एल्गोरिदम की श्रेणी में आता है)।

कार्यान्वयन मुद्दे

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

atomic { if (x != y) while (true) { } } atomic { x++; y++; } Transaction A Transaction B

बशर्ते x=y प्रारंभ में, उपरोक्त कोई भी लेन-देन इस अपरिवर्तनीय को नहीं बदलता है, लेकिन यह संभव है कि लेन-देन A, लेन-देन B द्वारा इसे अद्यतन करने के बाद x को पढ़ेगा, लेकिन लेन-देन B द्वारा इसे अद्यतन करने से पहले y को पढ़ेगा, जिससे यह एक अनंत लूप में प्रवेश करेगा। इससे निपटने की सामान्य रणनीति किसी भी घातक अपवाद को रोकना और किसी भी ऐसे लेनदेन को निरस्त करना है जो वैध नहीं है।

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

व्यावहारिक कार्यान्वयन

• हास्केल जीएचसी
• C++ cpp_stm_free
• क्लोजर रेफरी, नोड-एसटीएम पर पोर्ट किया गया
• जाओ_(प्रोग्रामिंग_भाषा) कश्मीर
• Rust_(प्रोग्रामिंग_भाषा) async-stm
• स्कैला_(प्रोग्रामिंग_भाषा) ZIO
• OCaml_(प्रोग्रामिंग_भाषा) kcas