टेस्ट-एंड-सेट
कंप्यूटर विज्ञान में, टेस्ट-एंड-सेट निर्देश एक मेमोरी लोकेशन पर 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] वे जो अभी भी पठन-संशोधित-लेखन या तुलना-और-स्वैप निर्देश का उपयोग करके परमाणु टेस्ट-एंड-सेट लागू नहीं कर सकते हैं।
टेस्ट-एंड-सेट निर्देश, जब बूलियन मानों के साथ प्रयोग किया जाता है, तो निम्न फ़ंक्शन में दिखाए गए तर्क का उपयोग करें, सिवाय इसके कि फ़ंक्शन को परमाणु रूप से निष्पादित किया जाना चाहिए। यही है, कोई अन्य प्रक्रिया फ़ंक्शन के मध्य-निष्पादन को बाधित करने में सक्षम नहीं होनी चाहिए, जिससे एक ऐसी स्थिति दिखाई दे जो केवल फ़ंक्शन निष्पादित होने पर मौजूद हो। इसके लिए हार्डवेयर समर्थन की आवश्यकता है; इसे जैसा दिखाया गया है वैसा लागू नहीं किया जा सकता। फिर भी, दिखाया गया कोड टेस्ट-एंड-सेट के व्यवहार की व्याख्या करने में मदद करता है। नोट: इस उदाहरण में, 'लॉक' को संदर्भ (या नाम से) द्वारा पारित किया जाना माना जाता है, लेकिन 'प्रारंभिक' के लिए असाइनमेंट एक नया मान बनाता है (न केवल एक संदर्भ की प्रतिलिपि)।
function TestAndSet(boolean_ref lock) {
boolean initial = lock;
lock = true;
return initial;
}
टेस्ट-एंड-सेट निर्देश के अर्थ में न केवल कोड को परमाणु नहीं दिखाया गया है, बल्कि यह डीपीआरएएम हार्डवेयर टेस्ट-एंड-सेट के ऊपर दिए गए विवरण से भी अलग है। यहां, मान सेट है और परीक्षण निश्चित और अपरिवर्तनीय है और परीक्षण के परिणाम की परवाह किए बिना मूल्य को अपडेट किया जाता है, जबकि डीपीआरएएम टेस्ट-एंड-सेट के लिए, मेमोरी तभी सेट की जाती है जब परीक्षण सफल होता है, और मूल्य सेट करने के लिए और परीक्षण की स्थिति सीपीयू द्वारा निर्दिष्ट की जाती है। यहां, सेट किया जाने वाला मान केवल 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= - ↑ 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
