डेडलॉक बचाव: बैंकर एल्गोरिदम | Deadlock Avoidance: Banker's Algorithm

ऑपरेटिंग सिस्टम में डेडलॉक (Deadlock) एक ऐसी स्थिति है जहाँ दो या दो से अधिक प्रक्रियाएँ (Processes) एक-दूसरे द्वारा रोके गए संसाधनों (Resources) का इंतज़ार करती रहती हैं, और अंततः कोई भी प्रक्रिया आगे नहीं बढ़ पाती। इस गंभीर समस्या से बचने के लिए सबसे प्रभावी और लोकप्रिय तरीका बैंकर एल्गोरिदम (Banker's Algorithm) है।

नीचे इस एल्गोरिदम और डेडलॉक बचाव की प्रक्रिया का विस्तृत विवरण दिया गया है:

1. डेडलॉक बचाव (Deadlock Avoidance) क्या है?

डेडलॉक बचाव का मुख्य सिद्धांत यह है कि जब भी कोई प्रक्रिया किसी संसाधन के लिए अनुरोध (Request) करती है, तो सिस्टम पहले यह गणना करता है कि उस संसाधन को आवंटित करने के बाद सिस्टम "सुरक्षित अवस्था" (Safe State) में रहेगा या नहीं। यदि आवंटन के बाद सिस्टम असुरक्षित अवस्था में जाने का खतरा हो, तो संसाधन आवंटित नहीं किया जाता।

2. बैंकर एल्गोरिदम (Banker's Algorithm)

इस एल्गोरिदम का नाम 'बैंकर' इसलिए पड़ा क्योंकि इसका उपयोग बैंकिंग प्रणाली में यह सुनिश्चित करने के लिए किया जा सकता है कि बैंक के पास अपने सभी ग्राहकों की अधिकतम जरूरतों को पूरा करने के लिए पर्याप्त नकदी बनी रहे।

यह एक Resource Allocation Graph का विकल्प है और मल्टीपल इंस्टेंस वाले संसाधनों के लिए उपयुक्त है।

आवश्यक डेटा संरचनाएँ (Data Structures)

इस एल्गोरिदम को चलाने के लिए चार मुख्य मैट्रिक्स/वेक्टर की आवश्यकता होती है (मान लीजिए $n$ प्रक्रियाएँ हैं और $m$ संसाधन प्रकार हैं):

1. Available (उपलब्ध): यह एक वेक्टर है जो बताता है कि प्रत्येक प्रकार के कितने संसाधन वर्तमान में खाली हैं।
2. Max (अधिकतम): यह एक n × m मैट्रिक्स है जो यह बताता है कि प्रत्येक प्रक्रिया को अपना कार्य पूरा करने के लिए अधिकतम कितने संसाधनों की आवश्यकता हो सकती है।
3. Allocation (आवंटित): यह n × m मैट्रिक्स है जो बताता है कि वर्तमान में किस प्रक्रिया के पास कितने संसाधन हैं।

4. Need (आवश्यकता): यह मैट्रिक्स बताता है कि प्रक्रिया को पूरा होने के लिए अभी और कितने संसाधनों की जरूरत है।

सूत्र: Need [i] [j] = Max [i] [j] - Allocation[i] [j]

3. एल्गोरिदम के दो मुख्य भाग

बैंकर एल्गोरिदम मुख्य रूप से दो चरणों में काम करता है:

A. सुरक्षा एल्गोरिदम (Safety Algorithm)

यह जांचता है कि क्या सिस्टम एक "Safe State" में है।

1. Work और Finish नाम के दो वेक्टर लें। Work = Available और सभी प्रक्रियाओं के लिए Finish[i] = False सेट करें।

2. ऐसी प्रक्रिया $P_i$ खोजें जिसके लिए Finish[i] == False हो और उसकी Need <= Work हो।

3. यदि ऐसी प्रक्रिया मिल जाए, तो मान लें कि वह अपना काम पूरा कर लेगी और अपने पास रखे संसाधनों को छोड़ देगी:

• Work = Work + Allocation

• Finish[i] = True
• स्टेप 2 पर वापस जाएं।

1. यदि सभी प्रक्रियाओं के लिए Finish 'True' हो जाता है, तो सिस्टम Safe State में है।

कंप्यूटर सिस्टम क्या है और कैसे काम करता | Computer System Explained

B. संसाधन अनुरोध एल्गोरिदम (Resource-Request Algorithm)

जब कोई प्रक्रिया P_i संसाधनों के लिए अनुरोध करती है:

1. यदि Request_i ≤ Need_i, तो स्टेप 2 पर जाएं। (अन्यथा त्रुटि है क्योंकि प्रक्रिया अपनी अधिकतम सीमा से अधिक मांग रही है)।
2. यदि Request_i ≤ Available_, तो स्टेप 3 पर जाएं। (अन्यथा प्रक्रिया को इंतजार करना होगा)।
3. सिस्टम को "मान लेना" चाहिए कि उसने संसाधन आवंटित कर दिए हैं और डेटा को इस तरह अपडेट करें:

• Available = Available - Request_i
• Allocation_i = Allocation_i + Request_i
• Need_i = Need_i - Request_i

1. अब Safety Algorithm चलाएं। यदि सिस्टम 'Safe' है, तो संसाधन आवंटित कर दिए जाते हैं। यदि 'Unsafe' है, तो प्रक्रिया को इंतजार कराया जाता है और पुराना डेटा बहाल (Restore) कर दिया जाता है।

4. एक उदाहरण के माध्यम से समझें

मान लीजिए हमारे पास 3 प्रक्रियाएँ (P0, P1, P2) और एक प्रकार का संसाधन है जिसके कुल 10 इंस्टेंस हैं।

प्रक्रिया	Max	Allocation	Need (Max - Alloc)
P0	10	5	5
P1	4	2	2
P2	9	2	7

• कुल आवंटित: 5 + 2 + 2 = 9
• Available: 10 - 9 = 1

जांच:

1. क्या P1 की Need (2) ≤ Available (1) है? नहीं।

2. यहाँ कोई भी प्रक्रिया अपनी जरूरत पूरी नहीं कर पा रही। यह एक Unsafe State है। यदि P1 को पहले ही 3 आवंटित किए होते, तो वह काम पूरा कर संसाधन वापस कर देती, जिससे सिस्टम सुरक्षित रहता।

5. बैंकर एल्गोरिदम की सीमाएँ (Limitations)

हालांकि यह एल्गोरिदम डेडलॉक से बचाता है, लेकिन इसके कुछ व्यावहारिक नुकसान भी हैं:

• पूर्व ज्ञान की आवश्यकता: प्रक्रिया को शुरू होने से पहले ही बताना पड़ता है कि उसे अधिकतम कितने संसाधनों की जरूरत होगी, जो वास्तविक जीवन में कठिन है।

• निश्चित संसाधन: यह मानता है कि संसाधनों की संख्या स्थिर रहेगी, लेकिन हार्डवेयर खराब होने पर यह बदल सकती है।

• निश्चित प्रक्रियाएँ: इसमें माना जाता है कि प्रक्रियाओं की संख्या स्थिर है, जबकि आधुनिक सिस्टम में प्रक्रियाएँ आती-जाती रहती हैं।

• ओवरहेड: बार-बार गणना करने के कारण सीपीयू पर बोझ बढ़ता है।

निष्कर्ष

डेडलॉक से बचने के लिए बैंकर एल्गोरिदम एक "सतर्क" दृष्टिकोण है। यह संसाधनों के आवंटन से पहले भविष्य की संभावनाओं को मापता है। हालांकि यह थोड़ा धीमा हो सकता है, लेकिन यह सुनिश्चित करता है कि सिस्टम कभी भी ऐसी स्थिति में न फंसे जहाँ काम पूरी तरह रुक जाए। सुरक्षित अनुक्रम (Safe Sequence) की तलाश ही इस पूरे एल्गोरिदम का आधार है।

Deadlock Avoidance: The Banker's Algorithm

In operating systems, a Deadlock is a situation where a set of processes are blocked because each process is holding a resource and waiting for another resource acquired by some other process. To prevent the system from entering this frozen state, the most prominent strategy used is Deadlock Avoidance, specifically implemented through the Banker's Algorithm.

1. Understanding Deadlock Avoidance

Unlike deadlock detection (which fixes a problem after it occurs) or deadlock prevention (which sets strict rules to negate one of the four Coffman conditions), avoidance is a proactive approach.

The system maintains a state of "Safe" or "Unsafe." Every time a process requests a resource, the OS simulates the allocation to see if it would leave the system in a Safe State. If the resulting state is unsafe (meaning there is a potential for deadlock), the request is denied or delayed, even if the resource is currently free.

2. The Banker's Algorithm

Developed by Edsger Dijkstra, this algorithm is named after the banking system. Just as a bank never lends out all its cash at once to ensure it can satisfy the immediate needs of its customers, the OS ensures it retains enough resources to satisfy at least one process's maximum remaining requirements.

computer science question sloved part 1

Prerequisites and Data Structures

To function, the algorithm requires $n$ (number of processes) and $m$ (number of resource types). It uses the following matrices:

1. Available: A 1D array indicating the number of available resources of each type.
2. Max: An $n \times m$ matrix defining the maximum demand of each process.
3. Allocation: An $n \times m$ matrix defining the number of resources of each type currently allocated to each process.

4. Need: An $n \times m$ matrix indicating the remaining resource need of each process.

Formula: Need [i] [j] = Max [i] [j] - Allocation[i] [j]

3. How the Algorithm Works

The Banker’s Algorithm is divided into two sub-algorithms: the Safety Algorithm and the Resource-Request Algorithm.

A. Safety Algorithm (The "Check")

This algorithm determines if a system is in a safe state by looking for a Safe Sequence.

1. Initialize Work = Available and Finish[i] = False for all processes.

2. Find an index $i$ such that Finish[i] == False and Need[i] <= Work.

3. If found:

   • Assume the process finishes: Work = Work + Allocation[i]

   • Set Finish[i] = True

   • Repeat Step 2.

4. If all Finish[i] == True, then the system is in a Safe State.

B. Resource-Request Algorithm (The "Action")

When a process $P_i$ makes a request:

1. Check 1: Is Request_i ≤ Need_i? (If not, the process has exceeded its maximum claim).

2. Check 2: Is Request_i ≤ Available? (If not, the process must wait as resources aren't free).

3. Trial Allocation: The OS "pretends" to allocate the rresources.

   • Available = Available - Request_i

   • Allocation_i = Allocation_i + Request_i

   • Need_i = Need_i - Request_i

4. Safety Test: Run the Safety Algorithm.

   • If Safe: Grant the resources.

   • If Unsafe: Roll back the trial allocation and make the process wait.

4. Practical Example

Imagine 3 processes (P0, P1, P2) and a resource with 10 total units.

Process	Max Demand	Currently Allocated	Remaining Need
P0	10	5	5
P1	4	2	2
P2	9	2	7

• Total Allocated: 5 + 2 + 2 = 9
• Available: 10 - 9 = 1

Analysis:

The system checks if any process can finish with the 1 available unit.

• P0 needs 5 (Available is only 1)
• P1 needs 2 (Available is only 1)

• P2 needs 7 (Available is only 1)

None can finish. This is an Uunsafe State.If the OS had granted an earlier request that led to this, it would have failed to avoid a potential deadlock.

5. Advantages and Limitations

Advantages:

• It is less restrictive than Deadlock Prevention.
• It ensures the system never enters a state from which it cannot recover.

Disadvantages:

• Fixed Resources: It assumes the number of resources remains constant.
• Prior Knowledge: Processes must declare their maximum needs upfront, which is often impossible in dynamic environments.
• Efficiency: Running the algorithm on every request adds significant overhead to the CPU.
• Independent Processes: It assumes processes are independent and do not have synchronization constraints outside of resources.

Conclusion

The Banker's Algorithm is a cornerstone of theoretical operating system design. While its strict requirements (like knowing "Max Need") make it difficult to implement in general-purpose systems like Windows or Linux, it remains a vital concept for Real-Time Operating Systems (RTOS) and safety-critical environments where resource predictability is mandatory.