Hardware support — atomic instruction, spinlock আর memory ordering

১ · শুধু সফটওয়্যার কেন যথেষ্ট নয় — reordering আর memory barrier

পর্ব ২২-এ দেখেছেন, একটি ভালো critical section সমাধানের তিনটি শর্ত: mutual exclusion (একসাথে একজনই ভেতরে), progress (ভেতরে কেউ না থাকলে ঢুকতে চাওয়া কাউকে অনির্দিষ্টকাল আটকে রাখা যাবে না) আর bounded waiting (ঢুকতে চাওয়ার পর অন্যরা সীমিত সংখ্যকবারই আগে ঢুকতে পারবে)। সেখানে Peterson-এর সমাধান শুধু সাধারণ load আর store দিয়ে দুটি থ্রেডের জন্য তিনটি শর্তই পূরণ করে। মনে করিয়ে দিই, থ্রেড i-এর প্রবেশ-অংশ:

flag[i] = true;            // "I want to enter"
turn = j;                  // "but you go first"
while (flag[j] && turn == j)
    ;                      // busy wait
/* critical section */
flag[i] = false;

এর প্রমাণে একটি নীরব অনুমান আছে: প্রতিটি থ্রেডের load আর store মেমরিতে ঠিক কোডের ক্রমে ঘটে, আর সব থ্রেড একই ক্রম দেখে। আধুনিক কম্পিউটারে এই অনুমান তিন জায়গায় ভাঙে:

• Compiler ক্রম বদলায়: একক থ্রেডের চোখে flag[i] = true আর flag[j] পড়া স্বাধীন — আলাদা ঠিকানা। তাই optimizer পড়াটিকে আগে আনতে পারে, বা লুপের ভেতরের flag[j] একবার পড়ে register-এ রেখে দিতে পারে।
• CPU ক্রম বদলায়: x86-এর প্রতিটি core নিজের লেখা প্রথমে একটি ছোট সারিতে রাখে — store buffer. লেখাটি অন্য core-এর কাছে পৌঁছানোর আগেই পরের load মেমরি থেকে পড়ে ফেলে। ফলে T0 পড়ে flag[1] == false, T1 পড়ে flag[0] == false — দুজনেই critical section-এ! অংশ ৮-এ এটি নিজের চোখে দেখবেন।
• একাধিক core: একটি core-এর যুগে সবচেয়ে পুরোনো kernel কৌশল ছিল interrupt বন্ধ করা (x86-এ cli): interrupt না এলে preemption নেই, তাই critical section নিরাপদ। কিন্তু multicore-এ অন্য core তো চলছেই; তা ছাড়া cli একটি privileged instruction, user program পারে না, আর বেশিক্ষণ interrupt বন্ধ রাখলে timer আর ডিভাইসের সংকেত দেরিতে পৌঁছায়।

Memory barrier — ক্রম বদলানোর দেয়াল

Memory barrier (বা fence) এমন একটি instruction, যা বলে: “এর আগের মেমরির কাজ শেষ না হওয়া পর্যন্ত পরেরগুলো শুরু হবে না” — অন্তত নির্দিষ্ট কিছু ধরনের ক্ষেত্রে। x86-এ পূর্ণ fence হলো mfence (আর যেকোনো lock-যুক্ত instruction-ও পূর্ণ fence-এর কাজ করে); ARMv8-এ dmb ish. Compiler-কেও আলাদা করে থামাতে হয় — GCC-তে asm volatile("" ::: "memory") একটি compiler barrier, যা কোনো CPU instruction তৈরি করে না, শুধু compiler-কে ক্রম বদলাতে নিষেধ করে। C11-এ দুটো একসাথে পাওয়া যায় atomic_thread_fence(memory_order_seq_cst) দিয়ে।

Peterson-এর turn = j-এর পরে একটি পূর্ণ fence বসালে x86-এ সে আবার সঠিক হয়। তবু বাস্তবে কেউ Peterson ব্যবহার করে না: এটি দুই থ্রেডের জন্য (n থ্রেডে অনেক জটিল), প্রতিটি থ্রেডের নম্বর জানা থাকতে হয়, আর fence-এর খরচ দিতেই হয়। তার চেয়ে সরল আর দ্রুত পথ — হার্ডওয়্যারকে দিয়েই একটি ঠিকানায় পড়া আর লেখা একটি অবিভাজ্য ধাপে করানো। এমন instruction-কে বলে read-modify-write (RMW) atomic instruction. পরের তিনটি অংশ তাদের নিয়ে।

২ · Test-and-set — দেখা আর দখল এক ধাপে

Test-and-set (TAS) একটি ঠিকানার পুরোনো মান ফেরত দেয় আর সেখানে true লিখে দেয় — দুটোই একটি অবিভাজ্য ধাপে। অর্থাৎ অন্য কোনো core মাঝখানে ওই ঠিকানা পড়তে বা লিখতে পারে না। C-র ভাষায় এর অর্থ (হার্ডওয়্যার এটি পুরোটা atomically করে):

bool test_and_set(bool *target) {   /* executed atomically */
    bool old = *target;
    *target = true;
    return old;
}

/* a TAS lock */
void lock(bool *L)   { while (test_and_set(L)) ;  /* spin */ }
void unlock(bool *L) { *L = false; }

x86-এ এটি সাধারণত xchg — মেমরির সাথে register অদলবদল, যার lock নিজে থেকেই লাগানো থাকে। C11-এ portable রূপ হলো atomic_flag: atomic_flag_test_and_set(&f) আর atomic_flag_clear(&f). মানদণ্ড অনুযায়ী atomic_flag-ই একমাত্র ধরন, যা সব প্ল্যাটফর্মে lock ছাড়া (lock-free) হওয়ার নিশ্চয়তা পায়।

