म्यूटेक्स गतिरोध को रोकने के लिए दो सरल नियम

हैलो, प्रिय Habrausers!

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

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

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

तो, शुरू से ही ताले के बारे में ...

गतिरोध की प्रकृति

हम गतिरोध की स्थितियों की जटिल रूप से सत्यापित परिभाषाओं में नहीं जाएंगे और बस कहेंगे: गतिरोध उस प्रणाली की एक स्थिति है जिसमें एक धागा कुछ होने की प्रतीक्षा कर रहा है, और यह कुछ नहीं हो सकता है क्योंकि एक और धागा कुछ होने की प्रतीक्षा कर रहा है फिर पहली धारा से।

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

सबसे सरल पारस्परिक तालों की विशिष्ट स्थितियों पर विचार करने के लिए आगे बढ़ने से पहले, मैं उस मॉडल के बारे में कुछ शब्द कहना चाहता हूं जिसका उपयोग हम मल्टीथ्रेडेड कार्यक्रमों और उनमें उत्पन्न होने वाली स्थितियों का वर्णन करने के लिए करते हैं।

मल्टीथ्रेडेड कार्यक्रमों के मॉडल के बारे में कुछ शब्द

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

एकल धारा (विषय) से युक्त मॉडल का एक उदाहरण:

चित्र 1

इस आंकड़े के अनुसार, विषय दो शाखाओं से गुजर सकता है: 0, L1, U1, 0 या 0, L1, L2, U2, U1, 0. इस योजना को एक परिमित राज्य मशीन के रूप में माना जा सकता है, जिसके व्याकरण में दो वाक्यांश शामिल हैं {0, एल 1, यू 1, 0} और {0, एल 1, एल 2, यू 2, यू 1, 0}। हम मानते हैं कि सिंक्रनाइज़ेशन साधनों के संबंध में क्रियाओं के बीच संक्रमण का समय परिमित है, अर्थात्। एल्गोरिदम सही है। हम किसी भी उपयोगकर्ता कार्रवाई के लिए प्रतीक्षा करते समय म्यूटेक्स को पकड़ने और पकड़ने के लिए एक सिंक्रनाइज़ेशन त्रुटि पर विचार नहीं करेंगे जो संभवतः कभी नहीं हो सकता है।
पारस्परिक अवरोधन की स्थिति की संभावित संभावना के लिए कार्यक्रम का अध्ययन करने के लिए, कार्यक्रम में सभी संभव अभिनेताओं के निष्पादन की श्रृंखला को तैयार करना आवश्यक है।

सरल म्यूटेक्स गतिरोध

मान लीजिए कि हमारे कार्यक्रम में, चित्र 1 में दिखाई गई धारा (विषय) के अलावा, एक और भी है:

चित्र 2

मैं यह कहने की हिम्मत करता हूं कि हमारे कार्यक्रम में एक संभावित गतिरोध है, और यहां तक ​​कि अगर आपके परीक्षक कहते हैं कि सब कुछ ठीक काम करता है, तो आप इस स्थिति से प्रतिरक्षा नहीं करते हैं कि आपका कार्यक्रम एक अलग हार्डवेयर पर इस तरह का व्यवहार करेगा:

चित्र 3

कुछ भी हमारे दो स्वतंत्र धागे को इस तरह निष्पादित करने से रोकता है: थ्रेड 1 म्यूटेक्स 1 पर कब्जा करने में कामयाब रहा, फिर शेड्यूलर ने निष्पादन को थ्रेड 2 में बदल दिया, जिसने म्यूटेक्स 2 पर कब्जा कर लिया, और उसके बाद हमारे दोनों धागे म्यूटेक्स को पकड़ने की कोशिश करते हैं जो पहले से ही कब्जा कर लिया है - गतिरोध!

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

चित्र 4

