Operating Systems (OS) Complete Notes — Deadlock & Synchronization (Part 2)
Computer Science के प्रत्येक student के लिये computer अनुदेशक (Advanced Level) और प्रोग्रामर परीक्षाओं के लिए Operating System का यह दूसरा भाग सबसे ज्यादा महत्वपूर्ण है। इसमें हम 'Process Synchronization' और 'Deadlock' के उन कठिन Concepts को समझेंगे जहाँ से हर बार वैचारिक और Numerical प्रश्न पूछे जाते हैं।
1. प्रोसेस सिंक्रोनाइजेशन (Process Synchronization)
जब एक से अधिक प्रोसेसेज एक ही डेटा या वेरिएबल को एक साथ एक्सेस (Share) करने की कोशिश करती हैं, तो डेटा में गड़बड़ी (Inconsistency) होने का खतरा रहता है। इसी समस्या को रोकने के लिए Process Synchronization का उपयोग किया जाता है।
क्रिटिकल सेक्शन (Critical Section Problem)
यह किसी भी कोड का वह महत्वपूर्ण हिस्सा (Block of Code) होता है जहाँ Shared resource (जैसे ग्लोबल वेरिएबल, फाइल आदि) को एक्सेस किया जाता है। क्रिटिकल सेक्शन की समस्या को हल करने के लिए किसी भी सिंक्रोनाइजेशन मैकेनिज्म को 3 मुख्य शर्तों को पूरा करना ही होगा:
- 1. Mutual Exclusion (परस्पर अपवर्जन): यदि कोई प्रोसेस क्रिटिकल सेक्शन में रन हो रही है, तो किसी भी दूसरी प्रोसेस को उस समय अंदर जाने की अनुमति नहीं होनी चाहिए। (यह सबसे आवश्यक शर्त है)।
- 2. Progress (प्रगति): यदि क्रिटिकल सेक्शन खाली है और कुछ प्रोसेसेज अंदर जाना चाहती हैं, तो केवल वही प्रोसेसेज निर्णय में भाग लेंगी जो अंदर जाना चाहती हैं। कोई External process उन्हें रोक नहीं सकती। (यह भी आवश्यक शर्त है)।
- 3. Bounded Waiting (सीमित प्रतीक्षा): ऐसा नहीं होना चाहिए कि एक ही प्रोसेस बार-बार अंदर जाती रहे और दूसरी प्रोसेस हमेशा के लिए भूखी (Starvation) बैठी रहे। अंदर जाने के लिए प्रतीक्षा की एक सीमा होनी चाहिए। (यह वैकल्पिक/सॉफ्ट शर्त है)।
सेमाफोर (Semaphores)
सेमाफोर एक इंटीजर वेरिएबल होता है जो क्रिटिकल सेक्शन की समस्या को हल करने के लिए उपयोग किया जाता है। इस पर केवल दो एटॉमिक (Atomic) ऑपरेशंस काम करते हैं:
- Wait Operation / P/ Down: यह सेमाफोर की वैल्यू को 1 से घटा देता है (S = S - 1)। यदि वैल्यू नेगेटिव हो जाए, तो प्रोसेस ब्लॉक हो जाती है।
- Signal Operation / V / Up: यह सेमाफोर की वैल्यू को 1 से बढ़ा देता है (S = S + 1)। यदि कोई प्रोसेस ब्लॉक थी, तो उसे जगा देता है।
सेमाफोर के प्रकार:
| Binary Semaphore (बाइनरी सेमाफोर) | Counting Semaphore (काउंटिंग सेमाफोर) |
|---|---|
| इसकी वैल्यू केवल 0 या 1 ही हो सकती है। यह बिल्कुल 'Mutex' की तरह काम करता है। | इसकी वैल्यू की कोई सीमा नहीं होती (यह नेगेटिव या पॉजिटिव कुछ भी हो सकती है)। यह कई रिसोर्सेज को मैनेज करने के काम आता है। |
2. डेडलॉक क्या है? (What is Deadlock?)
यह ऑपरेटिंग सिस्टम की वह अवांछित (Unwanted) स्थिति है जहाँ दो या दो से अधिक प्रोसेसेज एक दूसरे के रिसोर्सेज को होल्ड करके बैठ जाती हैं और एक दूसरे का काम खत्म होने का इंतजार करती हैं, जिससे पूरा सिस्टम ब्लॉक हो जाता है।
डेडलॉक की 4 आवश्यक शर्तें (Coffman Conditions)
परीक्षा में सीधा सवाल आता है कि डेडलॉक होने के लिए इन चारों शर्तों का एक साथ (Simultaneously) लागू होना अनिवार्य है:
- 1. Mutual Exclusion: कम से कम एक रिसोर्स ऐसा होना चाहिए जो 'Non-Shareable' हो (यानी एक समय में एक ही प्रोसेस उसे इस्तेमाल कर सके)।
- 2. Hold and Wait: एक प्रोसेस कम से कम एक रिसोर्स को अपने पास होल्ड (कब्जे में) रखे हुए हो और दूसरे नए रिसोर्स के लिए वेट कर रही हो।
- 3. No Preemption: रिसोर्स को किसी प्रोसेस से जबरदस्ती नहीं छीना जा सकता। प्रोसेस खुद ही उसे अपनी मर्जी से छोड़ेगी।
- 4. Circular Wait: प्रोसेसेज की एक ऐसी चेन या चक्र बनना चाहिए जहाँ हर प्रोसेस अपने से अगली प्रोसेस के पास मौजूद रिसोर्स का इंतजार कर रही हो।
3. डेडलॉक से निपटने के तरीके (Deadlock Handling)
ऑपरेटिंग सिस्टम डेडलॉक को संभालने के लिए मुख्य रूप से चार रणनीतियों का उपयोग करता है:
- A. Deadlock Ignorance (Ostrich Algorithm): इसमें ओएस मान लेता है कि डेडलॉक कभी आता ही नहीं। विंडोज और लिनक्स जैसे कमर्शियल ओएस इसी का उपयोग करते हैं क्योंकि डेडलॉक बहुत रेयर होता है और इसे रोकने की कॉस्ट बहुत ज्यादा होती है।
- B. Deadlock Prevention: इसमें हम ऊपर बताई गई 4 कफमैन शर्तों में से किसी भी एक शर्त को फेल कर देते हैं, जिससे डेडलॉक कभी हो ही नहीं पाता।
- C. Deadlock Detection and Recovery: सिस्टम को डेडलॉक में जाने दिया जाता है, फिर रिसोर्स एलोकेशन ग्राफ (RAG) की मदद से इसे डिटेक्ट करके किसी प्रोसेस को किल (Terminate) करके रिकवर किया जाता है।
- D. Deadlock Avoidance: इसमें ओएस हर रिसोर्स रिक्वेस्ट पर यह चेक करता है कि क्या रिसोर्स देने के बाद सिस्टम Safe State में रहेगा या नहीं। इसके लिए प्रसिद्ध Banker's Algorithm का उपयोग किया जाता है।
4. बैंकर एल्गोरिथ्म और न्यूमेरिकल (Banker's Algorithm & Numerical)
बैंकर एल्गोरिथ्म का उपयोग मुख्य रूप से यह जांचने के लिए किया जाता है कि सिस्टम सुरक्षित (Safe) है या असुरक्षित (Unsafe)। इसमें न्यूमेरिकल सॉल्व करने के लिए मुख्य फॉर्मूला है:
Need = Max\ Requirement - Current\ Allocation
एडवांस्ड न्यूमेरिकल उदाहरण:
प्रश्न: मान लीजिए सिस्टम में एक ही प्रकार के कुल 10 रिसोर्स हैं। तीन प्रोसेसेज $P_0, P_1, P_2$ की स्थिति नीचे दी गई है। क्या यह सिस्टम Safe State में है? यदि हाँ, तो इसका Safe Sequence क्या होगा?
| Process | Current Allocation | Max Requirement |
|---|---|---|
| P0 | 3 | 7 |
| P1 | 2 | 4 |
| P2 | 2 | 5 |
स्टेप-बाय-स्टेप हल:
- स्टेप 1: कुल एलोकेटेड और उपलब्ध (Available) रिसोर्स निकालें:
कुल एलोकेटेड रिसोर्स = 3 + 2 + 2 = 7
चूंकि कुल रिसोर्स 10 हैं, इसलिए वर्तमान में Available = 10 - 7 = 3 - स्टेप 2: हर प्रोसेस की बची हुई जरूरत (Need) निकालें:
- Need of P_0 = 7 - 3 = 4
- Need of P_1 = 4 - 2 = 2
- Need of P_2 = 5 - 2 = 3 - स्टेप 3: प्रोसेसेज की रिक्वेस्ट को पूरा करें (Safe Sequence ढूंढें):
- हमारे पास Available = 3 है।
- क्या हम P_0 की जरूरत (4) पूरी कर सकते हैं? नहीं (4 > 3), तो P_0 इंतजार करेगी।
- क्या हम P_1 की जरूरत (2) पूरी कर सकते हैं? हाँ (2 \le 3)। हम P_1 को रिसोर्स देंगे, वह अपना काम खत्म करके अपने पुराने एलोकेटेड रिसोर्स (2) भी लौटा देगी।
नया Available = पुराना Available + Allocation of P_1 = 3 + 2 = 5 । (पहला सीक्वेंस मिला: P_1)
- अब हमारे पास Available = 5 है। हम P_2 की जरूरत (3) को आराम से पूरा कर सकते हैं (3 \le 5)। P_2 काम पूरा करके अपने रिसोर्स (2) लौटा देगी।
नया Available = 5 + 2 = 7 । (दूसरा सीक्वेंस मिला: P_2)
- अंत में, हमारे पास Available = 7 है। अब हम P_0 की जरूरत (4) भी पूरी कर सकते हैं। P_0 भी समाप्त हो जाएगी। (तीसरा सीक्वेंस मिला: P_0)
🎯 अंतिम परिणाम:
सिस्टम पूरी तरह से Safe State में है और इसका सुरक्षित अनुक्रम (Safe Sequence) < P_1, P_2, P_0 > है।
📝 निष्कर्ष (Conclusion)
प्रोसेस सिंक्रोनाइजेशन और डेडलॉक किसी भी मल्टीप्रोग्रामिंग ऑपरेटिंग सिस्टम की आत्मा हैं। सेमाफोर के वैल्यू वेरिएशंस (जैसे क्रिटिकल सेक्शन एंट्री-एग्जिट पर होने वाले बदलाव) और बैंकर एल्गोरिथ्म के रिसोर्स एलोकेशन मैट्रिक्स से एडवांस लेवल की परीक्षाओं में न्यूमेरिकल प्रश्न 100% बनते हैं। इन शॉर्ट-ट्रिक्स और सूत्रों की मदद से आप कम समय में सटीक उत्तर निकाल सकते हैं।
ऑपरेटिंग सिस्टम का पार्ट-2 यहाँ समाप्त होता है। अगले भाग यानी Part-3 में हम बहुत ही महत्वपूर्ण टॉपिक Memory Management (Paging, Segmentation, Virtual Memory & Page Replacement) को इसी प्रकार सरल और रेडी-टू-ब्लॉग फॉर्मेट में कवर करेंगे। पढ़ते रहिए, बढ़ते रहिए!
