Deadlock prevention algorithms
कंप्यूटर विज्ञान में, गतिरोध रोकथाम एल्गोरिदम का उपयोग समवर्ती प्रोग्रामिंग में किया जाता है जब कई प्रक्रियाओं को एक से अधिक साझा संसाधन प्राप्त करने होते हैं। यदि दो या दो से अधिक समवर्ती प्रक्रियाएं अंधाधुंध रूप से कई संसाधन प्राप्त करती हैं, तो ऐसी स्थिति पैदा हो सकती है जहां प्रत्येक प्रक्रिया के पास किसी अन्य प्रक्रिया के लिए आवश्यक संसाधन हो। नतीजतन, कोई भी प्रक्रिया अपने लिए आवश्यक सभी संसाधन प्राप्त नहीं कर सकती है, इसलिए सभी प्रक्रियाएं आगे के निष्पादन से अवरुद्ध हो जाती हैं। इस स्थिति को गतिरोध कहा जाता है। एक गतिरोध रोकथाम एल्गोरिदम प्रत्येक प्रक्रिया द्वारा संसाधन उपयोग को व्यवस्थित करता है ताकि यह सुनिश्चित किया जा सके कि कम से कम एक प्रक्रिया हमेशा सभी संसाधनों को प्राप्त करने में सक्षम हो। डेडलॉक एल्गोरिदम का ऐसा ही एक उदाहरण बैंकर का एल्गोरिदम है। अवलोकन वितरित गतिरोध वितरित गतिरोध वितरित प्रणालियों में तब हो सकता है जब वितरित लेनदेन या समवर्ती नियंत्रण का उपयोग किया जा रहा हो। वितरित गतिरोध का पता या तो वैश्विक प्रतीक्षा-ग्राफ का निर्माण करके, गतिरोध डिटेक्टर पर स्थानीय प्रतीक्षा-ग्राफ से या किनारे का पीछा करने जैसे वितरित एल्गोरिदम द्वारा लगाया जा सकता है। फैंटम डेडलॉक डेडलॉक होते हैं जो सिस्टम की आंतरिक देरी के कारण एक वितरित प्रणाली में पाए जाते हैं लेकिन अब वास्तव में पता लगाने के समय मौजूद नहीं होते हैं। समान्तरता को बढ़ाने के कई अलग-अलग तरीके हैं जहां पुनरावर्ती ताले अन्यथा गतिरोध का कारण बन सकते हैं। लेकिन एक कीमत है। और वह कीमत या तो प्रदर्शन/ओवरहेड है, डेटा भ्रष्टाचार की अनुमति देता है, या दोनों। कुछ उदाहरणों में शामिल हैंः लॉक पदानुक्रम, लॉक संदर्भ-गिनती और प्रीएम्पशन (या तो संस्करण का उपयोग करना या प्रीएम्पशन होने पर डेटा भ्रष्टाचार की अनुमति देना); वेट-फॉर-ग्राफ (डब्ल्यू. एफ. जी.) एल्गोरिदम, जो सभी चक्रों को ट्रैक करते हैं जो डेडलक का कारण बनते हैं (अस्थायी डेडलक सहित); और ह्यूरिस्टिक्स एल्गोरिदम जो आवश्यक रूप से उन स्थानों के 100% में समानांतरता को नहीं बढ़ाते हैं जो डेडलक संभव हैं, लेकिन इसके बजाय उन्हें पर्याप्त स्थानों पर हल करके समझौता करते हैं ताकि प्रदर्शन/ओवरहेड बनाम समानांतरता स्वीकार्य हो। "क्रासिंग पर जब दो ट्रेनें एक-दूसरे के पास आती हैं" स्थिति पर विचार करें। समय पर रोकथाम एक ऐसे स्विच के साथ क्रॉसिंग (क्रॉसिंग गार्ड) पर खड़े व्यक्ति की तरह काम करती है जो केवल एक ट्रेन को "सुपर पटरियों" पर जाने देगा जो दूसरी प्रतीक्षा ट्रेन (ट्रेनों) के ऊपर और ऊपर चलती है। गैर-पुनरावर्ती ताले के लिए, एक ताला केवल एक बार दर्ज किया जा सकता है (जहां एक धागा बिना खोले दो बार प्रवेश करने से गतिरोध पैदा होगा, या परिपत्र प्रतीक्षा रोकथाम को लागू करने के लिए एक अपवाद फेंक देगा)। रिकर्सिव लॉक के लिए, केवल एक धागे को लॉक से गुजरने की अनुमति है। यदि कोई अन्य धागा ताला में प्रवेश करता है, तो उन्हें तब तक इंतजार करना चाहिए जब तक कि प्रारंभिक धागा जो गुजरता है वह पूरी तरह से n बार प्रवेश नहीं करता है। इसलिए पहले वाले के साथ समस्या यह है कि यह कोई गतिरोध की रोकथाम नहीं करता है। दूसरा वितरित गतिरोध की रोकथाम नहीं करता है। लेकिन दूसरे को एक गतिरोध परिदृश्य को रोकने के लिए पुनर्परिभाषित किया गया है जिसे पहला संबोधित नहीं करता है। बार-बार, केवल एक धागे को ताला से गुजरने की अनुमति है। यदि अन्य धागे ताला में प्रवेश करते हैं, तो उन्हें तब तक इंतजार करना चाहिए जब तक कि प्रारंभिक धागा जो n बार पूरा नहीं हो जाता। लेकिन अगर लॉकिंग में प्रवेश करने वाले धागे की संख्या लॉक की गई संख्या के बराबर है, तो एक धागे को सुपर-थ्रेड के रूप में निर्धारित करें, और इसे केवल तब तक चलने दें (लॉकिंग में प्रवेश करने/बाहर निकलने की संख्या पर नज़र रखें) जब तक कि यह पूरा न हो जाए। एक सुपर-थ्रेड समाप्त होने के बाद, स्थिति पुनरावर्ती ताला से तर्क का उपयोग करने के लिए वापस बदल जाती है, और बाहर निकलने वाला सुपर-थ्रेड खुद को एक सुपर-थ्रेड नहीं होने के रूप में सेट करता है जो लॉकर को सूचित करता है कि अन्य बंद, प्रतीक्षा धागे को इस स्थिति को फिर से जांचने की आवश्यकता है यदि एक गतिरोध परिदृश्य मौजूद है, तो एक नया सुपर-थ्रेड सेट करें और उस तर्क का पालन करें। अन्यथा, नियमित रूप से ताला लगाना फिर से शुरू करें। जिन मुद्दों को ऊपर संबोधित नहीं किया गया है, उनमें बहुत सारे भ्रम रुकने की समस्या के इर्द-गिर्द घूमते हैं। लेकिन यह तर्क रुकने की समस्या को हल नहीं करता है क्योंकि जिन स्थितियों में लॉक होता है वे ज्ञात हैं, जो एक विशिष्ट समाधान देता है (अन्यथा आवश्यक सामान्य समाधान के बजाय जो रुकने की समस्या की आवश्यकता होती है)। फिर भी, यह लॉकर इस तर्क का उपयोग करके केवल ताले पर विचार करते हुए सभी गतिरोध को रोकता है। लेकिन अगर इसका उपयोग अन्य ताला लगाने के तंत्र के साथ किया जाता है, तो एक ताला जो कभी शुरू नहीं होता है, कभी भी ताला नहीं खोलता है (बिना ताला खोले बाहर कूदना, ताला के भीतर अनिश्चित काल के लिए लूप करना, या ताला खोलने के लिए कॉल करना भूल जाना कोडिंग त्रुटि), गतिरोध बहुत संभव है। इन्हें शामिल करने के लिए शर्त को बढ़ाने के लिए ठहराव के मुद्दे को हल करने की आवश्यकता होगी, क्योंकि कोई ऐसी स्थितियों से निपट रहा होगा जिनके बारे में कोई कुछ नहीं जानता है और जिसे बदलने में असमर्थ है। एक अन्य मुद्दा यह है कि यह अस्थायी गतिरोध के मुद्दे (वास्तव में एक गतिरोध नहीं, बल्कि एक प्रदर्शन हत्यारा) को संबोधित नहीं करता है, जहां दो या दो से अधिक धागे एक दूसरे पर बंद हो जाते हैं जबकि एक अन्य असंबंधित धागा चल रहा होता है। इन अस्थायी गतिरोधों में विशेष रूप से उनके भीतर एक धागा चल सकता है, जिससे समानता बढ़ जाती है। लेकिन इस बात के कारण कि वितरित गतिरोध का पता लगाना सभी ताले के लिए कैसे काम करता है, और उसमें सबसेट नहीं है, अस्थायी गतिरोध को दूर करने के लिए सुपर-थ्रेड तर्क का प्रदर्शन करने से पहले असंबंधित चलने वाले धागे को पूरा करना होगा। उपरोक्त में अस्थायी लाइव-लॉक परिदृश्य देखा जा सकता है। यदि पहला असंबंधित धागा बाहर निकलने से पहले एक और असंबंधित चलने वाला धागा शुरू होता है, तो अस्थायी गतिरोध की एक और अवधि होगी। यदि ऐसा लगातार होता है (अत्यंत दुर्लभ), तो अस्थायी गतिरोध को कार्यक्रम से बाहर निकलने से ठीक पहले तक बढ़ाया जा सकता है, जब अन्य असंबंधित धागे समाप्त होने की गारंटी होती है (इस गारंटी के कारण कि एक धागा हमेशा पूरा होने तक चलेगा)। आगे विस्तार इसे समानांतरता बढ़ाने के लिए अतिरिक्त तर्क को शामिल करने के लिए आगे बढ़ाया जा सकता है जहां अस्थायी गतिरोध अन्यथा हो सकते हैं। लेकिन अधिक तर्क जोड़ने के प्रत्येक चरण के लिए, हम अधिक ओवरहेड जोड़ते हैं। कुछ उदाहरणों में शामिल हैंः मौजूदा ताले के प्रत्येक सबसेट पर विचार करने के लिए वितरित सुपर-थ्रेड लॉकिंग तंत्र का विस्तार करना; वेट-फॉर-ग्राफ (डब्ल्यू. एफ. जी.) एल्गोरिदम, जो सभी चक्रों को ट्रैक करते हैं जो डेडलक का कारण बनते हैं (अस्थायी डेडलक सहित); और ह्यूरिस्टिक्स एल्गोरिदम जो आवश्यक रूप से उन स्थानों के 100% में समानांतरता को नहीं बढ़ाते हैं जहां अस्थायी डेडलक संभव हैं, बल्कि उन्हें पर्याप्त स्थानों पर हल करके समझौता करते हैं ताकि प्रदर्शन/ओवरहेड बनाम समानांतरता स्वीकार्य हो (जैसे। उपलब्ध प्रत्येक प्रोसेसर के लिए, प्रोसेसर की संख्या + 1 गहराई से कम गतिरोध चक्र खोजने की दिशा में काम करें)। संदर्भ वितरित संगणना