Deadlock — চারটি শর্ত, resource graph আর প্রতিরোধ

১ · ঢাকার মোড়ে জট — deadlock আসলে কী

অফিস ছুটির সময় ঢাকার কোনো চার রাস্তার মোড়ের কথা ভাবুন। সিগন্যাল বন্ধ, ট্রাফিক পুলিশও নেই। উত্তর দিক থেকে একটি বাস মোড়ের মাঝখানে ঢুকে পড়েছে, কিন্তু সামনে পূর্ব দিকের একটি প্রাইভেট কার দাঁড়িয়ে। সেই কার এগোতে পারছে না, কারণ তার সামনে দক্ষিণ দিকের একটি সিএনজি। সিএনজির সামনে পশ্চিম দিকের একটি ট্রাক, আর ট্রাকের সামনে — সেই প্রথম বাসটিই।

চারটি গাড়ির প্রত্যেকে রাস্তার এক টুকরো দখল করে পরের টুকরোর অপেক্ষায়। কেউ পিছু হটছে না, কেউ কাউকে তুলে সরাতেও পারছে না — বাইরের কেউ এসে একটি গাড়ি পিছিয়ে না দিলে এই gridlock কোনোদিন খুলবে না।

কম্পিউটারে ঠিক এই অবস্থার নাম deadlock. গাড়ির জায়গায় থ্রেড বা প্রসেস, রাস্তার টুকরোর জায়গায় lock, ফাইল, প্রিন্টার বা মেমরির মতো সম্পদ। সংজ্ঞাটি নিখুঁতভাবে বলা যায় এভাবে:

সবচেয়ে ছোট উদাহরণ লাগে মাত্র দুটি থ্রেড আর দুটি mutex. ধরুন একটি ব্যাংক সফটওয়্যারে দুটি হিসাব A আর B, প্রতিটির নিজের lock. থ্রেড T1 টাকা পাঠায় A থেকে B-তে, তাই আগে A-র lock নেয়, তারপর B-র। একই মুহূর্তে থ্রেড T2 টাকা পাঠায় B থেকে A-তে, তাই আগে B, তারপর A:

/* T1: transfer(A -> B) */          /* T2: transfer(B -> A) */
pthread_mutex_lock(&A);              pthread_mutex_lock(&B);
pthread_mutex_lock(&B);  /* waits */  pthread_mutex_lock(&A);  /* waits */
move_money();                        move_money();
pthread_mutex_unlock(&B);            pthread_mutex_unlock(&A);
pthread_mutex_unlock(&A);            pthread_mutex_unlock(&B);

বেশিরভাগ সময় এই কোড ঠিকঠাক চলে। কিন্তু scheduler যদি কোনোদিন ঠিক এই ক্রমে চালায় — T1 নিল A, তারপর T2 নিল B — তাহলে T1 B-র জন্য আর T2 A-র জন্য চিরকাল অপেক্ষা করবে। প্রোগ্রাম crash করে না, error-ও দেখায় না; শুধু থেমে থাকে, CPU ব্যবহার শূন্য। test-এ হাজারবার চলে, আর ভারী load-এ রাত তিনটায় সার্ভার আটকে যায় — এটাই deadlock-এর কুখ্যাত স্বভাব।

২ · System model — resource type, instance আর request → use → release

Deadlock নিয়ে নিখুঁতভাবে ভাবতে হলে আগে একটি সরল মডেল লাগে। পাঠ্যবইগুলো সিস্টেমকে এভাবে দেখে:

• Resource type: একই রকম সম্পদের একটি শ্রেণি — R₁, R₂, … R_m. যেমন “প্রিন্টার”, “CPU core”, “হিসাব A-র lock”, “ডেটাবেসের একটি সারি”।
• Instance: প্রতিটি type-এর কয়টি একক আছে। একটি mutex-এর instance সবসময় একটি; একটি অফিসে একই মডেলের ৩টি প্রিন্টার থাকলে “প্রিন্টার” type-এর ৩টি instance — যেকোনো একটি পেলেই কাজ চলে।
• ব্যবহারের তিন ধাপ: প্রতিটি প্রসেস একটি সম্পদ ব্যবহার করে এই ক্রমে — request (চাওয়া; না পেলে অপেক্ষা), use (ব্যবহার), release (ছেড়ে দেওয়া)। Request আর release হয় system call বা library ফাংশন দিয়ে: open/close, malloc/free, pthread_mutex_lock/unlock, semaphore-এর wait/signal.

একটি সূক্ষ্ম পার্থক্যও মনে রাখুন। Reusable resource (lock, প্রিন্টার, মেমরি) ব্যবহারের পর ফেরত আসে। Consumable resource (একটি বার্তা, একটি signal, pipe-এ লেখা ডেটা) একবার পেলে খরচ হয়ে যায়। দুই প্রসেস একে অপরের বার্তার অপেক্ষায় read-এ আটকে থাকলে সেটিও deadlock, যদিও কোনো lock নেই। তবে বাস্তবের বেশিরভাগ deadlock lock-এর, তাই এই পর্বের মূল আলোচনা reusable সম্পদ নিয়ে।

দুটি mutex দিয়ে আসল deadlock — আর তা ধরা

এবার উপরের বিপজ্জনক ক্রমটি ইচ্ছা করে ঘটাই। সমস্যা হলো, সত্যিকারের deadlock-এ প্রোগ্রাম চিরকাল আটকে থাকবে — অনলাইন রানারে চালানো যাবে না। তাই দুটি কৌশল: (১) একটি barrier দিয়ে দুই থ্রেডকে বাধ্য করি যাতে দুজনেই প্রথম lock নিয়ে তারপর দ্বিতীয়টি চায় — ফলে খারাপ interleaving প্রতিবারই ঘটে; (২) সাধারণ pthread_mutex_lock-এর বদলে timed lock pthread_mutex_timedlock, যা নির্দিষ্ট সময়ের বেশি অপেক্ষা করে না:

#include <errno.h>
#include <pthread.h>
#include <stdio.h>
#include <time.h>
static pthread_mutex_t A = PTHREAD_MUTEX_INITIALIZER, B = PTHREAD_MUTEX_INITIALIZER;
static pthread_barrier_t both_hold, both_tried;
struct worker { const char *name, *has, *wants; pthread_mutex_t *first, *second; int rc; };
static void *run(void *p) {
    struct worker *w = p;
    pthread_mutex_lock(w->first);              /* hold one lock ...               */
    pthread_barrier_wait(&both_hold);          /* force the bad interleaving      */
    struct timespec dl; clock_gettime(CLOCK_REALTIME, &dl);
    dl.tv_nsec += 300000000L;                  /* ... and wait at most 0.3 s      */
    if (dl.tv_nsec >= 1000000000L) { dl.tv_sec++; dl.tv_nsec -= 1000000000L; }
    w->rc = pthread_mutex_timedlock(w->second, &dl);
    pthread_barrier_wait(&both_tried);         /* nobody lets go before both tried */
    if (w->rc == 0) pthread_mutex_unlock(w->second);
    pthread_mutex_unlock(w->first);            /* recovery: release and back off  */
    return NULL;
}
int main(void) {
    struct worker t[2] = {{"T1", "A", "B", &A, &B, 0}, {"T2", "B", "A", &B, &A, 0}};
    pthread_t id[2];
    pthread_barrier_init(&both_hold, NULL, 2); pthread_barrier_init(&both_tried, NULL, 2);
    for (int i = 0; i < 2; i++) pthread_create(&id[i], NULL, run, &t[i]);
    for (int i = 0; i < 2; i++) pthread_join(id[i], NULL);
    for (int i = 0; i < 2; i++)
        printf("%s holds %s, waits for %s: %s\n", t[i].name, t[i].has, t[i].wants,
               t[i].rc == ETIMEDOUT ? "timed out" : "got it");
    if (t[0].rc == ETIMEDOUT && t[1].rc == ETIMEDOUT)
        printf("deadlock detected: T1 -> B -> T2 -> A -> T1\n");
    return 0;
}

T1 holds A, waits for B: timed out
T2 holds B, waits for A: timed out
deadlock detected: T1 -> B -> T2 -> A -> T1

৩ · চারটি শর্ত — কেন চারটিই লাগে

Coffman ও তাঁর সহকর্মীরা দেখান, deadlock ঘটতে হলে নিচের চারটি শর্ত একই সময়ে সত্য হতে হবে। এগুলোকে একসাথে বলে Coffman conditions. ঢাকার মোড়ের সাথে মিলিয়ে দেখুন:

প্রমাণ: deadlock থাকলে চারটিই সত্য

পরীক্ষায় প্রায়ই জিজ্ঞেস করা হয়, “শর্তগুলো প্রয়োজনীয় (necessary) কেন?” যুক্তিটি ছোট, কিন্তু সুন্দর। ধরুন D একটি deadlocked প্রসেসের দল। সংজ্ঞা অনুযায়ী D-র প্রতিটি প্রসেস এমন একটি সম্পদের অপেক্ষায়, যা D-রই আরেকটি প্রসেস ধরে আছে।

1. Circular wait: D-র প্রতিটি প্রসেস থেকে একটি তীর আঁকুন সেই প্রসেসের দিকে, যার জন্য সে অপেক্ষা করছে। প্রতিটি গিঁট থেকে অন্তত একটি তীর বেরোয়, আর গিঁটের সংখ্যা সসীম। তাই তীর ধরে হাঁটতে থাকলে একসময় আগে দেখা কোনো গিঁটে ফিরতেই হবে (pigeonhole নীতি) — অর্থাৎ একটি চক্র আছে।
2. Hold and wait: চক্রের প্রতিটি প্রসেস অপেক্ষা করছে (তার থেকে তীর বেরিয়েছে), আবার কিছু ধরেও আছে (তার দিকে আগের প্রসেসের তীর এসেছে, অর্থাৎ আগেরজন তার হাতের সম্পদ চাইছে)।
3. No preemption: সম্পদ কেড়ে নেওয়া গেলে OS চক্রের যেকোনো একটি সম্পদ কেড়ে অপেক্ষারতকে দিত, আর অপেক্ষা চিরকাল চলত না।
4. Mutual exclusion: সম্পদ ভাগ করা গেলে চাওয়ামাত্র পাওয়া যেত — কাউকে অপেক্ষাই করতে হতো না।

অতএব deadlock ⇒ চারটি শর্ত। উল্টো দিক থেকে পড়লে এটিই deadlock prevention-এর মূল সূত্র: যেকোনো একটি শর্তকে কখনো সত্য হতে না দিলে deadlock অসম্ভব।

৪ · Resource-allocation graph — ছবিতে কে কী ধরে আছে

চারটি শর্ত মুখে বলা সহজ, কিন্তু দশটি প্রসেস আর পাঁচ রকম সম্পদ হলে মাথায় রাখা কঠিন। তাই আঁকা হয় resource-allocation graph (সংক্ষেপে RAG) — একটি directed graph, যার নিয়ম চারটি:

• বৃত্ত = একটি প্রসেস (P₁, P₂ …)।
• আয়তক্ষেত্র = একটি resource type; ভেতরের প্রতিটি বিন্দু = একটি instance.
• Request edge P_i → R_j: P_i R_j-এর একটি instance চেয়েছে, এখনো পায়নি, অপেক্ষা করছে। তীর যায় আয়তক্ষেত্রের কিনারা পর্যন্ত — কারণ যেকোনো একটি instance হলেই চলবে।
• Assignment edge R_j → P_i: R_j-এর একটি নির্দিষ্ট instance P_i-এর হাতে। তীর শুরু হয় নির্দিষ্ট বিন্দু থেকে।

এবার একটি পরিচিত পাঠ্যবই-উদাহরণ ধাপে ধাপে গড়ে তুলি। তিনটি প্রসেস; চারটি resource type — R1 (১টি instance), R2 (২টি), R3 (১টি), R4 (৩টি)। প্রতিটি ধাপে একটি করে ঘটনা ঘটবে, আর ডান পাশের টেবিলে দেখবেন কে অপেক্ষায়, চক্র আছে কি না।

তিনটি উপপাদ্য আর তাদের যুক্তি

৫ · চক্র মানেই deadlock নয় — আর wait-for graph

তৃতীয় উপপাদ্যের পাঠ্যবই-উদাহরণটি পরীক্ষায় সবচেয়ে বেশি আসে। দুটি resource type, R1 আর R2, প্রত্যেকটির ২টি instance; চারটি প্রসেস। চক্র আছে, তবু কোনো deadlock নেই। কেন, তা ধাপে ধাপে দেখুন:

যন্ত্র দিয়ে যাচাই — একটি ছোট RAG cycle detector

নিচের simulator একটি তীরের তালিকা নেয় ("P1>R1" মানে request, "R1>P2" মানে assignment), DFS দিয়ে প্রতিটি সরল চক্র খোঁজে, আর বলে deadlock নিশ্চিত কি না। চারটি graph-এ চালানো হয়েছে: দুই mutex-এর উল্টো ক্রম, আর উপরের তিনটি পাঠ্যবই-graph:

// RAG: "P1>R1" = request edge (P1 waits for R1), "R1>P2" = assignment edge (an R1 unit is held by P2)
function analyse(name, units, edges) {
  const adj = {};
  for (const e of edges) { const [a, b] = e.split(">"); (adj[a] = adj[a] || []).push(b); }
  const cycles = [];
  function dfs(start, v, path) {        // every simple cycle, listed once: from its smallest node
    for (const w of adj[v] || []) {
      if (w === start) cycles.push(path);
      else if (w > start && !path.includes(w)) dfs(start, w, [...path, w]);
    }
  }
  for (const s of Object.keys(adj).sort()) dfs(s, s, [s]);
  console.log(name);
  if (cycles.length === 0) { console.log("   no cycle -> NO deadlock (certain)"); return; }
  let certain = false;
  for (const c of cycles) {
    const multi = c.filter(n => n[0] === "R" && units[n] > 1);
    if (multi.length === 0) certain = true;
    console.log("   cycle: " + [...c, c[0]].join(" -> ") +
      (multi.length ? "   (multi-unit: " + multi.map(r => r + "x" + units[r]).join(", ") + ")" : "   (all single-unit)"));
  }
  console.log(certain ? "   => deadlock CERTAIN" : "   => deadlock POSSIBLE only: run a detection algorithm");
}
analyse("G1 two mutexes, opposite order", { R1: 1, R2: 1 },
  ["R1>P1", "P1>R2", "R2>P2", "P2>R1"]);
analyse("G2 textbook graph, no cycle", { R1: 1, R2: 2, R3: 1, R4: 3 },
  ["P1>R1", "P2>R3", "R1>P2", "R2>P2", "R2>P1", "R3>P3"]);
analyse("G3 same graph + P3 requests R2", { R1: 1, R2: 2, R3: 1, R4: 3 },
  ["P1>R1", "P2>R3", "R1>P2", "R2>P2", "R2>P1", "R3>P3", "P3>R2"]);
analyse("G4 cycle with spare holders", { R1: 2, R2: 2 },
  ["P1>R1", "P3>R2", "R1>P2", "R1>P3", "R2>P1", "R2>P4"]);

G1 two mutexes, opposite order
   cycle: P1 -> R2 -> P2 -> R1 -> P1   (all single-unit)
   => deadlock CERTAIN
G2 textbook graph, no cycle
   no cycle -> NO deadlock (certain)
G3 same graph + P3 requests R2
   cycle: P1 -> R1 -> P2 -> R3 -> P3 -> R2 -> P1   (multi-unit: R2x2)
   cycle: P2 -> R3 -> P3 -> R2 -> P2   (multi-unit: R2x2)
   => deadlock POSSIBLE only: run a detection algorithm
G4 cycle with spare holders
   cycle: P1 -> R1 -> P3 -> R2 -> P1   (multi-unit: R1x2, R2x2)
   => deadlock POSSIBLE only: run a detection algorithm

Wait-for graph — single instance হলে ছোট ছবি

সব resource single-instance হলে RAG থেকে resource-গিঁটগুলো মুছে আরও ছোট একটি graph বানানো যায়: P_i → R → P_j পথ থাকলে সরাসরি তীর P_i → P_j, মানে “P_i অপেক্ষা করছে P_j-এর জন্য।” এর নাম wait-for graph. এখানে deadlock আছে যদি এবং কেবল যদি চক্র থাকে, আর চক্র খোঁজা যায় DFS দিয়ে O(V + E) সময়ে (DSA কোর্সের DFS পর্ব)।

RAG (single instance)                    wait-for graph
P1 → R1 → P2 → R3 → P3                   P1 ──→ P2 ──→ P3
            P3 → R4 → P1                  ↑             │
                                          └─────────────┘   চক্র = deadlock

ডেটাবেস ঠিক এই কাজটিই করে — কোন transaction কার lock-এর অপেক্ষায়, তার wait-for graph রেখে নিয়মিত চক্র খোঁজে, আর একটিকে rollback করে জট খোলে। পুরো ব্যবস্থাটি, wait-die আর wound-wait সহ, DBMS কোর্সের concurrency control পর্বে বিস্তারিত আছে; এখানে আর পুনরাবৃত্তি করছি না।

৬ · Deadlock সামলানোর চার পথ — আর কেন বেশিরভাগ OS “উটপাখি”

সম্ভাব্য সব কৌশল চারটি দলে পড়ে:

উটপাখির কৌশল কেন যুক্তিসংগত

Andrew Tanenbaum তাঁর পাঠ্যবইয়ে মজা করে একে বলেন ostrich algorithm — বিপদ দেখলে বালিতে মাথা গুঁজে রাখা। শুনতে দায়িত্বহীন, কিন্তু প্রকৌশলের হিসাবে প্রায়ই এটাই ঠিক:

• খরচ সব সময়ের, লাভ কালেভদ্রে। প্রতিটি pthread_mutex_lock-এ চক্র খুঁজলে সবচেয়ে ঘন ঘন চলা অপারেশনটি ধীর হতো, অথচ বেশিরভাগ প্রোগ্রামে deadlock ঘটেই না।
• OS সব “সম্পদ” চেনে না, আর ধরলেও সারাতে পারে না। user-space spinlock বা বার্তার অপেক্ষা kernel দেখতে পায় না; আর অর্ধেক লেখা ফাইল “ফিরিয়ে নেওয়ার” উপায় নেই (ভাবনার প্রশ্ন ১)।

তবু কিছু সহায়তা আছে: POSIX-এর PTHREAD_MUTEX_ERRORCHECK mutex একই থ্রেড দ্বিতীয়বার lock নিতে গেলে আটকে না গিয়ে EDEADLK ফেরায়; Linux-এ fcntl-এর record lock-এ (F_SETLKW) kernel সরল চক্র ধরে EDEADLK দেয়। আর kernel-এর নিজের lock-এ deadlock মানে পুরো মেশিন অচল, তাই সেখানে lockdep-এর মতো কঠোর যাচাই চলে (অংশ ৮)।

৭ · Prevention — চারটি শর্তের প্রতিটি ভাঙার কৌশল ও তার দাম

অংশ ৩-এর প্রমাণ বলছে, যেকোনো একটি শর্ত ভাঙলেই যথেষ্ট। প্রতিটির জন্য পরিচিত কৌশল আছে, কিন্তু কোনোটিই বিনা খরচে নয়।

প্রমাণ: global lock order থাকলে circular wait অসম্ভব

নিচের ডায়াগ্রামে চারটি lock, নম্বর ১ থেকে ৪. তিনটি থ্রেড চেষ্টা করবে একটি চক্র বানাতে; দেখুন নিয়মটি কোথায় তাদের থামায়, আর কেন সেটি যেকোনো দৈর্ঘ্যের চক্রের জন্য সত্য।

এবার একই দুই-হিসাবের সমস্যা, কিন্তু একটি lock_pair ফাংশন দিয়ে, যা টাকা যেদিকেই যাক সবসময় ছোট id-র হিসাব আগে lock করে। দুই থ্রেড উল্টো দিকে লাখো বার টাকা পাঠাবে:

#include <pthread.h>
#include <stdio.h>
struct account { int id; long balance; pthread_mutex_t m; };
static struct account acc[2] = {{.id = 0, .balance = 100000}, {.id = 1, .balance = 100000}};

static void lock_pair(struct account *x, struct account *y) {
    if (x->id > y->id) { struct account *t = x; x = y; y = t; } /* smaller id first */
    pthread_mutex_lock(&x->m);
    pthread_mutex_lock(&y->m);
}
struct job { struct account *from, *to; int n; };
static void *transfer(void *p) {
    struct job *j = p;
    for (int i = 0; i < j->n; i++) {
        lock_pair(j->from, j->to);
        j->from->balance -= 1;
        j->to->balance += 1;
        pthread_mutex_unlock(&j->from->m);
        pthread_mutex_unlock(&j->to->m);
    }
    return NULL;
}
int main(void) {
    for (int i = 0; i < 2; i++) pthread_mutex_init(&acc[i].m, NULL);
    struct job j1 = {&acc[0], &acc[1], 200000}, j2 = {&acc[1], &acc[0], 150000};
    pthread_t t1, t2;
    pthread_create(&t1, NULL, transfer, &j1);   /* A -> B */
    pthread_create(&t2, NULL, transfer, &j2);   /* B -> A */
    pthread_join(t1, NULL); pthread_join(t2, NULL);
    printf("both threads finished: 200000 x (A->B), 150000 x (B->A)\n");
    printf("A = %ld, B = %ld, A + B = %ld\n", acc[0].balance, acc[1].balance,
           acc[0].balance + acc[1].balance);
    return 0;
}

both threads finished: 200000 x (A->B), 150000 x (B->A)
A = 50000, B = 150000, A + B = 200000

৮ · বাস্তবের কোডে — lock hierarchy, lockdep, livelock আর distributed deadlock

Lock hierarchy আর Linux-এর lockdep

বড় প্রজেক্টে প্রতিটি lock-কে নম্বর দেওয়ার বদলে স্তর বা lock hierarchy লিখে রাখা হয়: যেমন “আগে ফাইল-সিস্টেমের lock, তারপর inode-এর, তারপর page-এর” — উল্টো কখনো নয়। Linux kernel-এর বহু সোর্স ফাইলের শুরুতে এমন মন্তব্য থাকে, যেখানে কোন lock কার আগে নিতে হবে তা লেখা। দুটি একই রকম বস্তু একসাথে lock করতে হলে (যেমন scheduler-এর দুটি CPU-র run queue) kernel ঐতিহাসিকভাবে ঠিকানার ক্রম মেনেছে — ঠিক আমাদের lock_pair-এর মতো।

নিয়ম লিখে রাখলেই সবাই মানে না, তাই ২০০৬ সালে (kernel 2.6.18) Ingo Molnar ও Arjan van de Ven-এর তৈরি lockdep যুক্ত হয়। CONFIG_PROVE_LOCKING চালু করা debug kernel-এ এটি প্রতিটি lock নেওয়ার সময় হিসাব রাখে, “কোন lock ধরে থাকা অবস্থায় কোন lock নেওয়া হলো”। এই সম্পর্কগুলো দিয়ে সে একটি dependency graph বানায়, আর নতুন তীরে চক্র তৈরি হলে সতর্ক করে — deadlock আসলে না ঘটলেও। অর্থাৎ একদিন A → B আর অন্যদিন B → A ক্রম দেখলেই রিপোর্ট আসে, দুই থ্রেডের ভাগ্যক্রমে একসাথে আটকানোর দরকার পড়ে না:

======================================================
WARNING: possible circular locking dependency detected
------------------------------------------------------
kworker/0:1 is trying to acquire lock:
  (&dev->lock_b){+.+.}, at: driver_work+0x40/0x90
but task is already holding lock:
  (&dev->lock_a){+.+.}, at: driver_work+0x20/0x90
which lock already depends on the new lock.

User-space-এ Valgrind-এর helgrind আর ThreadSanitizer lock-order-inversion রিপোর্ট করে (পর্ব ১৫)। Java-র jstack চক্র পেলে লেখে “Found one Java-level deadlock”. Go-র runtime সব goroutine একসাথে ঘুমিয়ে পড়লে থামিয়ে দেয় all goroutines are asleep - deadlock! বলে, তবে আংশিক deadlock ধরে না। আর Linux-এর khungtaskd কোনো task অনেকক্ষণ (সাধারণত ১২০ সেকেন্ড) uninterruptible ঘুমে থাকলে সতর্ক করে — প্রমাণ নয়, লক্ষণ।

Deadlock, livelock আর starvation — তিনটি আলাদা অসুখ

অনেকে hold-and-wait ভাঙতে trylock ব্যবহার করেন: দ্বিতীয় lock না পেলে প্রথমটিও ছেড়ে আবার চেষ্টা। দুই থ্রেড যদি একদম একই তালে এটি করে, তাহলে দুজনে একসাথে নেয়, একসাথে ব্যর্থ হয়, একসাথে ছাড়ে, একসাথে আবার নেয় … চিরকাল। কেউ আটকে নেই, CPU পুরো ব্যস্ত, কিন্তু কাজ শূন্য। এর নাম livelock — সরু গলিতে মুখোমুখি দুজন মানুষ, দুজনেই ভদ্রতা করে একই দিকে সরে যাচ্ছেন বারবার।

বাস্তবের বিখ্যাত উদাহরণ receive livelock: ১৯৯০-এর দশকে Jeffrey Mogul ও K. K. Ramakrishnan দেখান, প্রতিটি নেটওয়ার্ক প্যাকেটে interrupt নেওয়া kernel প্রচণ্ড ভিড়ে শুধু interrupt সামলাতেই CPU শেষ করে, প্যাকেট প্রক্রিয়ার সময় পায় না। Dining philosophers-এ (পর্ব ২৬) সবাই একসাথে বাঁ কাঁটা নিলে deadlock, আর “না পেলে রেখে আবার চেষ্টা” করলে livelock — একই সমস্যার দুই রূপ।

Distributed system আর ডেটাবেসে deadlock — সংক্ষেপে

একাধিক মেশিনে ছড়ানো সিস্টেমে কারও কাছে পুরো wait-for graph নেই — প্রতিটি সার্ভার শুধু নিজের lock-গুলো জানে। T1 সার্ভার X-এ T2-র অপেক্ষায়, আর T2 সার্ভার Y-এ T1-এর অপেক্ষায়; দুই সার্ভারের নিজস্ব graph-এ চক্র নেই, অথচ মিলিয়ে দেখলে আছে। কেন্দ্রীয়ভাবে graph জোগাড় করলে দেরিতে আসা তথ্যে এমন চক্রও দেখা যায় যা কখনো ছিল না — একে বলে phantom deadlock. তাই বাস্তবে timeout আর timestamp-ভিত্তিক prevention-ই বেশি চলে (ভাবনার প্রশ্ন ৫)। ডেটাবেসের দিকটি DBMS কোর্সের concurrency control পর্বে, আর distributed সিস্টেমের OS-দিক পর্ব ৫৩-এ।

৯ · পরীক্ষার numerical — “কমপক্ষে কতটি resource লাগবে?”

বিশ্ববিদ্যালয়, চাকরি আর ইন্টারভিউর পরীক্ষায় সবচেয়ে বেশি আসা deadlock-numerical এটি: “একটি সিস্টেমে n টি প্রসেস, প্রত্যেকের একই ধরনের সম্পদের সর্বোচ্চ k টি একক লাগে। deadlock কখনো হবে না, তা নিশ্চিত করতে কমপক্ষে কতটি একক লাগবে?” উত্তর:

প্রমাণ (দুই দিক থেকে)

ধরে নেওয়া মডেল: প্রসেস এককগুলো একটি একটি করে চায়, যা পায় তা ধরে রাখে, আর নিজের সর্বোচ্চ k_i টি পেলে কাজ শেষ করে সব ফেরত দেয়।

• R = Σ(k_i − 1) হলে deadlock সম্ভব: প্রত্যেককে k_i − 1 টি দিন। সব একক শেষ, অথচ কেউ নিজের শেষ এককটি পায়নি — সবাই অপেক্ষায়, কেউ কিছু ছাড়বে না। এর চেয়ে কম R-এ একইভাবে সবাইকে অসম্পূর্ণ রেখে সব একক শেষ করা যায়।
• R = Σ(k_i − 1) + 1 হলে deadlock অসম্ভব: deadlock-এ সব একক বরাদ্দ হয়ে থাকতে হবে (একটি মুক্ত থাকলে কোনো অপেক্ষারত প্রসেস সেটি পেত), আর কেউ নিজের পূর্ণ k_i পায়নি — অর্থাৎ প্রত্যেকের হাতে বড়জোর k_i − 1. তাহলে মোট বরাদ্দ ≤ Σ(k_i − 1) < R, অর্থাৎ অন্তত একটি একক মুক্ত — বিরোধ। pigeonhole নীতি অনুযায়ী কাউকে না কাউকে শেষ এককটি পেতেই হবে; সে শেষ করে সব ফেরত দেয়, আর বাকিদের জন্য একই যুক্তি আবার খাটে।

একই শর্তের আরেকটি পরিচিত রূপ: Σ k_i < R + n হলে deadlock-মুক্ত। দুই দিক থেকে n বিয়োগ করলেই Σ(k_i − 1) < R, অর্থাৎ R ≥ Σ(k_i − 1) + 1 — একই কথা।

পাঁচটি সমাধান করা উদাহরণ

আরেকটি উল্টো রূপ: “১২টি একক আর ৪টি প্রসেস; প্রত্যেকের সর্বোচ্চ চাহিদা k হলে k-এর সবচেয়ে বড় মান কত, যাতে deadlock না হয়?” ৪(k − ১) + ১ ≤ ১২ ⇒ k − ১ ≤ ২.৭৫ ⇒ k ≤ ৩.৭৫, পূর্ণসংখ্যায় k = ৩. যাচাই: k = ৪ হলে প্রত্যেকে ৩টি করে নিলে ১২টিই শেষ, সবাই আটকে।

সূত্রে অন্ধ বিশ্বাস না করে যন্ত্র দিয়ে যাচাই করুন। নিচের simulator সূত্র ব্যবহার না করে প্রতিটি সম্ভাব্য “সবাই অসম্পূর্ণ, কিছুই মুক্ত নেই” অবস্থা খুঁজে দেখে, আর সবচেয়ে ছোট R বের করে যেখানে এমন অবস্থা নেই:

// Units are requested one at a time; a process that reaches its max need finishes and frees all.
// Deadlock = every unfinished process holds fewer than its need, and no unit is free.
function stuckState(need, R) {          // search all hold-vectors h[i] in 0..need[i]-1
  const h = new Array(need.length).fill(0);
  function go(i, used) {
    if (used > R) return null;
    if (i === need.length) return used === R ? [...h] : null;   // all R held, none free
    for (let x = 0; x < need[i]; x++) { h[i] = x; const r = go(i + 1, used + x); if (r) return r; }
    return null;
  }
  return go(0, 0);
}
function minUnits(need) {
  let R = 1;
  while (stuckState(need, R)) R++;      // grow R until no stuck state exists
  return R;
}
const cases = [[2, 2, 2], [3, 3, 3, 3], [4, 4, 4], [3, 4, 6]];
for (const need of cases) {
  const R = minUnits(need), formula = need.reduce((s, k) => s + (k - 1), 0) + 1;
  console.log("needs [" + need + "]: brute force R = " + R + ", formula sum(k-1)+1 = " + formula +
    " | with R-1 = " + (R - 1) + " stuck at holds [" + stuckState(need, R - 1) + "]");
}
// reverse question: 6 units, every process needs 2 -> how many processes are always safe?
let n = 1;
while (!stuckState(new Array(n + 1).fill(2), 6)) n++;
console.log("6 units, each needs 2: at most " + n + " processes are deadlock-free");

needs [2,2,2]: brute force R = 4, formula sum(k-1)+1 = 4 | with R-1 = 3 stuck at holds [1,1,1]
needs [3,3,3,3]: brute force R = 9, formula sum(k-1)+1 = 9 | with R-1 = 8 stuck at holds [2,2,2,2]
needs [4,4,4]: brute force R = 10, formula sum(k-1)+1 = 10 | with R-1 = 9 stuck at holds [3,3,3]
needs [3,4,6]: brute force R = 11, formula sum(k-1)+1 = 11 | with R-1 = 10 stuck at holds [2,3,5]
6 units, each needs 2: at most 5 processes are deadlock-free

“RAG এঁকে সিদ্ধান্ত নিন” — একটি পূর্ণ সমাধান

প্রশ্ন: R1 (১টি), R2 (২টি), R3 (১টি)। P1 ধরে আছে R2-এর একটি, চাইছে R1; P2 ধরে আছে R1, চাইছে R3; P3 ধরে আছে R3 আর R2-এর একটি, চাইছে R2. deadlock আছে কি?

সমাধান: তীরগুলো: R2 → P1, P1 → R1, R1 → P2, P2 → R3, R3 → P3, R2 → P3, P3 → R2. চক্র খুঁজুন: P1 → R1 → P2 → R3 → P3 → R2 → P1 — চক্র আছে। R2-তে দুটি instance, তাই reduction করুন: মুক্ত instance — R1: ০, R2: ০, R3: ০. কারও অনুরোধ মেটানো যায় না (P1-এর R1, P2-এর R3, P3-এর R2 — সবগুলোই ০)। কোনো প্রসেস সরানো যায় না, আর চক্রের বাইরে কোনো প্রসেস নেই। রায়: P1, P2, P3 deadlocked. এবার ধরুন একটি চতুর্থ প্রসেস P4 R2-এর একটি instance ধরে থাকত আর কিছু চাইত না (তখন R2-এর ৩টি instance) — P4 শেষ করে R2 ছাড়লে P3 পেত, আর জট খুলে যেত।

১০ · AI-এর যুগে deadlock-এর কোড

AI খুব দ্রুত থ্রেডের কোড লিখে দেয়, আর সেই কোড আপনার ল্যাপটপে প্রায় সবসময় চলে — কারণ deadlock-এর জন্য দরকার নির্দিষ্ট একটি interleaving, যা হালকা load-এ কালেভদ্রে ঘটে। “আমার মেশিনে চলে” তাই কোনো প্রমাণ নয়। AI-এর যে ভুলগুলো এই বিষয়ে বারবার দেখা যায়:

AI-এর দেওয়া concurrent কোড হাতে পেলে — চেকলিস্ট

• প্রতিটি জায়গায় একাধিক lock একই global ক্রমে নেওয়া হয়েছে, আর ক্রমটি একটি মন্তব্যে লেখা আছে
• lock ধরে রেখে কোনো blocking I/O, অন্য সার্ভিস-কল বা অজানা callback নেই
• ThreadSanitizer (-fsanitize=thread) বা helgrind দিয়ে চালিয়েছি — lock-order-inversion রিপোর্ট শূন্য
• অনেক থ্রেড, কম core (যেমন taskset -c 0) আর ভারী load-এ অনেকবার চালিয়েছি; barrier দিয়ে খারাপ ক্রমও জোর করে পরীক্ষা করেছি
• retry বা trylock থাকলে তাতে random backoff আর চেষ্টার সীমা আছে
• numerical-এর উত্তর ছোট একটি উদাহরণে হাতে মিলিয়েছি, আর API-গুলো আমার OS-এ আছে কি না man page-এ দেখেছি