म्युचुअल-बहिष्कार TestAndSet का उपयोग कर() अनुदेश

Question

पुस्तक Silberschatz द्वारा ऑपरेटिंग सिस्टम सिद्धांतों, Galvin और गैग्ने अध्याय में TestAndSet() अनुदेश तुल्यकालन पर के लिए निम्नलिखित परिभाषा में शामिल है

do { 
    while(TestAndSetLock(&lock)) 
     ; // do nothing 
     // critical section 
    lock = FALSE; 
     // remainder section 
} while(TRUE); 

अब, पारस्परिक अपवर्जन हासिल की है अगर वहाँ सही पर लक्ष्य स्थापित करने के लिए कोई शर्त है: ऊपर दिए गए निर्देश का उपयोग कर बहिष्कार भी इस प्रकार प्रदान की जाती है?

निम्न स्थिति पर विचार करें, प्रक्रिया P0 साझा चर लॉक को TRUE पर सेट करता है और इसके महत्वपूर्ण खंड में प्रवेश करता है। एक अन्य प्रक्रिया P1 ऊपर दिए गए लूप में TestAndSet() को कॉल करती है, यह TRUE लौटाती है (चूंकि पी 0 में लॉक है) जबकि बिना शर्त रूप से लॉक को FALSE पर सेट किया गया है। दूसरी बार टेस्ट एंडसेट() को लूप में बुलाया जाता है, यह वापस लौटाएगा और पी 1 इसके महत्वपूर्ण खंड में प्रवेश करेगा, भले ही पी 0 अपने महत्वपूर्ण खंड में है। फिर म्यूचुअल-बहिष्करण का उल्लंघन किया जाता है।

मैं कुछ खोज किया था और उन्होंने ही आचार्य और रॉबर्ट (उत्तरी केरोलिना राज्य विश्वविद्यालय सीएस विभाग के) Funderlic जो TestAndSet() के निम्नलिखित वैकल्पिक परिभाषा शामिल द्वारा एक कागज पर ठोकर खाई:

boolean Test-and-Set(boolean target) 
    begin 
     if(target == false): 
      target = true; 
     return target; 
    end 

यह बहुत बनाता है मेरे लिए और अधिक समझ में, मैंने इसे तुलना के लिए भी शामिल किया और यह भी कि पेपर सिलबर्सचैट द्वारा पुस्तक को इसके संदर्भों में से एक के रूप में सूचीबद्ध करता है।

मुझे समझ में नहीं आता कि मेरी पाठ्य पुस्तक में जो परिभाषा मिली है (जिसे मैंने पहले प्रदान किया था) आपसी बहिष्कार को दूर करने के लिए उपयोग किया जा सकता है, क्या कोई मदद कर सकता है?

Answer 1

टेस्ट एंडसेट फ़ंक्शन जिसे आप प्रारंभ में उद्धरण देते हैं केवल तभी निष्पादित किया जाता है जब लक्ष्य गलत होता है। अर्थात। धागा अवरुद्ध है जब तक लक्ष्य गलत नहीं है। मेरे पास उस पाठ्य पुस्तक नहीं है, लेकिन मुझे यकीन है कि यह टेक्स्ट में कहीं भी उल्लेख किया गया है।

कृपया ध्यान दें कि टेस्ट एंडसेट एक "परमाणु" फ़ंक्शन है जिसे ओएस के निम्नतम स्तर (या यहां तक ​​कि सीपीयू के निर्देश सेट द्वारा भी लागू किया जाना चाहिए)। यदि यह किसी उपयोगकर्ता एप्लिकेशन में लागू किया गया है, तो परीक्षण और सेट के बीच एक संदर्भ स्विच हो सकता है, जिससे भ्रष्टाचार होता है।

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

Answer 2

testAndset विधि का उपयोग करने के लिए, हम एक चर, ताला कहा जाता है जो गलत पर सेट है के साथ शुरू:

HdwareData lock = new HdwareData(false); 

Answer 3

यहाँ एक तरह से परमाणु TestAndSet के बारे में सहज में सोचना है।

एक धागा एक महत्वपूर्ण क्षेत्र में प्रवेश करने से पहले इसका उपयोग करता है।केवल दो मामलों:

1. लॉक किया जा रहा है (* लक्ष्य सही है): सही लौट सकते हैं और * लक्ष्य सही रहता है
2. को लॉक नहीं किया जा रहा है: गलत लौटने के लिए, और * लक्ष्य सही पर सेट किया जाता है

तो कोई अन्य धागा महत्वपूर्ण क्षेत्र में है इसलिए * लक्ष्य (TRUE) दर्शाता है कि मूल्य क्या होना चाहिए; या "मैं" अब इस महत्वपूर्ण क्षेत्र में प्रवेश कर रहा हूं, इसलिए * सत्य पर लक्ष्य निर्धारित करें।

Answer 4

कार्यान्वयन से पता चला इस तरह अधिक स्पष्ट रूप से लिखा जा सकता है:

while(TestAndSet(&lock)) 
{ 
    // spin in this loop until TestAndSet returns false 
} 
do_critical_section_stuff(); 
lock = FALSE; 
// We've now left the critical section 

