কনকারেন্সির বাগ আর আধুনিক কৌশল — priority inversion, lock-free আর RCU

১ · বাস্তবের concurrency বাগ — একটি গবেষণার মানচিত্র

মডিউল ৪-এর আগের পর্বগুলোতে হাতিয়ারগুলো একে একে এসেছে: race condition আর Peterson (পর্ব ২২), atomic instruction আর memory ordering (পর্ব ২৩), mutex আর semaphore (পর্ব ২৪), condition variable (পর্ব ২৫), ক্লাসিক সমস্যা (পর্ব ২৬), আর deadlock ও Banker's algorithm (পর্ব ২৭–২৮)। মডিউলের এই শেষ পর্বে প্রশ্নটি উল্টো দিক থেকে: বাস্তবের সফটওয়্যারে মানুষ আসলে কোন ভুলগুলো করে, আর বড় সিস্টেম lock-এর সীমা পেরোতে কোন কৌশল নেয়?

২০০৮ সালের ASPLOS সম্মেলনে Shan Lu, Soyeon Park, Eunsoo Seo আর Yuanyuan Zhou-এর একটি গবেষণাপত্র (“Learning from Mistakes”) MySQL, Apache, Mozilla আর OpenOffice থেকে বাস্তবে রিপোর্ট হওয়া ও সারানো ১০০-র কিছু বেশি concurrency বাগ বিশ্লেষণ করে। পেপারটির বহুল-উদ্ধৃত সারাংশ মোটামুটি এরকম (সংখ্যাগুলো ওই নমুনার, সব সফটওয়্যারের সাধারণ নিয়ম নয়):

পেপারের আরেকটি পর্যবেক্ষণ খুব কাজের: অধিকাংশ বাগ ঘটাতে দুটি থ্রেডই যথেষ্ট, আর তাদের কয়েকটি নির্দিষ্ট ব্যবহারের ক্রম ঠিক করে দিলেই বাগটি নিশ্চিতভাবে দেখা দেয়। তাই “দুই থ্রেড, কয়েকটি বিন্দু” ধরে সময়-বিন্যাস খুঁজলেই বেশিরভাগ বাগ ধরা সম্ভব — অংশ ৮-এর টুলগুলো এই ধারণার ওপর দাঁড়িয়ে।

Atomicity violation — যাচাই আর ব্যবহারের মাঝে ফাঁক

পেপারে উদ্ধৃত MySQL-এর একটি বাগের সরল রূপ। থ্রেড ১ দেখে একটি pointer খালি কিনা, তারপর সেটি ব্যবহার করে; থ্রেড ২ মাঝখানে pointer-টিকে NULL করে দেয়। একে বলে check-then-act বাগ:

/* BUGGY: check and use are two separate steps */
/* Thread 1 */                          /* Thread 2 */
if (thd->proc_info) {
                                        thd->proc_info = NULL;
    fputs(thd->proc_info, out);  /* NULL! crash */
}

/* FIXED: the check and the use happen under one lock */
pthread_mutex_lock(&info_lock);         /* Thread 2 also takes info_lock */
if (thd->proc_info)                     /* before it sets proc_info = NULL */
    fputs(thd->proc_info, out);
pthread_mutex_unlock(&info_lock);

লক্ষ করুন, এখানে প্রতিটি আলাদা পড়া বা লেখা হয়তো নিজে atomic — pointer পড়া x86-64-এ একটিই instruction. বাগটি কোনো একক ব্যবহারে নয়, দুটি ব্যবহারের মাঝের ফাঁকে। প্রোগ্রামার ধরে নিয়েছিলেন যে “যাচাই করে ব্যবহার” একটানা হবে। তাই শুধু ভ্যারিয়েবলটিকে _Atomic করলে বাগ সারে না; পুরো অংশটিকেই একটি critical section বানাতে হয়, অথবা মানটি একবার local-এ পড়ে সেটিই যাচাই আর ব্যবহার করতে হয় (তখন মেমরিটি যেন মুক্ত না হয়, তা আলাদাভাবে নিশ্চিত করতে হয় — অংশ ৫ আর ৬)। ব্যালান্স দেখে টাকা তোলাও একই রোগ — DBMS কোর্সের concurrency control-এ এটিই lost update আর write skew.

Order violation — “আগে init, পরে ব্যবহার” কেউ নিশ্চিত করেনি

পেপারে উদ্ধৃত Mozilla-র একটি বাগের ধাঁচে: main থ্রেড একটি worker তৈরি করে, তারপর একটি shared pointer-এ কনফিগারেশন বসায়। লেখকের মাথায় ছিল “worker চলতে চলতে তো init হয়ে যাবে”। কিন্তু pthread_create ফেরার আগেই worker চলতে পারে। নিচের প্রোগ্রামে অনিশ্চয়তা দূর করতে একটি flag দিয়ে দুর্ভাগ্যজনক ক্রমটি জোর করে ঘটানো হয়েছে — যাতে প্রতিবার একই ফল আসে। দ্বিতীয় অংশে একই কাজ সঠিকভাবে: worker একটি state flag-এর জন্য condition variable-এ অপেক্ষা করে:

