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

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

प्रदर्शन

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

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

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

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

वैचारिक लाभ और हानि

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

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

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

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

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

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

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

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

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

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

प्रपोसड लैंग्वेज सपोर्ट

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

// Insert a node into a doubly linked list atomically

atomic {

newNode->prev = node;

newNode->next = node->next;

node->next->prev = newNode;

node->next = newNode;

}                                       

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

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

 atomic (queueSize > 0) {
     remove item from queue and use it
 }  

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

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

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

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

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

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

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

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

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

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

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

atomic { if (x != y) while (true) { } } atomic { x++; y++; } ट्रांसैक्शन A ट्रांसैक्शन B

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

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

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

• हास्केल जीएचसी
• सी++ सीपीपी_एसटीएम_फ्री
• क्लोजर रेफरी, नोड-एसटीएम पर पोर्ट किया गया
• जाओ_(प्रोग्रामिंग_भाषा) कश्मीर
• रस्ट_(प्रोग्रामिंग_भाषा) एसिंक-एसटीएम
• स्कैला_(प्रोग्रामिंग_भाषा) जेडआईओ
• ओसीएएमएल_(प्रोग्रामिंग_भाषा) केसीएएस