সঠিকতার প্রমাণ — mutual exclusion আর progress

• Mutual exclusion: কোনো থ্রেড ভেতরে ঢোকে কেবল তখন, যখন তার TAS 0 ফেরত দেয়। TAS 0 ফেরত দিলে সেই একই ধাপে L = 1 হয়ে যায়। এরপর আরেকটি TAS 0 পেতে হলে মাঝে কাউকে L = 0 লিখতে হবে — আর সেটি লেখে শুধু ভেতরের থ্রেড, বেরোনোর সময়। তাই যেকোনো মুহূর্তে ভেতরে সর্বোচ্চ একজন। ∎
• Progress: L = 0 অবস্থায় এক বা একাধিক থ্রেড চেষ্টা করলে, তাদের মধ্যে প্রথম যে TAS ঘটে সেটি 0 পায়, তাই কেউ না কেউ ঢোকে। ∎

নিচে দুটি থ্রেড একটি TAS lock নিয়ে প্রতিযোগিতা করছে। খেয়াল করুন T2 কীভাবে ঘুরতে থাকে, আর শেষের দিকে কী অন্যায় ঘটে:

1lock:   while (test_and_set(&L)) ;  // spin2        /* critical section */3unlock: L = 0;

প্রমাণ: TAS lock-এ bounded waiting নেই

Bounded waiting মানে একটি নির্দিষ্ট সীমা k আছে: একটি থ্রেড ঢুকতে চাওয়ার পর অন্যরা সর্বোচ্চ k বার আগে ঢুকতে পারবে। TAS lock-এর জন্য এমন কোনো k নেই — একটি বৈধ execution দেখালেই যথেষ্ট:

1. T2 প্রবেশ-লুপে আছে। T1 ভেতরে, L = 1.
2. চিরকাল পুনরাবৃত্তি: T2-এর একটি TAS (পায় 1) → T1 unlock করে (L = 0) → T1-এর TAS (পায় 0, ঢোকে) → আবার T2-এর TAS (পায় 1)…
3. এই execution-এ T2 অসীমবার ধাপ নেয়, তাই scheduler তাকে বঞ্চিত করছে না; প্রতিটি ধাপ অ্যালগরিদমের নিয়ম মেনে চলে। তবু T1 অসীমবার ঢোকে, আর T2 একবারও না।

যেকোনো k-এর জন্য এই execution-এ T1 k + ১ বার ঢোকে T2-এর আগে, তাই কোনো সীমা টেকে না। ∎ মূল কারণ: lock-টি শুধু “খালি না ভরা” মনে রাখে, কে কতক্ষণ অপেক্ষা করছে তা নয়। এটি শুধু তাত্ত্বিক নয় — যে core সবে lock ছেড়েছে, তার cache-এ line-টি সবচেয়ে কাছে, তাই সে প্রায়ই আবার জেতে।

বইয়ের সমাধান — bounded-waiting TAS অ্যালগরিদম

Silberschatz-দের পাঠ্যবইয়ে n থ্রেডের জন্য একটি সংস্করণ আছে, যেখানে প্রতিটি থ্রেডের একটি waiting[i] ঘর থাকে, আর বেরোনোর সময় থ্রেডটি lock ছেড়ে না দিয়ে সরাসরি পরের অপেক্ষারত থ্রেডকে হাতে তুলে দেয়:

waiting[i] = true;
key = true;
while (waiting[i] && key)
    key = test_and_set(&lock);
waiting[i] = false;
    /* critical section */
j = (i + 1) % n;
while (j != i && !waiting[j])       // look for the next waiter, in circle
    j = (j + 1) % n;
if (j == i) lock = false;           // nobody waiting: open the lock
else        waiting[j] = false;     // hand over directly to thread j

• Mutual exclusion: থ্রেড i লুপ থেকে বেরোয় কেবল key == false (TAS 0 পেয়েছে) বা waiting[i] == false (কেউ হাতে তুলে দিয়েছে) হলে। প্রথম প্রবেশে শুধু একজনই TAS-এ 0 পায়। এরপর প্রতিটি বেরোনো থ্রেড ঠিক একটি কাজ করে — হয় lock = false, নয় একজনের waiting[j] = false — অর্থাৎ ঢোকার “অনুমতিপত্র” একটিই, হাতবদল হয়।
• Progress: বেরোনো থ্রেড হয় lock খুলে দেয়, নয় একজন অপেক্ষারতকে সরাসরি ঢুকিয়ে দেয়; তাই কেউ অপেক্ষা করলে সিস্টেম আটকে থাকে না।
• Bounded waiting: বেরোনো থ্রেড i + ১, i + ২, … এই বৃত্তাকার ক্রমে খোঁজে। তাই অপেক্ষারত একটি থ্রেডের আগে সর্বোচ্চ n − ১ জন ঢুকতে পারে। ∎

৩ · Compare-and-swap আর LL/SC — মান না বদলালে তবেই লেখা

TAS শুধু 1 লিখতে জানে। Compare-and-swap (CAS) বেশি সাধারণ: ঠিকানাটিতে যদি এখনো expected থাকে, তবেই new লেখা হয়, আর ফেরত মান জানায় লেখা সফল হলো কি না — সবটা একটি অবিভাজ্য ধাপে।

