Deadlock: resource graphs और safe states
लक्ष्य और model
Deadlock पहचानें, graph cycles की सावधानी से व्याख्या करें और छोटे allocation state की safety जाँचें। पूर्वज्ञान: locks और blocking। यहाँ resources reusable हैं; safety test के लिए processes maximum simultaneous demands बताते हैं; पूरा process अपने allocations लौटाता है। Arithmetic model में process failures या resources खोना नहीं है। Safety declared maximum claims पर जाँची जाती है, संभावित requests के अनुमान पर नहीं।
1. दो चाबियाँ, कोई progress नहीं
दो technicians सोचें। A के पास cabinet की अकेली चाबी है और वह workshop की अकेली चाबी चाहता है। B workshop की चाबी रखकर cabinet की चाबी चाहता है। दूसरी चाबी मिलने तक कोई पहली नहीं लौटाएगा। दोनों दूसरे के उस action की प्रतीक्षा कर रहे हैं जो वह कर नहीं सकता। यह deadlock है, केवल लंबा wait नहीं।
Classical resource deadlock की चार necessary conditions हैं: mutual exclusion, hold-and-wait, held resources का forced preemption न होना, और circular wait। Necessary का अर्थ यह नहीं कि इन policies की संभावना से current state deadlocked सिद्ध हो गया। Actual allocations और outstanding requests देखें।
Starvation अलग है: एक process बार-बार access हार सकता है जबकि बाकी progress करते हैं। Deadlock में एक group allowed transitions के अंतर्गत आगे नहीं बढ़ सकता। खत्म होने वाले device operation पर थोड़ी देर block होना अपने-आप deadlock या starvation नहीं।
2. Cycle से पहले arrow पढ़ें
Resource-allocation graph में P→R request है; resource instance R→P assignment है। हर resource type का ठीक एक instance हो तो usual blocking model में directed cycle deadlock बताता है। Cycle नहीं हो तो इस model में resource deadlock नहीं।
हल किया single-instance graph: R1→P1, P1→R2, R2→P2, P2→R1। P1 को R2 तभी मिलेगा जब P2 छोड़े; P2 को R1 तभी जब P1 छोड़े। दोनों blocked हैं, इसलिए cycle deadlock का प्रमाण है।
Multiple instances पर निष्कर्ष बदलता है। A के दो instances, B का एक है। P1 एक A रखकर B माँगता है। P2, B रखकर एक A माँगता है। P3 दूसरा A रखता है और उसे कुछ और नहीं चाहिए। Type-level cycle P1→B→P2→A→P1 है, फिर भी P3 पूरा होकर A छोड़ सकता है। फिर P2, A लेकर पूरा होगा और B छोड़ेगा; फिर P1 पूरा होगा। Multiple-instance resource types में cycle sufficient नहीं। Apparent cycle के बाहर के processes और हर instance का हिसाब रखें।
3. Prevention, avoidance, detection
Prevention design से कोई necessary condition तोड़ता है। सभी locks एक common strict order में लेने पर circular wait रुकता है: cycle में order लगातार बढ़कर अपने आरंभ पर वापस नहीं आ सकता। सारे resources साथ माँगना hold-and-wait हटा सकता है, पर utilization घट सकता है। सचमुच shareable resource को nonexclusive करने से उस पर mutual exclusion हटता है; हर resource सुरक्षित रूप से share नहीं हो सकता।
Avoidance maximum claims जैसी जानकारी से requests जाँचकर safe state बनाए रखता है। Detection allocations होने देता है और बाद में deadlock खोजता है। Recovery process termination या जहाँ सुरक्षित हो resources reclaim करके हो सकती है। ये अलग policies हैं। Lock ordering अपने-आप fair scheduling या हर starvation को नहीं रोकता।
4. दो resource types का safety algorithm
Allocation_i अभी held resources हैं और Max_i declared maximum। Need_i=Max_i−Allocation_i componentwise। Work=Available से शुरू करें। ऐसा unfinished process खोजें जिसकी Need_i≤Work हर component में हो। कल्पना करें कि उसे बाकी resources मिले, वह पूरा हुआ और सब लौटा दिए। Net update Work=Work+Allocation_i है, क्योंकि temporary Need grant भी वापस आ जाती है। दोहराएँ। सब पूरे हों तो state safe है और मिला order safe sequence। रुक जाएँ तो claims के अंतर्गत कोई safe sequence नहीं: state unsafe है, जरूरी नहीं कि अभी deadlocked हो।
हल किया state, resources (A,B):
| Process | Allocation | Max | Need |
|---|---|---|---|
| P0 | (1,0) | (3,2) | (2,2) |
| P1 | (1,1) | (2,1) | (1,0) |
| P2 | (1,1) | (3,2) | (2,1) |
Available=(1,1); total resources=(4,3)। शुरू में केवल P1 fit है। P1 के बाद Work=(1,1)+(1,1)=(2,2)। अब P0 fit; उसके बाद Work=(3,2)। P2 fit होकर (1,1) लौटाता है; final Work=(4,3), यानी total। इसलिए P1,P0,P2 safe sequence है। P1,P2,P0 भी सही है: sequence unique होना जरूरी नहीं। Max को सीधे Work में न जोड़ें और केवल components के योग की तुलना न करें।
5. Request उपलब्ध होकर भी unsafe हो सकती है
उसी state में P0, (1,0) माँगता है। यह Need=(2,2) और Available=(1,1), दोनों के भीतर है। Tentatively grant करने पर Available=(0,1), P0 Allocation=(2,0), Need=(1,2)। P1 को अभी (1,0), P2 को (2,1) चाहिए। किसी की Need, (0,1) में fit नहीं होती। Tentative state unsafe है। Avoidance algorithm request टालेगा, भले requested resource physically free है।
Unsafe का मतलब है maximum claims पूरी माँगी जाएँ तो guaranteed completion order नहीं। Processes कम माँगें या जल्दी छोड़ें तो फिर भी पूरा हो सकते हैं। इसलिए unsafe और already deadlocked समान नहीं। Safe certificate भी model तथा सही claims पर निर्भर है; arbitrary software bugs से सुरक्षा नहीं देता।
परीक्षा विधि
Instance counts और arrows लिखें। Safety test में Need nonnegative जाँचें; Allocation+Available से totals निकालें; vectors componentwise compare करें। हर Work update तथा final sequence लिखें। Request के लिए पहले Request≤Need और Request≤Available, फिर tentative grant और पूरा safety test करें। केवल Available देखकर grant न करें।
मौलिक अभ्यास: छह single-correct MCQ
हर प्रश्न में ठीक एक विकल्प चुनें। हर प्रश्न की आवश्यक मान्यताएँ उसी में दी गई हैं।
DL01. R1,R2 का एक-एक instance है। P1, R1 रखकर R2 चाहता है; P2, R2 रखकर R1 चाहता है। दूसरा मिले बिना कोई release नहीं कर सकता। State क्या है?
A. Safe क्योंकि दोनों के पास एक resource है B. Deadlocked C. केवल P1 terminated है D. केवल rescheduling से अवश्य सुलझेगा
उत्तर: B
A: दोनों को दूसरे का resource चाहिए।
B: दोनों दूसरे पर निर्भर हैं और release enabled नहीं।
C: Termination नहीं दी गई।
D: CPU scheduling missing release नहीं बना सकती।
DL02. Resource-allocation graph में directed cycle है, पर types के multiple instances हो सकते हैं। केवल cycle से क्या पता चलता है?
A. Deadlock निश्चित है B. Deadlock असंभव है C. अधिक allocation/request जानकारी चाहिए D. सभी processes समाप्त हैं
उत्तर: C
A: बाहर के instances release होकर wait तोड़ सकते हैं।
B: Cycle वास्तविक deadlock में भी हो सकती है।
C: Multiple instances में cycle अकेली sufficient नहीं।
D: Cycle termination नहीं बताती।
DL03. सभी threads locks एक ही strict increasing global order में लेते हैं; higher पकड़े lower नहीं माँगते। कौन सी necessary condition सीधे रुकती है?
A. Mutual exclusion B. Hold-and-wait C. No preemption D. Circular wait
उत्तर: D
A: Locks अभी exclusive हो सकते हैं।
B: Lower पकड़े higher माँगना अभी संभव है।
C: Resources अभी nonpreemptible हो सकते हैं।
D: Strictly increasing order अपने आरंभ तक cycle नहीं बना सकता।
DL04. Available=(1,1)। P0,P1,P2 allocations (1,0),(1,1),(1,1); maxima (3,2),(2,1),(3,2) हैं। कौन सा safe completion sequence है?
A. P0,P1,P2 B. P2,P0,P1 C. P1,P0,P2 D. कोई नहीं
उत्तर: C
A: P0 को शुरू में (2,2) चाहिए, जो fit नहीं।
B: P2 को (2,1) चाहिए, जो fit नहीं।
C: P1 Need=(1,0); Work फिर (2,2),(3,2),(4,3) होता है।
D: P1,P0,P2 सफल है।
DL05. P0,P1,P2 हेतु Available=(1,1), Allocation=(1,0),(1,1),(1,1), Max=(3,2),(2,1),(3,2)। Safety-based avoidance क्या P0 की (1,0) request तुरंत grant करे?
A. हाँ, क्योंकि available है B. नहीं, tentative state में safe sequence नहीं C. नहीं, P0 maximum claim से अधिक है D. हाँ, क्योंकि सभी needs zero हैं
उत्तर: B
A: Availability जरूरी है, पर्याप्त नहीं।
B: Grant के बाद Work=(0,1), needs (1,2),(1,0),(2,1); कोई fit नहीं।
C: Request P0 की remaining need (2,2) के भीतर है।
D: तीनों को resources अभी चाहिए।
DL06. Maximum-claim safety model में unsafe state का अर्थ क्या है?
A. सभी processes अभी सदा के लिए blocked हैं B. Declared remaining maximum needs पर safe sequence नहीं है C. हर process maximum पार कर गया है D. कोई physical resource गायब है
उत्तर: B
A: Unsafe current deadlock के समान नहीं; actual requests छोटी हो सकती हैं।
B: यही safety-test निष्कर्ष है।
C: Unsafe allocation individual maximum तोड़े बिना हो सकता है।
D: Unsafety completion guarantee की बात है, resource खोने की नहीं।
स्रोत और दायरा
यह मौलिक पाठ GATE 2026 course के मौजूदा OS foundations को आगे बढ़ाता है। इसका संबंध आधिकारिक 2026 syllabus के Section 8 से है; यह पूरे OS या GATE 2027 की पूर्ण तैयारी का दावा नहीं है। अभ्यास मौलिक हैं, पिछले वर्षों के प्रश्न नहीं।
स्रोत जाँचे गए: 2026-10-14।
प्रगति सहेजने के लिए साइन इन करें। साइन इन