Mutex আর semaphore

১ · Mutex — একটি চাবি, একজন মালিক

পর্ব ২২-এ দেখেছেন, একাধিক থ্রেড একই ডেটা একসাথে বদলালে race condition হয়, আর সমাধান হলো কোডের সেই অংশটিকে — critical section — এমনভাবে পাহারা দেওয়া, যাতে যেকোনো মুহূর্তে একজনই ভেতরে থাকে। এই নিশ্চয়তার নাম mutual exclusion. পর্ব ২৩-এ দেখেছেন hardware কীভাবে সাহায্য করে: atomic instruction আর তার ওপর বানানো spinlock. এই পর্বে আমরা এক ধাপ ওপরে উঠব — এমন দুটি হাতিয়ারে, যা প্রায় প্রতিটি OS আর প্রোগ্রামিং ভাষায় আছে: mutex আর semaphore.

Mutex-এর দুটি মূল অপারেশন:

• acquire (lock): তালা খোলা থাকলে অবিভাজ্যভাবে সেটি বন্ধ করে নিজেকে মালিক বানানো; বন্ধ থাকলে খোলা না হওয়া পর্যন্ত অপেক্ষা।
• release (unlock): তালা খুলে দেওয়া, আর কেউ অপেক্ষায় থাকলে তাদের একজনকে সুযোগ দেওয়া। এটি ডাকতে পারে শুধু মালিক।

যেকোনো ভালো lock-এর কাছে তিনটি জিনিস চাওয়া হয় (পর্ব ২২-এর তিন শর্তের সাথে মিলিয়ে দেখুন): সঠিকতা — একসাথে একজনই ভেতরে; ন্যায্যতা — কেউ চিরকাল অপেক্ষায় পড়ে থাকবে না (starvation নেই); আর কম খরচ — কেউ প্রতিযোগিতা না করলে lock নেওয়া-ছাড়া প্রায় বিনামূল্যে হওয়া উচিত। শেষেরটি কীভাবে সম্ভব, তা অংশ ৩-এ।

হাতে-কলমে দেখা যাক। একটি ব্যাংক হিসাবে শুরুতে ১০ লাখ টাকা। চারজন টেলার (চারটি থ্রেড) একসাথে প্রত্যেকে ১ লাখবার লেনদেন করেন: দুজন জমা দেন (৫ আর ৩ টাকা করে), দুজন তোলেন (২ আর ৪ টাকা করে)। তোলার আগে দেখা হয় টাকা আছে কি না — “দেখা আর বদলানো” একসাথে, mutex-এর ভেতরে:

#include <pthread.h>
#include <stdint.h>
#include <stdio.h>
#define OPS 100000                         /* operations per thread */
static long balance = 1000000;             /* shared account: 10 lakh taka */
static long refused = 0;                   /* withdrawals refused (no money) */
static pthread_mutex_t acct = PTHREAD_MUTEX_INITIALIZER;

static void *teller(void *arg) {
    long amount = (long)(intptr_t)arg;     /* > 0 deposit, < 0 withdraw */
    for (int i = 0; i < OPS; i++) {
        pthread_mutex_lock(&acct);         /* acquire: now WE own the lock */
        if (balance + amount >= 0) balance += amount;   /* check + update ... */
        else refused++;                    /* ... as ONE indivisible step */
        pthread_mutex_unlock(&acct);       /* release: only the owner may */
    }
    return NULL;
}

int main(void) {
    long amounts[4] = { +5, +3, -2, -4 };  /* taka per operation */
    pthread_t t[4];
    for (int i = 0; i < 4; i++)
        pthread_create(&t[i], NULL, teller, (void *)(intptr_t)amounts[i]);
    for (int i = 0; i < 4; i++) pthread_join(t[i], NULL);
    long expect = 1000000 + (long)OPS * (5 + 3 - 2 - 4);
    printf("final balance : %ld\n", balance);
    printf("expected      : %ld\n", expect);
    printf("refused       : %ld\n", refused);
    printf("match         : %s\n", balance == expect ? "yes" : "no");
    return 0;
}

final balance : 1200000
expected      : 1200000
refused       : 0
match         : yes

২ · অপেক্ষার দুই পথ — spin না ঘুম

Lock বন্ধ পেলে থ্রেড কী করবে? দুটি পথ আছে, আর এই পছন্দই mutex আর spinlock-কে আলাদা করে।

Kernel অপেক্ষারত থ্রেডকে কীভাবে ঘুম পাড়ায়

পর্ব ৮ আর ৯-এর ভাষায়: ঘুমানো মানে থ্রেডের অবস্থা running থেকে waiting/blocked-এ যাওয়া। ধাপগুলো মোটামুটি সব OS-এ একই — (১) থ্রেডের TCB সেই lock-এর wait queue-তে যোগ হয়, (২) অবস্থা “ঘুমন্ত” চিহ্নিত হয়, তাই সে আর ready queue-তে থাকে না, (৩) scheduler অন্য কাউকে CPU দেয়। Lock ছাড়ার সময় মালিক wait queue থেকে একজনকে তুলে আবার ready queue-তে রাখে — সে তখন CPU পাওয়ার যোগ্য, আর পরে চলতে শুরু করে lock আবার নেওয়ার চেষ্টা করে। Linux kernel-এর ভেতরের কোড এই ছাঁচের:

DEFINE_WAIT(wait);
for (;;) {
    prepare_to_wait(&q, &wait, TASK_UNINTERRUPTIBLE); /* join q, mark "sleeping" */
    if (condition)                 /* re-check AFTER joining the queue */
        break;
    schedule();                    /* give the CPU away; resume here when woken */
}
finish_wait(&q, &wait);            /* state = TASK_RUNNING, leave the queue */

/* the waker, e.g. at unlock time: */
condition = 1;
wake_up(&q);                       /* move a sleeper back to the run queue */

লক্ষ করুন ক্রমটি: আগে সারিতে নাম লেখানো আর “ঘুমন্ত” চিহ্ন, তারপর শর্ত আবার যাচাই, তারপর ঘুম। উল্টো ক্রমে করলে (আগে যাচাই, তারপর সারিতে যোগ) মাঝের মুহূর্তে জাগানোর সংকেত এসে কাউকে না পেয়ে হারিয়ে যেতে পারে — lost wakeup, অংশ ৮-এ বিস্তারিত।

কোনটি কখন — আর adaptive mutex

এক-CPU-র মেশিনে spin প্রায় সবসময় অর্থহীন: আপনি যতক্ষণ ঘুরছেন, মালিক CPU পাচ্ছে না, তাই lock খোলার সম্ভাবনাই নেই — পুরো time slice নষ্ট। Multicore-এ মালিক অন্য core-এ চলছে, শিগগির ছাড়বে — তখন অল্প spin ভালো। এই বুদ্ধি থেকে এসেছে adaptive mutex: মালিক যদি এই মুহূর্তে অন্য CPU-তে চলমান থাকে তবে কিছুক্ষণ spin, আর মালিক নিজেই ঘুমন্ত বা preempted হলে সঙ্গে সঙ্গে ঘুম। Solaris-এর adaptive mutex এর পরিচিত উদাহরণ, Linux kernel-এর নিজস্ব struct mutex-ও মালিক চলমান থাকলে কিছুক্ষণ spin করে (একে বলে optimistic spinning), আর glibc-তে PTHREAD_MUTEX_ADAPTIVE_NP নামের একটি অ-মানক ধরন আছে যা সীমিত কয়েকবার spin করে তারপর ঘুমায়। Windows-এর CRITICAL_SECTION-এও একটি spin count দেওয়া যায় (অংশ ৭)।

কতক্ষণ spin? — একটি ছোট প্রমাণ

ধরা যাক ঘুমিয়ে আবার জাগার মোট খরচ C (context switch, syscall ইত্যাদি), আর lock খুলতে কত সময় লাগবে (t) তা আগে থেকে জানা নেই। কৌশল: “C সময় পর্যন্ত spin, তখনও না খুললে ঘুম”। দাবি: এই কৌশলের খরচ কখনো সর্বোত্তম খরচের ২ গুণের বেশি নয় — এমনকি সেই সর্বোত্তম কৌশলের সাথে তুলনাতেও, যে আগে থেকেই t জানে।

• t ≤ C হলে: আমরা t সময় spin করে lock পাই, খরচ t. যে t জানে, সে-ও এর কম খরচ করতে পারে না (spin-এর খরচ t, ঘুমের খরচ C ≥ t). অনুপাত ১.
• t > C হলে: আমরা C spin করে তারপর ঘুমাই, মোট খরচ C + C = ২C. সর্বোত্তম কৌশল সঙ্গে সঙ্গে ঘুমাত, খরচ C. অনুপাত ২. ∎

অর্থাৎ ভবিষ্যৎ না জেনেও আমরা সর্বোত্তমের দ্বিগুণের মধ্যে থাকি। এ ধরনের নিশ্চয়তাকে বলে competitive ratio; Karlin, Li, Manasse আর Owicki-এর ১৯৯১ সালের একটি পরিচিত গবেষণা এই spin-then-block কৌশল বাস্তব কাজের চাপে মেপে দেখেছিল। Adaptive mutex একই ধারণার একটি ব্যবহারিক রূপ।

৩ · Linux-এ futex — user space-এ দ্রুত পথ, kernel-এ ধীর পথ

সমস্যাটি ভাবুন: ঘুমাতে kernel লাগে, অথচ প্রতিটি pthread_mutex_lock-এ system call করলে প্রতিযোগিতা ছাড়া lock-ও কয়েকশো ন্যানোসেকেন্ড বা তার বেশি সময় নেবে। বাস্তবের বেশিরভাগ lock নেওয়ার সময় কেউ প্রতিযোগিতা করে না। তাহলে kernel-এ যাব শুধু তখনই, যখন সত্যিই অপেক্ষা লাগবে — এটিই Linux-এর futex (fast userspace mutex)-এর মূল ধারণা। ২০০২ সালে Hubertus Franke, Rusty Russell আর Matthew Kirkwood-এর একটি প্রবন্ধে এর নকশা আসে, আর Linux 2.6 থেকে এটি glibc-র সব থ্রেড-সমন্বয়ের ভিত্তি।

