ডেডলক — চারটি প্রয়োজনীয় শর্ত
এই পাঠে যা শিখবেন
- ডেডলকের সুনির্দিষ্ট সংজ্ঞা এবং L21-এর ডাইনিং ফিলোসফার্সের সাথে এর সরাসরি সম্পর্ক
- ডেডলকের চারটি প্রয়োজনীয় শর্ত — প্রতিটির সুনির্দিষ্ট, নির্ভুল সংজ্ঞা
- রিসোর্স-অ্যালোকেশন গ্রাফ কী এবং এতে সাইকেল থাকা কেন ডেডলকের ইঙ্গিত দেয়
- Python দিয়ে DFS-ভিত্তিক সাইকেল-ডিটেকশন প্রয়োগ করে L21-এর ৫-ফিলোসফার ডেডলক দৃশ্যে সত্যিই একটি সাইকেল আছে কি না তা যাচাই
১ · ডেডলক কী — L21-এর সরাসরি ধারাবাহিকতা
L21-এ আমরা দেখেছি: ৫ জন ফিলোসফার সবাই একসাথে তাদের বাম ফর্ক তুলে নিলে, প্রত্যেকেই ডান ফর্কের জন্য চিরকাল অপেক্ষা করতে থাকে — কিন্তু ডান ফর্কটি তাদেরই এক প্রতিবেশী ধরে রেখেছে, যে নিজেও একই কারণে আটকে আছে। ডেডলক (Deadlock)Deadlockএকদল প্রসেস যেখানে প্রতিটি প্রসেস সেই একই দলের অন্য কোনো প্রসেসের ধরে-রাখা রিসোর্সের জন্য অপেক্ষা করছে, ফলে কোনো প্রসেসই কখনো এগোতে পারে না। হলো ঠিক এই পরিস্থিতির সাধারণ সংজ্ঞা — একদল প্রসেস, প্রতিটি সেই দলেরই আরেকজনের ধরে-রাখা রিসোর্সের জন্য অপেক্ষা করছে, ফলে কেউই কখনো এগোতে পারে না। ডাইনিং ফিলোসফার্স আসলে খাবার নিয়ে নয় — এটি ডাইকস্ট্রার তৈরি করা ডেডলকের একটি ক্লাসিক, কংক্রিট চিত্রায়ন মাত্র।
২ · চারটি প্রয়োজনীয় শর্ত
নিচের চারটি শর্তই একসাথে সত্যি হলে তবেই ডেডলক ঘটা সম্ভব — একটিও অনুপস্থিত থাকলে ডেডলক ঘটতে পারে না।
অন্তত একটি রিসোর্স অবশ্যই নন-শেয়ারেবল মোডে থাকতে হবে — একসময়ে কেবল একটি প্রসেসই তা ব্যবহার করতে পারে (L21-এ প্রতিটি ফর্ক একসাথে একজনের বেশি ব্যবহার করতে পারে না)।
অন্তত একটি রিসোর্স ধরে রেখে একটি প্রসেস অতিরিক্ত আরেকটি রিসোর্সের জন্য অপেক্ষা করছে (প্রতিটি ফিলোসফার বাম ফর্ক ধরে রেখেই ডান ফর্কের জন্য অপেক্ষা করছে)।
কোনো রিসোর্স জোরপূর্বক কেড়ে নেওয়া যায় না — যে প্রসেস তা ধরে রেখেছে, সে স্বেচ্ছায় ছেড়ে না দিলে অন্য কেউ তা নিতে পারে না।
দুই বা ততোধিক প্রসেসের একটি বৃত্তাকার চেইন থাকে, যেখানে প্রতিটি প্রসেস চেইনের পরবর্তীজনের ধরে-রাখা রিসোর্সের জন্য অপেক্ষা করছে (P0→F1→P1→F2→...→P4→F0 — এই চক্রটিই L21-এর মূল সমস্যা)।
চারটির যেকোনো একটি অনুপস্থিত থাকলে ডেডলক অসম্ভব হয়ে যায় — যেমন, যদি রিসোর্স প্রিএম্পশনের অনুমতি থাকতো (শর্ত ৩ ভাঙা), OS জোর করে একজনের ফর্ক কেড়ে অন্যজনকে দিয়ে দিতে পারতো, চক্রটি ভেঙে যেতো। এই পর্যবেক্ষণটাই M6-এর বাকি তিনটি পাঠের (L24 প্রিভেনশন, L25 অ্যাভয়ডেন্স, L26 ডিটেকশন) ভিত্তি — প্রতিটি কৌশল এই চারটি শর্তের কোনো না কোনোটিকে লক্ষ্য করে আক্রমণ করে বা পরিস্থিতি আগেভাগে যাচাই করে।
৩ · রিসোর্স-অ্যালোকেশন গ্রাফ
রিসোর্স-অ্যালোকেশন গ্রাফ (Resource-Allocation Graph)Resource-Allocation Graphএকটি ডিরেক্টেড গ্রাফ যেখানে নোড হলো প্রসেস ও রিসোর্স — অ্যাসাইনমেন্ট এজ (রিসোর্স→প্রসেস) দেখায় কোন রিসোর্স কার কাছে বরাদ্দ, আর রিকোয়েস্ট এজ (প্রসেস→রিসোর্স) দেখায় কোন প্রসেস কোন রিসোর্সের জন্য অপেক্ষমাণ। হলো একটি ডিরেক্টেড গ্রাফ — নোডগুলো প্রসেস ও রিসোর্স, দুই ধরনের এজ থাকে: অ্যাসাইনমেন্ট এজ (রিসোর্স → প্রসেস, "এই রিসোর্স ইতিমধ্যে এই প্রসেসকে বরাদ্দ") এবং রিকোয়েস্ট এজ (প্রসেস → রিসোর্স, "এই প্রসেস এই রিসোর্সের জন্য অপেক্ষমাণ")। এই গ্রাফে একটি সাইকেল (cycle) থাকা মানে ডেডলক সম্ভাব্য — এবং প্রতিটি রিসোর্স টাইপের মাত্র ১টি instance থাকলে (যেমন প্রতিটি ফর্ক), সাইকেল থাকা মানেই ডেডলক নিশ্চিত।
৪ · কোড: L21-এর দৃশ্যে সাইকেল যাচাই
নিচের কোড সেলে L21-এর ৫-ফিলোসফার/৫-ফর্ক নিখোঁজ-সমাধান দৃশ্যটিকে ঠিক এই রিসোর্স-অ্যালোকেশন গ্রাফ হিসেবে মডেল করা হলো, এবং একটি সাধারণ DFS-ভিত্তিক সাইকেল-ডিটেকশন ফাংশন দিয়ে যাচাই করা হলো সত্যিই একটি চক্র আছে কি না।
# রিসোর্স-অ্যালোকেশন গ্রাফ -- L21-এর ৫ ফিলোসফার / ৫ ফর্ক ডেডলক দৃশ্য মডেল করা
# assignment edge: fork -> philosopher (ফর্কটি তার কাছে বরাদ্দ/held, বাম ফর্ক)
# request edge: philosopher -> fork (ফিলোসফার সেই ফর্কের জন্য অপেক্ষমাণ, ডান ফর্ক)
n = 5
graph = {}
for i in range(n):
graph[f"F{i}"] = [f"P{i}"] # fork i -- philosopher i-র বাম ফর্ক, ইতিমধ্যে held
graph[f"P{i}"] = [f"F{(i + 1) % n}"] # philosopher i -- পরবর্তী ফর্কের (ডান ফর্ক) জন্য অপেক্ষমাণ
def find_cycle(graph):
"""সাধারণ DFS-ভিত্তিক ডিরেক্টেড-গ্রাফ সাইকেল ডিটেকশন (white/gray/black রঙ ব্যবহার করে)।"""
WHITE, GRAY, BLACK = 0, 1, 2
color = {node: WHITE for node in graph}
path = []
def dfs(node):
color[node] = GRAY
path.append(node)
for neighbor in graph.get(node, []):
if color.get(neighbor, WHITE) == GRAY:
idx = path.index(neighbor)
return path[idx:] + [neighbor] # সাইকেল পাওয়া গেছে
if color.get(neighbor, WHITE) == WHITE:
found = dfs(neighbor)
if found:
return found
color[node] = BLACK
path.pop()
return None
for node in graph:
if color[node] == WHITE:
found = dfs(node)
if found:
return found
return None
cycle = find_cycle(graph)
if cycle:
print("সাইকেল পাওয়া গেছে -- প্রতিটি রিসোর্সের ১টি instance থাকায় ডেডলক নিশ্চিত:")
print(" -> ".join(cycle))
else:
print("কোনো সাইকেল নেই -- এই দৃশ্যে ডেডলক ঘটছে না।")F0 -> P0 -> F1 -> P1 -> F2 -> P2 -> F3 -> P3 -> F4 -> P4 -> F0 —
পুরো ১০-নোডের চক্রটিই একটি একক সাইকেল, ঠিক L21-এর "সবাই বাম ফর্ক ধরে ডান ফর্কের জন্য আটকে আছে" পরিস্থিতির
গাণিতিক প্রতিচ্ছবি। যেহেতু প্রতিটি ফর্কের মাত্র ১টি instance আছে, এই সাইকেল মানেই ডেডলক নিশ্চিত — সম্ভাব্য নয়।
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিজে কিছুক্ষণ ভাবুন — তারপর "→ উত্তর" চাপুন।
প্র ০১ রিসোর্স-অ্যালোকেশন গ্রাফে সাইকেল থাকা মানেই কি সবসময় ডেডলক নিশ্চিত? কখন এটি শুধু "সম্ভাব্য" হয়?
না, সবসময় নয়। যদি প্রতিটি রিসোর্স টাইপের মাত্র ১টি instance থাকে (যেমন L21-এর প্রতিটি ফর্ক), সাইকেল থাকা মানেই ডেডলক নিশ্চিত। কিন্তু কোনো রিসোর্স টাইপের একাধিক instance থাকলে (যেমন ৩টি প্রিন্টার), একটি সাইকেল থাকলেও হয়তো অন্য কোনো instance খালি থাকতে পারে যা দিয়ে চক্রটি ভেঙে যেতে পারে — তখন সাইকেল কেবল "সম্ভাব্য ডেডলক" নির্দেশ করে, নিশ্চিত নয়। এই জটিলতাই L26-এর ডিটেকশন অ্যালগরিদমে একটি সাধারণীকৃত সেফটি-চেক-স্টাইল লজিক দরকার করে।
প্র ০২ উপরের গ্রাফে চারটি শর্তের মধ্যে কোনটি ঠিক কোথায় সত্যি হচ্ছে, সুনির্দিষ্টভাবে দেখান।
মিউচুয়াল এক্সক্লুশন — প্রতিটি ফর্ক একসাথে একজনের বেশি ব্যবহার করতে পারে না। হোল্ড-অ্যান্ড-ওয়েট — প্রতিটি
Pi ইতিমধ্যে Fi ধরে রেখেই F(i+1)%5-এর জন্য অপেক্ষা করছে। নো-প্রিএম্পশন
— কোনো ফিলোসফার তার প্রতিবেশীর হাত থেকে জোর করে ফর্ক কেড়ে নিতে পারে না। সার্কুলার ওয়েট — কোডে পাওয়া
F0→P0→F1→P1→...→P4→F0 চক্রটিই এই শর্তের সরাসরি প্রমাণ।
প্র ০৩
যদি graph["P4"] খালি তালিকা [] করে দেওয়া হয় (P4 কোনো ফর্ক চায় না ধরে নিলাম), তাহলে find_cycle() কী ফলাফল দেবে?
তখন P4 থেকে বের হওয়া কোনো এজ থাকবে না, তাই F0→P0→F1→P1→F2→P2→F3→P3→F4 পর্যন্ত পথ চলে গিয়ে P4-এ থেমে
যাবে (P4-এর কোনো প্রতিবেশী নেই), এবং DFS ব্যাকট্র্যাক করে অন্য কোনো আনভিজিটেড নোড থেকে আবার চেষ্টা করবে —
কিন্তু কোনো নোড থেকেই আর কোনো নতুন সাইকেল পাওয়া যাবে না। ফাংশন None রিটার্ন করবে, অর্থাৎ
"কোনো সাইকেল নেই" — চক্রটি ভাঙার এই ধারণাটিই L24-এর প্রিভেনশন কৌশলগুলোর মূল ভিত্তি।
অনুশীলন
-
চিন্তা করুন: কোড সেলের আউটপুটে পাওয়া সম্পূর্ণ চক্রটি হাতে কাগজে এঁকে যাচাই করুন প্রতিটি এজ সঠিক দিকে আছে কি না।
চক্রটি হলো
F0→P0→F1→P1→F2→P2→F3→P3→F4→P4→F0— প্রতিটিFi→Piএকটি অ্যাসাইনমেন্ট এজ (ফর্ক ইতিমধ্যে সেই ফিলোসফারের কাছে বরাদ্দ), আর প্রতিটিPi→F(i+1)%5একটি রিকোয়েস্ট এজ (ফিলোসফার পরের ফর্কের জন্য অপেক্ষমাণ) — মোট ১০টি নোড, ১০টি এজ, একটি একক বৃত্তাকার চক্র। -
পরীক্ষা করুন: কোড সেলে
graph["P2"] = []করে (P2 আর কোনো ফর্ক চায় না ধরে নিয়ে) Run চেপে দেখুন সাইকেল আর পাওয়া যায় কি না।P2-এর কোনো আউটগোয়িং এজ না থাকলে চক্রটিP2-এ এসে ভেঙে যাবে — DFSF0→P0→F1→P1→F2→P2পর্যন্ত গিয়ে থেমে যাবে, এবং কোনো নোড থেকেই আর নতুন সাইকেল খুঁজে পাবে না। ফলাফল: "কোনো সাইকেল নেই" — মাত্র একটি এজ সরিয়ে পুরো সার্কুলার-ওয়েট চেইনটি ভেঙে দেওয়া গেলো, যা প্রমাণ করে কেন সার্কুলার ওয়েট ভাঙা ডেডলক প্রতিরোধের এত কার্যকর একটি উপায় (L24-এ বিস্তারিত)।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- ক্লাসিক সিনক্রোনাইজেশন: ডাইনিং ফিলোসফার্স L21 এই পাঠের রিসোর্স-অ্যালোকেশন গ্রাফটি যে মূল দৃশ্য থেকে এসেছে, তা আরেকবার দেখে নিন।
- ডেডলক প্রিভেনশন পরবর্তী পাঠ এই চারটি শর্তের একটিকে কাঠামোগতভাবে ভেঙে দেওয়ার কৌশল — সার্কুলার-ওয়েট ভাঙার বাস্তব প্রয়োগসহ।
- কোর্সের সম্পূর্ণ সিলেবাস দেখুন ৫৬টি পাঠ ডেডলক মডিউল (M6) এই পাঠ থেকে শুরু — প্রিভেনশন, অ্যাভয়ডেন্স ও ডিটেকশন পরের তিন পাঠে।