Deadlock avoidance আর detection — Banker's algorithm

১ · প্রতিরোধ, এড়ানো, নাকি খুঁজে বের করা

পর্ব ২৭-এ দেখেছেন, deadlock হতে চারটি শর্ত একসাথে লাগে — mutual exclusion, hold and wait, no preemption আর circular wait. সেখানে prevention-এর কৌশলও দেখেছেন: নকশা দিয়েই চারটির অন্তত একটি অসম্ভব করে দেওয়া, যেমন সব lock একটি নির্দিষ্ট ক্রমে নেওয়া। Prevention নিরাপদ, কিন্তু প্রায়ই অপচয়ী — resource অকারণে আটকে থাকে, বা প্রোগ্রাম লেখা কঠিন হয়।

এই পর্বে বাকি দুটি পথ। Deadlock avoidance-এ চারটি শর্ত ভাঙা হয় না; বদলে OS প্রতিটি অনুরোধের সময় হিসাব করে, এখন দিলে ভবিষ্যতে আটকে যাওয়ার ঝুঁকি আছে কি না। এর জন্য আগাম তথ্য লাগে — প্রতিটি প্রসেস সর্বোচ্চ কত চাইবে। আর deadlock detection-এ OS কিছুই আটকায় না; deadlock হতে দেয়, মাঝে মাঝে খোঁজে, পেলে recovery করে।

শেষ সারিটি ঠাট্টা মনে হলেও Linux, Windows আর macOS সাধারণ প্রোগ্রামের lock আর resource-এর ক্ষেত্রে মূলত এটিই করে — প্রোগ্রামের deadlock প্রোগ্রামারের দায়িত্ব। তাহলে Banker's শিখে লাভ কী? তিনটি: পরীক্ষায় এটি সবচেয়ে বেশি আসা numerical-গুলোর একটি; “safe state” চিন্তাটি database, ক্লাউড আর embedded সিস্টেমে বারবার ফিরে আসে; আর detection algorithm বাস্তবে সত্যিই চলে — প্রায় প্রতিটি বড় database-এ।

২ · Safe state আর safe sequence

ধরুন সিস্টেমে n টি প্রসেস P₀ … P_n−1. প্রতিটি প্রসেস শুরুতে ঘোষণা করেছে সে সর্বোচ্চ কত resource চাইবে, আর একটি প্রসেস তার সর্বোচ্চ পেয়ে গেলে সীমিত সময়ে কাজ শেষ করে সব ফেরত দেয়।

অর্থাৎ safe sequence হলো একটি “পরিকল্পনা”: প্রথম জনকে এখনকার খালি resource দিয়েই শেষ করানো যায়; সে শেষ করে সব ফেরত দিলে দ্বিতীয় জনের জন্য যথেষ্ট হয়; এভাবে শেষ পর্যন্ত।

Safe ⇒ deadlock নেই — ছোট প্রমাণ

Unsafe ≠ deadlock — কেন

পাঠ্যবইয়ের একটি পরিচিত উদাহরণ দেখুন (সমিতির গল্পটিই, লাখ টাকার বদলে ১২টি tape drive). একটিমাত্র ধরনের resource, মোট ১২টি।

এই অবস্থা safe: <P1, P0, P2>. P1-এর Need ২ ≤ ৩, সে শেষ করলে খালি হয় ৫; P0-এর Need ৫ ≤ ৫, শেষে খালি ১০; P2-এর Need ৭ ≤ ১০, শেষে ১২. এখন ধরুন P2 আরও একটি drive চাইল, আর OS না ভেবে দিয়ে দিল। P2 ধরে ৩, Need ৬, খালি ২. P1 এখনো শেষ করতে পারে (খালি হয় ৪), কিন্তু তারপর P0-এর দরকার ৫, P2-এর ৬ — কেউই ৪ দিয়ে হয় না। কোনো safe sequence নেই: অবস্থাটি unsafe.