ব্যবস্থাটি দুই ভাগে:

• User space-এ একটি পূর্ণসংখ্যা (lock word), যা থ্রেডগুলো atomic instruction (পর্ব ২৩-এর compare-and-swap, exchange) দিয়ে বদলায়। প্রতিযোগিতা না থাকলে lock নেওয়া আর ছাড়া পুরোটাই এখানে — এটি fast path.
• একটি system call futex(addr, op, val, …), যার দুটি মূল কাজ: FUTEX_WAIT — *addr-এ এখনো val থাকলে ডাকা থ্রেডকে ঘুম পাড়ানো, আর FUTEX_WAKE — এই ঠিকানায় যারা ঘুমিয়ে আছে তাদের n জনকে জাগানো। এটি slow path, শুধু প্রতিযোগিতার সময়।

FUTEX_WAIT-এর “এখনো val থাকলে” অংশটিই আসল কৌশল। Kernel মান যাচাই আর ঘুমানো একসাথে, অবিভাজ্যভাবে করে। ফলে আপনি “lock বন্ধ, ঘুমাব” ঠিক করার পর কিন্তু ঘুমানোর আগে মালিক lock ছেড়ে দিলে kernel দেখবে মান বদলে গেছে, আর আপনাকে না ঘুমিয়ে সঙ্গে সঙ্গে ফিরিয়ে দেবে — জাগরণ হারায় না। নিচের mutex-টি Ulrich Drepper-এর বিখ্যাত প্রবন্ধ “Futexes Are Tricky”-র তৃতীয় নকশার সরলীকৃত রূপ; lock word-এর তিনটি মান: 0 = খোলা, 1 = বন্ধ, কেউ অপেক্ষায় নেই, 2 = বন্ধ, অপেক্ষায় কেউ থাকতে পারে। ধাপে ধাপে দেখুন:

1lock():2  c = cmpxchg(&word, 0, 1);  // 0 → 1 if free3  if (c == 0) return;        // fast path: no syscall4  if (c != 2) c = xchg(&word, 2);5  while (c != 0) {6    futex_wait(&word, 2);    // sleep if word is still 27    c = xchg(&word, 2); }8unlock():9  if (atomic_dec(&word) != 1) {  // old value 2?10    word = 0; futex_wake(&word, 1); }

বাস্তবের glibc-র pthread_mutex_lock আরও অনেক কিছু সামলায় (mutex-এর ধরন, মালিকের TID রাখা, robust আর priority-inheritance রূপ), কিন্তু normal mutex-এর মূল ছাঁচ এটিই। sem_wait/sem_post, condition variable আর pthread_join-ও futex-এর ওপর দাঁড়ানো (পর্ব ১৫-এ join-এর futex দেখেছেন)।

৪ · pthread mutex-এর ধরন, trylock আর timedlock

একই থ্রেড যদি নিজের ধরা mutex আবার lock করতে চায়, বা মালিক নয় এমন কেউ unlock করে — কী হবে? POSIX উত্তর ঠিক করে দিয়েছে mutex-এর ধরন দিয়ে, যা pthread_mutexattr_settype দিয়ে বাছা হয়:

সঙ্গে আছে অপেক্ষা না করার আর সীমিত অপেক্ষার দুটি উপায়। pthread_mutex_trylock lock খোলা থাকলে নেয়, বন্ধ থাকলে না ঘুমিয়ে সঙ্গে সঙ্গে EBUSY ফেরত দেয় — “পরে চেষ্টা করব, এখন অন্য কাজ”। pthread_mutex_timedlock একটি পরম সময় (CLOCK_REALTIME-এর একটি মুহূর্ত, “এখন থেকে ১০০ ms” নয়) পর্যন্ত অপেক্ষা করে, না পেলে ETIMEDOUT. নিচের ফলগুলো একটি পরীক্ষামূলক প্রোগ্রাম Wandbox-এ (glibc, Linux) চালিয়ে পাওয়া:

pthread_mutexattr_t a;
pthread_mutexattr_init(&a);
pthread_mutexattr_settype(&a, PTHREAD_MUTEX_ERRORCHECK);
pthread_mutex_init(&ec, &a);
pthread_mutex_lock(&ec);          /* 0                                   */
pthread_mutex_lock(&ec);          /* EDEADLK "Resource deadlock avoided" */

pthread_mutexattr_settype(&a, PTHREAD_MUTEX_RECURSIVE);
pthread_mutex_init(&rec, &a);
/* lock x3 -> 0 0 0,  unlock x3 -> 0 0 0,  4th unlock -> EPERM          */

pthread_mutex_lock(&nm);          /* a normal mutex, now held            */
pthread_mutex_trylock(&nm);       /* EBUSY  "Device or resource busy"    */
/* from ANOTHER thread:                                                  */
pthread_mutex_unlock(&ec);        /* EPERM  "Operation not permitted"    */
pthread_mutex_timedlock(&nm, &deadline_100ms);  /* ETIMEDOUT            */