#include <pthread.h>
#include <stdatomic.h>
#include <stdio.h>
struct config { int port; };
static struct config real = { 8080 };
/* BUGGY: the worker assumes main has already set cfg */
static _Atomic(struct config *) cfg = NULL;
static atomic_int checked = 0;            /* only to force the unlucky order */
static void *buggy_worker(void *arg) {
    (void)arg;
    struct config *c = atomic_load(&cfg);
    printf("buggy: worker sees cfg = %s\n", c ? "set" : "NULL (c->port would crash)");
    atomic_store(&checked, 1);
    return NULL;
}
/* FIXED: the worker waits for a state flag that main sets after init */
static struct config *ready = NULL;
static pthread_mutex_t mu = PTHREAD_MUTEX_INITIALIZER;
static pthread_cond_t cv = PTHREAD_COND_INITIALIZER;
static void *fixed_worker(void *arg) {
    (void)arg;
    pthread_mutex_lock(&mu);
    while (ready == NULL) pthread_cond_wait(&cv, &mu);   /* not ready: sleep */
    int port = ready->port;
    pthread_mutex_unlock(&mu);
    printf("fixed: worker uses port %d\n", port);
    return NULL;
}
int main(void) {
    pthread_t t;
    pthread_create(&t, NULL, buggy_worker, NULL);
    while (!atomic_load(&checked)) { }     /* force: worker runs before init */
    atomic_store(&cfg, &real);             /* init comes too late */
    pthread_join(t, NULL);
    pthread_create(&t, NULL, fixed_worker, NULL);  /* worker may run first, */
    pthread_mutex_lock(&mu);
    ready = &real;                                 /* but it cannot use cfg */
    pthread_cond_signal(&cv);                      /* before this point     */
    pthread_mutex_unlock(&mu);
    pthread_join(t, NULL);
    return 0;
}

buggy: worker sees cfg = NULL (c->port would crash)
fixed: worker uses port 8080

২ · Priority inversion গভীরে — Mars Pathfinder-এর সময়রেখা

পর্ব ১৮-এ (Priority scheduling আর Round Robin) priority inversion-এর মূল ছবি দেখেছেন: উচ্চ task H একটি lock-এর জন্য নিম্ন task L-এর অপেক্ষায়, আর মাঝারি task M, যার lock-এর সাথে কোনো সম্পর্কই নেই, L-কে সরিয়ে রাখে। এবার সংখ্যা দিয়ে, সময়সীমা দিয়ে, আর একটি আসল মহাকাশযানের গল্প দিয়ে।

নিচের ডায়াগ্রামে সংখ্যাগুলো শেখার জন্য বানানো (মহাকাশযানের আসল সময় নয়), কিন্তু কাঠামো একই। সময় এককে মাপা। L-এর critical section ৩ একক, যার শুরুতেই সে lock R নেয়। H আসে t = 1-এ; তার মোট কাজ ৩ একক — ১ একক নিজের হিসাব, তারপর R নিয়ে ২ একক। Watchdog-এর নিয়ম: H-কে t = 8-এর মধ্যে শেষ করতে হবে। M আসে t = 3-এ, ৬ একক কাজ নিয়ে, R লাগে না। অগ্রাধিকার H > M > L, আর scheduler preemptive.

কোনো একটি task-এর কোডে ভুল ছিল না; বাগটি ছিল তিনটি নীতির সংঘর্ষে — preemptive priority scheduling, একটি ভাগের mutex, আর একটি দীর্ঘ মাঝারি task (প্র ০১-এ আরও)।

৩ · Priority inheritance বনাম priority ceiling — প্রমাণ, হিসাব আর lock-এর আরও দুই রোগ

Priority inversion-এর আনুষ্ঠানিক তত্ত্ব দেন Lui Sha, Ragunathan Rajkumar আর John Lehoczky, ১৯৯০ সালে IEEE Transactions on Computers-এ প্রকাশিত “Priority Inheritance Protocols: An Approach to Real-Time Synchronization” প্রবন্ধে। সেখানে দুটি protocol আছে।

কেন PCP-তে blocking সর্বোচ্চ একটি critical section — একটি ছোট প্রমাণ

এক প্রসেসরের সিস্টেম ধরুন। “L, H-কে আটকাতে পারে” মানে L এমন একটি lock ধরে আছে, যার ceiling ≥ H-এর অগ্রাধিকার। দাবি: H-কে বড়জোর একটি নিম্ন task-এর একটি critical section আটকায়।

• ধাপ ১: ধরুন H আসার সময় দুটি নিম্ন task, L1 আর L2, এমন lock ধরে আছে যা H-কে আটকাতে পারে — L2-র হাতে S2, L1-এর হাতে S1, আর L2 আগে S2 নিয়েছে। তাহলে L1 যখন পরে S1 নিল, তখন S2 অন্যের হাতে ছিল, তাই PCP-র নিয়মে L1-এর অগ্রাধিকার ceiling(S2)-এর চেয়ে বেশি হতে হয়েছে। কিন্তু ceiling(S2) ≥ H-এর অগ্রাধিকার > L1-এর অগ্রাধিকার — বিরোধ। তাই এমন task বড়জোর একটি।
• ধাপ ২: H ready হওয়ার পর কোনো নিম্ন task নতুন করে এমন lock নিতে পারে না, কারণ H ready থাকতে নিম্ন task চলে শুধু উত্তরাধিকার পাওয়া অগ্রাধিকারে, তার বর্তমান critical section শেষ করার জন্য।
• ফল: H-এর blocking ≤ একটি নিম্ন task-এর দীর্ঘতম critical section (যার lock-এর ceiling ≥ H). একই যুক্তিতে deadlock-এর চক্রও অসম্ভব: চক্রের দ্বিতীয় task তার প্রথম lock-টিই নিতে পারত না। ∎

