Condition variable আর monitor

১ · Semaphore-এর পরে কী বাকি থাকে — শর্তের জন্য অপেক্ষা

পর্ব ২২-এ দেখেছেন critical section কী, আর পর্ব ২৪-এ mutex আর semaphore. Mutex একটি প্রশ্নের উত্তর দেয়: “এই মুহূর্তে কি অন্য কেউ ভেতরে আছে?” কিন্তু concurrent প্রোগ্রামে আরেকটি প্রশ্নও বারবার আসে: “আমি যে অবস্থার জন্য অপেক্ষা করছি, সেটি কি এসেছে?” যেমন — queue-তে কি কোনো কাজ আছে? buffer-এ কি জায়গা খালি? সব worker কি প্রস্তুত? এই অবস্থাগুলোকে বলে শর্ত বা predicate.

প্রথম ভুল পথ — busy-waiting

সবচেয়ে সরল সমাধান একটি লুপে শর্তটি বারবার দেখা:

pthread_mutex_lock(&m);
while (count == 0) {              /* nothing to take yet */
    pthread_mutex_unlock(&m);     /* let the producer in ...    */
    pthread_mutex_lock(&m);       /* ... and look again at once */
}
item = take(); count--;
pthread_mutex_unlock(&m);

এটি কাজ করে, কিন্তু খুব খরুচে। একে বলে busy-waiting: অপেক্ষারত থ্রেড ঘুমায় না, CPU-তে বসে লক্ষ লক্ষবার একই প্রশ্ন করে। এক core-এর মেশিনে আরও খারাপ — যে থ্রেড শর্তটি সত্য করবে, সে CPU-ই পায় না যতক্ষণ না অপেক্ষাকারীর time slice শেষ হয়। পর্ব ২৩-এর spinlock-এ খুব অল্প সময়ের জন্য ঘোরা যুক্তিসংগত; কিন্তু “queue-তে কাজ আসা” কয়েক মিলিসেকেন্ড থেকে কয়েক ঘণ্টা পরেও হতে পারে। তখন ঘুমানোই একমাত্র ঠিক পথ।

দ্বিতীয় পথ — semaphore দিয়ে শর্ত

Semaphore দিয়ে ঘুমানো যায়, আর Dijkstra-র P/V দিয়ে প্রায় সব সমন্বয়ই লেখা সম্ভব। পর্ব ২৬-এর bounded buffer-এ দেখবেন তিনটি semaphore: mutex, empty (খালি ঘরের সংখ্যা) আর full (ভরা ঘরের সংখ্যা)। তবে বড় প্রোগ্রামে semaphore-এর দুর্বলতা স্পষ্ট হয়:

• একই হাতিয়ার দুই কাজে: একটি semaphore কখনো তালা (mutual exclusion), কখনো গণনা (কতগুলো ঘর খালি), কখনো সংকেত। কোডে P(s) দেখে বোঝার উপায় নেই কোনটি কোন উদ্দেশ্যে।
• ক্রম ভুল হলে deadlock: bounded buffer-এর producer-এ P(empty); P(mutex);-এর জায়গায় P(mutex); P(empty); লিখলে buffer ভরা থাকলে producer mutex হাতে নিয়েই ঘুমায় — consumer আর ঢুকতে পারে না, দুজনেই চিরকাল আটকে (পর্ব ২৭-এর deadlock).
• ছড়িয়ে থাকা P আর V: একটি V ভুলে গেলে কেউ চিরকাল ঘুমায়, একটি বাড়তি V দিলে দুজন একসাথে critical section-এ। এই P আর V প্রোগ্রামের নানা ফাইলে ছড়িয়ে থাকে, তাই কোনো একটি জায়গা দেখে সঠিকতা যাচাই করা যায় না।
• জটিল শর্ত প্রকাশ করা কঠিন: “অন্তত ৩টি ঘর খালি এবং কোনো writer নেই” — এমন শর্ত একটি সংখ্যা দিয়ে প্রকাশ করা যায় না।

১৯৭০-এর দশকের শুরুতে ঠিক এই সমস্যাগুলো দেখে Per Brinch Hansen আর C. A. R. (Tony) Hoare একটি কাঠামোবদ্ধ বিকল্প প্রস্তাব করেন — monitor, যার ভেতরের অপেক্ষার হাতিয়ার condition variable. অংশ ৫-এ monitor-এর পুরো গল্প; তার আগে condition variable-কে আলাদা করে বুঝে নিই, কারণ আজকের pthreads-এ সেটিই সরাসরি পাওয়া যায়।

২ · Condition variable — wait, signal আর broadcast

Condition variable নিজে কোনো মান রাখে না — এটি শুধু ঘুমন্ত থ্রেডের একটি সারি। এর সাথে সবসময় থাকে একটি mutex (যা shared ডেটা রক্ষা করে) আর একটি শর্ত (যা ওই shared ডেটা নিয়ে একটি প্রশ্ন)। অপারেশন তিনটি:

দুটি কথা শুরুতেই মনে রাখুন। প্রথমত, condition variable-এর কোনো স্মৃতি নেই. কেউ অপেক্ষা না করার সময় signal দিলে তা হাওয়ায় মিলিয়ে যায়। Semaphore-এর V কিন্তু মনে রাখে — মান ১ বাড়ে, পরের P আর ঘুমায় না। এই পার্থক্যই অংশ ৪-এর lost wakeup-এর মূল। দ্বিতীয়ত, “অবিভাজ্যভাবে mutex ছাড়া আর ঘুমানো” অংশটিই condition variable-এর আসল জাদু: ছাড়া আর ঘুমের মাঝখানে কোনো ফাঁক থাকে না, যেখানে signal হারাতে পারে।

সঠিক ব্যবহারের ছাঁচ সবসময় একই, প্রায় মুখস্থ করার মতো:

/* waiting side */                       /* changing side */
pthread_mutex_lock(&m);                  pthread_mutex_lock(&m);
while (!condition)                       change_shared_state();   /* makes it true */
    pthread_cond_wait(&cv, &m);          pthread_cond_signal(&cv); /* or broadcast */
use_shared_state();   /* condition holds */ pthread_mutex_unlock(&m);
pthread_mutex_unlock(&m);

নিচের ডায়াগ্রামে একটি consumer (C) আর একটি producer (P) এই ছাঁচ মেনে এক-ঘরের একটি mailbox ব্যবহার করছে। দেখুন wait-এর ভেতরে mutex কখন ছাড়া হয়, কখন ফেরত আসে:

1C: lock(&m);2C: while (!full)3C:   cond_wait(&not_empty, &m);4C: x = slot; full = 0; unlock(&m);5P: lock(&m); slot = 10; full = 1;6P: cond_signal(&not_empty);7P: unlock(&m);

এবার আসল প্রোগ্রাম: একটি producer থ্রেড পাঁচটি সংখ্যা (10, 20, …, 50) পাঠায়, main থ্রেড consumer হিসেবে নেয়। ঘর একটিই, তাই দুটি condition variable লাগে — not_full (producer এখানে অপেক্ষা করে) আর not_empty (consumer এখানে)। ছাপা হয় lock ধরে, শর্ত বদলানোর মুহূর্তেই, তাই আউটপুটের ক্রম প্রতিবার একই:

#include <pthread.h>
#include <stdio.h>
static int slot, full = 0;                       /* the mailbox: one slot */
static pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
static pthread_cond_t not_full = PTHREAD_COND_INITIALIZER;
static pthread_cond_t not_empty = PTHREAD_COND_INITIALIZER;
static void *producer(void *arg) {
    (void)arg;
    for (int i = 1; i <= 5; i++) {
        pthread_mutex_lock(&m);
        while (full)                             /* slot taken: sleep */
            pthread_cond_wait(&not_full, &m);
        slot = i * 10; full = 1;
        printf("put %d\n", slot);
        pthread_cond_signal(&not_empty);         /* a letter has arrived */
        pthread_mutex_unlock(&m);
    }
    return NULL;
}
int main(void) {
    pthread_t p; int sum = 0;
    pthread_create(&p, NULL, producer, NULL);
    for (int k = 0; k < 5; k++) {                /* main is the consumer */
        pthread_mutex_lock(&m);
        while (!full)                            /* nothing yet: sleep */
            pthread_cond_wait(&not_empty, &m);
        printf("    got %d\n", slot);
        sum += slot; full = 0;
        pthread_cond_signal(&not_full);          /* the slot is free again */
        pthread_mutex_unlock(&m);
    }
    pthread_join(p, NULL);
    printf("sum = %d\n", sum);
    return 0;
}

put 10
    got 10
put 20
    got 20
put 30
    got 30
put 40
    got 40
put 50
    got 50
sum = 150

signal না broadcast? signal সস্তা — একজনকেই জাগায়। কিন্তু তিন অবস্থায় broadcast লাগে: (ক) একটি পরিবর্তনে একাধিক অপেক্ষাকারী এগোতে পারে (যেমন shutdown, বা অংশ ৮-এর latch); (খ) একই condition variable-এ ভিন্ন ভিন্ন শর্তের থ্রেড অপেক্ষা করে — signal ভুল জনকে জাগালে সে আবার ঘুমায় আর সঠিকজন ঘুমিয়েই থাকে; (গ) কে এগোতে পারবে আপনি জানেন না (অংশ ৭-এর ভিন্ন আকারের বরাদ্দ)। while লুপ থাকলে signal-এর জায়গায় broadcast দেওয়া সবসময় নিরাপদ — শুধু ধীর, কারণ সবাই জেগে lock-এর জন্য লাইন দেয় আর বেশিরভাগ আবার ঘুমায়। Lampson আর Redell এমন অবস্থাকে বলেছিলেন covering condition.

৩ · কেন সবসময় while — spurious wakeup আর “চুরি যাওয়া” জাগরণ

নতুনরা প্রায়ই লেখেন if (!full) wait(...) — যুক্তি সহজ: “signal তো তখনই আসে যখন শর্ত সত্য হয়েছে, তাহলে আবার দেখব কেন?” উত্তর: signal আসার মুহূর্তে শর্ত সত্য ছিল, কিন্তু wait থেকে ফেরার মুহূর্তে সত্য থাকবে — এমন কোনো প্রতিশ্রুতি pthreads দেয় না। দুটি কারণ:

1. Spurious wakeup: POSIX স্পষ্টভাবে অনুমতি দেয় যে কোনো signal ছাড়াই pthread_cond_wait ফিরতে পারে। আর pthread_cond_signal-এর সংজ্ঞাও “অন্তত একজনকে জাগাবে” — multiprocessor-এ দ্রুত বাস্তবায়নের জন্য কখনো দুজনও জাগতে পারে। Linux-এ বাস্তবে কারণ হতে পারে signal handler-এর বাধা বা futex-এর ভেতরের দৌড়। Windows-এর CONDITION_VARIABLE-এর ডকুমেন্টেশনও একই সতর্কবার্তা দেয়, আর Java-র Object.wait-এরও।
2. চুরি যাওয়া জাগরণ (stolen wakeup): signal পেয়ে জেগে ওঠা থ্রেড সঙ্গে সঙ্গে চলে না — তাকে mutex-এর জন্য লাইনে দাঁড়াতে হয়। সেই ফাঁকে অন্য একটি থ্রেড, যে সবে এসেছে আর কখনো ঘুমায়ইনি, mutex পেয়ে শর্তটি ভোগ করে ফেলতে পারে। এটিই Mesa semantics-এর স্বাভাবিক ফল (অংশ ৬)।

দ্বিতীয়টি কীভাবে ঘটে, ধাপে ধাপে দেখুন। দুজন consumer (C1, C2), একজন producer (P), আর একটিমাত্র item:

1consumer: lock(&m);2  if (items == 0)      // BUG: if, not while3    cond_wait(&cv, &m);4  items--;  take();  unlock(&m);5producer: lock(&m); items++;6  cond_signal(&cv); unlock(&m);

while কেন যথেষ্ট — একটি ছোট যুক্তি

বিশ্ববিদ্যালয়ের পরীক্ষায় প্রায়ই জিজ্ঞেস করা হয়, while লুপ “কেন সঠিক”। যুক্তিটি loop invariant দিয়ে:

• দাবি: while (!B) wait(cv, m); লুপ থেকে বেরোনোর মুহূর্তে থ্রেডটি m ধরে আছে আর B সত্য।
• প্রমাণ: লুপের প্রতিটি পরীক্ষার সময় থ্রেড m ধরে থাকে — লুপের আগে lock নেওয়া হয়েছে, আর wait ফেরার আগে lock আবার নেয়। লুপ থেকে বেরোনো যায় শুধু একটি পথে: পরীক্ষায় B সত্য পাওয়া। পরীক্ষা আর বেরোনোর মাঝে lock ছাড়া হয়নি, আর B শুধু m-রক্ষিত ডেটা দিয়ে লেখা, তাই অন্য কেউ এর মধ্যে B বদলাতে পারেনি। কতবার, কেন বা কে জাগিয়েছে — কোনোটিই যুক্তিতে লাগেনি। ∎
• ফল: while থাকলে নিরাপত্তা (safety) signal-এর ওপর নির্ভর করে না; signal শুধু অগ্রগতির (liveness) জন্য — B সত্য হওয়ার পর অন্তত একজন অপেক্ষাকারীকে কেউ জাগাবে। তাই বাড়তি signal বা broadcast কখনো ভুল ঘটায় না, আর signal কম পড়লে ঘটে শুধু চিরকালের ঘুম। Lampson আর Redell ঠিক এই অর্থে signal-কে বলেছিলেন একটি “ইঙ্গিত” (hint).

৪ · Lost wakeup — শর্ত আর ঘুমের মাঝের ফাঁক

while লুপ সঠিক, কিন্তু শুধু তখনই, যখন শর্ত পরীক্ষা আর শর্ত বদলানো দুটোই একই mutex ধরে হয়। কেউ “গতি বাড়াতে” lock ছাড়াই শর্তটি দেখলে বা বদলালে একটি সূক্ষ্ম বাগ জন্মায়: lost wakeup. মনে আছে, condition variable-এর স্মৃতি নেই? কেউ সারিতে ঢোকার আগেই signal এসে গেলে সেটি হারিয়ে যায়, আর পরে ঘুমানো থ্রেডটিকে জাগানোর আর কেউ থাকে না।

/* waiter: checks the flag WITHOUT the lock */
while (!ready) {                          /* (1) reads ready == 0       */
    pthread_mutex_lock(&m);               /*     ... preempted here ... */
    pthread_cond_wait(&cv, &m);           /* (4) sleeps -- forever?     */
    pthread_mutex_unlock(&m);
}
/* setter: changes the flag WITHOUT the lock */
ready = 1;                                /* (2) */
pthread_cond_signal(&cv);                 /* (3) nobody is waiting yet  */

1W: while (!ready) {        // no lock!2W:   lock(&m);3W:   cond_wait(&cv, &m);4S: ready = 1;               // no lock!5S: cond_signal(&cv);6// semaphore: V(s) is remembered

signal কি lock ধরে দেবেন, না ছেড়ে?

এখানে একটি সূক্ষ্ম পার্থক্য আছে। শর্ত বদলানো lock ধরে করা বাধ্যতামূলক — নইলে উপরের বাগ। কিন্তু signal নিজে unlock-এর আগে না পরে দেবেন, তা নিয়ে POSIX নমনীয়: সঠিকতার জন্য দুটিই চলে, শুধু শর্ত বদলানো lock ধরে হলেই। POSIX-এর ভাষায় mutex ধরা না থাকলেও signal ডাকা যায়, তবে “পূর্বানুমেয় scheduling আচরণ” চাইলে mutex ধরে ডাকতে হবে। দুই পক্ষের যুক্তি:

৫ · Monitor — mutual exclusion ভেতরেই বাঁধা

এতক্ষণ mutex আর condition variable আলাদা দুটি জিনিস ছিল, আর সঠিকভাবে জোড়া লাগানোর দায়িত্ব ছিল প্রোগ্রামারের। Monitor সেই দায়িত্ব ভাষা বা compiler-এর হাতে তুলে দেয়। একটি monitor হলো একটি মডিউল বা class, যার মধ্যে থাকে:

• shared ডেটা — যা বাইরের কেউ সরাসরি ছুঁতে পারে না;
• procedure (method) — ডেটা ছোঁয়ার একমাত্র পথ; আর নিয়ম: যেকোনো মুহূর্তে monitor-এর ভেতরে সর্বোচ্চ একটি থ্রেড সক্রিয় — compiler নিজেই প্রতিটি procedure-এর শুরুতে lock আর শেষে unlock বসায়;
• condition variable — monitor-এর ভেতরে অপেক্ষার জন্য, x.wait() আর x.signal();
• শুরুর কোড — ডেটার প্রাথমিক মান।

ঢুকতে চাওয়া কিন্তু অপেক্ষারত থ্রেডরা থাকে monitor-এর দরজার entry queue-তে; প্রতিটি condition variable-এর আলাদা সারি থাকে। x.wait() ডাকা থ্রেড monitor ছেড়ে x-এর সারিতে যায়, ফলে আরেকজন ঢুকতে পারে। Pseudocode-এ (Pascal-ঘেঁষা, পাঠ্যবইয়ের রীতিতে) এক-ঘরের mailbox:

monitor Mailbox {
    int slot;  bool full = false;        // shared data: only reachable inside
    condition notFull, notEmpty;

    procedure put(int v) {               // compiler adds: enter (lock)
        while (full) notFull.wait();
        slot = v;  full = true;
        notEmpty.signal();
    }                                    // compiler adds: leave (unlock)

    procedure get() returns int {
        while (!full) notEmpty.wait();
        full = false;  notFull.signal();
        return slot;
    }
}

অংশ ২-এর C প্রোগ্রামের সাথে তুলনা করুন: lock/unlock উধাও, slot আর full বাইরে থেকে ছোঁয়া যায় না, আর condition variable ঘোষণা হয়েছে ঠিক যে ডেটার সাথে সম্পর্কিত তার পাশে। সব সমন্বয়ের কোড এক জায়গায় — এক নজরে যাচাই করা যায়। অংশ ১-এর semaphore-এর সমস্যাগুলোর মধ্যে “lock ভুলে যাওয়া” আর “ভুল জায়গায় unlock” এখানে আর সম্ভবই নয়।

Monitor invariant

Monitor নিয়ে যুক্তি দেওয়ার মূল হাতিয়ার একটি monitor invariant — shared ডেটা নিয়ে এমন একটি শর্ত, যা monitor-এর ভেতরে কেউ না থাকলে সবসময় সত্য। mailbox-এ: “full সত্য হলে slot-এ একটি বৈধ, এখনো না-নেওয়া মান আছে”। নিয়ম হলো, প্রতিটি থ্রেড monitor ছাড়ার আগে — procedure-এর শেষে এবং wait() ডাকার আগে — invariant আবার সত্য করবে, কারণ wait-এর মুহূর্তে অন্য কেউ ঢুকবে। ভেতরে কাজের মাঝখানে invariant সাময়িক ভাঙতে পারে; কেউ তো দেখছে না।

৬ · Hoare বনাম Mesa — signal দিলে কে চলবে?

ধরুন থ্রেড P monitor-এর ভেতরে, আর x-এর সারিতে থ্রেড C ঘুমিয়ে। P x.signal() ডাকল। monitor-এর নিয়ম বলে ভেতরে একজনই সক্রিয় থাকবে — তাহলে কে? দুটি উত্তর, আর তাদের ফল অনেক দূর পর্যন্ত যায়।

একটি তৃতীয় রূপও আছে, Brinch Hansen-এর Concurrent Pascal-এ: signal হবে procedure-এর শেষ কাজ, আর signal দিয়েই P monitor ছেড়ে যায় (“signal-and-exit” বা signal-and-return). এতে Hoare-এর নিশ্চয়তা থাকে, কিন্তু urgent queue লাগে না। নিচে একই ঘটনা দুই semantics-এ পাশাপাশি দেখুন — C1 অপেক্ষায়, P একটি item দিয়ে signal দেয়, আর C2 দরজার লাইনে:

1C1, C2: while/if (items == 0) x.wait(); items--;2P:      items++; x.signal();3P:      ... more work inside ...; leave4arrival order at the door: C1, P, C2

একই ঘটনা নিচের ছোট simulator-এ চালিয়ে দেখুন। প্রতিটি থ্রেড একটি JavaScript generator: yield 'wait' বা yield 'signal' মানে monitor-এর কাছে অনুরোধ, আর run() নিয়ম অনুযায়ী ঠিক করে পরের জন কে। তিনটি সংমিশ্রণ চলে — Hoare + if, Mesa + if, Mesa + while:

// Monitor simulator: C1 waits for an item, P puts 1 item and signals, C2 queues at the door.
function* consumer(me, S, useWhile) {
  if (useWhile) { while (S.items === 0) { S.say(me + ' sees items=0, waits'); yield 'wait'; } }
  else if (S.items === 0) { S.say(me + ' sees items=0, waits'); yield 'wait'; }
  S.items--; S.say(me + ' takes item -> items=' + S.items + (S.items < 0 ? '  BUG!' : ''));
}
function* producer(S) {
  S.items++; S.say('P puts item -> items=' + S.items + ', signal(x)');
  yield 'signal';
  S.say('P continues inside the monitor');
}
function run(sem, useWhile) {
  const S = { items: 0, out: [], say(m) { this.out.push('  ' + m); } };
  const g = { C1: consumer('C1', S, useWhile), P: producer(S), C2: consumer('C2', S, useWhile) };
  const entry = ['C1', 'P', 'C2'], urgent = [], condQ = [];
  let owner = entry.shift();
  while (owner) {
    S.out.push('[' + owner + ' runs]  entry=' + (entry.join(',') || '-') + '  urgent=' + (urgent.join(',') || '-') + '  x=' + (condQ.join(',') || '-'));
    const act = g[owner].next().value;            // run owner until its next monitor action
    if (act === 'signal' && condQ.length) {
      const w = condQ.shift();
      if (sem === 'Hoare') { urgent.push(owner); owner = w; continue; }   // signal-and-wait
      entry.push(w);                                        // Mesa: back to the door
    }
    if (act === 'signal') { continue; }           // signaller keeps the monitor
    if (act === 'wait') condQ.push(owner);        // release monitor, sleep on x
    owner = urgent.shift() || entry.shift();      // leave: urgent first, then the entry queue
  }
  console.log('== ' + sem + ' + ' + (useWhile ? 'while' : 'if') + ' ==');
  console.log(S.out.join('\n') + '\n  end: items=' + S.items + ', still waiting on x: ' + (condQ.join(',') || 'none'));
}
run('Hoare', false); run('Mesa', false); run('Mesa', true);

== Hoare + if ==
[C1 runs]  entry=P,C2  urgent=-  x=-
  C1 sees items=0, waits
[P runs]  entry=C2  urgent=-  x=C1
  P puts item -> items=1, signal(x)
[C1 runs]  entry=C2  urgent=P  x=-
  C1 takes item -> items=0
[P runs]  entry=C2  urgent=-  x=-
  P continues inside the monitor
[C2 runs]  entry=-  urgent=-  x=-
  C2 sees items=0, waits
  end: items=0, still waiting on x: C2
== Mesa + if ==
[C1 runs]  entry=P,C2  urgent=-  x=-
  C1 sees items=0, waits
[P runs]  entry=C2  urgent=-  x=C1
  P puts item -> items=1, signal(x)
[P runs]  entry=C2,C1  urgent=-  x=-
  P continues inside the monitor
[C2 runs]  entry=C1  urgent=-  x=-
  C2 takes item -> items=0
[C1 runs]  entry=-  urgent=-  x=-
  C1 takes item -> items=-1  BUG!
  end: items=-1, still waiting on x: none
== Mesa + while ==
[C1 runs]  entry=P,C2  urgent=-  x=-
  C1 sees items=0, waits
[P runs]  entry=C2  urgent=-  x=C1
  P puts item -> items=1, signal(x)
[P runs]  entry=C2,C1  urgent=-  x=-
  P continues inside the monitor
[C2 runs]  entry=C1  urgent=-  x=-
  C2 takes item -> items=0
[C1 runs]  entry=-  urgent=-  x=-
  C1 sees items=0, waits
  end: items=0, still waiting on x: C1

৭ · Semaphore দিয়ে monitor বানানো আর resource allocator

Hoare-এর ১৯৭৪ সালের প্রবন্ধের একটি বড় দাবি ছিল: monitor semaphore-এর চেয়ে বেশি শক্তিশালী নয়, শুধু বেশি কাঠামোবদ্ধ — কারণ semaphore দিয়েই monitor বানানো যায়। পাঠ্যবইয়ে (Silberschatz-দের Operating System Concepts-এ) এই নির্মাণটি Hoare semantics-এর জন্য দেওয়া আছে, আর পরীক্ষায় এটি বারবার আসে। উপাদান পাঁচটি:

/* every monitor procedure F becomes: */
wait(mutex);
    ... body of F ...
if (next_count > 0) signal(next);     /* a signaller is parked: let it back in */
else                signal(mutex);    /* otherwise open the door               */

/* x.wait() */
x_count++;
if (next_count > 0) signal(next);     /* hand the monitor to a parked signaller */
else                signal(mutex);
wait(x_sem);                          /* sleep on x */
x_count--;

/* x.signal() */
if (x_count > 0) {                    /* no waiter: do nothing */
    next_count++;
    signal(x_sem);                    /* wake one waiter on x ...        */
    wait(next);                       /* ... and park myself (urgent)    */
    next_count--;
}

কেন্দ্রীয় কৌশলটির নাম baton passing: monitor থেকে বেরোনোর সময় থ্রেড “দরজা খুলে দেয়” না, বরং ব্যাটনটি (ভেতরে থাকার অধিকার) সরাসরি একজনের হাতে তুলে দেয় — আগে next-এ পার্ক করা কাউকে, কেউ না থাকলে তবেই mutex খুলে দরজার লাইনকে। x.signal-এ ব্যাটন যায় x-এর অপেক্ষাকারীর হাতে, mutex-এ হাত না দিয়েই। ফলে ব্যাটন যখন যেখানে যায়, mutex-এর মান 0-ই থাকে, আর লাইনের কেউ ফাঁক গলে ঢুকতে পারে না। এটিই Hoare-এর নিশ্চয়তা বাস্তবায়ন করে। ধাপে ধাপে দেখুন — C1 একটি procedure-এ x.wait() করে, P আরেকটিতে x.signal():

1F():  wait(mutex);2      body;3      if (next_count>0) signal(next); else signal(mutex);4x.wait:  x_count++;5  if (next_count>0) signal(next); else signal(mutex);6  wait(x_sem);  x_count--;7x.signal: if (x_count>0) {8  next_count++; signal(x_sem);9  wait(next); next_count--; }

Resource allocator — অগ্রাধিকারসহ অপেক্ষা

Hoare-এর প্রবন্ধে আরেকটি ধারণা ছিল conditional wait (scheduled wait): x.wait(c), যেখানে c একটি অগ্রাধিকার-সংখ্যা। x.signal() জাগায় সবচেয়ে ছোট সংখ্যার থ্রেডকে। পাঠ্যবইয়ের উদাহরণ: একটি সম্পদ (ধরুন একটি প্রিন্টার বা একটি টেপ ড্রাইভ) একবারে একজনকে দেওয়া হবে, আর যে যত কম সময় ব্যবহার করবে বলে জানায়, সে তত আগে পাবে — পর্ব ১৭-এর SJF-এর মতো, যা গড় অপেক্ষা কমায়।

monitor ResourceAllocator {
    bool busy = false;
    condition x;
    procedure acquire(int time) {      /* time = how long I will use it */
        if (busy) x.wait(time);         /* sleep, ordered by time         */
        busy = true;
    }
    procedure release() {
        busy = false;
        x.signal();                     /* wakes the smallest 'time'      */
    }
}
/* every user must follow:  R.acquire(t);  ...use...;  R.release(); */

লক্ষ করুন if — Hoare semantics-এ এটি বৈধ, কারণ release-এর signal-এর সাথে সাথেই জাগা থ্রেড চলে আর busy তখন false. Mesa semantics-এ এখানে while লাগবে, আর তখন অগ্রাধিকারের প্রতিশ্রুতিও দুর্বল হয়: জাগা থ্রেড দরজার লাইনে দাঁড়ানোর ফাঁকে নতুন আসা কেউ (যে কখনো ঘুমায়নি, যার time হয়তো বড়) আগে সম্পদ নিয়ে নিতে পারে। বাস্তবে এর সমাধান হলো সম্পদটি release-এর সময় সরাসরি জাগা থ্রেডের নামে বরাদ্দ করা (“hand-off”), অথবা সারির ক্রম নিজে একটি priority queue-তে রাখা। আর একটি সাবধানতা: SJF-এর মতোই বড় time-এর থ্রেড অনির্দিষ্টকাল starvation-এ পড়তে পারে, যদি ছোট কাজ আসতেই থাকে।

এই উদাহরণ monitor-এর একটি সীমাও দেখায়: monitor শুধু নিশ্চিত করে যে acquire আর release-এর ভেতরে কেউ মিশে যাবে না। কিন্তু কেউ acquire না করেই সম্পদ ব্যবহার করলে, বা release ভুলে গেলে, বা দুবার release করলে monitor কিছু করতে পারে না — ঠিক semaphore-এর মতো দায় তখন ফিরে আসে ব্যবহারকারীর কাছে। সমাধান হলো সম্পদটিকেই monitor-এর ভেতরে রাখা, যাতে বাইরের কেউ সরাসরি ছুঁতে না পারে।

৮ · বাস্তবের ভাষায় monitor — আর barrier ও latch

আধুনিক ভাষাগুলো monitor-এর ধারণা নিয়েছে, তবে প্রায় সবাই Mesa semantics-এ, আর অনেকে কিছুটা ঢিলেঢালাভাবে। নিচে একই এক-ঘরের mailbox পাঁচটি পরিবেশে (এগুলো এই পাতায় চালানো যায় না):

class Mailbox {
    private int slot;
    private boolean full = false;

    public synchronized void put(int v) throws InterruptedException {
        while (full) wait();          // releases this object's monitor
        slot = v; full = true;
        notifyAll();                  // one wait set for everyone: wake all
    }
    public synchronized int get() throws InterruptedException {
        while (!full) wait();
        full = false;
        notifyAll();
        return slot;
    }
}

import java.util.concurrent.locks.*;

class Mailbox2 {
    private final ReentrantLock lock = new ReentrantLock();
    private final Condition notFull = lock.newCondition();
    private final Condition notEmpty = lock.newCondition();
    private int slot; private boolean full;

    void put(int v) throws InterruptedException {
        lock.lock();
        try {
            while (full) notFull.await();
            slot = v; full = true;
            notEmpty.signal();        // two conditions: signal() is enough
        } finally { lock.unlock(); }  // unlock on every path
    }
}

class Mailbox {
    private readonly object gate = new object();
    private int slot; private bool full;

    public void Put(int v) {
        lock (gate) {                       // Monitor.Enter / Monitor.Exit
            while (full) Monitor.Wait(gate);
            slot = v; full = true;
            Monitor.PulseAll(gate);         // like notifyAll
        }
    }
    public int Get() {
        lock (gate) {
            while (!full) Monitor.Wait(gate);
            full = false;
            Monitor.PulseAll(gate);
            return slot;
        }
    }
}

package main

import "fmt"

func main() {
    box := make(chan int)            // unbuffered channel: a rendezvous
    done := make(chan struct{})
    go func() {
        for v := range box {          // receive until closed
            fmt.Println("got", v)
        }
        close(done)
    }()
    for i := 1; i <= 3; i++ {
        box <- i * 10                 // blocks until the consumer takes it
    }
    close(box)
    <-done
}

import threading

class Mailbox:
    def __init__(self):
        self.cv = threading.Condition()   # owns a lock (an RLock by default)
        self.full, self.slot = False, None

    def put(self, v):
        with self.cv:                       # acquire / release
            self.cv.wait_for(lambda: not self.full)   # the while loop, built in
            self.slot, self.full = v, True
            self.cv.notify_all()

    def get(self):
        with self.cv:
            self.cv.wait_for(lambda: self.full)
            self.full = False
            self.cv.notify_all()
            return self.slot

#include <windows.h>
static SRWLOCK lock = SRWLOCK_INIT;
static CONDITION_VARIABLE notEmpty = CONDITION_VARIABLE_INIT;
static int full, slot;

int get(void) {
    AcquireSRWLockExclusive(&lock);
    while (!full)                                  /* spurious wakeups happen */
        SleepConditionVariableSRW(&notEmpty, &lock, INFINITE, 0);
    full = 0;
    int v = slot;
    ReleaseSRWLockExclusive(&lock);
    return v;
}
/* producer side: ... full = 1; WakeConditionVariable(&notEmpty); */

Barrier আর countdown latch — “সবাই প্রস্তুত হলে একসাথে”

অনেক সময় অপেক্ষার শর্ত হলো একটি সংখ্যা: “N জন worker প্রস্তুত হয়েছে”। ক্রিকেট ম্যাচের শুরুর মতো — দুই আম্পায়ার, এগারোজন ফিল্ডার আর দুই ব্যাটার জায়গায় না দাঁড়ালে প্রথম বল হয় না। এর জন্য দুটি পরিচিত হাতিয়ার:

• Countdown latch: একটি গণনা N থেকে শুরু; প্রত্যেকে count_down করে, আর await করা থ্রেডরা 0 হওয়া পর্যন্ত অপেক্ষা করে। একবার 0 হলে চিরকাল খোলা — আবার ব্যবহার করা যায় না। Java-র CountDownLatch, C++20-এর std::latch, Go-র sync.WaitGroup (প্রায় একই), Linux kernel-এর completion.
• Barrier: N জন থ্রেড প্রত্যেকে barrier_wait ডেকে থামে; N-তম জন পৌঁছালে সবাই একসাথে ছাড়া পায়, আর barrier পরের দফার জন্য নিজেকে আবার প্রস্তুত করে (cyclic). POSIX-এর pthread_barrier_t — pthread_barrier_wait ঠিক একজনকে PTHREAD_BARRIER_SERIAL_THREAD ফেরত দেয় (“দফার শেষে একজন সারাংশ লিখুক”), বাকিদের 0. Java-র CyclicBarrier, C++20-এর std::barrier. সাবধান: macOS-এ pthread_barrier_t নেই।

Latch বানানো যায় mutex + condition variable + একটি counter দিয়ে — আর এখানে signal নয়, broadcast বাধ্যতামূলক, কারণ একটি পরিবর্তনে (count = 0) সব অপেক্ষাকারীর এগোনোর কথা। নিচের প্রোগ্রামে দুটি latch: ready (N = 4) — main অপেক্ষা করে সব worker প্রস্তুত হওয়া পর্যন্ত; আর start (N = 1) — একটি “স্টার্টিং গান”, main একবার count_down করলেই সব worker একসাথে ছাড়া পায়। Java-র CountDownLatch-এর ডকুমেন্টেশনের পরিচিত নকশাটিই এটি:

#include <pthread.h>
#include <stdio.h>
#define N 4
struct latch { pthread_mutex_t m; pthread_cond_t cv; int count; };
static struct latch ready = { PTHREAD_MUTEX_INITIALIZER, PTHREAD_COND_INITIALIZER, N };
static struct latch start = { PTHREAD_MUTEX_INITIALIZER, PTHREAD_COND_INITIALIZER, 1 };
static int seen[N];                               /* what each worker saw at the gate */
static void count_down(struct latch *l) {
    pthread_mutex_lock(&l->m);
    if (--l->count == 0) pthread_cond_broadcast(&l->cv);   /* wake ALL waiters */
    pthread_mutex_unlock(&l->m);
}
static void await_zero(struct latch *l) {
    pthread_mutex_lock(&l->m);
    while (l->count > 0) pthread_cond_wait(&l->cv, &l->m);
    pthread_mutex_unlock(&l->m);
}
static void *worker(void *arg) {
    int id = *(int *)arg;
    count_down(&ready);                           /* "I am ready" */
    await_zero(&start);                           /* wait for the starting gun */
    pthread_mutex_lock(&ready.m);
    seen[id] = N - ready.count;                   /* how many were ready by now */
    pthread_mutex_unlock(&ready.m);
    return NULL;
}
int main(void) {
    pthread_t t[N]; int ids[N];
    for (int i = 0; i < N; i++) { ids[i] = i; pthread_create(&t[i], NULL, worker, &ids[i]); }
    await_zero(&ready);
    printf("main: all %d workers ready, firing the start gate\n", N);
    count_down(&start);                           /* one broadcast releases everyone */
    for (int i = 0; i < N; i++) pthread_join(t[i], NULL);
    for (int i = 0; i < N; i++) printf("worker %d passed the gate, saw %d/%d ready\n", i, seen[i], N);
    return 0;
}

main: all 4 workers ready, firing the start gate
worker 0 passed the gate, saw 4/4 ready
worker 1 passed the gate, saw 4/4 ready
worker 2 passed the gate, saw 4/4 ready
worker 3 passed the gate, saw 4/4 ready

POSIX barrier দিয়ে একই “সবাই একসাথে” এভাবে লেখা যায় (Linux/glibc-তে চলে):

static pthread_barrier_t b;               /* in main: pthread_barrier_init(&b, NULL, 4); */
static void *phase_worker(void *arg) {
    for (int round = 0; round < 3; round++) {
        compute_my_part(arg, round);
        int rc = pthread_barrier_wait(&b); /* nobody starts round+1 early     */
        if (rc == PTHREAD_BARRIER_SERIAL_THREAD)
            merge_results(round);          /* exactly one thread per round    */
    }
    return NULL;
}

এমন ধাপে ধাপে চলা হিসাব — যেমন আবহাওয়ার মডেলের গ্রিড, যেখানে প্রতিটি ধাপের আগে প্রতিবেশীদের আগের ধাপ শেষ হওয়া চাই — barrier-এর প্রধান ব্যবহার। OpenMP-র #pragma omp barrier আর GPU-র block-স্তরের synchronization একই ধারণা।

৯ · AI-এর যুগে condition variable-এর কোড

Producer-consumer বা thread pool চাইলে AI মুহূর্তে কোড দেবে, আর হালকা টেস্টে সম্ভবত চলবেও। কিন্তু এই পর্বের প্রায় সব বাগই “বেশিরভাগ সময় চলে” ধরনের — if-এর বাগ ধরা পড়ে শুধু তৃতীয় একটি থ্রেড ঠিক সময়ে এলে, lost wakeup শুধু ঠিক জায়গায় preemption হলে। AI-এর লেখা কোডে যা বারবার দেখা যায়:

AI-এর লেখা অপেক্ষার কোড ব্যবহারের আগে — চেকলিস্ট

• প্রতিটি wait-এর জন্য বলতে পারি: কোন mutex, কোন শর্ত, আর কে সেটি সত্য করে signal দেয়
• সব wait while লুপে (বা predicate-ওয়ালা API-তে), কোনো if নেই
• শর্তের ভ্যারিয়েবল কোথাও lock ছাড়া পড়া বা লেখা হয় না — volatile বা atomic দিয়ে “ঠিক করা” নয়
• যেখানে একাধিক থ্রেড একসাথে এগোতে পারে (shutdown, latch, ভিন্ন শর্ত এক সারিতে), সেখানে broadcast
• -fsanitize=thread দিয়ে, producer-consumer-এর সংখ্যা বদলে (১:১, ৪:১, ১:৪), লুপে শতবার চালিয়েছি; কখনো ঝুলে যায়নি
• ভাষা আর OS মিলিয়ে নিয়েছি — যেমন macOS-এ pthread_barrier_t নেই, Java-য় এক অবজেক্টে এক wait set