আরও দুটি বিশেষ রূপ জেনে রাখুন। Robust mutex (pthread_mutexattr_setrobust): মালিক থ্রেড বা প্রসেস lock ধরা অবস্থায় মারা গেলে পরের জন lock পায় সাথে EOWNERDEAD সতর্কতা — ডেটা ঠিক করে pthread_mutex_consistent ডাকার সুযোগ। Process-shared mutex (PTHREAD_PROCESS_SHARED): shared memory-তে রাখা mutex দিয়ে দুটি প্রসেসের মধ্যে পাহারা (পর্ব ১২-এর shared memory). আর priority inheritance (PTHREAD_PRIO_INHERIT) পর্ব ২৯-এ।

৫ · Semaphore — Dijkstra-র সংকেত-খুঁটি

Mutex বলে “একজন”। কিন্তু অনেক সমস্যায় দরকার “n জন”, বা “ও শেষ করলে তবে আমি”। এর জন্য Edsger W. Dijkstra ১৯৬০-এর দশকের প্রথম দিকে একটি সাধারণ হাতিয়ার প্রস্তাব করেন — semaphore. ১৯৬৫ সালের তাঁর বিখ্যাত লেখা “Cooperating Sequential Processes” (EWD123)-এ এটি বিস্তারিত আসে, আর পরে নেদারল্যান্ডসের Eindhoven-এ তাঁর দলের তৈরি THE multiprogramming system-এ ব্যবহৃত হয়। নামটি রেলের সিগন্যাল-খুঁটি (semaphore) থেকে — যা বলে ট্রেন এগোবে, না থামবে।

P আর V — নাম কোথা থেকে

Semaphore একটি পূর্ণসংখ্যা S, যাকে শুরুতে একটি মান দেওয়া হয়, আর তারপর শুধু দুটি অবিভাজ্য অপারেশন দিয়ে ছোঁয়া যায়:

• P(S) — বিভিন্ন বইয়ে wait, down বা acquire: S থেকে ১ নেওয়ার চেষ্টা; না পারলে অপেক্ষা।
• V(S) — signal, up, post বা release: S-এ ১ ফেরত দেওয়া, আর অপেক্ষারত কাউকে জাগানো।

অক্ষর দুটি ডাচ শব্দ থেকে, তবে কোন শব্দ — তা নিয়ে বইভেদে ভিন্ন ব্যাখ্যা পাবেন। প্রচলিত একটি ব্যাখ্যা: V এসেছে verhogen (বাড়ানো) থেকে, আর P এসেছে Dijkstra-র বানানো শব্দ prolaag থেকে, যা probeer te verlagen (“কমানোর চেষ্টা”)-এর সংক্ষেপ। কিছু পুরোনো বইয়ে P = passeren (পার হওয়া) আর V = vrijgeven (ছেড়ে দেওয়া) লেখা আছে। পরীক্ষায় অর্থটি মনে রাখাই যথেষ্ট: P কমায়/অপেক্ষা করায়, V বাড়ায়/জাগায়।

সংজ্ঞা ১ — busy waiting দিয়ে (প্রাথমিক রূপ)

wait(S) {
    while (S <= 0)
        ;              /* busy wait */
    S--;
}
signal(S) {
    S++;
}
/* the test S <= 0 and S-- must happen as ONE atomic step */

সহজ, কিন্তু অপেক্ষারত প্রসেস CPU পুড়িয়ে ঘোরে — এক অর্থে এটি একটি spinlock. এখানে S কখনো ঋণাত্মক হয় না।

সংজ্ঞা ২ — অপেক্ষার সারিসহ (busy waiting ছাড়া)

typedef struct { int value; struct process *list; } semaphore;

wait(semaphore *S) {
    S->value--;
    if (S->value < 0) {
        add this process to S->list;
        sleep();               /* block: running -> waiting */
    }
}
signal(semaphore *S) {
    S->value++;
    if (S->value <= 0) {      /* someone was waiting */
        remove a process P from S->list;
        wakeup(P);             /* waiting -> ready */
    }
}

এই রূপে wait আগে মান কমায়, তারপর দেখে। তাই মান ঋণাত্মক হতে পারে, আর তখন |মান| = অপেক্ষারত প্রসেসের সংখ্যা: মান −২ মানে দুজন সারিতে। signal-এর পর মান ≤ ০ মানে কেউ অপেক্ষায় ছিল, তাই একজনকে জাগাতে হয়। একটি কথা খেয়াল করুন: wait আর signal নিজেরাও shared ডেটা (value আর list) বদলায়, তাই এদের অবিভাজ্য হতে হয় — kernel ভেতরে একটি ছোট spinlock বা (এক-CPU-তে) interrupt বন্ধ করে তা নিশ্চিত করে (পর্ব ২৩)। অর্থাৎ busy waiting পুরোপুরি যায়নি, সরে গেছে wait/signal-এর কয়েক লাইনের ভেতরে, যেখানে অপেক্ষা খুব ছোট।

