डेडलॉक

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

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

एक संचार प्रणाली में, गतिरोध मुख्य रूप से खोए या भ्रष्ट संकेतों के कारण होते हैं, संसाधन विवाद से नही।  
अंगूठाकार| दो प्रक्रियाएं जो विपरीत क्रम में दो संसाधनों के लिए प्रतिस्पर्धा कर रही हैं। 

 आवश्यक शर्तें 
एक संसाधन पर गतिरोध की स्थिति तब ही उत्पन्न हो सकती है, जब निम्न स्थितियाँ एक सिस्टम में एक साथ हो:  

 म्यूचुअल बहिष्करण : कम से कम एक संसाधन को गैर-साझाकरण मोड में रोका जाना चाहिए। अन्यथा, आवश्यक होने पर संसाधन का उपयोग करने से प्रक्रियाओं को रोका नहीं जाएगा। केवल एक प्रक्रिया किसी भी समय पर संसाधन का उपयोग कर सकती है।  
 पकड़ना और रुकना या संसाधन पकडना : एक प्रक्रिया वर्तमान में कम से कम एक संसाधन को रोकी हुई है और अतिरिक्त संसाधनों का अनुरोध कर रही है जो अन्य प्रक्रियाओं द्वारा रोकी जा रही हैं। 
 कोई पूर्वधारणा नहीं: एक संसाधन को केवल स्वेच्छा से ही इसे धारण करने वाली प्रक्रिया द्वारा छोडा जा सकता है। 
 परिपत्र प्रतीक्षा: प्रत्येक प्रक्रिया को एक संसाधन की प्रतीक्षा करनी चाहिए जो किसी अन्य प्रक्रिया द्वारा रोकी जा रही है, जो बदले में पहली प्रक्रिया द्वरा संसाधन को छोडने की प्रतीक्षा कर रही है। सामान्य तौर पर, प्रतीक्षा प्रक्रियाओं का एक सेट होता है, P = {P1, P2, …, PN}, जिसमें  P1 ,P2 द्वारा आयोजित संसाधन की प्रतीक्षा कर रहा है, P2 ,P3 द्वारा आयोजित संसाधन की प्रतीक्षा कर रहा है और इसी तरह P N, P 1 द्वारा रखे गए संसाधन की प्रतीक्षा कर रहा है।   

इन चार शर्तों को एडवर्ड जी कॉफमैन, जूनियर  द्वारा 1971 के लेख में अपने पहले विवरण से कॉफ़मैन की स्थिति के रूप में जाना जाता है । 

हालांकि ये स्थितियाँ एकल-उदाहरण संसाधन सिस्टम पर गतिरोध उत्पन्न करने के लिए पर्याप्त हैं, वे केवल संसाधनों के कई उदाहरण वाले सिस्टम पर गतिरोध की संभावना को इंगित करते हैं।

 डेडलॉक से निपटना 

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

 डेडलॉक की अनदेखी 
इस दृष्टिकोण में, यह माना जाता है कि डेडलॉक कभी नहीं होगा। यह ऑस्ट्रिच एल्गोरिथ्म का भी एक अनुप्रयोग है। इस दृष्टिकोण का उपयोग शुरू में  MINIX और  UNIX द्वारा किया गया था। इसका उपयोग तब किया जाता है जब डेडलॉक की घटनाओं के बीच का समय अंतराल बड़ा हो और हर बार होने वाले डेटा का नुकसान सहनीय हो।

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

एक डेडलॉक का पता चलने के बाद, उसे ठीक किया जा सकता है   
[ उद्धरण वांछित ]    

 बाहरी कड़ियाँ