PIP-এ এই নিশ্চয়তা নেই: সেখানে H প্রতিটি নিম্ন task-এর কাছে, বা প্রতিটি lock-এর কাছে, বড়জোর একবার করে আটকাতে পারে — অর্থাৎ সীমা min(n, m)টি critical section, যেখানে n নিম্ন task-এর সংখ্যা আর m lock-এর সংখ্যা।

একটি পূর্ণ হিসাব

চারটি task, অগ্রাধিকার τ1 > τ2 > τ3 > τ4. দুটি lock S1, S2. τ1 দুটিই ব্যবহার করে। τ3 S1 ধরে রাখে সর্বোচ্চ ৪ ms, τ4 S2 ধরে রাখে সর্বোচ্চ ৩ ms. τ2 কোনো lock নেয় না। τ1-এর worst-case blocking কত?

• Ceiling: S1 আর S2 দুটিই τ1 নেয়, তাই ceiling(S1) = ceiling(S2) = τ1-এর অগ্রাধিকার।
• PIP: দুর্ভাগ্যজনক ক্রমে τ4 S2 নিয়ে আছে, তাকে সরিয়ে τ3 S1 নিল; তারপর τ1 এল। τ1 প্রথমে S1-এ আটকায় (τ3-এর ৪ ms), তারপর S2-তে (τ4-এর ৩ ms). B₁ = ৪ + ৩ = ৭ ms.
• PCP: τ4 S2 ধরে থাকা অবস্থায় τ3 S1 নিতে পারত না, কারণ τ3-এর অগ্রাধিকার ceiling(S2)-এর চেয়ে বেশি নয়। তাই একসাথে দুজন হাতে থাকা সম্ভব নয়; B₁ = max(৪, ৩) = ৪ ms.

Real-time সিস্টেমে এই B মান পর্ব ২০-এর response-time হিসাবে যোগ হয়: R = C + B + (উচ্চতর task-দের interference). তাই blocking-এর সীমা না জানলে schedulability প্রমাণ করা যায় না।

বাস্তবের OS-এ

pthread_mutexattr_t a;
pthread_mutex_t m;
pthread_mutexattr_init(&a);
int rc = pthread_mutexattr_setprotocol(&a, PTHREAD_PRIO_INHERIT);  /* or PTHREAD_PRIO_PROTECT */
if (rc != 0) fprintf(stderr, "setprotocol: %s\n", strerror(rc));
/* for PRIO_PROTECT also: pthread_mutexattr_setprioceiling(&a, ceiling); */
pthread_mutex_init(&m, &a);
pthread_mutexattr_destroy(&a);

Linux-এ PTHREAD_PRIO_INHERIT mutex glibc বাস্তবায়ন করে PI-futex (FUTEX_LOCK_PI) দিয়ে, যা ২০০৬ সালের দিকে 2.6.18 kernel-এ এসেছিল; kernel-এর ভেতরে একই কাজ করে rt_mutex, আর PREEMPT_RT-এ সাধারণ spinlock-ও rt_mutex হয়ে যায়। Inheritance কাজে আসে শুধু real-time নীতিতে (SCHED_FIFO/SCHED_RR) চলা task-এ — CFS/EEVDF-এর nice মান কঠোর অগ্রাধিকার নয় (পর্ব ২১)। Windows-এর সাধারণ mutex-এ POSIX-ধাঁচের inheritance নেই; Windows Internals বইয়ের বর্ণনা অনুযায়ী Windows অনাহারী ready thread-কে সাময়িক boost দিয়ে সমস্যাটি কমায়। macOS-এ Apple-এর ডকুমেন্টেশন অনুযায়ী os_unfair_lock মালিকের তথ্য রাখে বলে kernel অগ্রাধিকার inversion এড়াতে পারে।

Lock-এর আরও দুই রোগ — convoy আর thundering herd

Lock convoy: একটি জনপ্রিয় lock-এর পেছনে অনেক থ্রেড সারি বাঁধে। Lock যদি “ন্যায্য হস্তান্তর” করে — ছাড়ার সময় সারির প্রথমজনকে দিয়ে দেয় — তাহলে প্রতিটি হস্তান্তরে একটি ঘুমন্ত থ্রেড জাগাতে হয়, আর জাগতে জাগতে lock অলস পড়ে থাকে। ফলে lock-এর critical section মাত্র কয়েক মাইক্রোসেকেন্ডের হলেও throughput নামে context switch-এর গতিতে, আর সারিটি নিজে থেকে আর ভাঙে না — যেমন অফিস ছুটির সময় ঢাকার কোনো মোড়ে সিগন্যাল সবুজ হলেও প্রতিটি গাড়ি চালু হতে সময় নেয়, তাই সারি ছোট হয় না। ১৯৭০-এর দশকের শেষে IBM-এর System R ডেটাবেসের প্রকৌশলীরা এটিকে “convoy phenomenon” নামে বর্ণনা করেছিলেন। প্রতিকার: ছোট critical section, lock ভাগ করা (প্রতিটি bucket-এর নিজের lock), আর “barging” — চলমান থ্রেড ঘুমন্তকে টপকে lock নিতে পারে; glibc আর Linux kernel-এর mutex মোটামুটি এ পথেই চলে।

