1. परिचय: डाइनिंग फिलॉसफर्स समस्या और कॉफ़मैन की चार शर्तें (1971)

1965 में डच कंप्यूटर वैज्ञानिक एड्सगर डब्ल्यू. डाइक्स्ट्रा (Edsger W. Dijkstra) ने प्रसिद्ध ‘डाइनिंग फिलॉसफर्स समस्या’ (Dining Philosophers Problem) प्रस्तुत की: पाँच दार्शनिक \(P_0 \dots P_4\) एक गोल मेज़ के चारों ओर बैठे हैं; प्रत्येक दो प्लेटों के बीच केवल एक काँटा (\(F_0 \dots F_4\)) रखा है। भोजन करने के लिए प्रत्येक दार्शनिक को अपने बाएँ काँटे \(F_i\) और दाएँ काँटे \(F_{(i+1)\bmod 5}\) दोनों को एक साथ पकड़ना आवश्यक है। यदि पाँचों दार्शनिकों को एक ही माइक्रोसेकंड में भूख लगे और सभी एक साथ अपना बायाँ काँटा \(F_i\) उठा लें, तो प्रत्येक दार्शनिक अनंत काल तक अपने दाएँ पड़ोसी द्वारा दूसरा काँटा छोड़े जाने की प्रतीक्षा करता रहेगा — और संपूर्ण प्रणाली हमेशा के लिए थम जाएगी। इसे डेडलॉक (Deadlock / गतिरोध) कहते हैं।

औपचारिक रूप से, प्रक्रियाओं का एक अरिक्त उपसमुच्चय \(D \subseteq \mathcal{P}\) डेडलॉक अवस्था में कहलाता है यदि और केवल यदि \(D\) की प्रत्येक प्रक्रिया \(P_i \in D\) किसी ऐसी घटना (जैसे संसाधन की मुक्ति) की प्रतीक्षा में अवरुद्ध (Blocked) है जिसे केवल उसी प्रतीक्षा समुच्चय \(D\) की किसी अन्य प्रक्रिया \(P_j \in D\) द्वारा ही घटित किया जा सकता है।

1971 में एडवर्ड जी. कॉफ़मैन (Edward G. Coffman Jr.), एम. जे. एल्फ़िक और एरी शोशानी ने सिद्ध किया कि संसाधन डेडलॉक केवल तभी हो सकता है जब चार आवश्यक शर्तें एक साथ पूरी हों:

1. पारस्परिक अपवर्जन (Mutual Exclusion): कम से कम एक संसाधन अनन्य (गैर-साझा) मोड में धारित हो।
2. धारण और प्रतीक्षा (Hold and Wait): कोई प्रक्रिया पहले से कम से कम एक संसाधन धारण किए हुए हो और साथ ही अन्य प्रक्रियाओं द्वारा धारित अतिरिक्त संसाधनों को प्राप्त करने के लिए प्रतीक्षा कर रही हो।
3. अ-प्रीएम्प्शन (No Preemption): आवंटित संसाधनों को किसी प्रक्रिया से बलपूर्वक छीना नहीं जा सकता; उन्हें धारक द्वारा कार्य पूर्ण होने पर स्वेच्छा से ही मुक्त किया जाता है।
4. चक्रीय प्रतीक्षा (Circular Wait): प्रतीक्षारत प्रक्रियाओं की एक बंद श्रृंखला \(\{P_0, P_1, \dots, P_{k-1}\}\) विद्यमान हो जिसमें प्रत्येक \(P_i\) प्रक्रिया \(P_{(i+1)\bmod k}\) द्वारा धारित संसाधन की प्रतीक्षा कर रही हो।

चूँकि ये चारों शर्तें व्यक्तिगत रूप से आवश्यक हैं, इसलिए सिस्टम डिज़ाइन में इनमें से किसी एक भी शर्त को तार्किक रूप से नकार देने पर डेडलॉक गणितीय रूप से \(100\%\) असंभव हो जाता है।

2. संसाधन आवंटन ग्राफ़ (RAG) और चक्र प्रमेय (Holt, 1972)

1972 में रिचर्ड होल्ट ने संसाधनों की स्थिति को एक द्विभाजित दिष्ट ग्राफ़ — संसाधन आवंटन ग्राफ़ (RAG) \(G = (V, E)\) के रूप में मॉडल किया, जहाँ \(V = \mathcal{P} \cup \mathcal{R}\) (प्रक्रिया शीर्ष \(P_i\) तथा \(W_j \ge 1\) समरूप इंस्टेंस वाले संसाधन प्रकार शीर्ष \(R_j\)), अनुरोध कोरें \(P_i \to R_j\) और आवंटन कोरें \(R_j \to P_i\) होती हैं।

ग्राफ़ \(G\) में दिष्ट चक्र (Directed Cycle) और डेडलॉक के बीच तीन मूलभूत प्रमेय हैं:

• प्रमेय 1 (अचक्रीयता \(\implies\) डेडलॉक-मुक्ति): यदि \(G\) में कोई दिष्ट चक्र नहीं है (अर्थात \(G\) एक DAG है), तो कोई भी प्रक्रिया डेडलॉक में नहीं है।
• प्रमेय 2 (एकल-इंस्टेंस आवश्यक और पर्याप्त प्रमेय): यदि प्रत्येक संसाधन प्रकार का केवल एक इंस्टेंस (\(\forall j, W_j = 1\)) है, तो \(G\) में दिष्ट चक्र \(\iff\) डेडलॉक।
• प्रमेय 3 (बहु-इंस्टेंस अपर्याप्तता प्रमेय): यदि किसी संसाधन प्रकार के एक से अधिक इंस्टेंस (\(\exists j, W_j > 1\)) हैं, तो दिष्ट चक्र का होना डेडलॉक के लिए आवश्यक शर्त तो है, किंतु पर्याप्त शर्त नहीं है!

  flowchart TD
    subgraph RAG_Single["केस A: एकल-इंस्टेंस RAG (चक्र <==> निश्चित डेडलॉक)"]
        PA1(("P1 (अवरुद्ध)")) -->|"अनुरोध"| RA1["R1 (1 इंस्टेंस: ●)"]
        RA1 -->|"आवंटित"| PA2(("P2 (अवरुद्ध)"))
        PA2 -->|"अनुरोध"| RA2["R2 (1 इंस्टेंस: ●)"]
        RA2 -->|"आवंटित"| PA1
    end

    subgraph RAG_Multi["केस B: बहु-इंस्टेंस RAG (चक्र P1->R1->P3->R2->P1 है, पर कोई डेडलॉक नहीं!)"]
        PB1(("P1 (अवरुद्ध)")) -->|"अनुरोध"| RB1["R1 (2 इंस्टेंस: ●●)"]
        RB1 -->|"इंस्टेंस #1"| PB3(("P3 (अवरुद्ध)"))
        PB3 -->|"अनुरोध"| RB2["R2 (2 इंस्टेंस: ●●)"]
        RB2 -->|"इंस्टेंस #1"| PB1
        RB1 -->|"इंस्टेंस #2"| PB2(("P2 (चालू: कोई अनुरोध नहीं!)"))
        RB2 -->|"इंस्टेंस #2"| PB4(("P4 (चालू: कोई अनुरोध नहीं!)"))
    end

केस B में यद्यपि चक्र \(P_1 \to R_1 \to P_3 \to R_2 \to P_1\) मौजूद है, फिर भी \(P_2\) और \(P_4\) की बाह्य-डिग्री \(0\) है (सक्रिय सिंक): जैसे ही वे अपना कार्य पूरा कर \(R_1\) और \(R_2\) के इंस्टेंस मुक्त करेंगी, चक्र स्वतः टूट जाएगा!

3. रणनीति 1 (रोकथाम): संपूर्ण लॉक क्रम (Total Lock Ordering) की विरोधाभास से उत्पत्ति

OS कर्नेल (जैसे Linux का lockdep) और मल्टीथ्रेडेड प्रोग्रामिंग में चौथी शर्त (चक्रीय प्रतीक्षा) को संपूर्ण लॉक क्रम (Total Lock Ordering) द्वारा समाप्त किया जाता है: प्रत्येक म्यूटेक्स \(L \in \mathcal{L}\) को एक अद्वितीय वैश्विक रैंक \(\phi(L) \in \mathbb{N}\) दी जाती है, और लॉक समुच्चय \(\mathcal{H}\) धारण करने वाला कोई भी थ्रेड नया लॉक \(L_{\text{new}}\) केवल तभी माँग सकता है जब उसकी रैंक строго अधिक हो:

【विरोधाभास द्वारा प्रमाण】: मान लीजिए कि \(k \ge 2\) लंबाई का एक चक्रीय प्रतीक्षा चक्र \(\{P_0, P_1, \dots, P_{k-1}\}\) बन जाता है, जहाँ \(P_i\) लॉक \(L_i\) को पकड़े हुए है और \(L_{(i+1)\bmod k}\) की प्रतीक्षा कर रहा है। चूँकि प्रत्येक थ्रेड लॉक क्रम नियम का पालन करता है, पूरे चक्र में असमिकाओं को जोड़ने पर:

चूँकि कोई भी प्राकृत संख्या स्वयं से सख्त छोटी नहीं हो सकती, यह एक विरोधाभास (\(\bot\)) है! अतः चाहे बैंक खाता अंतरण हो (हमेशा छोटे ID वाले खाते को पहले लॉक करना) या डाइनिंग फिलॉसफर्स (\(P_4\) द्वारा बाएँ काँटे \(F_4\) से पहले दायाँ काँटा \(F_0\) उठाना, क्योंकि \(0 < 4\)), चक्रीय प्रतीक्षा गणितीय रूप से असंभव हो जाती है। \(\blacksquare\)

4. रणनीति 2 (परिहार): डाइक्स्ट्रा का बैंकर एल्गोरिदम (5×3 मैट्रिक्स ट्रेस)