bool CAS(int *addr, int expected, int new) {   /* executed atomically */
    if (*addr != expected) return false;       /* someone changed it */
    *addr = new;
    return true;
}

x86 — lock cmpxchg

x86-এ CAS এসেছে ১৯৮৯ সালের Intel 80486-এর cmpxchg দিয়ে। এর নিয়ম: তুলনার মান আগে থেকে eax (বা rax) register-এ রাখতে হয়। মেমরির মান eax-এর সমান হলে নতুন মান লেখা হয় আর ZF flag 1 হয়; সমান না হলে মেমরির আসল মান eax-এ এনে দেওয়া হয় আর ZF 0 হয়। একাধিক core-এ অবিভাজ্য করতে সামনে lock prefix লাগে। দুই শব্দ একসাথে বদলানোর জন্য আছে cmpxchg8b আর x86-64-এ cmpxchg16b.

    mov   eax, 0              ; expected = 0 (lock free)
    mov   ecx, 1              ; new = 1
    lock cmpxchg [rdi], ecx   ; if [rdi] == eax: [rdi] = ecx, ZF = 1
                              ; else:          eax = [rdi], ZF = 0
    jnz   busy                ; ZF == 0 -> someone holds it

ARM — load-linked / store-conditional (ldxr/stxr)

ARM, RISC-V আর POWER-এর মতো RISC নকশায় একটি instruction-এ “পড়া + তুলনা + লেখা” রাখা হয়নি। তার জায়গায় একটি জোড়া: load-linked/store-conditional. ARMv8-এ ldxr (load exclusive) মান পড়ে, আর সঙ্গে সঙ্গে ওই ঠিকানার ওপর একটি exclusive monitor চালু করে — “এই ঠিকানায় নজর রাখছি”। পরে stxr (store exclusive) লিখতে চেষ্টা করে, কিন্তু সফল হয় কেবল যদি মাঝখানে নজরদারি ভাঙেনি — অর্থাৎ অন্য কেউ ওই অংশে লেখেনি (মাঝে context switch-এর মতো ঘটনাও নজর ভাঙতে পারে)। stxr একটি status register-এ 0 (সফল) বা 1 (ব্যর্থ) লেখে; ব্যর্থ হলে প্রোগ্রাম আবার শুরু থেকে চেষ্টা করে।

retry:
    ldaxr  w1, [x0]        // w1 = *x0 (acquire), start watching x0
    cmp    w1, w2          // equal to expected (w2)?
    b.ne   fail            // no: give up, w1 holds the current value
    stlxr  w4, w3, [x0]    // try *x0 = w3 (release); w4 = 0 ok, 1 failed
    cbnz   w4, retry       // watch was broken -> try again

দুটি পার্থক্য মনে রাখুন। প্রথমত, stxr “বিনা কারণে” ব্যর্থ হতে পারে, এমনকি মান না বদলালেও; তাই C11/C++-এ আছে compare_exchange_weak (মাঝে মাঝে মিথ্যা ব্যর্থতা মেনে নেয়, লুপের ভেতরে দ্রুত) আর compare_exchange_strong (মিথ্যা ব্যর্থতা নেই)। দ্বিতীয়ত, ARMv8.1-এর LSE (Large System Extensions) থেকে ARM-এও একক instruction আছে — cas, ldadd, swp — কারণ অনেক core-এর সার্ভারে LL/SC-এর লুপ বারবার ব্যর্থ হতে পারে।

CAS দিয়ে lock আর যেকোনো atomic হালনাগাদ

#include <stdatomic.h>
static atomic_int L = 0;                   /* 0 = free, 1 = held */

void lock(void) {
    int expected = 0;
    while (!atomic_compare_exchange_weak(&L, &expected, 1))
        expected = 0;     /* on failure, expected was overwritten with L */
}
void unlock(void) { atomic_store(&L, 0); }

/* CAS loop: atomically keep the maximum ever seen */
void update_max(atomic_int *m, int v) {
    int cur = atomic_load(m);
    while (cur < v && !atomic_compare_exchange_weak(m, &cur, v))
        ;                 /* cur now holds the fresh value; re-check */
}

দ্বিতীয় ফাংশনটি CAS-এর আসল শক্তি দেখায়: পড়া → নতুন মান হিসাব → CAS দিয়ে লেখার চেষ্টা → মাঝে কেউ বদলে থাকলে আবার শুরু — এই ধাঁচে যেকোনো হালনাগাদ অবিভাজ্য করা যায়। Lock-free stack আর queue এভাবেই বানানো হয়। তবে একটি ফাঁদ আছে: মান A থেকে B হয়ে আবার A হলে CAS টের পায় না (ABA সমস্যা)। এটি আর lock-free নকশা পর্ব ২৯-এ।

৪ · Fetch-and-add আর ticket lock — টোকেন নিয়ে লাইনে দাঁড়ানো

Fetch-and-add (FAA) একটি ঠিকানায় একটি সংখ্যা যোগ করে আর যোগের আগের মান ফেরত দেয় — অবিভাজ্যভাবে। x86-এ এটি lock xadd. পর্ব ১৫-এর lost update-এর সবচেয়ে সরাসরি সমাধান এটিই: counter++-এর load-add-store তিন ধাপ হার্ডওয়্যার একটি ধাপে করে দেয়।

static atomic_uint next_ticket = 0;   /* the token machine */
static atomic_uint now_serving = 0;   /* the display board */

void lock(void) {
    unsigned my = atomic_fetch_add(&next_ticket, 1);   /* take a token */
    while (atomic_load(&now_serving) != my)
        ;                                                /* wait for my number */
}
void unlock(void) {
    atomic_fetch_add(&now_serving, 1);   /* call the next token */
}