Thundering herd: একটি ঘটনার জন্য অনেক থ্রেড অপেক্ষায়, ঘটনা ঘটলে সবাইকে জাগানো হয়, কিন্তু কাজ পায় একজনই — বাকিরা CPU খরচ করে আবার ঘুমায়। যেমন একটি টোকেন ডাকলে ব্যাংকের সব গ্রাহক একসাথে কাউন্টারে ছুটে আসা। উদাহরণ: একটি আইটেমের জন্য pthread_cond_broadcast (যেখানে signal-ই যথেষ্ট), বা অনেক প্রসেস একই listening socket-এ অপেক্ষা। Linux বহু আগেই blocking accept()-এ একজনকেই জাগায়; epoll-এর জন্য Linux 4.5-এ EPOLLEXCLUSIVE যোগ হয়েছে, আর SO_REUSEPORT সংযোগগুলো আলাদা socket-এ ভাগ করে দেয়। তবে shutdown-এর মতো জায়গায় broadcast-ই ঠিক (পর্ব ১৫)।

৪ · Lock-free আর wait-free — progress-এর তিন স্তর আর Treiber stack

Lock-এর মৌলিক দুর্বলতা: lock-ধারী থ্রেড থেমে গেলে (preempt, page fault, মৃত্যু) বাকি সবাই আটকে থাকে — inversion, convoy আর deadlock এরই রূপ। বিকল্প: এমন ডেটা স্ট্রাকচার, যেখানে কেউ অন্যকে আটকে রাখতেই পারে না। এদের নিশ্চয়তা মাপা হয় progress guarantee দিয়ে:

প্রতিটি স্তর আগেরটির চেয়ে শক্তিশালী। Maurice Herlihy-র ১৯৯১ সালের “Wait-Free Synchronization” প্রবন্ধ দেখায় যে শুধু read/write দিয়ে সাধারণ wait-free ডেটা স্ট্রাকচার বানানো যায় না, কিন্তু compare-and-swap (CAS)-এর মতো instruction দিয়ে যায় — এ কারণেই আধুনিক CPU-গুলোতে CAS (x86-এর lock cmpxchg) বা LL/SC (ARM, POWER, RISC-V) থাকে (পর্ব ২৩)। CAS-এর অর্থ এক লাইনে: ঠিকানাটিতে যদি এখনো আগে দেখা মানটিই থাকে, তবে নতুন মান বসানো হয় আর ফল “সফল”; নইলে কিছুই বদলায় না, আর এখনকার মানটি জানিয়ে দেওয়া হয় — পুরোটা একটি অবিভাজ্য ধাপে।

Treiber stack — একটি pointer, একটি CAS

R. Kent Treiber ১৯৮৬ সালে IBM-এর একটি গবেষণা প্রতিবেদনে সবচেয়ে সরল lock-free ডেটা স্ট্রাকচারগুলোর একটি বর্ণনা করেন: একটি linked-list stack, যার পুরো অবস্থা একটি top pointer. Push: নতুন নোডের next-এ বর্তমান top বসানো, তারপর CAS(top, দেখা top, নতুন নোড). Pop: top পড়া, তার next পড়া, তারপর CAS(top, দেখা top, next). কেউ মাঝে top বদলে দিলে CAS ব্যর্থ হয়, আর আবার চেষ্টা। (Linked list আর stack-এর মৌলিক ধারণা: DSA কোর্সের stack পর্ব)

#include <pthread.h>
#include <stdatomic.h>
#include <stdio.h>
#include <stdlib.h>
struct node { int val; struct node *next; };
static _Atomic(struct node *) top = NULL;          /* whole stack = one pointer */

static void push(struct node *n) {
    struct node *old = atomic_load(&top);
    do n->next = old;                               /* link to the top we saw */
    while (!atomic_compare_exchange_weak(&top, &old, n));   /* moved? retry */
}
static struct node *pop(void) {
    struct node *old = atomic_load(&top);
    while (old && !atomic_compare_exchange_weak(&top, &old, old->next)) { }
    return old;                          /* on CAS failure, old = the new top */
}
static void *pusher(void *arg) {
    int base = *(int *)arg;
    for (int i = 0; i < 1000; i++) {
        struct node *n = malloc(sizeof *n);
        if (!n) abort();
        n->val = base + i; push(n);
    }
    return NULL;
}
int main(void) {
    pthread_t a, b; int base_a = 0, base_b = 1000;
    pthread_create(&a, NULL, pusher, &base_a);      /* pushes 0..999     */
    pthread_create(&b, NULL, pusher, &base_b);      /* pushes 1000..1999 */
    pthread_join(a, NULL); pthread_join(b, NULL);
    static char seen[2000]; int count = 0, dup = 0; long sum = 0;
    for (struct node *n; (n = pop()) != NULL; free(n)) {   /* one thread: no ABA */
        count++; sum += n->val; dup += seen[n->val]++ ? 1 : 0;
    }
    printf("lock-free: %s\n", atomic_is_lock_free(&top) ? "yes" : "no");
    printf("popped %d nodes, sum %ld (expected %ld), duplicates %d\n",
           count, sum, 1999L * 2000 / 2, dup);
    return 0;
}

lock-free: yes
popped 2000 nodes, sum 1999000 (expected 1999000), duplicates 0

প্রমাণ: Treiber stack lock-free, কিন্তু wait-free নয়