কিন্তু এটি কি deadlock? না, এখনো নয়। Max হলো “সবচেয়ে খারাপ হলে এতটা লাগতে পারে”-র ঘোষণা, বাধ্যবাধকতা নয়। P0 হয়তো আর একটিও drive না চেয়ে নিজের ৫টি দিয়েই কাজ শেষ করবে; তাহলে খালি হবে ৯, আর P2-এর ৬ মিটে যাবে। Deadlock হবে কেবল যদি P0 আর P2 দুজনেই সত্যিই নিজেদের পুরো বাকি চাহিদা চায়, আর সেই ক্রমে চায়। Unsafe মানে OS আর নিশ্চয়তা দিতে পারছে না — ভবিষ্যৎ অনুরোধের ওপর ফল নির্ভর করছে। তাই সম্পর্কটি তিন স্তরের:

Avoidance তাই ইচ্ছা করে সতর্ক: unsafe অবস্থায় ঢোকার আগেই থেমে যায়, যদিও অনেক unsafe অবস্থা থেকে বাস্তবে কিছুই খারাপ হতো না। এই সতর্কতার দাম — কখনো খালি resource থাকা সত্ত্বেও প্রসেসকে অপেক্ষা করানো — অংশ ৫-এ সংখ্যাসহ দেখবেন।

৩ · এক instance-এর resource — claim edge-সহ graph

প্রতিটি resource type-এর যদি একটিমাত্র instance থাকে (একটি printer, একটি lock), তাহলে Banker's-এর টেবিল লাগে না; পর্ব ২৭-এর resource-allocation graph-এ একটি নতুন ধরনের edge যোগ করলেই চলে — claim edge.

• Claim edge P_i ⇢ R_j (ভাঙা দাগ): “P_i ভবিষ্যতে R_j চাইতে পারে।” প্রসেস শুরুর আগেই সব claim edge ঘোষণা করতে হয়।
• অনুরোধ এলে: claim edge হয়ে যায় request edge P_i → R_j.
• মঞ্জুর হলে: request edge উল্টে assignment edge R_j → P_i. ছেড়ে দিলে আবার claim edge.
• নিয়ম: অনুরোধটি মঞ্জুর করা হয় কেবল যদি request edge-কে assignment edge-এ বদলালে graph-এ (claim edge-সহ) কোনো cycle না হয়। Cycle হলে অবস্থা unsafe, তাই resource খালি থাকলেও প্রসেস অপেক্ষা করে।

Cycle খোঁজার খরচ graph-এর edge-সংখ্যার সমানুপাতিক; n টি প্রসেসে edge সর্বোচ্চ n²-এর ক্রমে, তাই পাঠ্যবই একে O(n²) বলে। নিচে দুটি প্রসেস আর দুটি resource দিয়ে পুরো ঘটনাটি দেখুন।

1 declare: P1 may use R1, R2; P2 may use R1, R22 P1 requests R1  -> no cycle, GRANT3 P2 requests R1  -> R1 busy, P2 waits4 P2 requests R2  -> cycle with claim, DENY5 P1 requests R2  -> no cycle, GRANT6 P1 finishes     -> P2 gets R1, then R2

এই পদ্ধতি একাধিক instance-এ কাজ করে না: সেখানে cycle থাকলেও deadlock না-ও হতে পারে (পর্ব ২৭), তাই cycle-পরীক্ষা খুব কড়া হয়ে যায়। সেখানেই লাগে Banker's.

৪ · Banker's algorithm — চার টেবিল আর safety algorithm

ধরুন n টি প্রসেস আর m ধরনের resource. Banker's চারটি ডেটা স্ট্রাকচার রাখে:

দুটি ভেক্টর তুলনার নিয়ম: X ≤ Y মানে প্রতিটি j-এর জন্য X[j] ≤ Y[j]. যেমন (১, ২, ২) ≤ (৩, ৩, ২) সত্য, কিন্তু (৭, ৪, ৩) ≤ (৫, ৩, ২) মিথ্যা — একটি উপাদানও বড় হলে মিথ্যা।