এখন পরীক্ষার সবচেয়ে প্রিয় কাজ — মান আর সারি ট্রেস করা। S = ২ (যেমন ২টি কাউন্টার), চারটি প্রসেস A, B, C, D. প্রতিটি ধাপের পর দুই রীতিতে মান, সারি আর কে ভেতরে আছে দেখুন:

1S = 2           // initial value2A: wait(S)3B: wait(S)4C: wait(S)5D: wait(S)6A: signal(S)7B: signal(S)8C: signal(S)9D: signal(S)

কেন semaphore কাজ করে — invariant আর একটি প্রমাণ

অ-ঋণাত্মক রীতিতে ভাবুন। ধরুন শুরুর মান k, সম্পূর্ণ হওয়া wait-এর সংখ্যা #P, আর signal-এর সংখ্যা #V. প্রতিটি সম্পূর্ণ wait মান ১ কমায়, প্রতিটি signal ১ বাড়ায় (বা সরাসরি একজনের wait সম্পূর্ণ করায় — হিসাবে একই), তাই সবসময় সত্য থাকে এই invariant:

এখন ধরুন প্রতিটি প্রসেস wait(S); critical section; signal(S); মেনে চলে। যে প্রসেস ভেতরে আছে, সে wait সম্পূর্ণ করেছে কিন্তু signal দেয়নি; তাই ভেতরের সংখ্যা = #P − #V = k − S ≤ k, কারণ S ≥ ০. অর্থাৎ কখনোই k-এর বেশি প্রসেস একসাথে ভেতরে থাকতে পারে না; k = ১ হলে এটিই mutual exclusion-এর প্রমাণ। ∎ আর সারি যদি FIFO হয় (একে বলে strong semaphore), প্রতিটি অপেক্ষারত প্রসেস সীমিত সংখ্যক signal-এর পর জাগবেই — starvation নেই। সারি থেকে যেকোনো একজনকে জাগানো weak semaphore-এ এই নিশ্চয়তা থাকে না। POSIX FIFO নিশ্চিত করে না; priority scheduling-এ সবচেয়ে উচ্চ অগ্রাধিকারের অপেক্ষারত থ্রেড জাগে।

নিজে চালিয়ে দেখুন — semaphore simulator

নিচের simulator পাঠ্যবই-রীতিতে প্রতিটি অপারেশনের পর মান, সারি আর POSIX-রীতির মান ছাপে। এখানে S = ৩, পাঁচটি প্রসেস; মাঝে একটি ইচ্ছাকৃত ভুল অপারেশনও আছে — একটি ঘুমন্ত প্রসেস signal দিতে চাইছে। value আর ops বদলে নিজের প্রশ্ন বানিয়ে উত্তর মিলিয়ে নিন:

// Counting semaphore with a FIFO waiting queue (textbook style, value may go negative).
// wait: value--; if value < 0 the caller blocks.  signal: value++; if value <= 0 wake the first waiter.
let value = 3;                                     // initial value of S: 3 identical resources
const ops = ["P1 wait", "P2 wait", "P3 wait", "P4 wait", "P5 wait", "P5 signal",
             "P2 signal", "P1 signal", "P3 signal", "P4 signal", "P5 signal"];
const queue = [], blocked = new Set(), holds = new Set();
const row = (op, note) => console.log(op.padEnd(10) + String(value).padStart(5) + "   " +
  ("[" + queue.join(", ") + "]").padEnd(10) + String(Math.max(value, 0)).padStart(6) + "   " + note);
console.log("op        value   queue     POSIX-value   what happened");
row("start", "");
for (const op of ops) {
  const [p, kind] = op.split(" ");
  if (blocked.has(p)) { console.log(op.padEnd(10) + "  ERROR: " + p + " is blocked, it cannot run"); continue; }
  if (kind === "wait") {
    value--;
    if (value < 0) { queue.push(p); blocked.add(p); row(op, p + " blocks"); }
    else { holds.add(p); row(op, p + " passes"); }
  } else {
    holds.delete(p); value++;
    if (value <= 0) {                              // someone was waiting: hand the unit over
      const w = queue.shift(); blocked.delete(w); holds.add(w); row(op, "wakes " + w);
    } else row(op, "unit returned");
  }
}
console.log("final value = " + value + ", waiting = " + queue.length);
console.log("check: initial 3 - 5 waits + 5 signals = " + (3 - 5 + 5));

op        value   queue     POSIX-value   what happened
start         3   []             3
P1 wait       2   []             2   P1 passes
P2 wait       1   []             1   P2 passes
P3 wait       0   []             0   P3 passes
P4 wait      -1   [P4]           0   P4 blocks
P5 wait      -2   [P4, P5]       0   P5 blocks
P5 signal   ERROR: P5 is blocked, it cannot run
P2 signal    -1   [P5]           0   wakes P4
P1 signal     0   []             0   wakes P5
P3 signal     1   []             1   unit returned
P4 signal     2   []             2   unit returned
P5 signal     3   []             3   unit returned
final value = 3, waiting = 0
check: initial 3 - 5 waits + 5 signals = 3