• পর্যবেক্ষণ: top-এ লেখে শুধু সফল CAS. একটি থ্রেড T-এর CAS ব্যর্থ হয় শুধু যদি T-এর পড়া আর CAS-এর মাঝে top বদলেছে (weak CAS-এর কারণহীন ব্যর্থতা বাদে, যা hardware সীমিত রাখে)।
• তাই: T-এর প্রতিটি “আসল” ব্যর্থতার পেছনে অন্য কোনো থ্রেডের একটি সফল CAS আছে — অর্থাৎ কারও একটি push বা pop সম্পূর্ণ হয়েছে। T যদি অসীমবার ব্যর্থ হয়, অন্যরা অসীমবার সফল হয়েছে। সিস্টেম কখনো থামে না — এটিই lock-free-এর সংজ্ঞা। কেউ মাঝপথে থেমে গেলেও (preempt বা মৃত্যু) সে কোনো lock ধরে রাখে না, তাই কেউ আটকায় না।
• Wait-free নয়: দুর্ভাগ্যজনক scheduler-এ T প্রতিবার পড়ার পর অন্য কেউ top বদলে দিতে পারে — T-এর ধাপের কোনো ঊর্ধ্বসীমা নেই। ∎

তাই lock-free কাঠামো priority inversion থেকে মুক্ত; তবে hard real-time-এ প্রতিটি task-এর পূর্ণ নিশ্চয়তা দেয় শুধু wait-free.

৫ · ABA সমস্যা — CAS যখন ভুল করে সফল হয়

CAS শুধু যাচাই করে “মানটি কি এখনো একই?” — “এর মধ্যে কি কিছু ঘটেছে?” নয়। ধরুন আপনি বাড়ির দারোয়ানকে বললেন, “গেটের সামনে সাদা গাড়িটি থাকলে ড্রাইভারকে চাবি দিন।” আপনি সরে যাওয়ার পর গাড়িটি চলে গেল, আর একই মডেলের আরেকটি সাদা গাড়ি এসে দাঁড়াল। দারোয়ান দেখলেন “সাদা গাড়ি আছে” — শর্ত মিলেছে — আর ভুল মানুষকে চাবি দিলেন। মান A থেকে B হয়ে আবার A হলে CAS তফাত বোঝে না; একেই বলে ABA সমস্যা. Lock-free stack-এ এটি ঘটে যখন একটি নোড মুক্ত হয়ে আবার একই ঠিকানায় ফিরে আসে — malloc প্রায়ই সদ্য মুক্ত ঠিকানাই আবার দেয়।

একই interleaving একটি ছোট simulator-এ — প্রথমে সাধারণ pointer CAS, তারপর version-সহ CAS:

// ABA on a lock-free stack: plain CAS vs CAS on (pointer, version)
function run(tagged) {
  const next = { A: 'B', B: 'C', C: null };          // A -> B -> C
  let top = { ptr: 'A', ver: 0 };
  const freed = new Set();
  const cas = (exp, ptr) => {                         // atomic compare-and-swap
    const same = top.ptr === exp.ptr && (!tagged || top.ver === exp.ver);
    if (same) top = { ptr, ver: top.ver + 1 };
    return same;
  };
  const show = () => { let s = [], p = top.ptr;
    while (p && s.length < 5) { s.push(p + (freed.has(p) ? '(freed!)' : '')); p = next[p]; }
    return s.join(' -> ') + (tagged ? `  [ver ${top.ver}]` : ''); };
  console.log(`--- ${tagged ? 'CAS on (pointer, version)' : 'plain pointer CAS'} ---`);
  const seen = { ...top }, seenNext = next[seen.ptr];  // T1: old = A, next = B
  console.log(`T1 reads top=${seen.ptr}, next=${seenNext}, then is preempted`);
  cas({ ...top }, next[top.ptr]); console.log(`T2 pop A      : ${show()}`);
  cas({ ...top }, next[top.ptr]); freed.add('B'); console.log(`T2 pop B, free: ${show()}`);
  next.A = top.ptr; cas({ ...top }, 'A'); console.log(`T2 push A     : ${show()}`);
  if (cas(seen, seenNext)) {
    console.log(`T1 CAS(top: A -> B) succeeds -> ${show()}   WRONG`);
  } else {
    console.log('T1 CAS fails: top is A again, but the version changed');
    const old = { ...top };                           // retry with fresh values
    cas(old, next[old.ptr]); console.log(`T1 retries, pops A -> ${show()}   correct`);
  }
}
run(false);
run(true);

--- plain pointer CAS ---
T1 reads top=A, next=B, then is preempted
T2 pop A      : B -> C
T2 pop B, free: C
T2 push A     : A -> C
T1 CAS(top: A -> B) succeeds -> B(freed!) -> C   WRONG
--- CAS on (pointer, version) ---
T1 reads top=A, next=B, then is preempted
T2 pop A      : B -> C  [ver 1]
T2 pop B, free: C  [ver 2]
T2 push A     : A -> C  [ver 3]
T1 CAS fails: top is A again, but the version changed
T1 retries, pops A -> C  [ver 4]   correct

সমাধানের চার পথ — আর আসল সমস্যা “কখন মুক্ত করা নিরাপদ”