मुझे लगता है कि ओ पी के रूप में यह बदल गया था:

while(TestAndSet(&lock)) 
{ 
    lock = FALSE; 
} 
do_critical_section_stuff(); 

जो स्पष्ट कारणों के लिए ठीक से काम नहीं होगा।

Answer 5

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

स्थिति सफल होगी (टेस्ट एंडसेट सच हो जाएगा) जब तक कि किसी अन्य प्रक्रिया में संसाधन पर लॉक हो। जब किसी अन्य प्रक्रिया में संसाधन पर लॉक होता है, तो लॉक का मान सत्य होता है। जैसे ही दूसरी प्रक्रिया संसाधन पर अपना होल्ड जारी करती है, लॉक = झूठी सेट करके, टेस्ट एंडसेट झूठी वापसी करेगा।

जब टेस्ट एंडसेट झूठा लौटाता है, तो जबकि लूप की स्थिति विफल हो जाती है और इसलिए प्रक्रिया पी इसके महत्वपूर्ण खंड में प्रवेश करती है।

टेस्ट एंडसेट एक परमाणु संचालन है, यानी इसे बिना रुकावट के निष्पादित किया जाता है। लॉक के साथ दौड़ की स्थिति को रोकने के लिए यह किया जाता है।

Answer 6

आह मेरे पास यह प्रश्न भी था। मुझे अपनी समझ साझा करने दें।

प्रारंभ में * लक्ष्य गलत होगा। (यह एक दिया गया है)। यह सच है कि पी को लॉक प्राप्त करने के लिए while(TestAndSetLock(&lock)) ; // do nothing पास करने और महत्वपूर्ण अनुभाग दर्ज करने की आवश्यकता है। (लॉक प्राप्त करने के लिए, बस एक काल्पनिक बात है अगर यह जबकि पाश तो पारित कर सकते हैं यह ताला है)

किसी ताला लिया जा करने के लिए स्वतंत्र है, ताला मतलब है लक्ष्यसही है है लक्ष्यगलत है। इसलिए शुरुआत में यह

P1 (पहले ही समारोह कॉल करने के लिए भाग्यशाली मिल जाएगा) इस तरह है, है, वह देखता लक्ष्य गलत है और सच के लिए सेट और फाइनेंस फाल्स, जो इसे लूप प्रतीक्षा से बचने के लिए प्रेरित करता है।

अब लक्ष्य TRUE.Other तथ्य TestAndSet (boolean_ref ताला) है, और TestAndSet (boolean_ref लॉक) होगा हमेशा कहा जाता है मान प्रदान करेगा है लक्ष्य को TRUE पर सेट करें ताकि किसी को सोम में FALSE पर लक्ष्य सेट करना होगा ewhere बाकी

अन्य पी (तो लॉक के साथ भी इसे गलत करने के लिए सेट कर सकते हैं) आओ और देखो कि लक्ष्य सही है और जब TestAndSet(boolean_ref lock) बुला यह सही वापस आ जाएगी हमेशा असत्य पर P1 निर्धारित लक्ष्य तक होगा।

और मैं This site, you can download it from here

Answer 7

से यह अच्छा चित्रमय विवरण पाया सोचो गैर रैखिक। आप परिभाषा तीन मुद्दों ने बताया Silberchatz testAndSet() समारोह को लागू करने के लिए प्रदान:

(1) आप सही तरीके से कि लक्ष्य बिना शर्त सही पर सेट है, और (गलती से) का एहसास कहा एक समस्या है।

(2) (1) (जो अस्तित्व में नहीं है) में समस्या का समाधान करने के लिए, आपने प्रस्तावित किया है कि लक्ष्य को सत्य पर सेट करने से पहले परीक्षण किया जाना चाहिए।

(3) अंत में, आप तथ्य यह है कि परिणाम ब्लॉक कि म्युचुअल बहिष्करण लागू करता है के द्वारा भी बिना शर्त गलत पर सेट है (यह वास्तव में ऐसा नहीं होता है) के बारे में अपनी चिंताओं को दिखाया।

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

समस्या (2) के संबंध में, एक बार यह प्रदर्शित होने के बाद कि यह लक्ष्य को बिना शर्त शर्त पर सेट करने के लिए हानिकारक है, इसके मूल्य को पहले से जांचने की आवश्यकता नहीं है।

समस्या (3) भी मौजूद नहीं है क्योंकि परिणाम वास्तव में गलत नहीं है। मेरा मतलब है, यह है, लेकिन केवल महत्वपूर्ण क्षेत्र को प्रक्रिया द्वारा संसाधित किया गया है; यानी, जब परस्पर बहिष्करण अब आवश्यक नहीं है। प्रक्रिया को लक्ष्य को FALSE पर सेट करने के लिए जैसे ही महत्वपूर्ण अनुभाग छोड़ देता है (यह महत्वपूर्ण खंड से बाहर निकलने के बाद किसी अन्य प्रक्रिया को अवरुद्ध नहीं करना चाहिए)। महत्वपूर्ण खंड को संसाधित करने के बाद ताला छोड़ना अनिवार्य है!