৬ · Semaphore-এর তিন কাজ — পাহারা, ক্রম আর গণনা

একই হাতিয়ার, শুধু শুরুর মান বদলে তিনটি ভিন্ন সমস্যার সমাধান। পরীক্ষা আর ইন্টারভিউতে এই তিনটি ছাঁচ চিনতে পারা জরুরি।

(ক) Mutual exclusion — মান ১

semaphore mutex = 1;
/* every process: */
wait(mutex);
    /* critical section */
signal(mutex);
    /* remainder section */

অংশ ৫-এর প্রমাণে k = ১: একসাথে একজনের বেশি ভেতরে নয়। মান কেবল ০ আর ১-এর মধ্যে ঘোরে (অপেক্ষারত ছাড়া), তাই এমন semaphore-কে বলে binary semaphore. আর যার মান যেকোনো অ-ঋণাত্মক পূর্ণসংখ্যা হতে পারে, সেটি counting semaphore.

(খ) ক্রম বা সংকেত — মান ০

প্রসেস P1-এর statement S1 অবশ্যই P2-এর S2-এর আগে চলতে হবে — যেমন P1 একটি config ফাইল লিখবে, P2 সেটি পড়বে। একটি semaphore sync, শুরুর মান ০:

1semaphore sync = 0;2// P13S1;              // e.g. write config4signal(sync);5// P26wait(sync);7S2;              // e.g. read config

এবার আসল POSIX semaphore দিয়ে। থ্রেড B-কে ইচ্ছে করে আগে তৈরি করা হয়েছে, আর A ২০০ ms ধীরে কাজ করে — তবু B ছাপে শুধু A-এর পরে:

#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>
#include <time.h>
#include <unistd.h>
static sem_t done_a;                      /* "A has finished S1"; starts at 0 */
static int config = 0;                    /* written by A, read by B */
static struct timespec t0;                /* start time, set by main */
static void *thread_a(void *arg) {
    (void)arg;
    usleep(200000);                       /* A is slow: 200 ms of work */
    config = 42;                          /* S1 */
    printf("A: S1 done, config = %d\n", config);
    sem_post(&done_a);                    /* signal (V): wake B, or 0 -> 1 */
    return NULL;
}
static void *thread_b(void *arg) {
    (void)arg;
    sem_wait(&done_a);                    /* wait (P): sleeps while value is 0 */
    struct timespec t; clock_gettime(CLOCK_MONOTONIC, &t);
    double ms = (t.tv_sec - t0.tv_sec) * 1e3 + (t.tv_nsec - t0.tv_nsec) / 1e6;
    printf("B: S2 sees config = %d, waited >= 200 ms: %s\n", config, ms >= 200 ? "yes" : "no");
    return NULL;
}
int main(void) {
    sem_init(&done_a, 0, 0);              /* pshared 0 = between threads; value 0 */
    clock_gettime(CLOCK_MONOTONIC, &t0);
    pthread_t a, b;
    pthread_create(&b, NULL, thread_b, NULL);   /* B is started FIRST */
    pthread_create(&a, NULL, thread_a, NULL);
    pthread_join(a, NULL); pthread_join(b, NULL);
    int v; sem_getvalue(&done_a, &v);
    printf("main: semaphore value at the end = %d\n", v);
    return sem_destroy(&done_a);
}

A: S1 done, config = 42
B: S2 sees config = 42, waited >= 200 ms: yes
main: semaphore value at the end = 0

(গ) সম্পদ গণনা — মান n

একটি অফিসে ২টি প্রিন্টার, কিন্তু ৫ জন একসাথে ছাপাতে চান। Semaphore-এর শুরুর মান = প্রিন্টারের সংখ্যা। প্রত্যেকে ছাপার আগে wait, শেষে signal. অংশ ৫-এর প্রমাণ বলে একসাথে কখনো ২ জনের বেশি নয়। নিচের প্রোগ্রাম সেটি মেপে দেখে — একটি mutex দিয়ে রক্ষিত গণনায় সর্বোচ্চ কতজন একসাথে “ছাপাচ্ছিল”:

#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>
#include <unistd.h>
#define WORKERS 5
#define SLOTS 2                            /* e.g. 2 printers */

static sem_t slots;                        /* counts free printers */
static pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
static int active = 0, max_active = 0, done = 0;

static void *job(void *arg) {
    (void)arg;
    sem_wait(&slots);                      /* take a printer, or sleep */
    pthread_mutex_lock(&m);
    if (++active > max_active) max_active = active;   /* record the peak */
    pthread_mutex_unlock(&m);
    usleep(50000);                         /* "print" for 50 ms */
    pthread_mutex_lock(&m);
    active--; done++;
    pthread_mutex_unlock(&m);
    sem_post(&slots);                      /* give the printer back */
    return NULL;
}
int main(void) {
    sem_init(&slots, 0, SLOTS);            /* initial value = free printers */
    pthread_t t[WORKERS];
    for (int i = 0; i < WORKERS; i++) pthread_create(&t[i], NULL, job, NULL);
    for (int i = 0; i < WORKERS; i++) pthread_join(t[i], NULL);
    int v; sem_getvalue(&slots, &v);
    printf("workers finished: %d, printers: %d\n", done, SLOTS);
    printf("max active at a time: %d\n", max_active);
    printf("semaphore value now : %d\n", v);
    return sem_destroy(&slots);
}