গভীরে তাকালে ABA আসলে একটি বড় প্রশ্নের অংশ: safe memory reclamation — lock-free কাঠামো থেকে সরানো নোড কখন free করা নিরাপদ, যখন অন্য থ্রেড হয়তো এখনো তার pointer হাতে নিয়ে আছে? Java বা Go-র মতো garbage collector-ওয়ালা ভাষায় সমস্যাটি অনেকটা মিটে যায়: কেউ reference রাখলে GC নোডটি মুক্ত করে না, তাই একই ঠিকানা ফিরে আসে না — Java-র ConcurrentLinkedQueue (Michael আর Scott-এর ১৯৯৬ সালের queue-র ভিত্তিতে) তাই তুলনামূলক সরল। C আর C++-এ কাজটি আপনার; পরের অংশের RCU এর একটি অসাধারণ উত্তর। C++26-এর জন্য hazard pointer আর RCU-র সাধারণ library সমর্থন গৃহীত হয়েছে বলে জানা যায়; আপনার compiler-এ এসেছে কি না, তার ডকুমেন্টেশনে দেখে নিন।

৬ · পড়া বেশি, লেখা কম — seqlock আর RCU

অনেক shared ডেটা প্রতি সেকেন্ডে লাখবার পড়া হয়, কিন্তু কদাচিৎ বদলায়: ঘড়ি, routing table, কনফিগারেশন। এখানে পর্ব ২৬-এর readers-writer lock-ও অপচয়, কারণ প্রতিটি পাঠককে একটি shared counter-এ লিখতে হয়, আর সেই cache line core থেকে core-এ ছোটে। দুটি কৌশল পাঠককে প্রায় বিনা খরচে পড়তে দেয়।

Seqlock — “পড়ার আগে আর পরে নম্বর মিলিয়ে দেখুন”

একটি sequence counter থাকে। লেখক লেখার আগে counter-কে বিজোড় করে, লেখা শেষে আবার জোড়। পাঠক কোনো lock নেয় না: পড়ার আগে counter দেখে (s1), ডেটা কপি করে, তারপর আবার counter দেখে (s2). s1 বিজোড় হলে, বা s1 ≠ s2 হলে, মাঝে লেখা হয়েছে — কপিটি ফেলে আবার পড়ে। বাস টার্মিনালের সময়সূচির বোর্ডের মতো: কর্মী বোর্ড বদলানোর সময় “হালনাগাদ হচ্ছে” বাতি জ্বালান; যাত্রী পড়ার আগে আর পরে বাতি আর বোর্ডের নম্বর দেখে নেন — মাঝে বদলে থাকলে আবার পড়েন।

#include <pthread.h>
#include <stdatomic.h>
#include <stdio.h>
#define N 100000
static atomic_uint seq;            /* even = stable, odd = write in progress */
static atomic_long x, y;           /* the writer keeps y == -x               */
#define LD(v, o) atomic_load_explicit(&(v), memory_order_##o)
#define ST(v, val, o) atomic_store_explicit(&(v), (val), memory_order_##o)
static void *writer(void *arg) {
    (void)arg;
    for (long i = 1; i <= N; i++) {
        unsigned s = LD(seq, relaxed);
        ST(seq, s + 1, relaxed);                      /* odd: "writing" */
        atomic_thread_fence(memory_order_release);
        ST(x, i, relaxed); ST(y, -i, relaxed);        /* the pair */
        ST(seq, s + 2, release);                      /* even: "done"   */
    }
    return NULL;
}
static void *reader(void *arg) {
    long *bad = arg;
    for (int r = 0; r < N; r++) {
        unsigned s1, s2; long a, b;
        do {
            s1 = LD(seq, acquire);
            a = LD(x, relaxed); b = LD(y, relaxed);
            atomic_thread_fence(memory_order_acquire);
            s2 = LD(seq, relaxed);
        } while ((s1 & 1) || s1 != s2);         /* writer was busy: retry */
        if (a != -b) (*bad)++;                  /* a torn pair would count */
    }
    return NULL;
}
int main(void) {
    pthread_t w, r1, r2; long bad1 = 0, bad2 = 0;
    pthread_create(&w, NULL, writer, NULL);
    pthread_create(&r1, NULL, reader, &bad1);
    pthread_create(&r2, NULL, reader, &bad2);
    pthread_join(w, NULL); pthread_join(r1, NULL); pthread_join(r2, NULL);
    printf("writer: %d updates, final pair (%ld, %ld), seq = %u\n",
           N, LD(x, relaxed), LD(y, relaxed), LD(seq, relaxed));
    printf("readers: %d reads, inconsistent reads: %ld\n", 2 * N, bad1 + bad2);
    return 0;
}

writer: 100000 updates, final pair (100000, -100000), seq = 200000
readers: 200000 reads, inconsistent reads: 0

Linux kernel-এ seqlock আর তার হালকা রূপ seqcount ব্যবহৃত হয় সময়ের হিসাবে — যেমন ৩২-বিট মেশিনে ৬৪-বিট jiffies_64 পড়া, আর timekeeping-এর তথ্য। সবচেয়ে সুন্দর উদাহরণ vDSO: clock_gettime system call ছাড়াই user space থেকে kernel-এর ভাগ করা একটি পাতা পড়ে, আর একটি sequence counter দিয়েই নিশ্চিত হয় যে মাঝপথে বদলানো সময় পড়া হয়নি। সীমা: পাঠক pointer অনুসরণ করতে পারে না (লেখক মাঝপথে নোড মুক্ত করলে পাঠক মুক্ত মেমরি পড়বে), লেখা ঘন ঘন হলে পাঠক বারবার ফেরত যায়, আর একাধিক লেখক থাকলে তাদের আলাদা একটি lock লাগে।

