ডেডলক অ্যাভয়ডেন্স — ব্যাংকার'স অ্যালগরিদম
এই পাঠে যা শিখবেন
- অ্যাভয়ডেন্স প্রিভেনশন (L24) থেকে ঠিক কীভাবে আলাদা — এবং কেন Max ঘোষণা করা জরুরি
- Available, Max, Allocation, Need — চারটি ডেটা স্ট্রাকচারের সুনির্দিষ্ট সংজ্ঞা
- ব্যাংকার'স সেফটি অ্যালগরিদমের প্রকৃত লজিক, ধাপে ধাপে
- Python-এ সম্পূর্ণ সেফটি অ্যালগরিদম প্রয়োগ করে একটি হাতে-যাচাই করা উদাহরণে নিরাপদ সিকোয়েন্স খুঁজে বের করা, এবং একটি পরিবর্তিত অনুরোধ কীভাবে সিস্টেমকে আনসেফ করে দিতো তা দেখা
১ · অ্যাভয়ডেন্স প্রিভেনশন থেকে কীভাবে আলাদা
L24-এর প্রিভেনশন চারটি শর্তের একটিকে কাঠামোগতভাবে অসম্ভব করে দেয় — নিয়মটি সবসময় প্রযোজ্য, প্রতিটি অনুরোধের বিস্তারিত না দেখেই। ডেডলক অ্যাভয়ডেন্স (Deadlock Avoidance)Deadlock Avoidanceচারটি শর্ত কাঠামোগতভাবে না ভেঙে, প্রতিটি রিসোর্স-অনুরোধ মঞ্জুর করার আগে ডায়নামিক্যালি যাচাই করা যে তা সিস্টেমকে একটি "নিরাপদ" অবস্থায় রাখবে কি না — নিরাপদ না রাখলে অনুরোধ প্রত্যাখ্যাত হয়। এর বদলে চারটি শর্ত কাঠামোগতভাবে ভাঙে না — বরং প্রতিটি প্রসেসকে তার সর্বোচ্চ সম্ভাব্য রিসোর্স-চাহিদা আগে থেকে ঘোষণা করতে হয়, এবং OS প্রতিটি অনুরোধ মঞ্জুর করার আগে ডায়নামিক্যালি হিসাব করে দেখে — এই অনুরোধ মঞ্জুর করলে সিস্টেম কখনো ডেডলকের দিকে যেতে পারবে এমন কোনো অবস্থায় পড়বে কি না। এমন কোনো ঝুঁকি থাকলে (এমনকি অনুরোধটি নিজে থেকে তাৎক্ষণিক ডেডলক না করলেও), সেটি প্রত্যাখ্যাত হয়।
২ · চারটি ডেটা স্ট্রাকচার
বর্তমানে প্রতিটি রিসোর্স টাইপের কতটি instance খালি আছে।
প্রতিটি প্রসেসের আগে থেকেই ঘোষিত, সর্বোচ্চ সম্ভাব্য চাহিদা (পুরো জীবনচক্রে সে সর্বোচ্চ কতটুকু চাইতে পারে)।
প্রতিটি প্রসেস বর্তমানে কতটি instance আসলে ধরে রেখেছে।
প্রতিটি প্রসেসের এখনো কতটুকু বাকি আছে, তার ঘোষিত সর্বোচ্চ চাহিদা পূরণ করতে।
$$Need[i] = Max[i] - Allocation[i]$$
৩ · সেফটি অ্যালগরিদম কীভাবে কাজ করে
সেফটি অ্যালগরিদম প্রশ্ন করে: এমন কোনো ক্রম আছে কি না, যেখানে প্রতিটি প্রসেস একে একে সম্পূর্ণভাবে শেষ হতে পারবে ধরে নিয়ে যে প্রতিটি প্রসেস তার Need বর্তমানে খালি থাকা রিসোর্স (Available) দিয়ে মেটাতে পারলেই চলবে-শেষ করবে-এবং তার সব বরাদ্দ ফেরত দেবে। ধাপে ধাপে —
- এমন একটি অসম্পূর্ণ প্রসেস খুঁজুন যার
Need ≤ Available(বর্তমানে খালি থাকা দিয়েই তার বাকি চাহিদা মেটানো সম্ভব)। - সেই প্রসেসটিকে "চালিয়ে দিন" — ধরে নিন সে শেষ করে তার সব
Allocationফেরত দিলো, তাইAvailable += Allocation[সেই প্রসেস]। - সেই প্রসেসটিকে সিকোয়েন্সে যোগ করুন, "সম্পন্ন" চিহ্নিত করুন।
- সব প্রসেস সম্পন্ন না হওয়া পর্যন্ত, বা আর কোনো প্রসেসের Need মেটানো সম্ভব না হওয়া পর্যন্ত ১-৩ ধাপ পুনরাবৃত্তি করুন।
সব প্রসেস সম্পন্ন হলে অবস্থাটি নিরাপদ; কোনো এক পর্যায়ে আর কাউকে এগিয়ে নেওয়া না গেলে অবস্থাটি আনসেফ।
৪ · উদাহরণ ডেটা — যাচাইয়ের জন্য
তিনটি প্রসেস (P0, P1, P2), দুই ধরনের রিসোর্স (A, B — মোট instance যথাক্রমে ১০ ও ৫টি):
| প্রসেস | Allocation (A,B) | Max (A,B) | Need = Max−Allocation |
|---|---|---|---|
| P0 | (3, 1) | (7, 3) | (4, 2) |
| P1 | (2, 1) | (3, 2) | (1, 1) |
| P2 | (2, 1) | (6, 3) | (4, 2) |
মোট বরাদ্দকৃত = (3+2+2, 1+1+1) = (7, 3)। মোট instance = (10, 5)। তাই Available = (10−7, 5−3) = (3, 2)।
৫ · কোড: সম্পূর্ণ সেফটি অ্যালগরিদম
নিচের কোড সেলে উপরের ঠিক এই ডেটা দিয়ে বাস্তব সেফটি অ্যালগরিদম চালানো হলো — Need গণনা, সেফ সিকোয়েন্স খোঁজা, এবং তারপর একটি নির্দিষ্ট অনুরোধ (P0 আরও (3, 1) চায়) সিস্টেমকে আনসেফ অবস্থায় নিয়ে যায় কি না তা পরীক্ষা করে সঠিকভাবে প্রত্যাখ্যান করা।
# ব্যাংকার'স সেফটি অ্যালগরিদম -- Available/Max/Allocation/Need নিয়ে বাস্তব সেফ-সিকোয়েন্স অনুসন্ধান
available = [3, 2] # (রিসোর্স A, রিসোর্স B) -- বর্তমানে খালি
allocation = {
"P0": [3, 1],
"P1": [2, 1],
"P2": [2, 1],
}
maximum = {
"P0": [7, 3],
"P1": [3, 2],
"P2": [6, 3],
}
def compute_need(maximum, allocation):
return {p: [maximum[p][j] - allocation[p][j] for j in range(len(available))] for p in maximum}
def is_safe(available, allocation, need):
"""সেফটি অ্যালগরিদম -- একটি সেফ সিকোয়েন্স খুঁজে বের করার চেষ্টা করে।
রিটার্ন করে (is_safe: bool, safe_sequence: list)।"""
work = list(available)
finish = {p: False for p in allocation}
sequence = []
processes = list(allocation.keys())
progress = True
while progress and len(sequence) < len(processes):
progress = False
for p in processes:
if finish[p]:
continue
if all(need[p][j] <= work[j] for j in range(len(work))):
for j in range(len(work)):
work[j] += allocation[p][j]
finish[p] = True
sequence.append(p)
progress = True
return all(finish.values()), sequence
need = compute_need(maximum, allocation)
print("Need ম্যাট্রিক্স:", need)
safe, sequence = is_safe(available, allocation, need)
print("বেস অবস্থা নিরাপদ কি না:", safe)
print("খুঁজে পাওয়া সেফ সিকোয়েন্স:", sequence)
print("\n--- অনুরোধ পরীক্ষা: P0 আরও [3, 1] (A, B) চায় ---")
process, request = "P0", [3, 1]
request_valid = (
all(request[j] <= need[process][j] for j in range(len(request))) and
all(request[j] <= available[j] for j in range(len(request)))
)
if not request_valid:
print("অনুরোধ অবৈধ -- ঘোষিত Max অথবা বর্তমান Available ছাড়িয়ে যায়")
else:
# হাইপোথেটিক্যালি মঞ্জুর করে দেখি -- আসল available/allocation/need বদলাচ্ছি না, একটি কপিতে পরীক্ষা করছি
hyp_available = [available[j] - request[j] for j in range(len(request))]
hyp_allocation = {p: list(allocation[p]) for p in allocation}
hyp_allocation[process] = [hyp_allocation[process][j] + request[j] for j in range(len(request))]
hyp_need = {p: list(need[p]) for p in need}
hyp_need[process] = [hyp_need[process][j] - request[j] for j in range(len(request))]
safe2, sequence2 = is_safe(hyp_available, hyp_allocation, hyp_need)
if safe2:
print(f"অনুরোধ গ্রহণযোগ্য -- মঞ্জুর করলেও সিস্টেম নিরাপদ থাকবে, সেফ সিকোয়েন্স: {sequence2}")
else:
print("অনুরোধ প্রত্যাখ্যাত -- মঞ্জুর করলে সিস্টেম আনসেফ অবস্থায় চলে যেতো (কোনো সেফ সিকোয়েন্স পাওয়া যায়নি)")
print(f"হাইপোথেটিক্যাল Available হতো: {hyp_available} -- এখান থেকে কোনো প্রসেসই আর এগোতে পারে না")"আনসেফ" মানেই কিন্তু ডেডলক ঘটবেই তা নয় — এর মানে ডেডলক ঘটা সম্ভব, যদি প্রসেসগুলো একটি নির্দিষ্ট দুর্ভাগ্যজনক ক্রমে চলে। ব্যাংকার'স অ্যালগরিদম রক্ষণশীল (conservative) — সামান্যতম ঝুঁকিও এড়িয়ে সবসময় সেফ অবস্থায় থাকার নিশ্চয়তা দেয়, এমনকি সেই ঝুঁকি বাস্তবে কখনো ঘটতোই না এমন হলেও।
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিজে কিছুক্ষণ ভাবুন — তারপর "→ উত্তর" চাপুন।
প্র ০১ "আনসেফ অবস্থা" ও "ডেডলকড অবস্থা" — এই দুটো কি একই জিনিস? পার্থক্যটা ব্যাখ্যা করুন।
না, ভিন্ন। ডেডলকড অবস্থা মানে বর্তমানেই একদল প্রসেস চিরকালের জন্য আটকে আছে — কেউ এগোতে পারছে না, এখনই। আনসেফ অবস্থা মানে শুধু এটুকু যে, কোনো সেফ সিকোয়েন্স পাওয়া যায়নি — অর্থাৎ প্রসেসগুলো যদি একটি নির্দিষ্ট দুর্ভাগ্যজনক ক্রমে চলতে থাকে, তাহলে ভবিষ্যতে ডেডলক ঘটতে পারে। বাস্তবে প্রসেসগুলো হয়তো এমনভাবে চলবে যে ডেডলক আসলে কখনোই ঘটবে না — কিন্তু ব্যাংকার'স অ্যালগরিদম সেই ঝুঁকি নিতে রাজি নয়, তাই আনসেফ হলেই প্রত্যাখ্যান করে।
প্র ০২ প্রতিটি প্রসেসকে আগে থেকে তার Max ঘোষণা করতে হয় — এটি L24-এর হোল্ড-অ্যান্ড-ওয়েট আক্রমণের মতো কোন বাস্তব সীমাবদ্ধতাই আবার নিয়ে আসে?
L24-এর হোল্ড-অ্যান্ড-ওয়েট আক্রমণেও প্রসেসকে তার সব প্রয়োজন আগে থেকে জানাতে হতো। এখানেও একই সীমাবদ্ধতা — অনেক বাস্তব প্রোগ্রাম চলতে চলতে সিদ্ধান্ত নেয় তার কী কী রিসোর্স লাগবে (ইনপুট বা ব্যবহারকারীর আচরণের উপর নির্ভর করে), তাই শুরুতেই নিখুঁত Max বলে দেওয়া বাস্তবে প্রায়ই কঠিন বা অসম্ভব। এই কারণেই ব্যাংকার'স অ্যালগরিদম বাস্তবে সীমিত পরিসরে ব্যবহৃত হয় (যেমন embedded/নির্দিষ্ট-উদ্দেশ্য সিস্টেমে, যেখানে চাহিদা আগে থেকেই সুনির্দিষ্ট)।
প্র ০৩
কোডে অনুরোধ পরীক্ষার প্রথম শর্তেই কেন request ≤ Need এবং request ≤ Available — দুটোই — যাচাই করা হলো, শুধু সেফটি-চেক চালানোর আগেই?
request ≤ Need নিশ্চিত করে প্রসেসটি তার নিজের ঘোষিত Max-এর বেশি চাইছে না (Max ছাড়িয়ে যাওয়া
একটি প্রোগ্রামিং ভুল বা চুক্তি-ভঙ্গ, সেফটির প্রশ্নই আসে না)। request ≤ Available নিশ্চিত করে
এই মুহূর্তে সিস্টেমে আদৌ এত রিসোর্স খালি আছে কি না — না থাকলে অনুরোধটি এখনই মঞ্জুর করা ভৌতভাবেই অসম্ভব,
সেফটি অ্যালগরিদম চালানোরও দরকার নেই। এই দুটো প্রাথমিক শর্ত পাস হলে তবেই "মঞ্জুর করলে কি নিরাপদ থাকবে"
প্রশ্নটি অর্থবহ হয়ে ওঠে।
অনুশীলন
-
চিন্তা করুন: বেস অবস্থায় (Available=(3,2)) কেন সেফটি অ্যালগরিদম P1-কে সবার আগে এগিয়ে নিতে পারলো, P0 বা P2-কে নয়?
P1-এর Need মাত্র (1,1) — এবং Available=(3,2) দিয়েই তা সহজে মেটানো সম্ভব (1≤3, 1≤2)। কিন্তু P0-এর Need (4,2) — 4 > 3 (Available-এর A) হওয়ায় সরাসরি মেটানো যায় না, আর P2-এর Need (4,2)-ও একই কারণে আটকে যায়। তাই প্রথম ধাপে একমাত্র P1-ই যোগ্য, এবং P1 শেষ হয়ে তার Allocation ফেরত দেওয়ার পরই Available যথেষ্ট বেড়ে P0/P2-এর পথ খুলে দেয়।
-
পরীক্ষা করুন: কোড সেলে অনুরোধ
request = [3, 1]-এর বদলেprocess, request = "P2", [1, 1]করে Run চেপে দেখুন এটি গ্রহণযোগ্য হয় কি না।P2 (Need=4,2) [1,1] চাইলে তা Need ও Available উভয়ের মধ্যেই থাকে, তাই বৈধ। হাইপোথেটিক্যাল Available হবে (2,1), P2-এর নতুন Need হবে (3,1)। সেফটি-চেক করলে দেখা যাবে P1 (Need 1,1) প্রথমে চলতে পারে (Available হয় 4,2), এরপর P2 (নতুন Need 3,1 ≤ 4,2) চলতে পারে (Available হয় 7,4), তারপর P0 (Need 4,2 ≤ 7,4)। ফলে সিকোয়েন্স <P1, P2, P0> পাওয়া যাবে এবং অনুরোধটি গ্রহণযোগ্য হিসেবে প্রিন্ট হবে — উপরের অনুরোধের (P0-এর [3,1]) বিপরীতে, যা প্রত্যাখ্যাত হয়েছিলো।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- ডেডলক প্রিভেনশন L24 প্রিভেনশনের কাঠামোগত নিয়ম বনাম অ্যাভয়ডেন্সের ডায়নামিক যাচাই — পার্থক্যটা আরেকবার মিলিয়ে দেখুন।
- ডেডলক ডিটেকশন ও রিকভারি পরবর্তী পাঠ প্রিভেনশন বা অ্যাভয়ডেন্স কোনোটাই ব্যবহার না হলে, ডেডলক ইতিমধ্যে ঘটে গেছে কি না তা কীভাবে ধরা যায়।
- কোর্সের সম্পূর্ণ সিলেবাস দেখুন ৫৬টি পাঠ M6-এর শেষ পাঠ ডিটেকশন ও রিকভারি — এরপর M7 মেমরি ম্যানেজমেন্ট শুরু হবে।