Safety algorithm

1. Work = Available            // vector of length m
   Finish[i] = false for every i
2. find an i with Finish[i] == false and Need[i] <= Work
   (if several qualify, this course picks the LOWEST index)
   if no such i exists, go to step 4
3. Work = Work + Allocation[i] // Pi finishes and returns everything
   Finish[i] = true; append Pi to the sequence; go to step 2
4. if Finish[i] == true for all i: SAFE (the sequence is a safe sequence)
   else: UNSAFE

খরচ: ধাপ ২ প্রতিবার সর্বোচ্চ n টি প্রসেস দেখে, প্রতিটিতে m টি তুলনা; আর ধাপ ২–৩ সর্বোচ্চ n বার ঘোরে। মোট O(m·n²). পরীক্ষায় এই সংখ্যাটি প্রায়ই চাওয়া হয়।

পাঠ্যবইয়ের উদাহরণ

প্রশ্ন: পাঁচটি প্রসেস P0–P4, তিন ধরনের resource — A-এর মোট ১০টি, B-এর ৫টি, C-এর ৭টি। এই মুহূর্তের অবস্থা:

সিস্টেম কি safe? নিচে safety algorithm ধাপে ধাপে চলছে।

1 Work = Available = (3,3,2)2 P0? 7,4,3 no · P1: 1,2,2 <= 3,3,23 P0? no · P2? 6>5 no · P3: 0,1,1 ok4 P0: 7,4,3 <= 7,4,3 ok5 P2: 6,0,0 <= 7,5,3 ok6 P4: 4,3,1 <= 10,5,5 ok -> SAFE

নিচের simulator Need বের করে, প্রতিটি ধাপে Work দেখায়, তারপর তিনটি অনুরোধ একে একে বিচার করে (অনুরোধের নিয়ম অংশ ৫-এ)। সংখ্যা বদলে নিজের বইয়ের অনুশীলনী যাচাই করতে পারেন — তবে আগে হাতে করুন।

// Banker's algorithm: Need, safety check (lowest index first), request evaluation.
const max = [[7,5,3], [3,2,2], [9,0,2], [2,2,2], [4,3,3]];
let alloc = [[0,1,0], [2,0,0], [3,0,2], [2,1,1], [0,0,2]];
let avail = [3,3,2];
const fits = (a, b) => a.every((x, j) => x <= b[j]);           // a <= b, element by element
const needOf = al => al.map((row, i) => row.map((x, j) => max[i][j] - x));
function safe(av, al, show) {
  const need = needOf(al), work = [...av], fin = al.map(() => false), seq = [];
  for (let k = 0; k < al.length; k++) {
    const i = fin.findIndex((f, p) => !f && fits(need[p], work)); // lowest index first
    if (i < 0) break;
    const before = work.join(",");
    al[i].forEach((x, j) => work[j] += x); fin[i] = true; seq.push("P" + i);
    if (show) console.log("  P" + i + ": Need " + need[i] + " <= Work " + before + " -> Work " + work);
  }
  return fin.every(f => f) ? seq : null;
}
function request(p, req) {
  const tag = "P" + p + " requests (" + req + "): ";
  if (!fits(req, needOf(alloc)[p])) return console.log(tag + "ERROR, more than its Need");
  if (!fits(req, avail)) return console.log(tag + "WAIT, Available is only " + avail);
  const av2 = avail.map((x, j) => x - req[j]);                    // pretend to allocate
  const al2 = alloc.map((r, i) => i === p ? r.map((x, j) => x + req[j]) : [...r]);
  const seq = safe(av2, al2, false);
  if (!seq) return console.log(tag + "DENIED, new state unsafe -> roll back, P" + p + " waits");
  avail = av2; alloc = al2;
  console.log(tag + "GRANTED, Available = " + avail + ", safe sequence " + seq.join(" "));
}
console.log("Need: " + needOf(alloc).map((r, i) => "P" + i + "=" + r).join("  "));
console.log("Safety check, Work starts at " + avail);
console.log("Safe sequence: " + safe(avail, alloc, true).join(" "));
request(1, [1,0,2]);
request(4, [3,3,0]);
request(0, [0,2,0]);