তিনটি থ্রেড A, B, C একটি ticket lock নিয়ে কাজ করছে — নম্বর আর পর্দা ধাপে ধাপে দেখুন:

1lock:   my = fetch_add(&next_ticket, 1);2        while (now_serving != my) pause;3        /* critical section */4unlock: now_serving++;   // only the holder

প্রমাণ: mutual exclusion, FIFO আর bounded waiting

• অনন্য টোকেন: fetch_add অবিভাজ্য, তাই প্রতিটি কল আলাদা মান পায়, আর মানগুলো কল হওয়ার ক্রমে বাড়ে।
• Mutual exclusion: ভেতরে থাকার শর্ত now_serving == my. যেকোনো মুহূর্তে now_serving একটিই সংখ্যা, আর সেই নম্বরের টোকেন একজনেরই। now_serving বদলায় শুধু ভেতরের থ্রেডের unlock-এ। ∎
• FIFO আর bounded waiting: now_serving একবারে ১ করে বাড়ে, তাই টোকেন t-ধারী ঢোকে ঠিক t − (তার আসার সময়ের now_serving) জন বেরোনোর পরে। একসাথে n থ্রেড থাকলে এই সংখ্যা সর্বোচ্চ n − ১. ∎
• সংখ্যা ঘুরে গেলে? unsigned 2³²-এ পৌঁছে 0-তে ফেরে, কিন্তু তুলনা শুধু সমতার, তাই একসাথে 2³²-এর কম থ্রেড অপেক্ষা করলে কোনো সমস্যা নেই।

ticket lock-এর দুটি দুর্বলতাও আছে। সব অপেক্ষারত core একই now_serving পড়ে, তাই প্রতিটি unlock সবার cache-এর কপি বাতিল করে (অংশ ৬)। আর ন্যায্যতার উল্টো পিঠ: পরের টোকেনধারী থ্রেডটি যদি সেই মুহূর্তে CPU-তে না থাকে (scheduler সরিয়ে দিয়েছে), তবে lock খালি থাকলেও কেউ ঢুকতে পারে না — পেছনের সবাই অপেক্ষা করে। অংশ ৬-এর পরীক্ষায় এটি সত্যিই দেখা যাবে।

৫ · Atomic variable — C11, C++ আর Java-তে

প্রতিদিনের কোডে assembly লিখতে হয় না। ভাষাগুলো atomic variable দেয়: একটি সাধারণ ভ্যারিয়েবলের মতো দেখতে, কিন্তু তার প্রতিটি পড়া, লেখা আর হালনাগাদ অবিভাজ্য, আর compiler সেগুলো সরিয়ে বা মিশিয়ে ফেলে না। C11-এ <stdatomic.h> আর _Atomic কীওয়ার্ড (atomic_int হলো _Atomic int), C++11-এ std::atomic<T>, Java 5 (২০০৪) থেকে java.util.concurrent.atomic.

পর্ব ১৫-এর lost update আবার দেখি, এবার ৪টি থ্রেডে। প্রত্যেকে ১০ লাখবার যোগ করে — একবার সাধারণ int-এ, একবার atomic_fetch_add দিয়ে:

#include <pthread.h>
#include <stdatomic.h>
#include <stdio.h>
#define T 4                          /* threads */
#define N 1000000                    /* increments per thread */
static int plain = 0;                /* ordinary int: shared, unprotected */
static atomic_int counter = 0;       /* C11 atomic int */
static void *inc_plain(void *arg) {
    (void)arg;
    for (int i = 0; i < N; i++) plain++;                    /* load, add, store */
    return NULL;
}
static void *inc_atomic(void *arg) {
    (void)arg;
    for (int i = 0; i < N; i++) atomic_fetch_add(&counter, 1);  /* one RMW */
    return NULL;
}
static void run(void *(*fn)(void *)) {
    pthread_t t[T];
    for (int i = 0; i < T; i++) pthread_create(&t[i], NULL, fn, NULL);
    for (int i = 0; i < T; i++) pthread_join(t[i], NULL);
}
int main(void) {
    run(inc_plain);
    run(inc_atomic);
    printf("expected        : %d\n", T * N);
    printf("plain int       : %d\n", plain);
    printf("atomic_fetch_add: %d\n", atomic_load(&counter));
    return 0;
}

expected        : 4000000
plain int       : 1346132
atomic_fetch_add: 4000000

#include <atomic>
std::atomic<int> hits{0};
hits.fetch_add(1, std::memory_order_relaxed);   // a counter needs no ordering
int seen = hits.load();                         // default: seq_cst

std::atomic<bool> busy{false};
bool expected = false;
if (busy.compare_exchange_strong(expected, true)) { /* we got it */ }
static_assert(std::atomic<long>::is_always_lock_free);   // C++17

import java.util.concurrent.atomic.*;

AtomicInteger hits = new AtomicInteger();
hits.incrementAndGet();                 // atomic ++
hits.compareAndSet(5, 0);               // CAS: if 5 then 0
LongAdder fast = new LongAdder();       // many writers: spread over cells
fast.increment();
long total = fast.sum();

#include <windows.h>
volatile LONG hits = 0;
InterlockedIncrement(&hits);                         /* lock xadd on x86 */
LONG old = InterlockedCompareExchange(&hits, 0, 5);  /* if hits == 5 then 0 */

