टेस्ट-एंड-सेट

From Vigyanwiki
Revision as of 18:09, 31 May 2023 by alpha>Sweta (→‎रूपांतर 2)

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

एक परमाणु परीक्षण और टेस्ट-एंड-सेट का उपयोग करके एक लॉक बनाया जा सकता है:[1]

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

मौरिस हर्लिही (1991) ने साबित किया कि टेस्ट-एंड-सेट (1-बिट तुलना) में एक सीमित आम सहमति संख्या होती है और अधिकतम दो समवर्ती प्रक्रियाओं के लिए प्रतीक्षा-मुक्त आम सहमति की समस्या को हल कर सकता है।[2] इसके विपरीत, तुलना-और-स्वैप (32-बिट तुलना) इस समस्या का अधिक सामान्य समाधान प्रदान करता है, और कुछ कार्यान्वयनों में, तुलना-दोहरा-और-स्वैप (64-बिट तुलना) विस्तारित उपयोगिता के लिए भी उपलब्ध है।

टेस्ट-एंड-सेट का हार्डवेयर कार्यान्वयन

डीपीआरएएम टेस्ट-एंड-सेट निर्देश कई तरीकों से काम कर सकते हैं। यहां दो भिन्नताएं हैं, जिनमें से दोनों डीपीआरएएम का वर्णन करती हैं जो वास्तव में 2 पोर्ट प्रदान करती हैं, जिससे 2 अलग-अलग इलेक्ट्रॉनिक घटकों (जैसे 2 सीपीयू) को डीपीआरएएम पर प्रत्येक मेमोरी लोकेशन तक पहुंच मिलती है।

रूपांतर 1

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

सीपीयू 2 स्मृति लोकेशन तक पहुँचने का प्रयास कर रहा था या नहीं, डीपीआरएएम सीपीयू 1 द्वारा दिए गए परीक्षण को करता है। यदि परीक्षण सफल होता है, तो डीपीआरएएम स्मृति लोकेशन को सीपीयू 1 द्वारा दिए गए मान पर सेट करता है। फिर डीपीआरएएम अपने "आंतरिक नोट" को मिटा देता है जो कि सीपीयू 1 वहां लिख रहा था। इस बिंदु पर, सीपीयू 2 एक टेस्ट-एंड-सेट जारी कर सकता है, जो सफल होगा।

रूपांतर 2

सीपीयू 1 "मेमोरी लोकेशन A" में लिखने के लिए एक टेस्ट-एंड-सेट निर्देश जारी करता है। डीपीआरएएम तुरंत स्मृति लोकेशन A में मूल्य को संग्रहीत नहीं करता है, बल्कि स्मृति लोकेशन A की सामग्री को एक विशेष "फ्लैग वैल्यू" पर सेट करते समय वर्तमान मान को एक विशेष रजिस्टर में ले जाता है। यदि इस बिंदु पर, CPU 2 स्मृति लोकेशन A पर एक परीक्षण-और-सेट जारी करता है, डीपीआरएएम विशेष फ्लैग वैल्यू का पता लगाता है, और जैसा कि भिन्नता 1 में है, एक व्यस्त व्यवधान जारी करता है।

चाहे सीपीयू 2 मेमोरी लोकेशन तक पहुँचने का प्रयास कर रहा था या नहीं, डीपीआरएएम अब सीपीयू 1 का परीक्षण करता है। यदि परीक्षण सफल हो जाता है, तो डीपीआरएएम मेमोरी लोकेशन A को सीपीयू 1 द्वारा निर्दिष्ट मान पर सेट करता है। यदि परीक्षण विफल हो जाता है, तो डीपीआरएएम मूल्य को विशेष रजिस्टर से मेमोरी लोकेशन A में वापस कॉपी करता है। कोई भी ऑपरेशन विशेष फ़्लैग मान मिटा देता है। यदि सीपीयू 2 अब एक टेस्ट-एंड-सेट जारी करता है, तो यह सफल होगा।


== टेस्ट-एंड-सेट == का सॉफ्टवेयर कार्यान्वयन

कुछ निर्देश सेटों में एक परमाणु परीक्षण और सेट मशीन भाषा निर्देश होता है। उदाहरणों में x86 शामिल हैं[3] और आईबीएम सिस्टम/360 और इसके उत्तराधिकारी (जेड/आर्किटेक्चर सहित)।[4] जो अभी भी एक पठन-संशोधित-लेखन या तुलना-और-स्वैप निर्देश का उपयोग करके एक परमाणु परीक्षण-और-सेट को लागू नहीं कर सकते हैं।

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

फ़ंक्शन टेस्ट एंडसेट (बूलियन_रेफ लॉक) {
    बूलियन इनिशियल = लॉक;
    ताला = सच;
    प्रारंभिक वापसी;
}

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

सी (प्रोग्रामिंग भाषा) में, कार्यान्वयन इस प्रकार होगा: 

#define LOCKED 1

