टेस्ट-एंड-सेट
कंप्यूटर विज्ञान में, टेस्ट-एंड-सेट निर्देश सेट वास्तुकला एक स्मृति स्थान पर 1 लिखने (सेट) करने के लिए उपयोग किया जाने वाला निर्देश है और इसके पुराने मान को एकल परमाणु (कंप्यूटर विज्ञान) (यानी, गैर-व्यवधान) ऑपरेशन के रूप में लौटाता है। कॉल करने वाला तब परिणाम का परीक्षण कर सकता है यह देखने के लिए कि क्या कॉल द्वारा राज्य को बदल दिया गया था। यदि एकाधिक प्रक्रियाएं एक ही मेमोरी स्थान तक पहुंच सकती हैं, और यदि कोई प्रक्रिया वर्तमान में टेस्ट-एंड-सेट कर रही है, तो पहली प्रक्रिया के टेस्ट-एंड-सेट समाप्त होने तक कोई अन्य प्रक्रिया एक और टेस्ट-एंड-सेट शुरू नहीं कर सकती है। एक सेंट्रल प्रोसेसिंग यूनिट (सीपीयू) एक अन्य इलेक्ट्रॉनिक घटक, जैसे डीपीआरएएम | डुअल-पोर्ट रैम द्वारा दिए गए टेस्ट-एंड-सेट निर्देश का उपयोग कर सकता है; एक सीपीयू स्वयं एक टेस्ट-एंड-सेट निर्देश भी दे सकता है।
एक परमाणु परीक्षण और सेट का उपयोग करके एक ताला (कंप्यूटर विज्ञान) बनाया जा सकता है[1] निर्देश इस प्रकार है:
यह कोड मानता है कि पहले टेस्ट-एंड-सेट से पहले किसी बिंदु पर स्मृति स्थान को 0 पर प्रारंभ किया गया था। कॉलिंग प्रक्रिया लॉक प्राप्त करती है यदि पुराना मान 0 था, अन्यथा लूप लॉक प्राप्त करने की प्रतीक्षा कर रहा है। इसे spinlock कहा जाता है। किसी भी बिंदु पर, लॉक का धारक किसी अन्य द्वारा अधिग्रहण के लिए लॉक को रिलीज़ करने के लिए मेमोरी लोकेशन को वापस 0 पर सेट कर सकता है - इसके लिए किसी विशेष हैंडलिंग की आवश्यकता नहीं होती है क्योंकि धारक इस मेमोरी लोकेशन का मालिक होता है। टेस्ट और टेस्ट-एंड-सेट एक और उदाहरण है।
मौरिस हर्लिही (1991) ने साबित किया कि टेस्ट-एंड-सेट (1-बिट तुलना) में एक परिमित सहमति (कंप्यूटर विज्ञान) है और अधिकतम दो समवर्ती प्रक्रियाओं के लिए प्रतीक्षा-मुक्त सहमति (कंप्यूटर विज्ञान) को हल कर सकता है।[2] इसके विपरीत, तुलना-और-स्वैप (32-बिट तुलना) इस समस्या का अधिक सामान्य समाधान प्रदान करता है, और कुछ कार्यान्वयनों में विस्तारित उपयोगिता के लिए तुलना-दोहरा-और-स्वैप (64-बिट तुलना) भी उपलब्ध है।
== टेस्ट-एंड-सेट == का हार्डवेयर कार्यान्वयन DPRAM टेस्ट-एंड-सेट निर्देश कई तरह से काम कर सकते हैं। यहां दो भिन्नताएं हैं, जिनमें से दोनों डीपीआरएएम का वर्णन करती हैं जो वास्तव में 2 पोर्ट प्रदान करती हैं, जिससे 2 अलग-अलग इलेक्ट्रॉनिक घटकों (जैसे 2 सीपीयू) को डीपीआरएएम पर प्रत्येक मेमोरी स्थान तक पहुंच की अनुमति मिलती है।
रूपांतर 1
जब CPU 1 एक टेस्ट-एंड-सेट निर्देश जारी करता है, तो DPRAM पहले एक विशेष स्थान पर स्मृति स्थान के पते को संग्रहीत करके इसका एक आंतरिक नोट बनाता है। यदि इस बिंदु पर, CPU 2 उसी स्मृति स्थान के लिए एक परीक्षण-और-सेट निर्देश जारी करता है, तो DPRAM पहले अपने आंतरिक नोट की जांच करता है, स्थिति को पहचानता है, और एक व्यस्त व्यवधान जारी करता है, जो CPU 2 को बताता है कि उसे प्रतीक्षा करनी होगी और पुन: प्रयास करें। यह इंटरप्ट मैकेनिज्म का उपयोग करके व्यस्त प्रतीक्षा या स्पिनलॉक का कार्यान्वयन है। चूंकि यह सब हार्डवेयर की गति पर होता है, स्पिन-लॉक से बाहर निकलने के लिए CPU 2 का इंतजार बहुत कम है।
CPU 2 स्मृति स्थान तक पहुँचने का प्रयास कर रहा था या नहीं, DPRAM CPU 1 द्वारा दिया गया परीक्षण करता है। यदि परीक्षण सफल होता है, तो DPRAM स्मृति स्थान को CPU 1 द्वारा दिए गए मान पर सेट करता है। फिर DPRAM अपने आंतरिक नोट को मिटा देता है। वह सीपीयू 1 वहां लिख रहा था। इस बिंदु पर, CPU 2 एक टेस्ट-एंड-सेट जारी कर सकता है, जो सफल होगा।
रूपांतर 2
CPU 1 स्मृति स्थान A पर लिखने के लिए परीक्षण-और-सेट निर्देश जारी करता है। डीपीआरएएम स्मृति स्थान ए में मूल्य को तुरंत संग्रहीत नहीं करता है, बल्कि स्मृति स्थान ए की सामग्री को विशेष ध्वज मान पर सेट करते समय वर्तमान मूल्य को एक विशेष रजिस्टर में ले जाता है। यदि इस बिंदु पर, CPU 2 स्मृति स्थान A पर एक परीक्षण-और-सेट जारी करता है, DPRAM विशेष ध्वज मान का पता लगाता है, और भिन्नता 1 के रूप में, एक व्यस्त व्यवधान जारी करता है।
CPU 2 स्मृति स्थान तक पहुँचने का प्रयास कर रहा था या नहीं, DPRAM अब CPU 1 का परीक्षण करता है। यदि परीक्षण सफल होता है, तो DPRAM स्मृति स्थान A को CPU 1 द्वारा निर्दिष्ट मान पर सेट करता है। यदि परीक्षण विफल हो जाता है, तो DPRAM मान को विशेष रजिस्टर से वापस स्मृति स्थान A में कॉपी कर देता है। या तो ऑपरेशन विशेष ध्वज मान को मिटा देता है। यदि CPU 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 के लिए स्टोरेज ओवरहेड कुछ भी नहीं है क्योंकि केवल एक लॉक की आवश्यकता होती है। केवल एक परमाणु निर्देश और शाखा की आवश्यकता के बाद से अनियंत्रित विलंबता भी कम है।
यह भी देखें
- लायें और जोड़ें
- टेस्ट और टेस्ट-एंड-सेट
- लोड-लिंक/स्टोर-सशर्त
- तुलना करें और स्वैप करें
संदर्भ
- ↑ 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= - ↑ 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