RCU — পাঠক কখনো অপেক্ষা করে না

Read-Copy-Update-এর নাম থেকেই কৌশল: হালনাগাদ করতে চাইলে পুরোনো ডেটা কপি করুন, কপিতে বদলান, তারপর একটি pointer এক ধাপে নতুন কপিতে সরিয়ে দিন। পাঠক lock ছাড়া pointer পড়ে — হয় পুরো পুরোনোটা দেখে, নয় পুরো নতুনটা, মাঝামাঝি কখনো না। কঠিন প্রশ্ন একটিই: পুরোনো কপি কখন মুছবেন? উত্তর: যখন নিশ্চিত হবেন যে pointer বদলানোর আগে শুরু হওয়া সব পাঠক শেষ করেছে — এই অপেক্ষার সময়টির নাম grace period. Linux-এর classic RCU-তে পাঠকের critical section-এ ঘুমানো বা preempt হওয়া চলে না; তাই প্রতিটি CPU একবার context switch করলে, idle হলে বা user mode-এ গেলে (quiescent state) বোঝা যায়, সেই CPU-র পুরোনো পাঠক শেষ। পাঠকের rcu_read_lock() তাই প্রায় বিনা খরচের — classic RCU-তে সেটি শুধু preemption বন্ধ করে।

struct config { int limit; struct rcu_head rcu; };
static struct config __rcu *gcfg;
static DEFINE_SPINLOCK(cfg_lock);                 /* writers only */

int read_limit(void)                              /* reader: no lock, no wait */
{
	int v;
	rcu_read_lock();
	v = rcu_dereference(gcfg)->limit;
	rcu_read_unlock();
	return v;
}

int set_limit(int limit)                          /* writer: copy, publish, wait, free */
{
	struct config *new = kmalloc(sizeof(*new), GFP_KERNEL), *old;
	if (!new)
		return -ENOMEM;
	spin_lock(&cfg_lock);
	old = rcu_dereference_protected(gcfg, lockdep_is_held(&cfg_lock));
	*new = *old;                                  /* copy */
	new->limit = limit;                           /* update the copy */
	rcu_assign_pointer(gcfg, new);                /* publish */
	spin_unlock(&cfg_lock);
	synchronize_rcu();                            /* wait for old readers */
	kfree(old);                                   /* or: kfree_rcu(old, rcu); */
	return 0;
}

RCU-র জন্ম ১৯৯০-এর দশকে Sequent-এ, Paul McKenney আর Jack Slingwine-এর কাজে; ২০০২ সালে এটি Linux 2.5-এ আসে। আজ kernel-এ RCU-র API হাজার হাজার জায়গায় ব্যবহৃত — routing আর socket lookup, VFS-এর path lookup, প্রসেস আর module-এর তালিকা। User space-এর জন্য আছে liburcu. এর দাম আর ইতিহাস নিয়ে প্র ০৩ দেখুন।

৭ · Transactional memory আর lock ছাড়া অন্য মডেল

Transactional memory — ডেটাবেসের transaction মেমরিতে

ধারণাটি সুন্দর: প্রোগ্রামার শুধু লিখবেন “এই অংশটি atomic”, আর hardware বা runtime ডেটাবেসের মতো (DBMS কোর্সের transaction পর্ব) সেটিকে একটি transaction হিসেবে চালাবে — অন্য কারও সাথে সংঘাত না হলে সব লেখা একসাথে commit, হলে সব বাতিল (abort) করে আবার চেষ্টা। কোন lock, কোন ক্রমে — এসব ভাবনা নেই, তাই lock-ক্রমের deadlock-ও নেই। Maurice Herlihy আর Eliot Moss ১৯৯৩ সালে hardware transactional memory প্রস্তাব করেন; Nir Shavit আর Dan Touitou ১৯৯৫ সালে software রূপ।

বাস্তবতা মিশ্র। Intel ২০১৩ সালে Haswell প্রসেসরে TSX (Transactional Synchronization Extensions) আনে — দুটি অংশ: HLE (পুরোনো lock-কোডকে transaction হিসেবে চালানোর ইঙ্গিত) আর RTM (xbegin/xend). ২০১৪ সালে একটি hardware ত্রুটি (erratum) ধরা পড়ায় microcode হালনাগাদ দিয়ে Haswell আর প্রথম দিকের কিছু Broadwell-এ TSX বন্ধ করা হয়। ২০১৯ সালে TSX-সংশ্লিষ্ট একটি নিরাপত্তা দুর্বলতা (TAA) প্রকাশের পর আরও অনেক প্রসেসরে এটি বন্ধ করার বিকল্প আসে, আর পরে Intel-এর microcode হালনাগাদে বহু client প্রসেসরে TSX ডিফল্টভাবে বন্ধ হয়ে যায় — কোন মডেলে কী অবস্থা, তা Intel-এর ডকুমেন্টেশন আর আপনার OS-এর /proc/cpuinfo-তে rtm flag দেখে নিশ্চিত হতে হয়। IBM-এর কয়েকটি প্রসেসরেও hardware TM ছিল। সমস্যা মৌলিক: ডেটা cache-এ না ধরলে বা system call ও page fault-এ abort, তাই একটি সাধারণ lock-এর “fallback” পথ সবসময় লাগে (প্র ০২-এ বিস্তারিত)। Software TM টিকে আছে ভাষার স্তরে — Haskell-এর STM আর Clojure-এর ref.

Shared memory একেবারে বাদ — message passing

আরেকটি দর্শন: থ্রেডেরা মেমরি ভাগই করবে না, শুধু বার্তা পাঠাবে (পর্ব ১২-এর message passing-এর ধারণা, এবার প্রোগ্রামিং মডেল হিসেবে)। অফিসের ফাইল ক্যাবিনেটে সবাই হাত না দিয়ে, প্রতিটি ফাইলের একজন দায়িত্বপ্রাপ্ত কর্মী, আর অন্যরা তাঁকে চিরকুট পাঠান। Data race তখন গঠনগতভাবেই অসম্ভব — কিন্তু বাগ শেষ নয়।

-module(counter).
-export([start/0, loop/1]).

start() -> spawn(counter, loop, [0]).        % a new actor with state 0

loop(N) ->
    receive                                    % one message at a time
        {inc, From} -> From ! {ok, N + 1}, loop(N + 1);
        {get, From} -> From ! {value, N},  loop(N)
    end.

package main

import "fmt"

func main() {
    jobs := make(chan int)                 // unbuffered: send waits for a receiver
    results := make(chan int)
    go func() {                            // a goroutine (lightweight thread)
        for j := range jobs { results <- j * j }
        close(results)
    }()
    go func() { for i := 1; i <= 3; i++ { jobs <- i }; close(jobs) }()
    for r := range results { fmt.Println(r) }   // 1 4 9
}

let balance = 100;
async function withdraw(amount) {
  if (balance >= amount) {                 // check
    await logToServer(amount);             // other tasks run here!
    balance -= amount;                     // act -- on a stale check
  }
}
// withdraw(80) and withdraw(80) started together -> balance = -60

৮ · বাগ ধরার হাতিয়ার — sanitizer থেকে model checking

পর্ব ১৫-এ (POSIX thread হাতে-কলমে) ThreadSanitizer আর Helgrind-এর আসল আউটপুট পড়েছেন — এখানে পুনরাবৃত্তি নয়, পুরো মানচিত্র। হাতিয়ারগুলোকে তিন দলে ভাবা যায়: চলমান প্রোগ্রাম পর্যবেক্ষণ, kernel-এর নিজের পাহারা, আর নকশা স্তরে সব সম্ভাব্য ক্রম যাচাই।

lockdep (Ingo Molnar, ২০০৬) বিশেষভাবে চমৎকার: প্রতিটি lock-কে একটি “class”-এ ফেলে, আর প্রতিবার কেউ A ধরে B নিলে A → B ধার যোগ করে। কখনো B → A ধার যোগ হলেই চক্র — পর্ব ২৭-এর resource-allocation graph-এর চক্র — আর kernel সঙ্গে সঙ্গে সতর্ক করে, যদিও দুটি পথ কখনো একসাথে চলেনি। বাস্তবের deadlock ঘটার অপেক্ষা না করে নিয়মভঙ্গ ধরা — ঠিক যেভাবে TSan race ধরে।

TLA+ Leslie Lamport-এর তৈরি একটি specification ভাষা; TLC model checker ছোট আকারের (যেমন ৩টি থ্রেড, ২টি আইটেম) সিস্টেমের প্রতিটি অবস্থা ঘুরে দেখে কোনো invariant ভাঙে কি না। Amazon Web Services-এর প্রকৌশলীরা ২০১৫ সালে Communications of the ACM-এ জানান, DynamoDB আর S3-এর মতো সিস্টেমের নকশায় TLA+ এমন সূক্ষ্ম বাগ ধরেছে, যা পরীক্ষা আর code review-এ ধরা পড়েনি। ABA বা Pathfinder-এর মতো বাগ ছোট মডেলেই বেরিয়ে আসে, কারণ model checker ঠিক “দুর্ভাগ্যজনক ক্রমগুলো”ই খোঁজে।

৯ · AI-এর যুগে concurrency-র কোড আর তথ্য

AI এক নিমেষে একটি “lock-free queue” লিখে দেবে, আর সেটি আপনার ল্যাপটপে হাজারবার ঠিক চলতেও পারে — এই পর্বের প্রতিটি বাগ সাধারণ পরীক্ষায় এভাবেই লুকিয়ে থাকে। সাধারণ ভুলগুলো:

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

• প্রতিটি shared ভ্যারিয়েবলের রক্ষাকারী (lock, atomic, RCU, মালিক থ্রেড) বলতে পারি
• প্রতিটি “আগে X, পরে Y” অনুমানের জন্য কোডে একটি সমন্বয় (join, flag + condvar, semaphore) আছে
• Lock-free হলে: মেমরি কখন মুক্ত হয়, আর ABA কেন ঘটবে না — দুটির উত্তর জানি
• TSan আর ASan দিয়ে, অনেক থ্রেড আর অনেক পুনরাবৃত্তিতে চালিয়েছি; কম core-এর container-এও
• x86-এর বাইরে (ARM) পরীক্ষা করেছি, বা memory ordering-এর যুক্তি নিজে মিলিয়েছি
• Real-time বা priority-ভিত্তিক সিস্টেমে mutex-এর protocol (inherit/protect) ঠিক করেছি