workers finished: 5, printers: 2
max active at a time: 2
semaphore value now : 2

Producer-consumer-এর মতো সমস্যায় এই তিন ছাঁচ একসাথে লাগে — একটি mutex (মান ১), খালি ঘরের গণনা (মান n), ভরা ঘরের গণনা (মান ০)। পূর্ণ সমাধান আর readers-writers ও dining philosophers পর্ব ২৬-এ।

৭ · Binary semaphore বনাম mutex, আর বাস্তবের API

“Binary semaphore আর mutex কি একই?” — এটি সম্ভবত OS ইন্টারভিউর সবচেয়ে পরিচিত প্রশ্ন। দুটিই একজনকে ঢুকতে দেয়, কিন্তু নকশার উদ্দেশ্য আলাদা:

শেষ সারিটি গুরুত্বপূর্ণ: POSIX-এ “binary semaphore” বলে আলাদা কিছু নেই — এটি মান ১ দিয়ে শুরু করা একটি সাধারণ semaphore, আর ভুল করে দুবার sem_post দিলে মান ২, ফলে দুজন একসাথে ভেতরে। এজন্যই পাহারার কাজে mutex নিরাপদ পছন্দ, আর semaphore রাখা হয় সংকেত আর গণনার জন্য। Linux kernel-ও এই পথে গেছে: ২০০৬ সালে Linux 2.6.16-এ আলাদা struct mutex যোগ হওয়ার পর kernel-এর ভেতরে পাহারার কাজে semaphore-এর জায়গা ধীরে ধীরে mutex নিয়েছে।

POSIX semaphore — unnamed আর named

এই ফাংশনগুলো, pthread-এর উল্টো, ব্যর্থ হলে −১ দেয় আর কারণ রাখে errno-তে। একটি ব্যবহারিক ফাঁদ: sem_wait ঘুমের মধ্যে signal এলে −১ আর EINTR দিয়ে ফিরতে পারে, তাই নির্ভরযোগ্য কোডে লেখা হয় while (sem_wait(&s) == -1 && errno == EINTR) ;. আর OS-ভেদে পার্থক্য: macOS-এ unnamed semaphore (sem_init) কার্যত সমর্থিত নয় — ডাকলে ব্যর্থ হয়; সেখানে named semaphore বা Apple-এর dispatch_semaphore ব্যবহার করা হয়।

System V semaphore

পুরোনো কিন্তু এখনো সব Unix-এ থাকা আরেকটি API হলো System V semaphore (পর্ব ১২-এর System V IPC পরিবারের সদস্য)। এর বৈশিষ্ট্য তিনটি: semget একসাথে semaphore-এর একটি সেট বানায়; semop সেটের কয়েকটির ওপর একাধিক অপারেশন একসাথে, অবিভাজ্যভাবে করতে পারে (হয় সবগুলো, নয় একটিও না); আর SEM_UNDO flag দিলে প্রসেস হঠাৎ মারা গেলে kernel তার করা বদলগুলো উল্টে দেয় — semaphore চিরকাল আটকে থাকে না। বিনিময়ে API জটিল, আর প্রতিটি অপারেশন system call. ipcs -s দিয়ে সিস্টেমের System V semaphore তালিকা দেখা যায়। নতুন কোডে সাধারণত POSIX semaphore বেছে নেওয়া হয়।

Windows-এ সমতুল্য

Windows-এর নিজস্ব হাতিয়ারগুলো মোটামুটি এভাবে মেলে (বিস্তারিত আচরণ Microsoft-এর ডকুমেন্টেশনে মিলিয়ে নিন):

• CRITICAL_SECTION — একই প্রসেসের থ্রেডদের জন্য দ্রুত mutex; প্রতিযোগিতা না থাকলে user mode-এই কাজ সারে, প্রয়োজনে kernel-এ অপেক্ষা করে; একই থ্রেড একাধিকবার ঢুকতে পারে (recursive); InitializeCriticalSectionAndSpinCount দিয়ে spin count দেওয়া যায়।
• SRWLOCK (Windows Vista থেকে) — মাত্র একটি pointer-এর সমান আকারের হালকা lock, exclusive আর shared (reader-writer) দুই রূপে; recursive নয়। নতুন কোডে প্রায়ই প্রথম পছন্দ।
• Mutex object (CreateMutex, WaitForSingleObject, ReleaseMutex) — kernel-এর অবজেক্ট; নাম দিলে একাধিক প্রসেসের মধ্যে কাজ করে; মালিকানা আছে, আর মালিক থ্রেড না ছেড়ে মারা গেলে পরের অপেক্ষাকারী WAIT_ABANDONED পায়। প্রতিটি অপারেশন kernel-এ যায় বলে ধীর।
• Semaphore object (CreateSemaphore, WaitForSingleObject, ReleaseSemaphore) — counting semaphore, তবে একটি সর্বোচ্চ মানসহ: সর্বোচ্চের বেশি ছাড়তে চাইলে ব্যর্থ হয় — POSIX-এর “দুবার post” ভুলটি এখানে ধরা পড়ে।