Atomic জাদু নয়, খরচ আছে। একই cache line-এ অনেক core একসাথে atomic যোগ করলে line-টি core থেকে core-এ ঘুরে বেড়ায়, আর প্রতিটি যোগ শত শত cycle নিতে পারে। তাই Linux kernel-এর পরিসংখ্যান-গণনা প্রায়ই per-CPU counter: প্রতিটি CPU নিজের ঘরে যোগ করে, পড়ার সময় সব ঘর যোগ হয়।

৬ · Spinlock — কখন ঘোরা ভালো, কখন ঘুমানো

এতক্ষণের TAS, CAS আর ticket lock — সবাই spinlock: lock না পেলে থ্রেড ঘুমায় না, লুপে ঘুরে বারবার দেখে। বিকল্প হলো ঘুমানো: kernel-কে জানিয়ে রাখা, lock খুললে যেন জাগিয়ে দেয় (পর্ব ২৪-এর mutex আর semaphore). কোনটি ভালো, তা নির্ভর করে অপেক্ষা কতক্ষণ, তার ওপর।

একটি সহজ হিসাব: ঘুমিয়ে জাগার খরচ মোটামুটি দুটি context switch (ধরা যাক C). অপেক্ষা যদি C-এর চেয়ে কম হয়, ঘোরাই সস্তা। অজানা হলে একটি প্রচলিত কৌশল — প্রায় C সময় পর্যন্ত ঘুরে তারপর ঘুমানো। প্রমাণ করা যায়, এতে মোট খরচ সবচেয়ে ভালো সিদ্ধান্তের দ্বিগুণের বেশি কখনো হয় না। অনেক আধুনিক lock — যেমন Linux kernel-এর mutex, বা glibc-র adaptive mutex (PTHREAD_MUTEX_ADAPTIVE_NP) — ঠিক এভাবেই একটু ঘুরে তারপর ঘুমায়।

এবার TAS lock আর ticket lock দুটিই আসল কোডে, ২টি থ্রেড, প্রত্যেকে ১০ লাখবার lock নিয়ে একটি counter বাড়ায়। pause হলো x86-এর একটি ইঙ্গিত-instruction (নিচে ব্যাখ্যা); __builtin_ia32_pause GCC/Clang-এ শুধু x86-এ চলে:

#include <pthread.h>
#include <stdatomic.h>
#include <stdio.h>
#include <time.h>
#define T 2
#define N 1000000
static atomic_flag flag = ATOMIC_FLAG_INIT;            /* TAS lock */
static atomic_uint next_ticket = 0, now_serving = 0;   /* ticket lock */
static long counter;                                   /* protected by the lock */
static int ticket_mode;
static void relax(void) { __builtin_ia32_pause(); }    /* x86 "pause" hint */
static void lock(void) {
    if (!ticket_mode) { while (atomic_flag_test_and_set(&flag)) relax(); return; }
    unsigned me = atomic_fetch_add(&next_ticket, 1);   /* take a token */
    while (atomic_load(&now_serving) != me) relax();   /* wait for my number */
}
static void unlock(void) {
    if (!ticket_mode) atomic_flag_clear(&flag);
    else atomic_fetch_add(&now_serving, 1);            /* call the next token */
}
static void *work(void *a) {
    (void)a;
    for (int i = 0; i < N; i++) { lock(); counter++; unlock(); }
    return NULL;
}
static void run(const char *name) {
    pthread_t t[T]; struct timespec s, e; counter = 0;
    clock_gettime(CLOCK_MONOTONIC, &s);
    for (int i = 0; i < T; i++) pthread_create(&t[i], NULL, work, NULL);
    for (int i = 0; i < T; i++) pthread_join(t[i], NULL);
    clock_gettime(CLOCK_MONOTONIC, &e);
    double ms = (e.tv_sec - s.tv_sec) * 1e3 + (e.tv_nsec - s.tv_nsec) / 1e6;
    printf("%-6s lock: counter = %ld (expected %d), %.0f ms\n", name, counter, T * N, ms);
}
int main(void) { run("TAS"); ticket_mode = 1; run("ticket"); return 0; }

TAS    lock: counter = 2000000 (expected 2000000), 24 ms
ticket lock: counter = 2000000 (expected 2000000), 34 ms

Cache line-এর টানাটানি — MESI আর test-and-test-and-set

পর্ব ৪-এ দেখেছেন, multicore-এ cache coherence নিশ্চিত করে যে একই ঠিকানার কপিগুলো পরস্পরবিরোধী নয়। প্রচলিত protocol MESI: প্রতিটি cache line-এর অবস্থা Modified (শুধু আমার কাছে, বদলানো), Exclusive (শুধু আমার কাছে, অপরিবর্তিত), Shared (কয়েকজনের কাছে, শুধু পড়ার জন্য) বা Invalid (বাতিল)। লেখার আগে core-কে line-টির একচ্ছত্র মালিক হতে হয় — বাকিদের কপি বাতিল করিয়ে। আর TAS তো সবসময় লেখে, ফল 1 হলেও। তাই TAS-এ ঘোরা প্রতিটি core প্রতিটি চেষ্টায় line-টি কেড়ে নেয়: line একবার এই core-এ, একবার ওই core-এ — একে বলে cache-line bouncing. সমাধান test-and-test-and-set (TTAS): প্রথমে শুধু পড়ে ঘোরা, আর মান 0 দেখলে তবেই TAS.

