Deadlock detection: current requests और resource bounds
लक्ष्य और model
Current deadlock detection को maximum-claim safety से अलग करें; छोटे allocation table को reduce करें; single-resource deadlock-free bound निकालें। पूर्वज्ञान: resource-graph/Banker-style safety पाठ। Resources reusable और एक type में identical हैं। Outstanding requests blocking हैं, resources बाहर से न आते न खोते हैं। Reduction model में आगे बढ़ सकने वाला process अंततः पूरा होकर allocation छोड़ता है। Failures या hidden synchronization dependencies नहीं।
1. अभी क्या चाहिए, बाद में कितना चाहिए हो सकता है?
Workshop में worker का current order अभी माँगे tools हैं। Declared maximum पूरे job में एक समय पर सबसे ज्यादा जरूरी tools हैं। दोनों अलग जानकारी हैं। Banker avoidance Need=Max−Allocation से देखता है कि सभी maximum claims किसी completion order में पूरी हो सकती हैं या नहीं। Detection current Request से देखता है कि अभी की waits possible releases से सुलझ सकती हैं या नहीं।
Zero Request का अर्थ zero maximum नहीं। Successful detection reduction current snapshot बताता है; बाद की request नया deadlock बना सकती है। उलटे, failed maximum-claim safety test से अभी कोई blocked है, यह सिद्ध नहीं होता।
2. Current table reduce करें
Work=Available से शुरू करें। Resource-holding processes unfinished रखें। ऐसा unfinished process खोजें जिसकी Request हर component में Work से अधिक न हो। मानें request पूरी हुई और process finish हुआ; उसे finished mark करके उसका pre-existing Allocation Work में जोड़ें। Net Work=Work+Allocation, क्योंकि temporary Request grant भी पुरानी allocation के साथ वापस आती है। कोई और process न हट सके तब तक दोहराएँ।
Conventional resource-holder detection में zero-allocation process को शुरू में finished mark कर सकते हैं: उसके पास दूसरों को resource cycle में फँसाने वाला कुछ नहीं। वह deadlocked group के पीछे blocked फिर भी हो सकता है; इसका मतलब actual termination नहीं। यहाँ finished reduction का bookkeeping marker है, observed CPU event नहीं। नीचे सभी numerical processes nonzero allocation रखते हैं, इसलिए शुरू में सब unfinished हैं।
3. Apparent cycle के बाहर से release
Resources (A,B), Available=(0,0), current state:
| Process | Allocation | Current Request |
|---|---|---|
| P0 | (1,0) | (0,1) |
| P1 | (0,1) | (1,0) |
| P2 | (1,1) | (0,0) |
Total=(2,2)। शुरू में P0,P1 नहीं चल सकते, पर P2 और कुछ नहीं माँगता। P2 हटाएँ: Work=(1,1)। P0 की (0,1) fit; उसके बाद Work=(2,1)। P1 की (1,0) fit; final Work=(2,2)। इसलिए P2,P0,P1 क्रम से सब reduce होते हैं। केवल P0,P1 की dependency deadlock सिद्ध नहीं करती: P2 दूसरे instances छोड़ सकता है। Final Work=total, स्वतंत्र arithmetic check है।
अब केवल P2 की Request=(1,1) करें। Work=(0,0); तीनों nonzero requests fit नहीं। Stated blocking/finish model में कोई release नहीं कर सकता। तीनों resource-holding unfinished processes deadlocked हैं। Available=0 अकेला criterion नहीं था; requests बदलने से उत्तर बदला।
4. Unsafe होकर भी अभी कोई blocked न हो
एक type के दो instances हैं। P0,P1 एक-एक रखते हैं; Available=0। दोनों का Max=2, इसलिए Need=1। दोनों maxima माँग सकते हों तो Banker safe sequence नहीं। पर अभी Requests=0 हों और actual remaining execution कोई और request न करे, तो कोई एक finish/release, फिर दूसरा finish कर सकता है: current deadlock नहीं। इसके बदले दोनों allocations रखकर एक और माँगें तो deadlock। Vector को Current Request या remaining maximum Need स्पष्ट label करें।
5. Resource bound derive करें
n processes, एक resource type लें। हर process का maximum simultaneous claim k≥1; requests claim के भीतर; remaining needs मिलें तो finish/release कर सकता है; कोई दूसरी blocking वजह नहीं। Sufficient worst-case count R=n(k−1)+1 है।
क्यों? हर process k से एक कम रखे तो maximum total n(k−1) held होगा। एक अतिरिक्त unit worst distribution में भी किसी एक को maximum तक पहुँचने देता है; वह finish/release करता है और बाकी आगे बढ़ते हैं। सामान्य रूप में किसी की remaining claim available में fit न हो तो held counts/shortfalls का योग R>n(k−1) से विरोधाभास देता है। यह model के अंतर्गत resource-deadlock guarantee है, unfair scheduler या unrelated locks के विरुद्ध नहीं।
n=3,k=3 पर R=7 पर्याप्त। R=6 guarantee नहीं: हर process को 2 देकर तीसरा माँगने दें। सभी छह held, सब waiting। इससे दिखता है कि सभी allocation patterns में resource-deadlock freedom guarantee करने वाला minimum 7 है। अलग maxima k_i के लिए same assumptions में bound 1+Σ(k_i−1)। अलग resource types जोड़कर यह single-type formula न लगाएँ।
6. Detection के बाद recovery अलग निर्णय है
Deadlocked set खोजने से कुछ release नहीं होता। Recovery में selected processes abort, work rollback या safely preserve/restore हो सकने वाले resource का preemption हो सकता है। Lost work और repeated victim selection की cost है; वही victim चुनते रहना starvation दे सकता है। केवल CPU quantum बदलने से blocked holder का resource release नहीं होता। ये policy consequences हैं, इस पाठ द्वारा किए actions नहीं।
परीक्षा checklist
Current Request और Need अलग columns में रखें। Resource conservation जाँचें; vectors componentwise compare करें; हर Work update और remaining unfinished holders का अर्थ लिखें। Bound में सभी single-type/max-claim assumptions दें और guarantee से एक कम पर failing allocation दिखाएँ।
मौलिक अभ्यास: छह single-correct MCQ
हर प्रश्न में ठीक एक विकल्प चुनें। हर प्रश्न की आवश्यक मान्यताएँ उसी में दी गई हैं।
DD01. Current resource-deadlock detection reduction में अभी कौन आगे बढ़ सकता है, इसके लिए Work से कौन सा vector compare करें?
A. Declared Max सीधे B. Current outstanding Request C. केवल Allocation का योग D. Process identifier
उत्तर: B
A: Max कुल declared claim है, current request नहीं।
B: Detection में current waits हेतु Request≤Work componentwise।
C: Allocation योग current unmet requests नहीं बताता।
D: PID resource need नहीं मापता।
DD02. Available=(0,0)। P0,P1,P2 allocations (1,0),(0,1),(1,1), current requests (0,1),(1,0),(0,0)। Request मिले तो process finish करके सब छोड़ सकता है। कौन सा order काम करता है?
A. P0,P1,P2 B. P1,P0,P2 C. P2,P0,P1 D. कोई process finish नहीं कर सकता
उत्तर: C
A: P0 को शुरू में unavailable B चाहिए।
B: P1 को शुरू में unavailable A चाहिए।
C: P2 (1,1) छोड़ता है; फिर P0 (1,0); उसके बाद P1।
D: P2 कुछ और नहीं माँगता और model में finish कर सकता है।
DD03. Available=(0,0)। P0,P1,P2 allocations (1,0),(0,1),(1,1); blocking current requests (0,1),(1,0),(1,1)। Request मिलने तक release नहीं। Detection result?
A. केवल P2 पहले finish करता है B. तीनों holders deadlocked रह जाते हैं C. Total (2,2) होने से deadlock नहीं D. सभी requests अभी fit हैं
उत्तर: B
A: P2 भी resources माँगता है; zero-request case की तरह नहीं चल सकता।
B: Zero Available में कोई nonzero request fit नहीं; कोई release नहीं।
C: Held resources available नहीं; total अकेला पर्याप्त नहीं।
D: तीनों requests में unavailable unit चाहिए।
DD04. एक type के दो instances। P0,P1 एक-एक रखते, Max=2 बताते, पर current request zero और आगे बिना request finish करेंगे। क्या सही है?
A. Remaining Max need 1 होने से अभी deadlocked B. Maximum claims पर unsafe, पर stated execution में current deadlock नहीं C. Request=0 होने से maximum claims पर safe D. किसी के पास resource नहीं
उत्तर: B
A: Need और Current Request अलग हैं।
B: Available=0 पर Max safe sequence नहीं, पर zero-request process finish/release कर सकता है।
C: Maximum safety में अभी भी हर Need=1 है।
D: हर process एक instance रखता है।
DD05. तीन processes एक identical resource type share करते हैं। हर एक अधिकतम 3 रखता है; remaining claim मिले तो finish कर सकता है; अन्य blocking नहीं। हर allocation pattern में resource deadlock से freedom का minimum total?
A. 3 B. 6 C. 7 D. 9
उत्तर: C
A: हर एक एक रखकर और माँग सकता है।
B: हर एक दो रखकर तीसरा माँगे तो कोई free नहीं।
C: n(k−1)+1=3×2+1=7; छह पर counterexample है।
D: नौ sufficient है पर minimum नहीं।
DD06. Detection में Work=(2,1)। Process Allocation=(1,2), Request=(1,1) रखता है। Request temporary grant होकर process सब release करता है। Net नया Work?
A. (3,3) B. (3,2) C. (4,4) D. (1,0)
उत्तर: A
A: Request घटाकर Allocation+Request लौटती है; net Work+Allocation=(3,3)।
B: यह पुरानी allocation की जगह केवल Request जोड़ता है।
C: Temporary Request grant दो बार गिनी गई।
D: यह grant के तुरंत बाद है, completion/release से पहले।
स्रोत और दायरा
यह मौलिक पाठ GATE 2026 course के मौजूदा OS foundations को आगे बढ़ाता है। इसका संबंध आधिकारिक 2026 syllabus के Section 8 से है; यह पूरे OS या GATE 2027 की पूर्ण तैयारी का दावा नहीं है। अभ्यास मौलिक हैं, पिछले वर्षों के प्रश्न नहीं।
- Official GATE 2026 CS syllabus, Section 8
- MIT Operating Systems Lecture Notes: Deadlock, Martin C. Rinard
स्रोत जाँचे गए: 2026-10-14।
प्रगति सहेजने के लिए साइन इन करें। साइन इन