int test_and_set(int* lockPtr) {
    int oldValue;

    // -- Start of atomic segment --
    // This should be interpreted as pseudocode for illustrative purposes only.
    // Traditional compilation of this code will not guarantee atomicity, the
    // use of shared memory (i.e., non-cached values), protection from compiler
    // optimizations, or other required properties.
    oldValue = *lockPtr;
    *lockPtr = LOCKED;
    // -- End of atomic segment --

    return oldValue;
}

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

== टेस्ट-एंड-सेट == का उपयोग करके पारस्परिक बहिष्करण आपसी बहिष्करण को लागू करने का एक तरीका टेस्ट-एंड-सेट आधारित लॉक का उपयोग करना है[5][6] निम्नलिखित नुसार:

=== एक स्पिन लॉक === का छद्म-सी कार्यान्वयन 

volatile int lock = 0;

void critical() {
    // Spin lock: loop forever until we get the lock; we know the lock was
    // successfully obtained after exiting this while loop because the 
    // test_and_set() function locks the lock and returns the previous lock 
    // value. If the previous lock value was 1 then the lock was **already**
    // locked by another thread or process. Once the previous lock value
    // was 0, however, then it indicates the lock was **not** locked before we
    // locked it, but now it **is** locked because we locked it, indicating
    // we own the lock.
    while (test_and_set(&lock) == 1);  
    critical section  // only one process can be in this section at a time
    lock = 0;  // release lock when finished with the critical section
}

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

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

विधानसभा कार्यान्वयन

enter_region:        ; A "jump to" tag; function entry point.

  tsl reg, flag      ; Test and Set Lock; flag is the
                     ; shared variable; it is copied
                     ; into the register reg and flag
                     ; then atomically set to 1.

  cmp reg, #0        ; Was flag zero on entry_region?

  jnz enter_region   ; Jump to enter_region if
                     ; reg is non-zero; i.e.,
                     ; flag was non-zero on entry.

  ret                ; Exit; i.e., flag was zero on
                     ; entry. If we get here, tsl
                     ; will have set it non-zero; thus,
                     ; we have claimed the resource
                     ; associated with flag.

leave_region:
  move flag, #0      ; store 0 in flag
  ret                ; return to caller

यहाँ tsl एक परमाणु निर्देश है और flag ताला चर है। यह प्रक्रिया तब तक वापस नहीं आती जब तक कि यह लॉक प्राप्त नहीं कर लेती।

== टेस्ट-एंड-सेट लॉक्स == का प्रदर्शन मूल्यांकन

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

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

जब हम निष्पक्षता पर विचार करते हैं, तो हम विचार करते हैं कि क्या एक प्रोसेसर को लॉक प्राप्त करने का उचित मौका मिलता है जब वह मुक्त हो जाता है। एक चरम स्थिति में प्रोसेसर भूखा हो सकता है यानी यह उस समय के दौरान मुक्त होने के बावजूद विस्तारित अवधि के लिए लॉक प्राप्त करने में सक्षम नहीं हो सकता है।

TSL के लिए स्टोरेज ओवरहेड कुछ भी नहीं है क्योंकि केवल एक लॉक की आवश्यकता होती है। केवल एक परमाणु निर्देश और शाखा की आवश्यकता के बाद से अनियंत्रित विलंबता भी कम है।

यह भी देखें

  • लायें और जोड़ें
  • टेस्ट और टेस्ट-एंड-सेट
  • लोड-लिंक/स्टोर-सशर्त
  • तुलना करें और स्वैप करें

संदर्भ

  1. ↑ Anderson, T. E. (1990-01-01). "शेयर्ड-मनी मल्टीप्रोसेसरों के लिए स्पिन लॉक विकल्पों का प्रदर्शन". IEEE Transactions on Parallel and Distributed Systems. 1 (1): 6–16. doi:10.1109/71.80120. ISSN 1045-9219.
  2. ↑ Herlihy, Maurice (January 1991). "प्रतीक्षा-मुक्त तुल्यकालन" (PDF). ACM Trans. Program. Lang. Syst. 13 (1): 124–149. CiteSeerX 10.1.1.56.5659. doi:10.1145/114005.102808. S2CID 2181446. Retrieved 2007-05-20.
  3. ↑ "BTS—Bit Test and Set". www.felixcloutier.com. Retrieved 2016-11-21.
  4. ↑ "आईबीएम ज्ञान केंद्र". www.ibm.com. Retrieved 2016-11-21.
  5. ↑ Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau (2015). Operating Systems: Three Easy Pieces (0.91 ed.). Arpaci-Dusseau Books – via http://www.ostep.org/. {{cite book}}: External link in |via= (help)
  6. ↑ Solihin, Yan (2009). Fundamentals of parallel computer architecture : multichip and multicore systems. p. 252. ISBN 9780984163007.
  7. ↑ Solihin, Yan (2016). समानांतर वास्तुकला के मूल तत्व. Boca Raton, FL: CRC Press. ISBN 978-1-4822-1118-4.


बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=टेस्ट-एंड-सेट&oldid=185079’