मान लीजिए कि एक सँकरे, एकल मार्ग वाले पुल के बीच में विपरीत दिशाओं से आई दो कारें आमने-सामने खड़ी हैं। यदि दोनों चालक बिना हिले इस इंतज़ार में रहें कि दूसरा पहले पीछे हटे, तो दोनों कारें कभी पुल पार नहीं कर पाएँगी। इसमें किसी एक को दोषी ठहराना भी कठिन है, लेकिन ऐसी स्थिति बन गई है जिसमें कोई भी आगे नहीं बढ़ सकता।
कंप्यूटर के भीतर भी ठीक ऐसा ही होता है, और इसे ‘गतिरोध (Deadlock)’ कहते हैं। सरल शब्दों में, गतिरोध वह स्थिति है जिसमें कई प्रोग्राम एक-दूसरे के पास मौजूद संसाधनों की प्रतीक्षा करते हुए रुक जाते हैं और कोई भी अपना काम आगे नहीं बढ़ा पाता। कंप्यूटर खराब न होने के बावजूद अचानक रुका हुआ दिखाई देने की कई घटनाओं का कारण यही गतिरोध होता है।
इस सामग्री में हम क्रम से देखेंगे कि गतिरोध किस रूप में दिखाई देता है, उसके उत्पन्न होने की चार शर्तें क्या हैं, उसे समझाने वाला प्रसिद्ध उदाहरण क्या है और कंप्यूटर उससे कैसे निपटते हैं।
एक-दूसरे की प्रतीक्षा में थम जाने वाला कंप्यूटर
गतिरोध कैसे उत्पन्न होता है
कंप्यूटर के भीतर कई प्रोग्राम एक साथ चलते हैं और प्रिंटर, फ़ाइल तथा मेमोरी जैसे संसाधनों का साझा उपयोग करते हैं।
(1) ऐसे संसाधन जिन्हें एक समय में केवल एक प्रोग्राम उपयोग कर सकता है
कुछ संसाधनों का कई प्रोग्राम एक साथ उपयोग करें तो उनकी सामग्री गड़बड़ा सकती है, इसलिए जब एक प्रोग्राम उनका उपयोग कर रहा हो, तब दूसरे प्रोग्राम को प्रतीक्षा करनी पड़ती है। किसी संसाधन पर कुछ समय के लिए एकाधिकार रखने की इस व्यवस्था को लॉक (Lock) कहते हैं।
(2) अलग-अलग क्रम के कारण रुक जाना
उदाहरण के लिए, पहला प्रोग्राम फ़ाइल A को लॉक करके फ़ाइल B की प्रतीक्षा कर रहा हो सकता है, जबकि दूसरा प्रोग्राम फ़ाइल B को लॉक करके फ़ाइल A की प्रतीक्षा कर रहा हो। दोनों प्रोग्राम अपने पास मौजूद संसाधन छोड़ते नहीं और केवल दूसरे के संसाधन की प्रतीक्षा करते रहते हैं, इसलिए दोनों हमेशा के लिए रुके रह जाते हैं।
(3) बाहर से क्या दिखाई देता है
गतिरोध में फँसा प्रोग्राम बिना किसी त्रुटि संदेश के बस प्रतिक्रिया देना बंद कर देता है। बैंकिंग कंप्यूटर नेटवर्क या आरक्षण प्रणालियों जैसे स्थानों पर, जहाँ एक साथ बहुत से अनुरोध संसाधित होते हैं, इस तरह रुक जाना बड़ी समस्या बन सकता है।
गतिरोध उत्पन्न होने की चार शर्तें
1971 में कंप्यूटर वैज्ञानिक एडवर्ड कॉफ़मैन (Edward G. Coffman Jr.) ने बताया कि गतिरोध उत्पन्न होने के लिए निम्नलिखित चार शर्तों का एक साथ पूरा होना आवश्यक है। उनके नाम पर इन्हें कॉफ़मैन की शर्तें कहा जाता है।
- पारस्परिक अपवर्जन (Mutual Exclusion): किसी संसाधन का एक समय में केवल एक प्रोग्राम उपयोग कर सकता है।
- कब्ज़ा और प्रतीक्षा (Hold and Wait): प्रोग्राम पहले से एक संसाधन अपने पास रखकर किसी अन्य संसाधन की प्रतीक्षा करता है।
- बिना ज़बरन संसाधन वापसी (No Preemption): किसी दूसरे के पास मौजूद संसाधन को ज़बरदस्ती नहीं छीना जा सकता; उसे रखने वाले को स्वयं ही छोड़ना होता है।
- चक्रीय प्रतीक्षा (Circular Wait): 1 नंबर वाला 2 नंबर वाले की, 2 नंबर वाला 3 नंबर वाले की और 3 नंबर वाला फिर 1 नंबर वाले की प्रतीक्षा करता है। इस प्रकार प्रतीक्षा एक चक्र में जुड़ जाती है।
(1) एक भी कड़ी तोड़ने से गतिरोध खुल जाता है
चार शर्तों में से एक भी अनुपस्थित हो तो गतिरोध उत्पन्न नहीं होता। इसलिए गतिरोध को रोकने के अधिकांश तरीके इन चार कड़ियों में से किसी एक को तोड़ने से शुरू होते हैं।
भोजन करते दार्शनिकों की समस्या
गतिरोध समझाने के लिए सबसे अधिक इस्तेमाल की जाने वाली कहानी ‘भोजन करते दार्शनिकों की समस्या (Dining Philosophers Problem)’ है, जो नीदरलैंड के कंप्यूटर वैज्ञानिक एड्सखर डाइकस्ट्रा (Edsger W. Dijkstra) द्वारा प्रस्तुत एक समस्या से निकली है।
(1) समस्या की स्थिति
एक गोल खाने की मेज़ पर पाँच दार्शनिक बैठे हैं। हर दो व्यक्तियों के बीच एक काँटा रखा है, यानी कुल पाँच काँटे हैं। दार्शनिक सोचते रहते हैं और भूख लगने पर तभी भोजन कर सकते हैं जब वे अपने दोनों ओर के दोनों काँटे उठा लें।
(2) वह क्षण जब सभी भूखे रह जाते हैं
यदि पाँचों एक साथ अपने बाएँ वाला काँटा उठा लें, तो सभी अपने दाएँ वाले काँटे की प्रतीक्षा करने लगेंगे। कोई भी बाएँ वाला काँटा नीचे नहीं रखता, इसलिए अंततः पाँचों भोजन नहीं कर पाते और केवल प्रतीक्षा करते रहते हैं। यह गतिरोध का एक सामान्य उदाहरण है जिसमें चारों शर्तें पूरी होती हैं।
(3) एक सरल समाधान
यदि हर काँटे को एक नंबर दे दिया जाए और यह तय कर दिया जाए कि सभी पहले छोटे नंबर वाला काँटा उठाएँगे, तो प्रतीक्षा का चक्र नहीं बनेगा। यह स्पष्ट रूप से दिखाता है कि केवल एक क्रम तय करके चक्रीय प्रतीक्षा को तोड़ा जा सकता है।
कंप्यूटर गतिरोध से कैसे निपटते हैं
ऑपरेटिंग सिस्टम और डेटाबेस स्थिति के अनुसार अलग-अलग तरीके चुनते हैं।
(1) पहले से रोकथाम करना
संसाधनों के उपयोग का क्रम तय कर दिया जाता है या सभी आवश्यक संसाधनों का अनुरोध शुरुआत में एक साथ करवाया जाता है, ताकि चार शर्तों में से कोई एक उत्पन्न ही न हो।
(2) गतिरोध से बचना
संसाधन देने से पहले गणना की जाती है कि इस अनुरोध को स्वीकार करने से आगे चलकर गतिरोध उत्पन्न हो सकता है या नहीं। डाइकस्ट्रा द्वारा विकसित बैंकर एल्गोरिदम (Banker's Algorithm) इसका एक प्रमुख तरीका है। यह वैसा ही है जैसे बैंक ऋण देते समय जाँचता है कि वह अंत तक सभी ग्राहकों की माँगें पूरी कर पाएगा या नहीं।
(3) पता लगाकर समाधान करना
पहले गतिरोध को उत्पन्न होने दिया जाता है, फिर यह जाँचा जाता है कि कौन किसकी प्रतीक्षा कर रहा है। यदि कोई चक्र मिलता है, तो एक प्रोग्राम को रोककर या शुरुआत से दोबारा चलाकर उलझन सुलझाई जाती है। कई डेटाबेस इस तरीके का उपयोग करते हैं।
(4) अनदेखा करना
यदि गतिरोध बहुत कम होता हो और उससे होने वाली हानि भी कम हो, तो कभी-कभी उसे रोकने की विशेष कोशिश करने के बजाय उसके होने पर दोबारा शुरू करने का विकल्प चुना जाता है। रेत में सिर छिपाने वाले शुतुरमुर्ग की उपमा देते हुए इसे शुतुरमुर्ग एल्गोरिदम (Ostrich Algorithm) कहा जाता है।
गतिरोध किसी एक की गलती से नहीं, बल्कि तब पैदा होने वाली समस्या है जब सभी अपना-अपना हिस्सा थामे हुए केवल दूसरे की प्रतीक्षा करते रहते हैं। इसलिए इसका समाधान भी क्रम तय करने और कभी-कभी अपने पास मौजूद चीज़ पहले छोड़ देने से शुरू होता है।
यह समझना कि एक-दूसरे का थामा हुआ केवल एक हाथ छोड़ देने से भी रास्ता खुल सकता है, रुकी हुई प्रणाली को फिर से चलाने की समझ की ओर पहला कदम है।