यह याद रखना महत्वपूर्ण है कि धाराएँ एक दूसरे के साथ जोड़ीदार हो सकती हैं, लेकिन एक बड़े संयोजन में संगत नहीं। चित्रा 5 कार्यक्रम का मॉडल दिखाता है, जहां सभी विषय एक-दूसरे के साथ जोड़ीदार हैं, लेकिन सभी एक साथ मिलकर परस्पर अवरोध की स्थिति पैदा करते हैं।

चित्र 5

चित्रा 6 चित्र 5 में दिखाए गए मॉडल के लिए निष्पादन श्रृंखलाओं के संयोजन का एक और प्रकार दिखाता है, जिसमें एक गतिरोध होता है।

चित्र 6

मैं सिर्फ इतना कहना चाहता हूं: कितना डरावना है!

और यह सच होगा यदि दो बहुत ही सरल नियम नहीं थे जो पेशेवर प्रोग्रामर सहजता से पालन करते हैं, अक्सर बिना यह सोचे भी कि वे ऐसा क्यों करते हैं।

पहला नियम

हमेशा कैप्चर किए गए म्यूटेक्स को रिवर्स कैप्चर ऑर्डर में जारी करें, अर्थात तर्क का पालन करें "पहले पर कब्जा कर लिया गया है - अंतिम जारी किया गया है । "

दूसरा नियम

हमेशा एक ही म्यूटेक्स कैप्चर ऑर्डर का पालन करें।
यदि आप एक धागे में म्यूटेक्स 1 को पकड़ते हैं और फिर म्यूटेक्स 2 को, तो उन्हें दूसरे धागे में एक अलग क्रम में पकड़ना अस्वीकार्य है।
वास्तव में, नियम उतना सरल नहीं है जितना पहली नज़र में लगता है। आइए चित्रा 6 पर करीब से नज़र डालें। इस नियम का उल्लंघन किया गया है, लेकिन यह कुछ हद तक अविश्वसनीय है। पहली स्ट्रीम को देखते हुए, हम ठीक करते हैं कि हम म्यूटेक्स 2 को म्यूटेक्स के बाद कैप्चर करते हैं। दूसरी स्ट्रीम को देखते हुए, हम ठीक करते हैं कि हम म्यूटेक्स 3 के बाद म्यूटेक्स को कैप्चर करते हैं। इन टिप्पणियों को मिलाने का मतलब है कि हम म्यूटेक्स 1 के बाद म्यूटेक्स 3 को कैप्चर करते हैं, जो नहीं है थ्रेड में निष्पादित 3. इस विफलता का परिणाम गतिरोध है, जो आंकड़े में दिखाया गया है।

इन नियमों की सादगी के बावजूद, मैं यह कहने की हिम्मत करता हूं कि यदि आपका प्रोग्राम केवल म्यूटेक्स को सिंक्रोनाइज़ेशन के साधन के रूप में उपयोग करता है और आपने इन नियमों का पालन किया है, तो आपसी अवरोधन आपके लिए कोई समस्या नहीं है! बेशक, हम एक गैर-पुनरावर्ती म्यूटेक्स को एक धागे में कैद करने की कोशिश करने की स्थिति को ध्यान में नहीं रखते हैं, लेकिन गतिरोध की तुलना में यह अधिक बेवकूफ है।

अंत में, मैं एक सवाल पूछना चाहूंगा: क्या यह विषय ह्रोब दर्शकों के लिए दिलचस्प है? यदि ऐसा है, तो संकेत चर का उपयोग करते समय उत्पन्न होने वाली थोड़ी और दिलचस्प स्थितियों के बारे में बात करने की इच्छा और अवसर है, शायद, साक्ष्य के आधार में थोड़ा गहरा डुबकी लगाते हैं - यह पहले से ही मल्टीथ्रेडेड अनुप्रयोगों के परिष्कृत प्रोग्रामर के लिए है।

आशा है यह पोस्ट मददगार रही होगी।

निरंतरता पढ़ें - सिग्नल चर पर गतिरोध के खिलाफ व्यंजनों ।