Need: P0=7,4,3  P1=1,2,2  P2=6,0,0  P3=0,1,1  P4=4,3,1
Safety check, Work starts at 3,3,2
  P1: Need 1,2,2 <= Work 3,3,2 -> Work 5,3,2
  P3: Need 0,1,1 <= Work 5,3,2 -> Work 7,4,3
  P0: Need 7,4,3 <= Work 7,4,3 -> Work 7,5,3
  P2: Need 6,0,0 <= Work 7,5,3 -> Work 10,5,5
  P4: Need 4,3,1 <= Work 10,5,5 -> Work 10,5,7
Safe sequence: P1 P3 P0 P2 P4
P1 requests (1,0,2): GRANTED, Available = 2,3,0, safe sequence P1 P3 P0 P2 P4
P4 requests (3,3,0): WAIT, Available is only 2,3,0
P0 requests (0,2,0): DENIED, new state unsafe -> roll back, P0 waits

একই safety algorithm C-তে, যেভাবে পরীক্ষার খাতায় বা ইন্টারভিউতে লিখতে বলা হয়। এখানে Need আলাদা টেবিলে না রেখে max − alloc সরাসরি হিসাব করা হয়েছে:

#include <stdio.h>
#include <stdbool.h>
#define N 5   /* processes */
#define M 3   /* resource types A, B, C */

int alloc[N][M] = {{0,1,0}, {2,0,0}, {3,0,2}, {2,1,1}, {0,0,2}};
int max[N][M]   = {{7,5,3}, {3,2,2}, {9,0,2}, {2,2,2}, {4,3,3}};
int avail[M]    = {3, 3, 2};

int main(void) {
    int work[M], seq[N], count = 0;
    bool finish[N] = {false};
    for (int j = 0; j < M; j++) work[j] = avail[j];
    while (count < N) {
        int found = -1;
        for (int i = 0; i < N && found < 0; i++) {     /* lowest index first */
            if (finish[i]) continue;
            bool ok = true;
            for (int j = 0; j < M; j++)
                if (max[i][j] - alloc[i][j] > work[j]) ok = false;   /* Need > Work */
            if (ok) found = i;
        }
        if (found < 0) break;                            /* nobody can finish */
        for (int j = 0; j < M; j++) work[j] += alloc[found][j];
        finish[found] = true;
        seq[count++] = found;
    }
    if (count < N) { printf("UNSAFE: only %d of %d can finish\n", count, N); return 0; }
    printf("SAFE, sequence:");
    for (int k = 0; k < N; k++) printf(" P%d", seq[k]);
    printf("\nWork at the end: %d %d %d\n", work[0], work[1], work[2]);
    return 0;
}

SAFE, sequence: P1 P3 P0 P2 P4
Work at the end: 10 5 7

৫ · Resource-request algorithm — দেব, নাকি অপেক্ষা করাব

প্রসেস P_i একটি অনুরোধ-ভেক্টর Request_i নিয়ে এলে OS চারটি ধাপে সিদ্ধান্ত নেয় — এটিই resource-request algorithm:

1. Request_i ≤ Need_i? না হলে এটি ভুল (error) — প্রসেস নিজের ঘোষিত সর্বোচ্চের বেশি চাইছে। সাধারণত প্রসেসটিকে বন্ধ করা বা অনুরোধ বাতিল করা হয়।
2. Request_i ≤ Available? না হলে resource-ই নেই — P_i অপেক্ষা করে।
3. দিয়েছি ধরে নেওয়া (pretend): Available −= Request_i; Allocation_i += Request_i; Need_i −= Request_i.
4. Safety algorithm চালানো: নতুন অবস্থা safe হলে অনুরোধ মঞ্জুর। Unsafe হলে ধাপ ৩-এর বদল ফিরিয়ে নেওয়া (roll back), আর P_i অপেক্ষা করে।

এবার পাঠ্যবইয়ের তিনটি অনুরোধ, একটির পর একটি: প্রথমে P1 চায় (১, ০, ২); তারপর P4 চায় (৩, ৩, ০); তারপর P0 চায় (০, ২, ০)।

1 P1 asks (1,0,2): <= Need 1,2,2, <= Avail 3,3,22 pretend: Avail 2,3,0 · Need P1 0,2,03 safety: P1 P3 P0 P2 P4 -> GRANTED4 P4 asks (3,3,0): A 3 > Avail 2 -> WAIT5 P0 asks (0,2,0): checks pass; pretend6 safety: nobody fits 2,1,0 -> DENIED

একটি সূক্ষ্ম বিষয়: একই P0 (০, ২, ০) অনুরোধ যদি শুরুর অবস্থায় (P1-এর অনুরোধের আগে, Available = ৩, ৩, ২) আসত, তাহলে ধরে নেওয়ার পর Available হতো (৩, ১, ২), আর simulator-এর একই নিয়মে safe sequence মেলে <P3, P1, P0, P2, P4> — মঞ্জুর। অর্থাৎ একটি অনুরোধের রায় নির্ভর করে কখন এল তার ওপর; পরীক্ষায় প্রশ্নের অনুরোধগুলো আলাদা আলাদা (শুরুর অবস্থা থেকে) না পরপর — সেটি আগে স্পষ্ট পড়ে নিন।

৬ · Deadlock detection — হতে দিয়ে খুঁজে বের করা

Avoidance-এর দুই শর্ত — সবার Max আগে জানা, আর প্রতিটি অনুরোধে হিসাব — বেশিরভাগ সিস্টেমে মেলে না। Detection-এর জন্য ভবিষ্যৎ জানা লাগে না, শুধু এখন কে কী ধরে আছে আর কে কীসের জন্য অপেক্ষা করছে।

এক instance: wait-for graph

প্রতিটি resource-এর একটি instance হলে resource-allocation graph থেকে resource-এর node গুলো মুছে দিন: P_i → R → P_j (P_i চায় R, যা P_j-এর কাছে) হয়ে যায় P_i → P_j, অর্থাৎ “P_i অপেক্ষা করছে P_j-এর জন্য।” এটিই wait-for graph. এখানে cycle থাকা মানেই deadlock, আর cycle-এর প্রসেসগুলোই আটকে আছে। খোঁজার খরচ O(n²) (DFS দিয়ে cycle খোঁজা, পর্ব ২৭ আর DSA-র graph পর্ব)।

resource-allocation graph            wait-for graph
P1 -> R1 -> P2                         P1 -> P2
P2 -> R3 -> P3   (R = one instance)    P2 -> P3
P3 -> R2 -> P1                         P3 -> P1     cycle P1 -> P2 -> P3 -> P1: DEADLOCK
P4 -> R1 -> P2                         P4 -> P2     P4 waits, but is NOT in the cycle

লক্ষ করুন P4: সে আটকে থাকা P2-এর জন্য অপেক্ষা করছে, তাই কার্যত সেও থেমে আছে, কিন্তু cycle-এ নেই। Cycle ভাঙলে (যেমন P3 বন্ধ করলে) P2 এগোবে, আর P4-ও পরে পাবে।

একাধিক instance: detection algorithm

এখানে Banker's-এর মতো টেবিল লাগে, কিন্তু Max বা Need নেই — আছে Request: P_i এই মুহূর্তে কীসের জন্য আটকে আছে।

1. Work = Available
   Finish[i] = true  if Allocation[i] == 0   // holds nothing: cannot be part of a deadlock
   Finish[i] = false otherwise
2. find an i with Finish[i] == false and Request[i] <= Work   (lowest index first)
   if none, go to step 4
3. Work = Work + Allocation[i]; Finish[i] = true; go to step 2
4. every i with Finish[i] == false is DEADLOCKED

Safety algorithm-এর সাথে তিনটি পার্থক্য: Need-এর জায়গায় Request; কিছু না ধরে থাকা প্রসেস শুরু থেকেই Finish = true; আর ফলাফল শুধু “হ্যাঁ/না” নয় — কারা আটকে আছে তার তালিকা। খরচ একই, O(m·n²). ধাপ ৩-এ একটি আশাবাদী অনুমান আছে: যার Request মেটানো যায়, সে আর কিছু চাইবে না আর শেষ করবে। ভুল হলে ক্ষতি নেই — পরে সে আরও চাইলে পরের detection-এ ধরা পড়বে।

প্রশ্ন (পাঠ্যবইয়ের উদাহরণ): পাঁচটি প্রসেস P0–P4; A-এর মোট ৭টি, B-এর ২টি, C-এর ৬টি। Available = (০, ০, ০)।

অবস্থা ১-এ সিস্টেমে deadlock নেই (simulator-এর ক্রম <P0, P2, P1, P3, P4>). অবস্থা ২-এ শুধু একটি বদল — P2 আরও একটি C চায়। এবার কী হয়, দেখুন।

1 Work = (0,0,0); nobody has zero Allocation2 P0: Request 0,0,0 <= Work -> Work 0,1,03 P1 2,0,2 · P2 0,0,1 · P3 1,0,0 · P4 0,0,2: no4 Finish false: P1 P2 P3 P4 -> DEADLOCKED5 recovery test: abort P1, Work 2,1,06 P3 -> P2 -> P4 can now finish

// Deadlock detection, several instances per resource type (A, B, C).
// Request = what each process is waiting for RIGHT NOW (not a declared maximum).
function detect(title, avail, alloc, req) {
  console.log(title + " -- Work starts at " + avail);
  const work = [...avail];
  const fin = alloc.map(r => r.every(x => x === 0));  // holds nothing -> cannot be in a deadlock
  for (;;) {
    const i = fin.findIndex((f, p) => !f && req[p].every((x, j) => x <= work[j])); // lowest index
    if (i < 0) break;
    alloc[i].forEach((x, j) => work[j] += x);          // assume Pi finishes and returns everything
    fin[i] = true;
    console.log("  P" + i + ": Request " + req[i] + " <= Work -> Work " + work);
  }
  const stuck = fin.map((f, i) => f ? null : "P" + i).filter(Boolean);
  console.log(stuck.length ? "  DEADLOCKED: " + stuck.join(", ") : "  no deadlock");
}
const alloc = [[0,1,0], [2,0,0], [3,0,3], [2,1,1], [0,0,2]];   // A = 7, B = 2, C = 6 in total
detect("Case 1", [0,0,0], alloc, [[0,0,0], [2,0,2], [0,0,0], [1,0,0], [0,0,2]]);
detect("Case 2: P2 asks one more C", [0,0,0], alloc,
       [[0,0,0], [2,0,2], [0,0,1], [1,0,0], [0,0,2]]);

Case 1 -- Work starts at 0,0,0
  P0: Request 0,0,0 <= Work -> Work 0,1,0
  P2: Request 0,0,0 <= Work -> Work 3,1,3
  P1: Request 2,0,2 <= Work -> Work 5,1,3
  P3: Request 1,0,0 <= Work -> Work 7,2,4
  P4: Request 0,0,2 <= Work -> Work 7,2,6
  no deadlock
Case 2: P2 asks one more C -- Work starts at 0,0,0
  P0: Request 0,0,0 <= Work -> Work 0,1,0
  DEADLOCKED: P1, P2, P3, P4

কখন, কত ঘন ঘন চালাবেন

দুটি প্রশ্নের ওপর নির্ভর করে: deadlock কত ঘন ঘন হয়, আর হলে কতগুলো প্রসেস ক্ষতিগ্রস্ত হয়।

• প্রতিটি অনুরোধে, যা সঙ্গে সঙ্গে মেটানো যায় না: সবচেয়ে দ্রুত ধরা পড়ে, আর কোন অনুরোধটি cycle তৈরি করল তাও জানা যায় — কিন্তু খরচ সবচেয়ে বেশি।
• নির্দিষ্ট সময় পরপর (যেমন কয়েক মিনিট বা ঘণ্টায় একবার), বা যখন CPU-র ব্যবহার অস্বাভাবিকভাবে কমে যায় (deadlock হলে প্রসেসগুলো ঘুমিয়ে থাকে, CPU অলস হয়) — পাঠ্যবই এর উদাহরণ হিসেবে ৪০%-এর নিচে নামার কথা বলে। খরচ কম, কিন্তু ততক্ষণে আটকে থাকা দল বড় হয়ে যেতে পারে, আর কে “দোষী” তা বলা কঠিন।
• Database-এর বাস্তব উদাহরণ: PostgreSQL একটি lock-এর জন্য কিছুক্ষণ অপেক্ষার পর (ডিফল্ট deadlock_timeout ১ সেকেন্ড) তবেই wait-for graph পরীক্ষা করে — কারণ বেশিরভাগ অপেক্ষা deadlock নয়, আর প্রতিবার পরীক্ষা ব্যয়বহুল। MySQL-এর InnoDB ডিফল্টভাবে অপেক্ষা শুরু হতেই পরীক্ষা করে, আর খুব বেশি concurrency-তে এই পরীক্ষা বন্ধ করে শুধু lock-wait timeout-এর ওপর ভরসা করার সেটিংও রাখে। বিস্তারিত DBMS কোর্সের concurrency control পর্বে।

৭ · Recovery — বন্ধ করা, নাকি কেড়ে নেওয়া

Deadlock ধরা পড়লে দুটি পথ: প্রসেস বন্ধ করা, বা resource কেড়ে নেওয়া।

কাকে বন্ধ করবেন বা কার থেকে নেবেন (victim selection) — পাঠ্যবইয়ের মাপকাঠিগুলো, যাদের লক্ষ্য মোট খরচ সর্বনিম্ন রাখা:

• প্রসেসের priority কত
• এ পর্যন্ত কতক্ষণ চলেছে, আর শেষ হতে আর কতক্ষণ লাগবে
• কত resource আর কোন ধরনের ধরে আছে (সহজে কেড়ে নেওয়া যায় কি না)
• শেষ করতে আর কত resource লাগবে
• মোট কতগুলো প্রসেস বন্ধ করতে হবে
• প্রসেসটি interactive না batch (ব্যবহারকারী বসে আছেন কি না)

Starvation ঠেকানো: খরচের হিসাব যদি প্রতিবার একই প্রসেসকে সবচেয়ে “সস্তা” দেখায়, সে বারবার rollback হবে আর কখনো শেষ করবে না। সমাধান — খরচের সূত্রে এ পর্যন্ত কতবার rollback হয়েছে সেই সংখ্যাটি যোগ করা, যাতে প্রতিবার শিকার হলে পরের বার তাকে বেছে নেওয়ার খরচ বাড়ে। এটি পর্ব ১৮-এর aging-এর আত্মীয়। Database-এ এটি খুব বাস্তব: deadlock-এ একটি transaction-কে বাতিল (abort) করে rollback করা হয়, আর অ্যাপ্লিকেশন আবার চেষ্টা করে। InnoDB সাধারণত “ছোট” transaction — কম row বদলেছে এমনটি — বাতিলের জন্য বেছে নেয়।

৮ · Banker's বাস্তবে কেন কম, আর এর ছায়া কোথায়

Banker's সুন্দর, প্রমাণযোগ্য — তবু সাধারণ OS এটি চালায় না। কারণগুলো পরীক্ষায় “limitations” প্রশ্নের উত্তরও:

• Max আগে জানা যায় না। একটি ব্রাউজার বা ওয়েব সার্ভার কতগুলো lock, ফাইল বা কত মেমরি চাইবে, তা আগে থেকে বলা প্রায় অসম্ভব। বেশি করে ঘোষণা করলে Banker's অকারণে অপেক্ষা করায়।
• প্রসেসের সংখ্যা স্থির নয়। প্রসেস প্রতি মুহূর্তে তৈরি হয় আর শেষ হয়; algorithm ধরে নেয় একটি নির্দিষ্ট দল।
• Resource-এর সংখ্যাও স্থির নয়। একটি ডিস্ক নষ্ট হতে পারে, USB খোলা হতে পারে।
• “সীমিত সময়ে ফেরত দেবে” — নিশ্চয়তা নেই। একটি সার্ভিস দিনের পর দিন চলে।
• খরচ। হাজারো প্রসেস আর অনেক ধরনের resource-এ প্রতিটি অনুরোধে O(m·n²) চালানো চলে না।

তাহলে চিন্তাটি কোথায় বেঁচে আছে? যেখানেই আগে ঘোষণা করা চাহিদা দিয়ে “নিতে পারব কি না” সিদ্ধান্ত হয়:

• Admission control: real-time সিস্টেমে নতুন কাজ নেওয়ার আগে schedulability পরীক্ষা (পর্ব ২০), নেটওয়ার্কে নতুন সংযোগের আগে bandwidth আছে কি না দেখা — “ঘোষিত চাহিদা মেটানো যাবে কি না” প্রশ্ন।
• Kubernetes-এর resource request (উপমা হিসেবে): প্রতিটি pod আগে থেকে জানায় তার কত CPU আর মেমরি লাগবে, আর scheduler তাকে এমন node-এ বসায় যেখানে বাকি অনুরোধ-না-করা ক্ষমতা যথেষ্ট; namespace-এর ResourceQuota সীমা ছাড়ালে নতুন pod গ্রহণই করা হয় না। এটি Banker's-এর “Max ঘোষণা আর Available-এর সাথে তুলনা”-র মতো দেখতে, কিন্তু মনে রাখুন — এটি deadlock-এর safety পরীক্ষা নয়, শুধু ধারণক্ষমতার হিসাব; কোনো safe sequence খোঁজা হয় না।
• Database: avoidance নয়, detection — প্রায় প্রতিটি relational database-এ wait-for graph-ভিত্তিক deadlock detector আর victim বাতিল করার ব্যবস্থা আছে (অংশ ৬–৭)।
• Embedded আর নিরাপত্তা-সংবেদনশীল সিস্টেম: যেখানে কাজের তালিকা আগে থেকে স্থির, সেখানে নকশার সময়ই resource-এর চাহিদা বিশ্লেষণ করে deadlock-মুক্ততা যাচাই করা হয় — Banker's-এর চিন্তা, কিন্তু চলার সময় নয়, আগেই।

৯ · AI-এর যুগে Banker's algorithm

Banker's-এর অঙ্ক AI-কে দিলে উত্তর দ্রুত আসে, কিন্তু এই বিষয়ে কয়েকটি ভুল বারবার দেখা যায়:

AI-এর উত্তর মানার আগে — চেকলিস্ট

• Available = মোট − Allocation-এর যোগফল, নিজে হিসাব করেছি
• প্রতিটি ধাপে Need ≤ Work উপাদান ধরে ধরে মিলিয়েছি, আর Work-এ Allocation যোগ হয়েছে কি না দেখেছি
• শেষ Work মোট resource-এর সমান কি না দেখেছি
• অনুরোধগুলো পরপর নাকি আলাদা — প্রশ্নের নির্দেশ অনুযায়ী বিচার হয়েছে কি না দেখেছি
• উপরের simulator-এ একই সংখ্যা বসিয়ে ফল মিলিয়েছি
• বাস্তব সিস্টেমের দাবি (Linux, Windows, database) ডকুমেন্টেশন বা man page দিয়ে যাচাই করেছি; AI-এর দেওয়া কনকারেন্ট কোড “আমার মেশিনে চলে” বলে মেনে নিইনি, লোড দিয়ে পরীক্ষা করেছি