1TAS:  while (test_and_set(&L)) ;2TTAS: for (;;) {3        while (load(L) == 1) pause;   // read-only4        if (!test_and_set(&L)) break; }5unlock: L = 0;

static atomic_int L = 0;
void lock(void) {
    unsigned delay = 1;
    for (;;) {
        while (atomic_load_explicit(&L, memory_order_relaxed))
            __builtin_ia32_pause();                 /* local, read-only spin */
        if (!atomic_exchange_explicit(&L, 1, memory_order_acquire))
            return;                                 /* got it */
        for (unsigned i = 0; i < delay; i++)        /* lost the race: back off */
            __builtin_ia32_pause();
        if (delay < 1024) delay *= 2;               /* exponential, with a cap */
    }
}
void unlock(void) { atomic_store_explicit(&L, 0, memory_order_release); }

Exponential backoff: হেরে গেলে কিছুক্ষণ অপেক্ষা, আর প্রতিবার হারলে অপেক্ষা দ্বিগুণ (একটি সীমা পর্যন্ত) — Ethernet-এর সংঘর্ষ সামলানোর একই বুদ্ধি। এতে একসাথে TAS করা core কমে। আর pause (Pentium 4-এর SSE2-এর সময় এসেছে; encoding rep nop, তাই পুরোনো CPU-তে এটি সাধারণ nop) CPU-কে বলে “এটি একটি spin-loop”: CPU লুপটি ধীরে চালায়, বিদ্যুৎ কম খরচ করে, hyper-threading-এর সঙ্গী থ্রেডকে বেশি সুযোগ দেয়, আর lock খোলার মুহূর্তে লুপ থেকে বেরোনোর সময় memory-order-এর জটিলতায় যে বড় খরচ হয়, তা এড়ায়। একটি pause কত cycle নেয়, তা প্রজন্মভেদে অনেক আলাদা (Intel-এর Skylake-এর সার্ভার সংস্করণ থেকে আগের চেয়ে বহু গুণ বেশি), তাই backoff-এর সময় “কতবার pause” দিয়ে মাপা portable নয়। ARM-এ সমতুল্য ইঙ্গিত yield, আর অপেক্ষার জন্য wfe.

৭ · Linux kernel-এর spinlock — spin_lock_irqsave থেকে qspinlock

User-space-এ spinlock সাবধানে ব্যবহার্য, কিন্তু kernel-এ এটি প্রধান হাতিয়ার — কারণ kernel জানে কে কোন CPU-তে চলছে, আর preemption নিজেই বন্ধ করতে পারে। Linux-এ spin_lock(&l) প্রথমে নিজের CPU-তে preemption বন্ধ করে (যাতে holder-কে scheduler সরিয়ে না দেয়), তারপর lock নেয়। Interrupt handler-ও একই ডেটা ছুঁলে আরেকটি বিপদ: process-এর কোড lock ধরে আছে, এমন সময় সেই CPU-তেই interrupt এল, handler-ও একই lock চাইল — handler ঘোরে, অথচ holder ওই CPU-তেই আটকে, interrupt শেষ না হলে চলতে পারবে না। Deadlock, একটিমাত্র CPU-তে। তাই আছে spin_lock_irqsave: নিজের CPU-র interrupt বন্ধ করে, আগের অবস্থা flags-এ রেখে, তারপর lock নেয়।

static DEFINE_SPINLOCK(stats_lock);      /* shared with the IRQ handler */

void update_stats(struct my_dev *dev, unsigned int len)
{
    unsigned long flags;

    spin_lock_irqsave(&stats_lock, flags);   /* local IRQs off + take lock */
    dev->rx_packets++;
    dev->rx_bytes += len;                    /* short, never sleeps */
    spin_unlock_irqrestore(&stats_lock, flags);  /* lock off, IRQ state back */
}

Kernel-এর নিয়ম কঠোর: spinlock ধরে থাকা অবস্থায় ঘুমানো যাবে না — kmalloc(GFP_KERNEL), copy_from_user বা mutex নেওয়ার মতো কাজ, যা ঘুমাতে পারে, নিষেধ (debug kernel-এ “BUG: sleeping function called from invalid context” দেখায়)। Critical section হবে ছোট।

Ticket থেকে qspinlock — MCS-এর ধারণা

Linux ২০০৮ সালে (2.6.25) পুরোনো TAS-ধাঁচের spinlock বদলে ticket spinlock আনে — ন্যায্যতার জন্য। কিন্তু অনেক core-এর মেশিনে সব অপেক্ষারত CPU একই শব্দে ঘোরায় প্রতিটি unlock-এ সবার cache-এ বার্তা যায়। এর তাত্ত্বিক সমাধান আগেই ছিল: ১৯৯১ সালে Mellor-Crummey আর Scott-এর MCS lock. প্রতিটি অপেক্ষারত থ্রেড নিজের একটি ছোট node নিয়ে সারিতে দাঁড়ায় (lock-এর tail-এ একটি atomic exchange দিয়ে), আর ঘোরে নিজের node-এর flag-এ। Holder বেরোনোর সময় শুধু পরের জনের flag বদলায় — একটি বার্তা, একটি core:

lock(L, me):
    me->next = NULL;  me->locked = 1;
    prev = atomic_exchange(&L->tail, me);     // join the queue at the end
    if (prev != NULL) {
        prev->next = me;                       // tell the one ahead of me
        while (me->locked) pause;              // spin on MY OWN flag
    }
unlock(L, me):
    if (me->next == NULL) {
        if (CAS(&L->tail, me, NULL)) return;   // nobody behind me
        while (me->next == NULL) pause;        // someone is joining right now
    }
    me->next->locked = 0;                      // wake exactly one waiter

সমস্যা ছিল আকার: kernel-এর অগণিত struct-এ spinlock মাত্র ৪ বাইট, আর MCS-এর node-এর জন্য পয়েন্টার লাগে। ২০১৫ সালে Linux 4.2-এ x86-এ এল qspinlock (মূল কাজ Waiman Long-এর), যা MCS-এর ধারণা ৪ বাইটে ঢুকিয়েছে: একটি “locked” বাইট, একটি “pending” bit, আর একটি tail অংশ, যেখানে পয়েন্টারের বদলে CPU নম্বর লেখা থাকে (প্রতিটি CPU-র জন্য আগে থেকে বানানো কয়েকটি MCS node আছে)। কেউ অপেক্ষা না করলে lock নেওয়া একটি CAS মাত্র; দ্বিতীয়জন pending bit দিয়ে কাছেই ঘোরে; তৃতীয়জন থেকে সবাই MCS সারিতে, নিজের node-এ।

অন্য OS-এ একই ধারণা: Windows kernel-এ KeAcquireSpinLock CPU-র IRQL বাড়িয়ে DISPATCH_LEVEL-এ নেয় (ফলে ওই CPU-তে thread scheduling থামে), আর অনেক core-এর জন্য আছে in-stack queued spinlock — MCS-এর মতো। macOS/iOS-এ user-space-এর OSSpinLock ২০১৬ সালে বাতিল ঘোষিত হয়ে os_unfair_lock এসেছে (কারণ ভাবনার প্রশ্ন ৪-এ)।

৮ · Memory ordering — sequential consistency, x86-TSO আর store buffer

১৯৭৯ সালে Leslie Lamport sequential consistency (SC) সংজ্ঞায়িত করেন: একটি multiprocessor-এর যেকোনো রানের ফল এমন হবে যেন সব প্রসেসরের সব কাজ একটি ক্রমে একের পর এক ঘটেছে, আর সেই ক্রমে প্রতিটি প্রসেসরের নিজের কাজগুলো তার প্রোগ্রামের ক্রমেই আছে। এটি আমাদের স্বাভাবিক ধারণা — “থ্রেডগুলো পালা করে মেশানো”। কোন ক্রম ভাঙা অনুমোদিত, সেই নিয়মকে বলে একটি memory ordering মডেল (memory model).

মডেল যাচাইয়ের ছোট পরীক্ষাকে বলে litmus test. সবচেয়ে বিখ্যাতটি store buffering (SB): শুরুতে x = y = 0.

Thread 1            Thread 2
x = 1;              y = 1;
r1 = y;             r2 = x;
/* Is r1 == 0 && r2 == 0 possible? */

SC-তে অসম্ভব — প্রমাণ: চারটি কাজের একটি একক ক্রম ধরুন, যা দুই থ্রেডের প্রোগ্রাম-ক্রম মানে। সেই ক্রমের শেষ কাজটি অবশ্যই একটি load, কারণ প্রতিটি থ্রেডে store আগে, load পরে। ধরা যাক শেষ কাজটি r1 = y. তাহলে Thread 2-এর y = 1 তার আগেই ঘটেছে (সেটি Thread 2-এর load-এর আগে, যা শেষ কাজের আগে), তাই r1 = 1. শেষ কাজটি r2 = x হলে একইভাবে r2 = 1. অর্থাৎ অন্তত একটি 1. ∎ SC-তে সম্ভাব্য ফল শুধু (0, 1), (1, 0) আর (1, 1).

x86-TSO — store buffer

x86 SC নয়। এর মডেলকে বলে x86-TSO (Total Store Order), যা ২০০৯–১০ সালে Peter Sewell, Scott Owens ও সহকর্মীরা আনুষ্ঠানিকভাবে লিখেছিলেন। মূল কথা: প্রতিটি core-এর একটি নিজস্ব FIFO store buffer. Store প্রথমে সেখানে যায়, পরে কোনো এক সময় মেমরিতে (cache-এ) নামে। Load প্রথমে নিজের store buffer দেখে (নিজের লেখা নিজে সঙ্গে সঙ্গে দেখে), না পেলে মেমরি থেকে পড়ে। ফল: একটি পরের load আগের store-কে (ভিন্ন ঠিকানায়) ছাড়িয়ে যেতে পারে — x86-এ অনুমোদিত reordering কার্যত এই একটিই। Store-store, load-load আর load-store-এর ক্রম রক্ষা হয়।

1CPU 0:  x = 1;2CPU 0:  r1 = y;3CPU 1:  y = 1;4CPU 1:  r2 = x;5fix: store; mfence; load  (both CPUs)

এবার নিজে চালিয়ে দেখুন। দুটি থ্রেড একসাথে শুরু করে প্রতি পরীক্ষায় একজোড়া নতুন x, y (দুটিই 0) ব্যবহার করে — মোট এক লাখ পরীক্ষা, প্রথমবার relaxed atomic দিয়ে (কোনো ordering নেই), দ্বিতীয়বার store আর load-এর মাঝে একটি seq_cst fence দিয়ে:

#include <pthread.h>
#include <stdatomic.h>
#include <stdint.h>
#include <stdio.h>
#define N 100000                         /* trials per mode */
static atomic_int x[2][N], y[2][N];      /* fresh zeros for every trial */
static int r1[2][N], r2[2][N];
static atomic_int arrive;                /* tiny start barrier */
static int m;                            /* mode 0 = relaxed, 1 = seq_cst fence */
static void *side(void *arg) {           /* side 0: x=1; r1=y   side 1: y=1; r2=x */
    int me = (int)(intptr_t)arg;
    atomic_int *mine = me ? y[m] : x[m], *other = me ? x[m] : y[m];
    int *r = me ? r2[m] : r1[m];
    for (int i = 0; i < N; i++) {
        atomic_fetch_add(&arrive, 1);                       /* both start together */
        while (atomic_load(&arrive) < 2 * (i + 1)) __builtin_ia32_pause();
        atomic_store_explicit(&mine[i], 1, memory_order_relaxed);      /* store */
        if (m) atomic_thread_fence(memory_order_seq_cst);              /* fence */
        r[i] = atomic_load_explicit(&other[i], memory_order_relaxed);  /* load  */
    }
    return NULL;
}
int main(void) {
    for (m = 0; m < 2; m++) {
        pthread_t a, b; int both0 = 0;
        atomic_store(&arrive, 0);
        pthread_create(&a, NULL, side, (void *)0); pthread_create(&b, NULL, side, (void *)1);
        pthread_join(a, NULL); pthread_join(b, NULL);
        for (int i = 0; i < N; i++) both0 += (r1[m][i] == 0 && r2[m][i] == 0);
        printf("%s: r1 == 0 && r2 == 0 in %d of %d trials\n", m ? "seq_cst fence" : "relaxed      ", both0, N);
    }
    return 0;
}

relaxed      : r1 == 0 && r2 == 0 in 3079 of 100000 trials
seq_cst fence: r1 == 0 && r2 == 0 in 0 of 100000 trials

অন্য প্রসেসর আরও ঢিলা

তাই x86 ল্যাপটপে “চলছে” এমন lock-ছাড়া কোড ARM ফোনে বা ক্লাউড সার্ভারে ভাঙতে পারে। সমাধান কখনো প্রসেসর-নির্দিষ্ট fence হাতে বসানো নয় — ভাষার memory model অনুযায়ী লেখা, পরের অংশের মতো।

৯ · Acquire, release আর volatile-এর ভুল ধারণা

পূর্ণ fence দামি, আর সবসময় দরকারও নেই। সবচেয়ে প্রচলিত দরকার হলো message passing: একটি থ্রেড ডেটা তৈরি করে একটি flag তোলে, আরেকটি flag দেখে ডেটা পড়ে। এর জন্য যথেষ্ট দুটি একমুখী বাধা:

• Release store: এর আগের কোনো পড়া-লেখা এর পরে সরতে পারবে না। “সব গুছিয়ে তারপর flag তুলি।”
• Acquire load: এর পরের কোনো পড়া-লেখা এর আগে সরতে পারবে না। “flag দেখার পরেই ডেটা ছুঁই।”

int data;                          /* ordinary, non-atomic */
atomic_int ready = 0;

/* producer thread */
data = 42;
atomic_store_explicit(&ready, 1, memory_order_release);   /* publish */

/* consumer thread */
while (atomic_load_explicit(&ready, memory_order_acquire) == 0)
    ;                                                      /* wait */
printf("%d\n", data);              /* guaranteed to print 42 */

Consumer-এর acquire load যদি producer-এর release store-এর লেখা মান (1) পড়ে, তবে দুটির মধ্যে একটি happens-before সম্পর্ক তৈরি হয় — তাই data = 42 নিশ্চিতভাবে দেখা যাবে, আর data-তে কোনো data race নেই। Lock-ও আসলে এটিই: lock নেওয়া একটি acquire, ছাড়া একটি release, তাই একজনের critical section-এর সব লেখা পরের জন দেখে। x86-এ acquire load আর release store সাধারণ mov-ই (TSO এমনিতেই এগুলো রক্ষা করে — বাধা দিতে হয় শুধু compiler-কে); ARMv8-এ এদের জন্য আলাদা instruction ldar আর stlr. relaxed রাখুন শুধু সেখানে, যেখানে ক্রম লাগে না — যেমন একটি পরিসংখ্যান counter, যা শেষে join-এর পরে পড়া হবে।

১০ · AI-এর যুগে — atomic, lock আর memory order-এর কোডে AI

Lock-ছাড়া কোড, নিজের spinlock বা memory order নিয়ে AI খুব আত্মবিশ্বাসী উত্তর দেয়। সমস্যা হলো, এই কোডের বাগ x86 ল্যাপটপে প্রায় কখনো দেখা দেয় না — দেখা দেয় ARM সার্ভারে, বেশি load-এ, বা মাসে একবার। AI-এর সাধারণ ভুল:

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

• প্রতিটি shared ভ্যারিয়েবল হয় atomic, নয় একটি নির্দিষ্ট lock দিয়ে রক্ষিত; কোথাও volatile-কে synchronization হিসেবে ব্যবহার করা হয়নি
• প্রতিটি relaxed/acquire/release-এর পক্ষে নিজে যুক্তি দিতে পারি, বা নিশ্চিত না হলে ডিফল্ট seq_cst রেখেছি
• -fsanitize=thread দিয়ে, আর -O0 ও -O2 দুই ভাবে বারবার চালিয়েছি
• সম্ভব হলে ARM মেশিনেও (Apple M-series, Raspberry Pi 4/5, বা ARM ক্লাউড সার্ভার) পরীক্ষা করেছি — শুধু x86-এ নয়
• নিজের spinlock হলে core-এর চেয়ে বেশি থ্রেড দিয়ে load test করেছি, আর ভেবে দেখেছি সাধারণ mutex কেন যথেষ্ট নয়
• Kernel বা CPU-সংক্রান্ত দাবি (সংস্করণ, instruction-এর আচরণ) kernel-এর Documentation বা CPU manual-এর সাথে মিলিয়েছি