৮ · সাধারণ ভুল — signal ভোলা, উল্টো ক্রম আর হারানো জাগরণ

Semaphore শক্তিশালী, কিন্তু কাঠামোহীন: wait আর signal কোডের যেকোনো জায়গায় বসানো যায়, আর compiler কিছুই যাচাই করে না। একটি ভুল জায়গার লাইন পুরো সিস্টেম আটকে দিতে পারে। পরিচিত ভুলগুলো:

উল্টো ক্রমে wait — deadlock

দুটি semaphore S আর Q, দুটিরই শুরুর মান ১. দুই প্রসেস দুটিই চায়, কিন্তু উল্টো ক্রমে:

P0:  wait(S);      P1:  wait(Q);
     wait(Q);           wait(S);
     ...                ...
     signal(S);         signal(Q);
     signal(Q);         signal(S);

যদি P0 wait(S) করে আর ঠিক তখনই P1 wait(Q) করে, তাহলে P0 Q-এর জন্য ঘুমায় আর P1 S-এর জন্য — কেউ কখনো signal দেবে না, কারণ যে দেবে সে নিজেই ঘুমিয়ে। এটিই deadlock. বেশিরভাগ রানে এমন সময়-মিল হয় না, তাই টেস্টে ধরা পড়ে না; তারপর একদিন চাপের মধ্যে সিস্টেম জমে যায়। প্রচলিত প্রতিকার: সব থ্রেড সব lock একই নির্দিষ্ট ক্রমে নেবে। Deadlock-এর চার শর্ত আর প্রতিরোধ পর্ব ২৭-এ।

হারানো জাগরণ — কেন semaphore-এর “স্মৃতি” দরকার

ধরুন semaphore ছাড়া, শুধু একটি সাধারণ count আর দুটি ধারণাগত কল sleep()/wakeup(p) দিয়ে লেখা হলো:

/* consumer */                         /* producer */
if (count == 0)                        count = count + 1;
    /* <-- preempted HERE */           if (count == 1)
    sleep();                               wakeup(consumer);   /* not asleep yet: lost! */

Consumer দেখল count = ০, ঘুমাতে যাবে — ঠিক তখনই preempt হলো। Producer একটি জিনিস রেখে wakeup পাঠাল, কিন্তু consumer তখনো ঘুমায়নি, তাই সংকেতটি কেউ পেল না। Consumer আবার CPU পেয়ে ঘুমিয়ে পড়ল — হয়তো চিরকালের জন্য। Andrew Tanenbaum-এর OS বইয়ে producer-consumer প্রসঙ্গে এটি একটি পরিচিত উদাহরণ। তিনটি সমাধান এই কোর্সে দেখছেন: semaphore-এর মান সংকেতটি মনে রাখে (অংশ ৬-এর ক্রম ২); futex-এর kernel মান যাচাই আর ঘুম একসাথে করে (অংশ ৩); আর condition variable mutex ধরে শর্ত যাচাই করে, আর wait mutex ছাড়া ও ঘুমানো একসাথে করে (পর্ব ২৫)। মূল নীতি একটিই: “যাচাই” আর “ঘুম”-এর মাঝে কোনো ফাঁক রাখা যাবে না।

৯ · AI-এর যুগে mutex আর semaphore

AI আপনাকে সেকেন্ডে একটি “thread-safe” queue বা connection limiter লিখে দেবে। কিন্তু সমন্বয়ের কোডে ভুল সাধারণত কয়েক হাজার রানে একবার ধরা দেয়, আর AI-এর লেখা কোড প্রায়ই সেই একবারের কথা ভাবে না। সাধারণ ভুলগুলো:

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

• প্রতিটি semaphore-এর শুরুর মান কেন ০, ১ বা n — তা এক বাক্যে বলতে পারি (ক্রম, পাহারা, না গণনা)
• প্রতিটি lock/wait-এর জোড়া unlock/signal প্রতিটি ফেরার পথে আছে, error-পথসহ
• একাধিক lock থাকলে সব জায়গায় একই ক্রমে নেওয়া হয়
• -fsanitize=thread বা Helgrind দিয়ে চালিয়েছি, আর লুপে শতবার চালিয়ে ফল একই পেয়েছি
• কোড আমার OS-এর (POSIX বনাম Win32; macOS-এ sem_init নেই) — man page মিলিয়ে দেখেছি
• পরীক্ষার হিসাব (মান আর সারির trace) হাতে করে simulator দিয়ে মিলিয়েছি, আর কোন রীতি ধরেছি তা লিখেছি