परीक्षण और सेट

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

एक परमाणु परीक्षण और सेट का उपयोग करके एक लॉक (कंप्यूटर विज्ञान) बनाया जा सकता है^[1] निर्देश इस प्रकार है:

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

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

परीक्षण और सेट का हार्डवेयर कार्यान्वयन

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

भिन्नता 1

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

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

भिन्नता 2

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

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

परीक्षण और सेट का सॉफ्टवेयर कार्यान्वयन

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

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

फ़ंक्शन TestAndSet(boolean_ref लॉक) {
    बूलियन प्रारंभिक = लॉक;
    ताला = सत्य;
    आरंभिक वापसी;
}

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

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

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

यह भी देखें

प्राप्त करें और जोड़ें
परीक्षण और परीक्षण-और-सेट
लोड-लिंक/स्टोर-सशर्त
तुलना करें और बदलें

संदर्भ

↑ 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.
↑ 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.
↑ "BTS—Bit Test and Set". www.felixcloutier.com. Retrieved 2016-11-21.
↑ "आईबीएम नॉलेज सेंटर". www.ibm.com. Retrieved 2016-11-21.
↑ 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)
↑ Solihin, Yan (2009). Fundamentals of parallel computer architecture : multichip and multicore systems. p. 252. ISBN 9780984163007.
↑ Solihin, Yan (2016). समानांतर वास्तुकला के मूल सिद्धांत. Boca Raton, FL: CRC Press. ISBN 978-1-4822-1118-4.

बाहरी संबंध

Description from Encyclopaedia of Delay-Insensitive Systems
"Wait-free Test-and-Set" by Yehuda Afek
int testandset(int *lock) - C-callable routine written in Sun SPARC assembly language
Intel Developer Manual

[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.

[Solihin-7] Solihin, Yan (2016). समानांतर वास्तुकला के मूल सिद्धांत. Boca Raton, FL: CRC Press. ISBN 978-1-4822-1118-4.

[1]

[2]

[3]

[4]

[5]

[6]

[7]