जब लॉक क्रम पहले से तय न हो सके, तो डाइक्स्ट्रा का बैंकर एल्गोरिदम (1965 / Habermann, 1969) प्रत्येक प्रक्रिया से उसकी अधिकतम माँग \(\mathbf{Max}\) की पूर्व घोषणा करवाता है और प्रत्येक आवंटन से पहले \(O(m \cdot n^2)\) समय में जाँचता है कि क्या परिणामी अवस्था कम से कम एक सुरक्षित अनुक्रम (Safe Sequence) वाली सुरक्षित अवस्था (Safe State) बनी रहती है (\(\text{डेडलॉक} \subsetneq \text{असुरक्षित अवस्था}\))।

\(n=5\) प्रक्रियाओं \(\{P_0 \dots P_4\}\) और \(m=3\) संसाधनों \(\mathbf{Total} = (A=10, B=5, C=7)\) वाली प्रणाली में कुल आवंटित \((7,2,5)\) होने पर प्रारंभिक उपलब्ध सदिश \(\mathbf{Available} = (10,5,7) - (7,2,5) = \mathbf{(3, 3, 2)}\) है:

सुरक्षित अनुक्रम \(\langle P_1, P_3, P_4, P_0, P_2 \rangle\) सिद्ध करता है कि अवस्था \(t_0\) सुरक्षित है। यदि \(P_1\) अब \((1,0,2)\) माँगता है, तो अस्थायी आवंटन के बाद \(\mathbf{Available}=(2,3,0) \ge \mathbf{Need}_1=(0,2,0)\) सुरक्षित रहता है (तुरंत स्वीकृत)। किंतु यदि तुरंत बाद \(P_0\) सदिश \((0,2,0)\) माँगता है, तो उपलब्ध संसाधन घटकर \((2,1,0)\) रह जाते हैं जिससे किसी भी प्रक्रिया की \(\mathbf{Need}\) पूरी नहीं हो सकती (असुरक्षित अवस्था): बैंकर एल्गोरिदम इसे अस्वीकार कर \(P_0\) को ब्लॉक कर देता है!

5. रणनीति 3 व 4 (WFG पहचान, Wait-Die/Wound-Wait, शुतुरमुर्ग) और Livelock बनाम Starvation

रिलेशनल डेटाबेस (PostgreSQL, MySQL InnoDB) वेट-फ़ॉर ग्राफ़ (WFG) बनाते हैं और \(O(|V|+|E|)\) DFS द्वारा चक्र ढूँढकर सबसे कम Undo लॉग वाले पीड़ित ट्रांज़ैक्शन को रोलबैक करते हैं (MySQL में तुरंत; PostgreSQL में deadlock_timeout = 1s बाद)। वितरित डेटाबेस (Google Spanner) रोज़ेनक्रांत्ज़ आदि (1978) के टाइमस्टैम्प \(\text{TS}(T_i)\) आधारित Wait-Die (गैर-प्रीएम्प्टिव) और Wound-Wait (प्रीएम्प्टिव, कम व्यर्थ रीस्टार्ट) प्रोटोकॉल अपनाते हैं, तथा स्टार्वेशन रोकने के लिए रीस्टार्ट पर मूल टाइमस्टैम्प \(\text{TS}(T_i)\) को सुरक्षित रखते हैं। अत्यंत दुर्लभ OS टेबल रिक्तीकरण के लिए UNIX/Windows शुतुरमुर्ग एल्गोरिदम (Ostrich Algorithm) अपनाकर समस्या को अनदेखा करते हैं ताकि दैनिक सिस्टम कॉल धीमे न हों।

  flowchart TD
    Req["वितरित ट्रांज़ैक्शन Ti, Tj द्वारा धारित लॉक का अनुरोध करता है"] --> Cmp{"प्रारंभ टाइमस्टैम्प तुलना: क्या TS(Ti) < TS(Tj) है?<br/>(क्या अनुरोधकर्ता Ti धारक Tj से अधिक पुराना/वरिष्ठ है?)"}
    Cmp -->|"हाँ: Ti वरिष्ठ है (Older)"| WD1["[Wait-Die (गैर-प्रीएम्प्टिव)]: वरिष्ठ Ti कनिष्ठ Tj की प्रतीक्षा करता है (वरिष्ठ -> कनिष्ठ)<br/>[Wound-Wait (प्रीएम्प्टिव)]: वरिष्ठ Ti कनिष्ठ Tj को घायल (रोलबैक) कर लॉक छीन लेता है!"]
    Cmp -->|"नहीं: Ti कनिष्ठ है (Younger)"| WD2["[Wait-Die (गैर-प्रीएम्प्टिव)]: कनिष्ठ Ti स्वयं समाप्त होता है (मूल TS के साथ पुनः प्रयास)<br/>[Wound-Wait (प्रीएम्प्टिव)]: कनिष्ठ Ti शांत रहकर वरिष्ठ Tj की प्रतीक्षा करता है (कनिष्ठ -> वरिष्ठ)"]

अंत में, तीनों लाइवनेस विफलताओं (Liveness Failures) की तुलना: