ক্লাসিক সমস্যা — producer-consumer, readers-writers আর dining philosophers

১ · ক্লাসিক সমস্যা কেন — তিনটি ছাঁচ

পর্ব ২২ থেকে ২৫-এ আপনি হাতিয়ারগুলো চিনেছেন: race condition কেন হয়, critical section কী, mutex, semaphore, condition variable আর monitor. এবার প্রশ্ন — এসব হাতিয়ার দিয়ে আসল সমস্যা কীভাবে সমাধান করবেন? এখানেই আসে কয়েকটি “ক্লাসিক” সমস্যা। ১৯৬০ আর ১৯৭০-এর দশকে Edsger Dijkstra, Tony Hoare, David Parnas-এর মতো গবেষকেরা এগুলো প্রস্তাব করেছিলেন। তারপর থেকে প্রায় প্রতিটি OS বই আর পরীক্ষায় এগুলো ঘুরে ফিরে আসে।

কারণটি সহজ। প্রতিটি সমস্যা একটি ছাঁচ — বাস্তবের হাজার রকম সমস্যা আসলে এদেরই কোনো একটির রূপ। একটি নতুন সমন্বয়-সমস্যা দেখলে আগে জিজ্ঞেস করুন, “এটি কোন ছাঁচের?” — উত্তর পেলে সমাধানের অর্ধেক হয়ে যায়।

এই পর্বে লেখার নিয়ম: semaphore-এর দুই অপারেশন লিখব wait(S) আর signal(S). Dijkstra এদের নাম দিয়েছিলেন P আর V (ডাচ শব্দ থেকে), আর POSIX-এ এরা sem_wait ও sem_post. wait(S) মানে: S-এর মান ০-এর বেশি হলে এক কমানো আর এগিয়ে যাওয়া, নইলে ঘুমানো। signal(S) মানে: কেউ ঘুমিয়ে থাকলে একজনকে জাগানো, নইলে S এক বাড়ানো। প্রতিটি wait আর signal নিজে অবিভাজ্য (atomic) — এর ভেতরের বাস্তবায়ন পর্ব ২৪-এ দেখেছেন।

২ · Producer–consumer — তিনটি semaphore দিয়ে bounded buffer

Producer–consumer সমস্যায় এক বা একাধিক producer (উৎপাদক) থ্রেড জিনিস বানিয়ে একটি bounded buffer-এ রাখে, আর এক বা একাধিক consumer (ভোক্তা) থ্রেড সেখান থেকে তোলে। Buffer-টি n ঘরের একটি বৃত্তাকার সারি: in দেখায় পরের জিনিস কোন ঘরে রাখা হবে, out দেখায় পরের জিনিস কোন ঘর থেকে তোলা হবে, আর দুটিই শেষ ঘরের পর আবার ০-তে ফেরে ((in + 1) % n). পর্ব ১২-এর ৩ ঘরের bounded mailbox-এ kernel এই কাজটি আমাদের হয়ে করেছিল; এবার নিজেরা করব।

তিনটি শর্ত মানতে হবে: (ক) buffer-এর ভেতরের ডেটা (buf, in, out) একবারে একজনই বদলাবে; (খ) buffer ভর্তি থাকলে producer অপেক্ষা করবে; (গ) খালি থাকলে consumer অপেক্ষা করবে। প্রতিটি শর্তের জন্য একটি করে semaphore:

semaphore mutex = 1, empty = n, full = 0;
item buf[n]; int in = 0, out = 0;

producer:                          consumer:
  while (true) {                     while (true) {
    item x = produce();                wait(full);      // a filled slot?
    wait(empty);    // a free slot?    wait(mutex);     // then enter
    wait(mutex);    // then enter      x = buf[out];
    buf[in] = x;                       out = (out + 1) % n;
    in = (in + 1) % n;                 signal(mutex);
    signal(mutex);                     signal(empty);   // one more free
    signal(full);   // one more item   consume(x);
  }                                  }

লক্ষ করুন, produce() আর consume(x) critical section-এর বাইরে। ভারী কাজ lock ধরে করলে অন্যরা অকারণে অপেক্ষা করে — critical section যত ছোট, তত ভালো। নিচে n = 3 নিয়ে একজন producer (P) আর একজন consumer (C) ধাপে ধাপে চলুক। জিনিসগুলোর নাম a, b, c, d, e.

1P: wait(empty);2P: wait(mutex);3P: buf[in] = x; in = (in+1) % 3;4P: signal(mutex); signal(full);5C: wait(full);6C: wait(mutex);7C: x = buf[out]; out = (out+1) % 3;8C: signal(mutex); signal(empty);

কেন এটি সঠিক — একটি ছোট প্রমাণ

ধরুন এ পর্যন্ত মোট pটি জিনিস রাখা শেষ (P signal(full) পর্যন্ত গেছে) আর মোট cটি তোলা শেষ। কোনো থ্রেড wait আর signal-এর মাঝখানে নেই এমন মুহূর্তে full = p − c আর empty = n − (p − c), কারণ প্রতিটি রাখায় full এক বাড়ে আর empty এক কমে, প্রতিটি তোলায় উল্টো। Semaphore-এর মান কখনো ঋণাত্মক হয় না, তাই p − c ≥ 0 (খালি থেকে তোলা অসম্ভব) আর p − c ≤ n (n-এর বেশি জমা অসম্ভব)। এটিই শর্ত (খ) আর (গ)। শর্ত (ক) আসে mutex থেকে: buf, in, out শুধু wait(mutex) আর signal(mutex)-এর মাঝে ছোঁয়া হয়। এ ধরনের সবসময়-সত্য সম্পর্ককে বলে invariant — concurrent কোডের সঠিকতা প্রমাণের সবচেয়ে কাজের হাতিয়ার।

৩ · wait-এর ক্রম উল্টালে deadlock — তারপর C-তে চালিয়ে দেখা

Producer-এর দুটি লাইন — wait(empty) আর wait(mutex) — জায়গা বদল করলে কী হয়? দেখতে নির্দোষ: “আগে buffer-এ ঢুকি, তারপর দেখি জায়গা আছে কি না।” কিন্তু buffer ভর্তি থাকলে (n = 3, empty = 0, full = 3) এমন ঘটে:

এটিই deadlock: দুজনেই এমন একটি ঘটনার জন্য অপেক্ষা করছে, যা কেবল অপরজনই ঘটাতে পারে, আর অপরজনও অপেক্ষায়। Consumer-এর দিকেও একই বিপদ: সে আগে wait(mutex) নিলে খালি buffer-এ wait(full)-এ ঘুমাবে mutex হাতে রেখে, আর producer কখনো ঢুকতে পারবে না। নিয়মটি মনে রাখুন: যে wait-এ দীর্ঘক্ষণ ঘুমাতে হতে পারে (empty/full), সেটি আগে; ছোট্ট সময়ের তালা (mutex) পরে। তালা হাতে রেখে কখনো এমন কিছুর জন্য ঘুমাবেন না, যা ঘটাতে অন্যকে সেই তালাই লাগবে। তবে signal দুটির ক্রম বদলালে (signal(full) আগে) কোনো deadlock হয় না — signal কখনো ঘুমায় না; শুধু জেগে ওঠা থ্রেড একটু বেশি অপেক্ষা করতে পারে।

এবার আসল POSIX semaphore দিয়ে — n = 4 ঘরের buffer, দুজন producer (প্রত্যেকে ৫টি জিনিস: 11..15 আর 21..25), দুজন consumer. কোন consumer কোন জিনিস পাবে, তা রান-ভেদে বদলায়; তাই প্রোগ্রামটি শুধু এমন জিনিস ছাপে, যা প্রতিবার একই হওয়ার কথা — মোট সংখ্যা, যোগফল, আর buffer কখনো n ছাড়িয়েছে কি না:

#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>
#define N 4                                /* buffer slots */
#define ITEMS 5                            /* items per producer */
static int buf[N], in, out, count, max_count, consumed; static long sum;
static sem_t empty, full, mutex;           /* start: N, 0, 1 */
static void *producer(void *arg) {
    int base = *(int *)arg;
    for (int i = 1; i <= ITEMS; i++) {
        sem_wait(&empty);                  /* 1. wait for a free slot */
        sem_wait(&mutex);                  /* 2. then lock the buffer */
        buf[in] = base + i; in = (in + 1) % N;
        if (++count > max_count) max_count = count;
        sem_post(&mutex); sem_post(&full); /* one more item */
    }
    return NULL;
}
static void *consumer(void *arg) {
    (void)arg;
    for (int i = 0; i < ITEMS; i++) {
        sem_wait(&full); sem_wait(&mutex);
        sum += buf[out]; out = (out + 1) % N; count--; consumed++;
        sem_post(&mutex); sem_post(&empty);/* one more free slot */
    }
    return NULL;
}
int main(void) {
    sem_init(&empty, 0, N); sem_init(&full, 0, 0); sem_init(&mutex, 0, 1);
    pthread_t p[2], c[2]; int base[2] = {10, 20};
    for (int k = 0; k < 2; k++) {
        pthread_create(&p[k], NULL, producer, &base[k]); pthread_create(&c[k], NULL, consumer, NULL); }
    for (int k = 0; k < 2; k++) { pthread_join(p[k], NULL); pthread_join(c[k], NULL); }
    int e, f; sem_getvalue(&empty, &e); sem_getvalue(&full, &f);
    printf("consumed %d items, sum = %ld (expected 180)\n", consumed, sum);
    printf("max occupancy <= N=%d: %s\n", N, max_count <= N ? "yes" : "no");
    printf("end: empty=%d full=%d count=%d in==out: %s\n", e, f, count, in == out ? "yes" : "no");
    return 0;
}

consumed 10 items, sum = 180 (expected 180)
max occupancy <= N=4: yes
end: empty=4 full=0 count=0 in==out: yes

একই সমাধান condition variable আর monitor দিয়ে

Semaphore একসাথে দুটি কাজ করে — গোনা আর ঘুম পাড়ানো — তাই কোড ছোট, কিন্তু ভুল ক্রমে লেখা সহজ। পর্ব ২৫-এর condition variable-এ শর্তটি সরাসরি লেখা থাকে (“count == N হলে অপেক্ষা”), তাই পড়তে বেশি স্পষ্ট। একটি mutex আর দুটি condition variable:

pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t not_full = PTHREAD_COND_INITIALIZER, not_empty = PTHREAD_COND_INITIALIZER;

void put(int x) {
    pthread_mutex_lock(&m);
    while (count == N)                       /* while, never if */
        pthread_cond_wait(&not_full, &m);    /* releases m while asleep */
    buf[in] = x; in = (in + 1) % N; count++;
    pthread_cond_signal(&not_empty);
    pthread_mutex_unlock(&m);
}
int get(void) {
    pthread_mutex_lock(&m);
    while (count == 0)
        pthread_cond_wait(&not_empty, &m);
    int x = buf[out]; out = (out + 1) % N; count--;
    pthread_cond_signal(&not_full);
    pthread_mutex_unlock(&m);
    return x;
}

এখানে ক্রমের ফাঁদটি নেই, কারণ pthread_cond_wait ঘুমানোর সময় নিজেই mutex ছেড়ে দেয় আর জাগার পর আবার নেয়। while জরুরি: spurious wakeup ছাড়াও, দুজন consumer থাকলে একজন জেগে ওঠার আগেই অন্যজন জিনিসটি তুলে নিতে পারে। এই put/get জোড়া, mutex আর condition variable সব একটি “বাক্সে” ভরলে সেটিই একটি monitor — Hoare আর Brinch Hansen ১৯৭০-এর দশকে যে কাঠামো প্রস্তাব করেন: বাক্সের ভেতরের ডেটা শুধু বাক্সের ফাংশনই ছোঁয় আর একবারে একটিই ফাংশন চলে। Java-র synchronized মেথড আর wait()/notifyAll() ঠিক এই ধারণা, আর Java-র ArrayBlockingQueue বা Go-র buffered channel (make(chan int, 4)) তৈরি bounded buffer.

৪ · Readers–writers — প্রথম সমাধান আর লেখকের starvation

Readers–writers সমস্যায় একটি shared ডেটা (একটি ফাইল, টেবিল বা কনফিগারেশন) কিছু থ্রেড শুধু পড়ে (reader), কিছু থ্রেড বদলায় (writer). একটি সাধারণ mutex দিলেও কাজ চলে, কিন্তু অপচয় হয়: দুজন reader একসাথে পড়লে কোনো ক্ষতি নেই, অথচ mutex তাদেরও এক এক করে পড়ায়। তাই নিয়ম: অনেক reader একসাথে থাকতে পারে; writer থাকলে আর কেউ নয়। সমস্যাটির আনুষ্ঠানিক রূপ দেন P. J. Courtois, F. Heymans আর D. L. Parnas, ১৯৭১ সালে Communications of the ACM-এ; “প্রথম” আর “দ্বিতীয়” readers–writers সমস্যার নাম সেখান থেকেই।

প্রথম সমাধানে তিনটি জিনিস: read_count (এখন কতজন পড়ছে), mutex (read_count রক্ষা করে, শুরু ১) আর rw_mutex (ডেটায় লেখার অধিকার, শুরু ১)। কৌশলটি হলো — প্রথম reader পুরো পাঠক-দলের হয়ে rw_mutex নেয়, আর শেষ reader সেটি ছাড়ে:

semaphore rw_mutex = 1, mutex = 1;  int read_count = 0;

writer:                          reader:
  wait(rw_mutex);                  wait(mutex);
  ... write ...                    read_count++;
  signal(rw_mutex);                if (read_count == 1) wait(rw_mutex);  // first in
                                   signal(mutex);
                                   ... read ...
                                   wait(mutex);
                                   read_count--;
                                   if (read_count == 0) signal(rw_mutex); // last out
                                   signal(mutex);

Writer লিখছে আর কয়েকজন reader এল? প্রথম reader wait(rw_mutex)-এ ঘুমায় — mutex হাতে রেখে — তাই বাকি reader-রা wait(mutex)-এ সারি বাঁধে। এখানে তালা ধরে ঘুমানো নিরাপদ, কারণ writer-এর mutex লাগে না। কিন্তু বড় দুর্বলতাটি আরেক জায়গায়। একজন reader পড়ছে, এমন অবস্থায় writer এলে সে অপেক্ষা করে — ঠিক আছে। কিন্তু নতুন reader এলে সে writer-কে ডিঙিয়ে সরাসরি ঢুকে পড়ে, কারণ read_count তখন ০ নয়। পাঠকের স্রোত না থামলে writer কখনো সুযোগ পায় না:

1R: wait(mutex); read_count++;2R: if (read_count == 1) wait(rw_mutex);3R: signal(mutex);  ... read ...4R: wait(mutex); read_count--;5R: if (read_count == 0) signal(rw_mutex);6R: signal(mutex);7W: wait(rw_mutex); ... write ...; signal(rw_mutex);

৫ · লেখক-অগ্রাধিকার, ন্যায্য সমাধান আর বাস্তবের rwlock

দ্বিতীয় readers–writers সমস্যা উল্টো দাবি করে: একজন writer অপেক্ষা শুরু করলে আর কোনো নতুন reader ঢুকতে পারবে না। এর কাঠামো: writer-দের জন্যও একটি write_count, আর একটি read_try semaphore, যেটি প্রথম অপেক্ষমাণ writer বন্ধ করে দেয় আর শেষ writer খোলে। Reader-কে ঢোকার আগে read_try পেরোতে হয়, তাই writer অপেক্ষায় থাকলে নতুন reader বাইরে আটকায়:

writer:                                   reader:
  wait(wmutex); write_count++;              wait(read_try);        // blocked if a writer waits
  if (write_count == 1) wait(read_try);     wait(mutex); read_count++;
  signal(wmutex);                           if (read_count == 1) wait(rw_mutex);
  wait(rw_mutex); ... write ...             signal(mutex);
  signal(rw_mutex);                         signal(read_try);
  wait(wmutex); write_count--;              ... read ...
  if (write_count == 0) signal(read_try);   (leave exactly as in solution 1)
  signal(wmutex);

সমস্যা উল্টে গেল: writer-দের স্রোত না থামলে এবার reader-রা starve করে। প্রথম আর দ্বিতীয় — দুই সমাধানেই কেউ না কেউ অনন্তকাল বসে থাকতে পারে। তৃতীয়, ন্যায্য সমাধান একটি বাড়তি queue semaphore (শুরু ১) যোগ করে, যা সবাইকে আসার ক্রমে এক দরজা দিয়ে ঢোকায় — ব্যাংকের টোকেন-কাউন্টারের মতো, যেখানে “শুধু দেখব” আর “টাকা জমা দেব” দুই ধরনের গ্রাহকই একই টোকেন-লাইনে দাঁড়ান:

semaphore queue = 1, rw_mutex = 1, mutex = 1;  int read_count = 0;

writer:                          reader:
  wait(queue);                     wait(queue);           // stand in line
  wait(rw_mutex);                  wait(mutex);
  signal(queue);                   read_count++;
  ... write ...                    if (read_count == 1) wait(rw_mutex);
  signal(rw_mutex);                signal(queue);         // let the next one in
                                   signal(mutex);
                                   ... read ...
                                   (leave exactly as in solution 1)

Writer queue ধরে রেখে rw_mutex-এর অপেক্ষা করে, তাই তার পরে আসা reader-রা দরজায় আটকে যায় — আগের ডায়াগ্রামের শেষ ধাপ ঠিক এটিই দেখিয়েছে। পরপর আসা reader-রা তবু একসাথে পড়ে, কারণ প্রত্যেকে দরজা পেরিয়েই সেটি পরের জনের জন্য খুলে দেয়। একটি সতর্কতা: এই ন্যায্যতা নির্ভর করে queue-এর সারি সত্যিই FIFO হওয়ার ওপর; POSIX কোনো semaphore-এর জাগানোর ক্রম কঠোরভাবে নিশ্চিত করে না, তাই বাস্তবের ন্যায্য lock-গুলো ভেতরে নিজস্ব সারি রাখে।

বাস্তবের reader–writer lock

রোজকার কোডে কেউ এই semaphore-গুলো হাতে লেখেন না — প্রতিটি প্ল্যাটফর্মে তৈরি reader–writer lock আছে। আর প্রতিটির অগ্রাধিকার-নীতি আলাদা, যা জানা জরুরি:

নিচের প্রোগ্রামে ৪টি reader থ্রেড প্রত্যেকে ২,০০০ বার পড়ে, আর ২টি writer প্রত্যেকে ৫০০ বার লেখে। Writer দুটি ভ্যারিয়েবল a আর b দুই ধাপে বাড়ায় — কোনো reader কখনো a != b দেখলে বুঝব আধা-লেখা অবস্থা পড়া হয়েছে। সাথে atomic counter দিয়ে গোনা হয়, ভেতরে কতজন reader আর writer — নিয়ম ভাঙলেই violations বাড়ে:

#include <pthread.h>
#include <stdatomic.h>
#include <stdio.h>
static pthread_rwlock_t rw = PTHREAD_RWLOCK_INITIALIZER;
static long a, b;                            /* a writer keeps a == b */
static atomic_int readers_in, writers_in, violations;
static atomic_long reads;
static void *reader(void *arg) {
    (void)arg;                               /* unused */
    for (int i = 0; i < 2000; i++) {
        pthread_rwlock_rdlock(&rw);          /* shared: many readers at once */
        atomic_fetch_add(&readers_in, 1);
        if (atomic_load(&writers_in) != 0 || a != b) atomic_fetch_add(&violations, 1);
        atomic_fetch_add(&reads, 1);
        atomic_fetch_sub(&readers_in, 1);
        pthread_rwlock_unlock(&rw);
    }
    return NULL;
}
static void *writer(void *arg) {   (void)arg;
    for (int i = 0; i < 500; i++) {
        pthread_rwlock_wrlock(&rw);          /* exclusive: nobody else inside */
        if (atomic_fetch_add(&writers_in, 1) != 0 || atomic_load(&readers_in) != 0)
            atomic_fetch_add(&violations, 1);
        a++; b++;                            /* two steps: never visible half-done */
        atomic_fetch_sub(&writers_in, 1);
        pthread_rwlock_unlock(&rw);
    }
    return NULL;
}
int main(void) {
    pthread_t t[6];
    for (int i = 0; i < 6; i++) pthread_create(&t[i], NULL, i < 4 ? reader : writer, NULL);
    for (int i = 0; i < 6; i++) pthread_join(t[i], NULL);
    printf("reads = %ld, a = %ld, b = %ld\n", (long)atomic_load(&reads), a, b);
    int v = atomic_load(&violations);
    printf("violations = %d\nwriters never overlapped readers: %s\n", v, v == 0 ? "yes" : "no");
    return 0;
}

reads = 8000, a = 1000, b = 1000
violations = 0
writers never overlapped readers: yes

৬ · Dining philosophers — deadlock কীভাবে জন্মায়

Dining philosophers-এর গল্প: গোল টেবিলে পাঁচজন দার্শনিক (P0…P4), প্রতি দুজনের মাঝে একটি কাঁটাচামচ (fork F0…F4). প্রত্যেকে পালা করে ভাবেন আর খান; খেতে দুপাশের দুটো fork লাগে। Pi-এর বাঁ দিকে Fi, ডান দিকে F((i+1) mod 5) — তাই F1 ভাগ করেন P0 আর P1. প্রচলিত বর্ণনা অনুযায়ী Dijkstra ১৯৬৫ সালে সমস্যাটি দিয়েছিলেন পাঁচটি কম্পিউটার আর ভাগাভাগি করা tape drive-এর অনুশীলনী হিসেবে; Hoare পরে এটিকে দার্শনিক আর স্প্যাগেটির গল্পে রূপ দেন। প্রতিটি fork-কে একটি mutex ধরলে সবচেয়ে সহজ কোড:

philosopher(i):
  while (true) {
    think();
    lock(fork[i]);              // left fork
    lock(fork[(i + 1) % 5]);    // right fork
    eat();
    unlock(fork[(i + 1) % 5]); unlock(fork[i]);
  }

বেশিরভাগ সময় এটি চলে। কিন্তু একটি দুর্ভাগা মুহূর্তে পাঁচজনই প্রায় একসাথে ক্ষুধার্ত হলে:

1philosopher(i): while (true) {2  think();3  lock(fork[i]);            // left4  lock(fork[(i+1) % 5]);    // right5  eat();6  unlock both; }7// 4 conditions: ME, H&W, NP, CW8// fix: lock lower-numbered fork first

বাস্তবে এই deadlock হাজারে একবার ঘটতে পারে — কারণ ধাপ ২–৫-এর মতো “সবাই প্রথম fork তুলে থেমে যাওয়া” ঘটতে scheduler-এর ঠিক ওই ক্রমে থ্রেড বদলাতে হয়। নিচের simulator ভাগ্যের ওপর নির্ভর করে না: প্রতিটি tick-এ সব ক্ষুধার্ত দার্শনিক একসাথে পরের fork-টি চান (lock-step), একই fork দুজন চাইলে ছোট id-এর জন পায়, আর খাওয়া চলে এক tick. কোনো tick-এ কেউ এগোতে না পারলে আর কেউ না খেলে সেটিই deadlock. প্রথমে সাধারণ “বাঁ fork আগে”, তারপর “ছোট নম্বরের fork আগে”:

// Dining philosophers in lock-step: every tick, all hungry philosophers try their next fork at once
const N = 5, MEALS = 2;
function run(name, firstFork) {
  const owner = Array(N).fill(-1);                 // owner[f] = philosopher holding fork f
  const ph = [...Array(N).keys()].map(i => {
    const L = i, R = (i + 1) % N, a = firstFork(L, R);
    return { want: [a, a === L ? R : L], step: 0, meals: 0 };  // step 0/1 = need fork, 2 = eating
  });
  console.log(`--- ${name} ---`);
  for (let tick = 1; tick <= 50; tick++) {
    let changed = false;
    const req = new Map();                         // fork -> lowest id asking for it this tick
    ph.forEach((p, i) => {
      if (p.step === 2) {                          // finished eating: put both forks down
        p.meals++; p.step = 0; owner[p.want[0]] = owner[p.want[1]] = -1; changed = true;
      } else if (p.meals < MEALS) {
        const f = p.want[p.step];
        if (owner[f] === -1 && !req.has(f)) req.set(f, i);
      }
    });
    for (const [f, i] of req) { owner[f] = i; ph[i].step++; changed = true; }
    const row = ph.map((p, i) => `P${i}:` + (p.meals >= MEALS ? "done" :
      ["needs " + p.want[0], "has " + p.want[0], "EATS"][p.step])).join("  ");
    console.log(`t${String(tick).padStart(2)}  ${row}`);
    if (ph.every(p => p.meals >= MEALS)) { console.log(`all ate ${MEALS} times by tick ${tick}`); return; }
    if (!changed && !ph.some(p => p.step === 2)) {
      const cyc = ph.map((p, i) => `P${i}->fork${p.want[p.step]}(P${owner[p.want[p.step]]})`);
      console.log("DEADLOCK: nobody can move. waits-for: " + cyc.join(" "));
      return;
    }
  }
}
run("naive: left fork first", (L, R) => L);
run("ordered: lower-numbered fork first", (L, R) => Math.min(L, R));

--- naive: left fork first ---
t 1  P0:has 0  P1:has 1  P2:has 2  P3:has 3  P4:has 4
t 2  P0:has 0  P1:has 1  P2:has 2  P3:has 3  P4:has 4
DEADLOCK: nobody can move. waits-for: P0->fork1(P1) P1->fork2(P2) P2->fork3(P3) P3->fork4(P4) P4->fork0(P0)
--- ordered: lower-numbered fork first ---
t 1  P0:has 0  P1:has 1  P2:has 2  P3:has 3  P4:needs 0
t 2  P0:has 0  P1:has 1  P2:has 2  P3:EATS  P4:needs 0
t 3  P0:has 0  P1:has 1  P2:has 2  P3:needs 3  P4:needs 0
t 4  P0:has 0  P1:has 1  P2:EATS  P3:needs 3  P4:needs 0
t 5  P0:has 0  P1:has 1  P2:needs 2  P3:has 3  P4:needs 0
t 6  P0:has 0  P1:EATS  P2:needs 2  P3:EATS  P4:needs 0
t 7  P0:has 0  P1:needs 1  P2:has 2  P3:done  P4:needs 0
t 8  P0:EATS  P1:needs 1  P2:EATS  P3:done  P4:needs 0
t 9  P0:needs 0  P1:has 1  P2:done  P3:done  P4:has 0
t10  P0:needs 0  P1:EATS  P2:done  P3:done  P4:EATS
t11  P0:needs 0  P1:done  P2:done  P3:done  P4:needs 0
t12  P0:has 0  P1:done  P2:done  P3:done  P4:needs 0
t13  P0:EATS  P1:done  P2:done  P3:done  P4:needs 0
t14  P0:done  P1:done  P2:done  P3:done  P4:has 0
t15  P0:done  P1:done  P2:done  P3:done  P4:EATS
t16  P0:done  P1:done  P2:done  P3:done  P4:done
all ate 2 times by tick 16

৭ · Deadlock-এর প্রতিকার — চারটি কৌশল আর তাদের প্রমাণ

ডায়াগ্রামের চার শর্তের যেকোনো একটি ভাঙলেই সমস্যা মেটে। পাঠ্যবই আর পরীক্ষায় সবচেয়ে বেশি আসে এই চারটি প্রতিকার:

semaphore room = 4;          // at most 4 philosophers at the table
philosopher(i):
  wait(room);
  lock(fork[i]); lock(fork[(i + 1) % 5]);
  eat();
  unlock(fork[(i + 1) % 5]); unlock(fork[i]);
  signal(room);

philosopher(i):
  if (i % 2 == 0) { lock(fork[i]);           lock(fork[(i + 1) % 5]); }  // even: left first
  else            { lock(fork[(i + 1) % 5]); lock(fork[i]); }            // odd: right first
  eat();
  unlock both;

monitor DiningPhilosophers {
  enum { THINKING, HUNGRY, EATING } state[5];
  condition self[5];

  void pickup(int i) {
    state[i] = HUNGRY;
    test(i);                                  // can I eat right now?
    if (state[i] != EATING) self[i].wait();   // no: sleep until a neighbour wakes me
  }
  void putdown(int i) {
    state[i] = THINKING;
    test((i + 4) % 5);                        // maybe my left neighbour can eat now
    test((i + 1) % 5);                        // maybe my right neighbour can eat now
  }
  void test(int i) {
    if (state[(i + 4) % 5] != EATING && state[i] == HUNGRY && state[(i + 1) % 5] != EATING) {
      state[i] = EATING;
      self[i].signal();
    }
  }
  init: for i in 0..4: state[i] = THINKING;
}

philosopher(i):
  a = min(i, (i + 1) % 5);  b = max(i, (i + 1) % 5);
  lock(fork[a]); lock(fork[b]);     // always the lower-numbered fork first
  eat();
  unlock(fork[b]); unlock(fork[a]);

এবার resource ordering আসল থ্রেড আর mutex দিয়ে — পাঁচজন দার্শনিক প্রত্যেকে ১,০০০ বার খান। খাওয়ার সময় প্রত্যেকে একটি atomic পতাকা তোলেন, আর দেখেন কোনো প্রতিবেশীর পতাকা ওঠানো কি না (তাহলে দুজন একই fork-এ — নিয়মভঙ্গ):

#include <pthread.h>
#include <stdatomic.h>
#include <stdint.h>
#include <stdio.h>
#define P 5
#define K 1000                                 /* meals per philosopher */
static pthread_mutex_t forks[P];
static atomic_int eating[P], clashes;
static int meals[P], uses[P];
static void *philosopher(void *arg) {
    int i = (int)(intptr_t)arg, left = i, right = (i + 1) % P;
    int first = left < right ? left : right;   /* lower-numbered fork first */
    int second = left < right ? right : left;
    for (int k = 0; k < K; k++) {
        pthread_mutex_lock(&forks[first]);
        pthread_mutex_lock(&forks[second]);
        atomic_store(&eating[i], 1);           /* eating: neighbours must not be */
        if (atomic_load(&eating[(i + P - 1) % P]) || atomic_load(&eating[right]))
            atomic_fetch_add(&clashes, 1);
        meals[i]++; uses[left]++; uses[right]++;
        atomic_store(&eating[i], 0);
        pthread_mutex_unlock(&forks[second]);
        pthread_mutex_unlock(&forks[first]);
    }
    return NULL;
}
int main(void) {
    pthread_t t[P];
    for (int i = 0; i < P; i++) pthread_mutex_init(&forks[i], NULL);
    for (int i = 0; i < P; i++) pthread_create(&t[i], NULL, philosopher, (void *)(intptr_t)i);
    for (int i = 0; i < P; i++) pthread_join(t[i], NULL);
    int total = 0, ok = 1;
    for (int i = 0; i < P; i++) {
        int r = (i + 1) % P;
        printf("P%d: ate %d times, takes fork %d then %d\n", i, meals[i], i < r ? i : r, i < r ? r : i);
        total += meals[i]; if (uses[i] != 2 * K) ok = 0;
    }
    printf("total meals = %d, every fork used %d times: %s\n", total, 2 * K, ok ? "yes" : "no");
    printf("neighbours eating together: %d | all threads finished: no deadlock\n", atomic_load(&clashes));
    return 0;
}

P0: ate 1000 times, takes fork 0 then 1
P1: ate 1000 times, takes fork 1 then 2
P2: ate 1000 times, takes fork 2 then 3
P3: ate 1000 times, takes fork 3 then 4
P4: ate 1000 times, takes fork 0 then 4
total meals = 5000, every fork used 2000 times: yes
neighbours eating together: 0 | all threads finished: no deadlock

Chandy–Misra — পরিষ্কার আর ময়লা fork

উপরের সমাধানগুলোতে হয় একটি কেন্দ্রীয় monitor লাগে, নয়তো সবাইকে একটি সাধারণ নম্বর-ক্রম মানতে হয়। K. Mani Chandy আর Jayadev Misra ১৯৮৪ সালে (“The Drinking Philosophers Problem”, ACM TOPLAS) একটি বিতরণকৃত (distributed) সমাধান দেন, যেখানে দার্শনিকেরা শুধু প্রতিবেশীর সাথে বার্তা আদান-প্রদান করেন। মূল নিয়ম: প্রতিটি fork “পরিষ্কার” বা “ময়লা”. শুরুতে প্রতিটি fork ছোট id-এর প্রতিবেশীর হাতে, ময়লা অবস্থায়। ক্ষুধার্ত হলে দার্শনিক প্রতিবেশীর কাছে অনুরোধ পাঠান। যার হাতে ময়লা fork আছে আর যিনি খাচ্ছেন না, তিনি অনুরোধ পেলে সেটি পরিষ্কার করে দিয়ে দেন; পরিষ্কার fork খাওয়ার আগে কেউ ছাড়েন না। খাওয়ার পর সব fork ময়লা হয়ে যায়। ফলে যিনি সদ্য খেয়েছেন, তিনি অগ্রাধিকার হারান, আর অগ্রাধিকারের একটি চক্রহীন ক্রম সবসময় বজায় থাকে — deadlock আর starvation দুটোই নেই।

Deadlock বনাম starvation — পার্থক্যটি স্পষ্ট করুন

তৃতীয় একটি অবস্থাও আছে — livelock. ধরুন প্রত্যেক দার্শনিক বাঁ fork তুলে ডানটি না পেলে বাঁটি নামিয়ে রেখে আবার চেষ্টা করেন। সবাই একই তালে চললে সবাই একসাথে তোলেন, একসাথে নামান, আবার তোলেন — কেউ ঘুমাচ্ছেন না, CPU ব্যস্ত, অথচ কেউ খাচ্ছেন না। ঠিক যেন সরু গলিতে মুখোমুখি দুজন, দুজনেই একসাথে একই দিকে সরে যাচ্ছেন। সমাধান সাধারণত এলোমেলো অপেক্ষা (random backoff) — Ethernet-এর সংঘর্ষ সামলানোর কৌশলের মতো।

৮ · Sleeping barber, cigarette smokers আর বাস্তব সিস্টেম

Sleeping barber — ঘুমন্ত নাপিত

Sleeping barber সমস্যাটিও Dijkstra-র ১৯৬০-এর দশকের লেখা থেকে। একটি সেলুনে একজন নাপিত, একটি কাটার চেয়ার আর অপেক্ষার n-টি চেয়ার। কোনো খদ্দের না থাকলে নাপিত ঘুমান। খদ্দের এসে নাপিতকে ঘুমন্ত দেখলে জাগান; নাপিত ব্যস্ত থাকলে খালি চেয়ারে বসেন; কোনো চেয়ার খালি না থাকলে চলে যান। এটি আসলে একটি bounded buffer, যেখানে buffer ভর্তি হলে producer অপেক্ষা না করে চলে যায় — ঠিক যেমন ভিড় হলে web server নতুন অনুরোধ ফিরিয়ে দেয় (HTTP 503). সমাধানের কাঠামো (Tanenbaum-এর বইয়ে প্রচলিত রূপ):

semaphore customers = 0, barber = 0, mutex = 1;  int waiting = 0;

barber:                              customer:
  while (true) {                       wait(mutex);
    wait(customers);  // sleep if none   if (waiting < CHAIRS) {
    wait(mutex);                           waiting++;
    waiting--;                             signal(customers);  // wake barber if asleep
    signal(barber);   // call next one     signal(mutex);
    signal(mutex);                         wait(barber);       // wait for my turn
    cut_hair();                            get_haircut();
  }                                      } else {
                                           signal(mutex);      // shop full: leave
                                         }

waiting একটি সাধারণ পূর্ণসংখ্যা, কারণ খদ্দেরকে মান পড়ে সিদ্ধান্ত নিতে হয় (“চেয়ার খালি আছে?”) — semaphore-এর মান পড়ে সিদ্ধান্ত নেওয়ার নির্ভরযোগ্য উপায় নেই। তাই mutex দিয়ে রক্ষিত একটি counter, আর ঘুম-জাগানোর জন্য আলাদা দুটি semaphore.

Cigarette smokers — ধূমপায়ীদের সমস্যা

Cigarette smokers সমস্যা ১৯৭১ সালে Suhas Patil দেন। তিনজন ধূমপায়ী; সিগারেট বানাতে তামাক, কাগজ আর দেশলাই লাগে। প্রত্যেকের কাছে একটি উপকরণ অফুরন্ত। একজন “এজেন্ট” প্রতিবার এলোমেলোভাবে বাকি দুটি উপকরণ টেবিলে রাখে; যার কাছে তৃতীয়টি আছে, তাকেই নিতে হবে, আর সে শেষ করলে এজেন্ট আবার রাখবে। কঠিন শর্ত: এজেন্টের কোড বদলানো যাবে না — সে শুধু প্রতিটি উপকরণের জন্য একটি করে semaphore-এ signal দেয়। কাগজের ধূমপায়ী সরল মনে wait(tobacco); wait(match); লিখলে বিপদ: এজেন্ট রাখল তামাক আর কাগজ, কাগজের ধূমপায়ী তামাক তুলে নিল, দেশলাইয়ের ধূমপায়ী কাগজ পেল কিন্তু তামাক আর নেই — দুজনেই একটি করে ধরে বসে আছে।

প্রচলিত সমাধান (Allen Downey-র “The Little Book of Semaphores”-এ সুন্দরভাবে আছে) তিনটি সহকারী “pusher” থ্রেড যোগ করে। প্রতিটি pusher একটি উপকরণের semaphore-এ অপেক্ষা করে; জাগলে একটি mutex ধরে বুলিয়ান পতাকা দেখে — অন্য উপকরণটি আগেই এসেছে কি না। এসে থাকলে ঠিক সেই ধূমপায়ীকে signal দেয়, যার কাছে তৃতীয়টি আছে; নইলে নিজের উপকরণের পতাকা তুলে রাখে। শিক্ষা: যখন সিদ্ধান্ত নির্ভর করে কোন কোন ঘটনা ঘটেছে তার সমন্বয়ের ওপর, তখন semaphore-এর সাথে mutex-রক্ষিত অবস্থা (state) লাগে — ঠিক monitor-এর ধারণা।

বাস্তব সিস্টেমে এই ছাঁচগুলো

ডেটাবেস কীভাবে এগুলো সামলায়, দেখুন DBMS কোর্সের concurrency control পর্বে। আর Linux kernel lock-এর ক্রম রক্ষার জন্য নিজেই পাহারা দেয়: lockdep নামের একটি debug ব্যবস্থা প্রতিটি lock নেওয়ার ক্রম মনে রাখে, আর কোথাও উল্টো ক্রম দেখা গেলেই — deadlock আসলে না ঘটলেও — সতর্কবার্তা দেয়।

৯ · AI-এর যুগে ক্লাসিক সমস্যা

“Producer-consumer-এর C কোড দাও” — AI এক সেকেন্ডে দেবে, আর বেশিরভাগ সময় কোডটি দেখতে পাঠ্যবইয়ের মতো। কিন্তু এই সমস্যাগুলোর বাগ লুকিয়ে থাকে এক লাইনের ক্রমে, আর সাধারণ টেস্টে সেটি প্রায় কখনো ধরা পড়ে না। AI-এর সাধারণ ভুল:

AI-এর লেখা সমন্বয়-কোড ব্যবহারের আগে — চেকলিস্ট

• প্রতিটি semaphore বা condition variable কোন শর্ত বোঝায়, আর তার invariant (যেমন empty + full = N) বলতে পারি
• কোনো থ্রেড একটি lock ধরে এমন কিছুর জন্য ঘুমায় না, যা ঘটাতে অন্যকে সেই lock-ই লাগবে
• একাধিক lock নেওয়া হলে সবাই একই ক্রমে নেয়; ক্রমটি কোডে লেখা আছে
• starvation সম্ভব কি না ভেবেছি — অগ্রাধিকার-নীতি (reader, writer, FIFO) জানা আছে
• ছোট buffer, ধীর consumer, বেশি থ্রেড আর -fsanitize=thread দিয়ে শতবার চালিয়ে যোগফল মিলিয়েছি
• API আমার OS-এর (POSIX বনাম Win32, Linux বনাম macOS); man page মিলিয়ে দেখেছি