Atomics ও Lock-Free Programming — CAS দিয়ে lock ছাড়াই ডেটা স্ট্রাকচার

আগে এটা বুঝি

operating-systems/futex-and-lock-implementation লেসনে আমরা একটা পুরো mutex hand-লিখেছিলাম — একটা atomic_int state, আর একটা futex() syscall যা শুধু contention হলে ডাকা হয়। সেই লেসনের কেন্দ্রীয় building block ছিল একটা single hardware instruction: lock cmpxchg (x86) বা LL/SC (ARM) — compare-and-swap।

আজকের প্রশ্নটা এক ধাপ ভিন্ন দিকে যায়। মুটেক্স মানে — যদি lock না পাওয়া যায়, অপেক্ষা করো (spin করো, বা ঘুমাও)। এই “অপেক্ষা করা” ধারণাটাই বাদ দিলে কী হয়? একটা ডেটা স্ট্রাকচার কি বানানো সম্ভব যেখানে কোনো thread কখনো lock ধরে রাখার কারণে অন্য কাউকে ব্লক করে না — এমনকি যদি সেই thread মাঝপথে descheduled হয়ে যায়, বা crash করে?

উত্তর হ্যাঁ, আর সেই একই CAS instruction দিয়েই এটা সম্ভব — কিন্তু ভিন্নভাবে ব্যবহার করে। Mutex-এ CAS ব্যবহার হয় একটা lock-flag সেট করতে (যা fail করলে thread block করে)। আজকের লেসনে CAS ব্যবহার হবে সরাসরি ডেটা স্ট্রাকচার নিজেই আপডেট করতে, একটা loop-এ retry করে, কখনো block না করে। এটাই lock-free programming-এর কেন্দ্রীয় কৌশল।

কিন্তু এই শক্তির একটা দাম আছে — একটা genuinely subtle bug class যেটা শুধু lock-free কোডে দেখা যায়, আর যেটার নাম নিজেই তার প্রকৃতি বহন করে: ABA problem। এই লেসনের শেষে আমরা সরাসরি এই সমস্যার মুখোমুখি হব, আর দেখব কেন এটা এই মডিউলের নিজস্ব “Lock-free Queue” প্রজেক্টের কেন্দ্রীয় চ্যালেঞ্জ।

মূল ধারণা

Compare-And-Swap — নির্ভুল সংজ্ঞা

futex লেসনে CAS-এর একটা সংক্ষিপ্ত পরিচয় হয়েছিল। আজ এটাকে পুরোপুরি নির্ভুলভাবে সংজ্ঞায়িত করা দরকার, কারণ আজকের পুরো আলোচনা এই একটা অপারেশনের উপর দাঁড়াবে।

CAS(location, expected, desired) — একটা একক, অবিভাজ্য (atomic) hardware অপারেশন যা তিনটা কাজ করে: ১. location-এর বর্তমান মান পড়ে, ২. যদি সেই মান expected-এর সমান হয়, location-এ desired লিখে দেয়, আর সফলতা report করে, ৩. যদি সমান না হয়, কিছুই লেখে না, আর ব্যর্থতা report করে (সাধারণত location-এর প্রকৃত বর্তমান মানও ফেরত দেয়, যাতে caller আবার চেষ্টা করতে পারে না-হারানো তথ্য নিয়ে)।

গুরুত্বপূর্ণ শব্দ — অবিভাজ্য। এই তিনটা ধাপের মাঝে কোনো অন্য thread ঢুকে সেই location বদলাতে পারে না — hardware এটা নিশ্চিত করে (futex লেসনের cache-coherence-ভিত্তিক ব্যাখ্যা এখানে অক্ষত থাকে: lock prefix চলাকালীন সেই cache line-এর exclusive মালিকানা সাময়িকভাবে একটা core দখল করে রাখে)।

C++11-এ:

#include <atomic>

std::atomic<int> loc{10};
int expected = 10;
int desired  = 20;

bool success = loc.compare_exchange_strong(expected, desired);
/* success == true হলে: loc এখন 20, expected অপরিবর্তিত (10)  */
/* success == false হলে: loc-এর মান 10 ছিল না; expected এখন loc-এর *প্রকৃত* মান দিয়ে আপডেট হয়ে গেছে */

লক্ষ করুন expected pass by reference — ব্যর্থ হলে compiler এটাকে location-এর প্রকৃত মান দিয়ে overwrite করে দেয়, ঠিক এই কারণে যে একটা CAS-loop-এ পরের চেষ্টার জন্য এই তথ্য দরকার (নিচে দেখা যাবে)।

`_strong` বনাম `_weak`

loc.compare_exchange_weak(expected, desired);

weak সংস্করণ spuriously fail করতে পারে — অর্থাৎ, এমনকি যদি loc == expected সত্যিই true হয়, এটা মাঝেমধ্যে false রিটার্ন করতে পারে, কোনো প্রকৃত conflict ছাড়াই। এটা কোনো বাগ না — এটা ARM-জাতীয় LL/SC-ভিত্তিক architecture-এর একটা সৎ প্রতিফলন (futex লেসনের LL/SC আলোচনা মনে করুন): ldrex/strex জোড়ায় মাঝখানে কোনো অসম্পর্কিত cache event (একটা interrupt, এমনকি একটা ভিন্ন cache line-এর eviction) reservation ভেঙে দিতে পারে, strex ব্যর্থ হয় যদিও memory-র মান আসলে বদলায়নি। strong ভেতরে ভেতরে নিজেই একটা ছোট loop চালিয়ে এই spurious ব্যর্থতা লুকিয়ে ফেলে (retry করে, যতক্ষণ না প্রকৃত mismatch বা প্রকৃত সাফল্য হয়)।

নিয়ম: যদি আপনার কোড ইতিমধ্যে একটা loop-এ থাকে (যেমন এই লেসনের সব উদাহরণ), weak ব্যবহার করুন — spurious failure শুধু loop-টাকে একবার বেশি ঘোরাবে, কোনো ক্ষতি নেই, আর ARM-এ সামান্য দ্রুততর (double-loop এড়ানো যায়)। যদি CAS একবারই চালানো হচ্ছে, loop-এর বাইরে, strong ব্যবহার করুন।

CAS কেন “universal” — সংক্ষেপে

Maurice Herlihy-র ১৯৯১-এর বিখ্যাত ফলাফল: বিভিন্ন atomic primitive-এর একটা শক্তির ক্রম আছে, যাকে বলে consensus number — কতজন thread-এর মধ্যে একটা lock-free consensus protocol সেই primitive দিয়ে বানানো সম্ভব।

Primitive	Consensus number	মানে
Atomic read/write	১	শুধু single-thread-এ যথেষ্ট
Test-and-set, fetch-and-add, atomic swap	২	ঠিক দুইজন thread-এর মধ্যে consensus সম্ভব, তিনজনে না
Compare-and-swap	∞ (অসীম)	যেকোনো সংখ্যক thread-এর মধ্যে lock-free consensus সম্ভব

এই সংখ্যাটার ব্যবহারিক অর্থ: fetch_add বা test_and_set দিয়ে একটা counter নিরাপদে বাড়ানো যায় (দুইজনের বেশি thread থাকলেও, কারণ সেই সহজ অপারেশনের জন্য “কে জিতেছে” প্রশ্নটাই আসে না — সবার increment-ই সফল হয়)। কিন্তু জটিল, multi-step সিদ্ধান্ত (যেমন “এই নির্দিষ্ট নতুন node-টাকে stack-এর মাথায় বসাও, শুধু যদি stack এখনো ঠিক যেভাবে আমি শেষ দেখেছিলাম সেভাবেই থাকে”) — এই ধরনের conditional, all-or-nothing সিদ্ধান্তের জন্য CAS-এর মতো শক্তি লাগে, যা arbitrary সংখ্যক প্রতিযোগী thread-এর মধ্যেও সঠিকভাবে ঠিক করতে পারে কে “জিতেছে”।

এই লেসনের বাকি অংশের ভিত্তি এক লাইনে

CAS-এর এই সর্বজনীন ক্ষমতার কারণেই প্রায় প্রতিটা lock-free ডেটা স্ট্রাকচার (stack, queue, hash table, skip list) শেষ পর্যন্ত একটা প্যাটার্নে নেমে আসে: “বর্তমান অবস্থা পড়ো, নতুন অবস্থা গণনা করো, CAS দিয়ে বসানোর চেষ্টা করো, ব্যর্থ হলে আবার শুরু থেকে।” এই একটা প্যাটার্নই এই লেসনের বাকি সব উদাহরণের কঙ্কাল।

Progress guarantee — চারটা টায়ার

“Lock-free” শব্দটা প্রায়ই ভুলভাবে “দ্রুত” বা “instant”-এর সমার্থক ভাবা হয়। প্রকৃত সংজ্ঞাটা সম্পূর্ণ ভিন্ন কিছু নিয়ে — এটা একটা আনুষ্ঠানিক progress guarantee, গতির প্রতিশ্রুতি না।

Tier	সংজ্ঞা	ব্যর্থতার মোড
Blocking (mutex-ভিত্তিক)	একজন thread lock ধরে রেখে descheduled/crash হলে, বাকি সবাই অনির্দিষ্টকালের জন্য আটকে যেতে পারে	সবচেয়ে দুর্বল — একটা thread-এর দুর্ভাগ্য সবাইকে থামাতে পারে
Obstruction-free	একটা thread যদি কোনো বাধা ছাড়া একা চলে (অন্য thread না ছুঁলে), সসীম সময়ে শেষ করবে — কিন্তু ক্রমাগত conflict-এ সবাই বারবার retry করে কখনো এগোতে না-ও পারে (livelock)	দুর্বল গ্যারান্টি — practical use কম
Lock-free	সিস্টেম-স্তরে গ্যারান্টি: প্রতিটা ধাপে অন্তত একজন thread অগ্রগতি করছে (কেউ না কেউ CAS জিতছে) — কিন্তু কোনো নির্দিষ্ট thread চিরকাল হারতেই থাকতে পারে (তত্ত্বগতভাবে)	কেউ না কেউ এগোয়, কিন্তু “আমি” নাও এগোতে পারি
Wait-free	প্রতিটা thread একটা সসীম, bounded সংখ্যক ধাপে শেষ করবে, অন্য thread-দের আচরণ নির্বিশেষে	সবচেয়ে শক্তিশালী, কিন্তু বাস্তবায়ন করা কঠিনতম ও প্রায়ই ধীরতর

'Lock-free' মানে 'সবার জন্য দ্রুত' না -- এটাই এই লেসনের প্রথম বড় সংশোধন

Lock-free গ্যারান্টি বলে কেউ না কেউ এগোবে — এটা একটা system-wide liveness গ্যারান্টি, individual thread-এর গ্যারান্টি না। চরম contention-এ (অনেক thread একই CAS-এ বারবার প্রতিযোগিতা করছে), একটা নির্দিষ্ট হতভাগ্য thread তাত্ত্বিকভাবে বারবার হেরে যেতে পারে (যদিও বাস্তবে randomized backoff বা hardware-এর নিজস্ব fairness heuristic এটা চরম বিরল করে তোলে) — futex লেসনের misconception সেকশনে ঠিক এই কথাই বলা হয়েছিল: উচ্চ contention-এ একটা lock-free retry-loop CPU পুড়িয়ে যেতে পারে, যেখানে একটা mutex সেই থ্রেডকে ঘুম পাড়িয়ে CPU খালি করে দিত। lock-free-এর আসল সুবিধা contention কম-মাঝারি অবস্থায় (কোনো thread কখনো “সম্পূর্ণ ব্লক” হয় না, descheduling-এর কারণে কেউ বাকি সবাইকে থামাতে পারে না) — সেটা “সবসময় সবচেয়ে দ্রুত” দাবি না।

Blocking বনাম lock-free-এর আসল পার্থক্য একটা দৃশ্যে স্পষ্ট হয়: একটা mutex-ভিত্তিক stack-এ, যদি lock ধরে থাকা thread push()-এর মাঝপথে OS scheduler দ্বারা preempt হয় (বা worse, একটা বাগে infinite loop-এ আটকে যায়, বা crash করে lock ধরে রেখেই), প্রতিটা অন্য thread সেই lock-এর জন্য চিরকাল অপেক্ষা করবে — futex লেসনের “lock convoy” ধারণার চরম রূপ। একটা lock-free stack-এ এটা কাঠামোগতভাবে অসম্ভব — কোনো thread কখনো “lock ধরে রাখে না” বলে কেউ কখনো অন্য কারো descheduling-এর শিকার হয় না।

ভেতরে কী ঘটছে

Treiber Stack — একটা lock-free stack, ধাপে ধাপে

R. Kent Treiber-এর ১৯৮৬-এর ক্লাসিক algorithm — একটা singly-linked list, একটা atomic head pointer। এই algorithm-টাই futex লেসনের একদম নিচের স্তরের সরাসরি সম্প্রসারণ: সেখানে CAS একটা scalar (lock state) বদলাতে ব্যবহার হয়েছিল, এখানে সেই একই CAS একটা pointer বদলাতে ব্যবহার হবে, পুরো ডেটা স্ট্রাকচারের আকৃতি বদলে দিতে।

#include <atomic>

template <typename T>
struct LockFreeStack {
    struct Node {
        T data;
        Node* next;
    };
    std::atomic<Node*> head{nullptr};

    void push(T value) {
        Node* new_node = new Node{value, nullptr};
        Node* old_head = head.load(std::memory_order_relaxed);
        do {
            new_node->next = old_head;   /* এখনো প্রকাশিত না, শুধু প্রস্তুত করা */
        } while (!head.compare_exchange_weak(
                     old_head, new_node,
                     std::memory_order_release,   /* সফল হলে: new_node->next-সহ সব আগের write প্রকাশিত হোক */
                     std::memory_order_relaxed));  /* ব্যর্থ হলে: শুধু old_head রিফ্রেশ হোক, আর কিছু দরকার নেই */
    }

    bool pop(T& out) {
        Node* old_head = head.load(std::memory_order_acquire);
        while (old_head != nullptr) {
            if (head.compare_exchange_weak(
                    old_head, old_head->next,
                    std::memory_order_acquire,
                    std::memory_order_acquire)) {
                out = old_head->data;
                delete old_head;    /* ⚠ এই লাইনেই ABA problem-এর বীজ -- নিচে দেখুন */
                return true;
            }
            /* ব্যর্থ হলে old_head স্বয়ংক্রিয়ভাবে রিফ্রেশড, লুপ আবার চেষ্টা করবে */
        }
        return false;   /* stack খালি */
    }
};

push() -- একটা CAS-loop-এর সম্পূর্ণ decision path

new_node তৈরি, head-এর বর্তমান মান পড়াএখনো stack-এ কিছু প্রকাশিত হয়নি, শুধু local প্রস্তুতি
new_node->next = old_headনতুন node-কে পুরনো chain-এর সাথে লিঙ্ক করা, still local
CAS(head, old_head, new_node) চেষ্টাযদি এই মুহূর্তে head এখনো old_head-ই থাকে (কেউ মাঝে push/pop করেনি), সফল
সফল হলেnew_node এখন স্ট্যাকের মাথা -- push সম্পন্ন, কোনো block হয়নি, কোনো syscall না
ব্যর্থ হলে (অন্য thread মাঝে push/pop করেছে)old_head স্বয়ংক্রিয়ভাবে বর্তমান head দিয়ে আপডেট, লুপ আবার -- new_node->next আবার রিলিঙ্ক করা হয়

Memory ordering-এর যুক্তি — গত লেসনের সরাসরি প্রয়োগ

push-এর সফল CAS-এ release: এটাই নিশ্চিত করে new_node->next = old_head এবং (গুরুত্বপূর্ণ) new_node->data-এর লেখা — যা নতুন node তৈরির সময় ঘটেছিল — অন্য কোনো thread-এর pop()-এর matching acquire-এর আগেই visible হয়ে গেছে। এটা ঠিক গত লেসনের MP (message-passing) litmus test-এর কাঠামো: data লেখা → flag(এখানে head) প্রকাশ করা।
pop-এর CAS-এ acquire (উভয় সফল ও ব্যর্থ ক্ষেত্রে): সফল হলে, এটাই নিশ্চিত করে আমরা যে old_head->data/old_head->next পড়ছি, তা push করা thread-এর সব write-এর পরে ঘটছে বলে দেখা যাবে — অন্যথায় আমরা একটা আংশিকভাবে-নির্মিত node পড়ার ঝুঁকিতে থাকতাম।

কেন relaxed যথেষ্ট না -- একটা concrete পাল্টা-উদাহরণ

যদি push-এর CAS-এ memory_order_relaxed ব্যবহার করা হতো (release-এর বদলে), একটা দ্বিতীয় thread pop() দিয়ে head-এর নতুন মান দেখে ফেলতে পারত, কিন্তু hardware/compiler reordering-এর কারণে new_node->data-এর write তখনো তার কাছে visible না-ও হতে পারত (ঠিক গত লেসনের MP litmus test-এর মতো, ARM/weak-memory হার্ডওয়্যারে) — ফলাফল একটা garbage value পড়া, কোনো crash বা error ছাড়াই। এটাই কারণ প্রতিটা “একটা atomic variable অন্য ডেটার দৃশ্যমানতা নিয়ন্ত্রণ করছে” পরিস্থিতিতে (গত লেসনের নিয়ম) release/acquire-এর কম কিছু দিয়ে চলে না।

ABA Problem — যখন CAS “সফল” হয় কিন্তু ভুলভাবে

উপরের pop()-এ একটা মন্তব্য ছিল — delete old_head লাইনটাই সমস্যার উৎস। বিস্তারিত দেখা যাক।

দৃশ্যকল্প: stack-এ ক্রমানুসারে A → B → C (head = A)। Thread 1 pop() করতে চায়।

সময়   Thread 1                              Thread 2 (একই সময়ে, সমান্তরালে)
────  ────────────────────────────────────  ─────────────────────────────────
 t0   pop() শুরু
      old_head = head.load()  → A
      next = old_head->next   → B
      (এখনো CAS ডাকেনি -- এখানেই preempt/delay হয়)
 t1                                          pop() করে -- head: A→B, A ফ্রি হয়
 t2                                          pop() করে -- head: B→C, B ফ্রি হয়
 t3                                          push(A_new) করে -- নতুন node allocate,
                                              কিন্তু allocator পুরনো A-র ঠিকানাই
                                              পুনর্ব্যবহার করে (freed মেমরি reuse)!
                                              head এখন আবার "A" (same address),
                                              কিন্তু ->next = C (নতুন chain: A→C)
 t4   CAS(head, expected=A, desired=B)       
      head-এর মান এই মুহূর্তে "A" (ঠিকানা মিলে যায়!)
      CAS **সফল** হয় -- head এখন B
 t5   কিন্তু "B" ইতিমধ্যে t2-তে free হয়ে গেছে!
      Thread 1 এখন একটা freed/dangling
      node-কে stack-এর head বানিয়ে দিয়েছে --
      মেমরি করাপশন

ABA problem -- Thread 1-এর CAS সফল হয় কিন্তু stack-এর প্রকৃত গঠন সম্পূর্ণ বদলে গেছে মাঝখানে।

Thread 1-এর CAS ঠিকানার সমতা (head == A) দেখে “কিছুই বদলায়নি” ধরে নিয়েছিল — কিন্তু বাস্তবে stack সম্পূর্ণ পুনর্গঠিত হয়ে গেছে (A free হয়েছে, B free হয়েছে, একটা নতুন node একই ঠিকানা A-তে বরাদ্দ হয়েছে)। CAS হার্ডওয়্যার-স্তরে শুধু বিট প্যাটার্ন তুলনা করে — তার কাছে “ঠিকানা A থেকে B হয়ে আবার A” আর “ঠিকানা A কখনো বদলায়নি” — এই দুইটা সম্পূর্ণ একই রকম দেখায়। এই নাম থেকেই সমস্যার নাম: মান A-থেকে B-তে, তারপর আবার A-তে ফিরে আসা — মাঝের পরিবর্তনটা CAS সম্পূর্ণ মিস করে যায়।

কেন এটা শুধু 'পুরনো ডেটা পড়া' না, বরং memory corruption

লক্ষ করুন t5-এ ফলাফলটা শুধু ভুল মান পড়া না — এটা stack-এর গঠনই ভেঙে ফেলেছে। Thread 1 head-কে B-তে সেট করে দিয়েছে, কিন্তু B ইতিমধ্যে freed — পরের যেকোনো pop()/push() একটা dangling pointer dereference করবে। এটাই কারণ ABA problem-কে “শুধু একটা সূক্ষ্ম সংখ্যাগত ভুল” না, বরং use-after-free-এর একটা সরাসরি পথ হিসেবে দেখা উচিত — একটা genuinely বিপজ্জনক bug class, ঠিক এই লেসনের objective-এ বলা “বাস্তব bug” কথাটার পূর্ণ অর্থে।

সমাধান ১ — Tagged pointer (versioned CAS)

মূল ধারণা: pointer-এর সাথে একটা monotonically বাড়তে-থাকা counter/tag জুড়ে দিন, আর CAS-টা pointer এবং tag — দুটো একসাথে, একটা wider atomic value হিসেবে — তুলনা করুক।

struct TaggedPtr {
    Node* ptr;
    uint64_t tag;   /* প্রতিটা সফল CAS-এ +1 */
};
std::atomic<TaggedPtr> head;   /* 128-বিট CAS দরকার (DWCAS -- x86-এ cmpxchg16b) */

এখন t4-এ Thread 1-এর CAS-এ expected-এর ঠিকানা A, tag ৫ ধরে চেক করবে — কিন্তু t3-এর পরে বাস্তব মান ঠিকানা A, tag ৭ (কারণ t1 আর t2-র pop, t3-র push প্রতিটাই tag বাড়িয়েছে)। ঠিকানা মিললেও tag মেলে না — CAS ব্যর্থ হয়, Thread 1 বুঝে ফেলে “কিছু একটা মাঝে বদলে গেছে”, নতুন করে head পড়ে আবার চেষ্টা করে। এটাই Windows-এর InterlockedPushEntrySList কীভাবে ABA সমাধান করে — একটা built-in tagged/versioned double-word CAS দিয়ে, OS-স্তরে।

সমাধান ২ — Hazard pointer (memory reclamation বিলম্বিত করা)

Tagged pointer সমস্যাটা “detect” করে (ভুল CAS আটকায়), কিন্তু আসল মূল কারণ — freed memory পুনর্ব্যবহার হওয়া — সেটাই যদি এড়ানো যায়? Hazard pointer কৌশল ঠিক এটাই করে: প্রতিটা thread pop() করার আগে ঘোষণা করে “আমি এই ঠিকানাটা এই মুহূর্তে পড়ছি” (একটা shared, thread-visible “hazard” array-তে লিখে)। কোনো thread কোনো node free করার আগে সেই hazard array চেক করে — যদি কোনো অন্য thread এখনো সেই node-কে “hazardous” ঘোষণা করে রেখেছে, free করা বিলম্বিত হয় (একটা retirement list-এ রাখা হয়, পরে safe হলে free করা হয়)।

এর মানে t2-তে B freed হতেই পারে না যদি Thread 1 এখনো তার hazard pointer-এ B-কে (বা A-কে) ঘোষণা করে রাখে — memory reuse ঘটতে দেওয়া হয় না যতক্ষণ না নিশ্চিত হওয়া যায় কেউ সেটা পড়ছে না। এটা tagged pointer-এর চেয়ে বেশি জটিল implementation, কিন্তু 128-বিট atomic hardware সমর্থন (যা সব architecture-এ নেই) ছাড়াই কাজ করে, আর arbitrary-আকারের data structure-এ generalize করা সহজ।

এই মডিউলের নিজস্ব প্রজেক্ট -- Lock-free Queue

এই মডিউলের (Level 11) নিজস্ব “Lock-free Queue” প্রজেক্ট (একটা CAS-based MPSC queue) ঠিক এই ABA problem-কে সরাসরি মুখোমুখি হওয়ার জন্য ডিজাইন করা — এই লেসনের stack-এর চেয়ে জটিল একটা কাঠামোয় (একাধিক producer, তাই একাধিক দিক থেকে একই সমস্যা ঘটতে পারে)। এখানে যা শিখলেন — সমস্যার প্রকৃতি, আর দুইটা সমাধান-পরিবারের নাম ও যুক্তি — সেটাই সেই প্রজেক্টের ভিত্তি।

উদাহরণ

একটা সঠিক interleaving — কোনো ABA ছাড়া

ABA-র ভয়াবহতা বোঝার পর, একটা স্বাভাবিক, সাধারণ contention দৃশ্যও দেখা দরকার — যেখানে CAS-loop ঠিক যেভাবে ডিজাইন করা, সেভাবেই কাজ করে, কোনো ABA ছাড়াই।

stack: A → B (head = A)। দুইজন thread একসাথে pop() করতে চায়।

সময়   Thread 1                         Thread 2
────  ───────────────────────────────  ───────────────────────────────
 t0   old_head = head.load()  → A      old_head = head.load()  → A
 t1   next = A->next  → B               next = A->next  → B
 t2   CAS(head, A, B) -- সফল            CAS(head, A, B) -- head এখন B,
      (head এখন B)                      কিন্তু expected এখনো A ধরে চেষ্টা
                                         করছে -- head আর A নেই, ব্যর্থ!
 t3   out = A->data, delete A           CAS ব্যর্থ -- old_head স্বয়ংক্রিয়
      pop() সফল, return true            রিফ্রেশ হয়ে যায় B (নতুন head)
 t4                                     লুপ আবার: next = B->next → nullptr
                                         CAS(head, B, nullptr) -- সফল
                                         out = B->data, pop() সফল

লক্ষ করুন — কোনো block হয়নি। Thread 2-র প্রথম CAS ব্যর্থ হয়েছে (Thread 1 জিতেছে), কিন্তু Thread 2 অপেক্ষা করেনি — সাথে সাথে নতুন তথ্য নিয়ে আবার চেষ্টা করেছে, আর দ্বিতীয় চেষ্টায় সফল হয়েছে। এটাই lock-free-এর প্রতিশ্রুতির বাস্তব রূপ: দুইজনই শেষমেশ সফল হয়েছে, কারো জন্য কোনো blocking/syscall লাগেনি, আর কোনো মুহূর্তেই stack-এর গঠন অসামঞ্জস্যপূর্ণ ছিল না (এখানে কোনো node freed memory-তে পুনরায় push হয়নি, তাই ABA-র সুযোগ নেই)।

এই দৃশ্য বনাম ABA দৃশ্যের পার্থক্যটাই গুরুত্বপূর্ণ: ABA ঘটার জন্য শুধু contention যথেষ্ট না — memory পুনর্ব্যবহার (free করে আবার allocate) আর তার সাথে একটা নির্দিষ্ট, সরু timing দরকার। এই কারণেই ABA production-এ প্রায়ই মাসের পর মাস ধরা পড়ে না — সাধারণ contention প্রতিদিন ঘটে (আর নিরাপদে সামলানো হয়, ঠিক উপরের মতো), কিন্তু ABA-র নির্দিষ্ট allocator-timing সমাপতন বিরল।

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

EXPERIMENT

Lock-free stack সঠিকতা যাচাই -- বহু thread, কোনো lost/duplicate item নেই

Linux/macOS, g++ (C++11+), -pthread· ২০ মিনিট

// stack_test.cpp -- g++ -O2 -pthread -std=c++17 -o stack_test stack_test.cpp
#include <atomic>
#include <thread>
#include <vector>
#include <cstdio>
#include <unordered_set>
#include <mutex>

template <typename T>
struct LockFreeStack {
    struct Node { T data; Node* next; };
    std::atomic<Node*> head{nullptr};

    void push(T value) {
        Node* n = new Node{value, nullptr};
        Node* old_head = head.load(std::memory_order_relaxed);
        do { n->next = old_head; }
        while (!head.compare_exchange_weak(old_head, n,
                   std::memory_order_release, std::memory_order_relaxed));
    }
    bool pop(T& out) {
        Node* old_head = head.load(std::memory_order_acquire);
        while (old_head) {
            if (head.compare_exchange_weak(old_head, old_head->next,
                    std::memory_order_acquire, std::memory_order_acquire)) {
                out = old_head->data;
                delete old_head;
                return true;
            }
        }
        return false;
    }
};

#define NTHREADS   8
#define PER_THREAD 100000

LockFreeStack<long> stack;
std::atomic<long> total_popped{0};
std::mutex seen_mutex;
std::unordered_set<long> seen;   /* duplicate/lost detect করতে */

void producer(int id) {
    for (long i = 0; i \< PER_THREAD; i++)
        stack.push(id * (long)PER_THREAD + i);   /* প্রতিটা value globally unique */
}
void consumer() {
    long v;
    while (total_popped.load() \< (long)NTHREADS * PER_THREAD) {
        if (stack.pop(v)) {
            total_popped.fetch_add(1);
            std::lock_guard<std::mutex> lk(seen_mutex);   /* শুধু verification-এর জন্য, algorithm-এর অংশ না */
            if (!seen.insert(v).second)
                printf("DUPLICATE ধরা পড়েছে: %ld\n", v);
        }
    }
}

int main() {
    std::vector<std::thread> producers, consumers;
    for (int i = 0; i \< NTHREADS; i++) producers.emplace_back(producer, i);
    for (int i = 0; i \< NTHREADS; i++) consumers.emplace_back(consumer);
    for (auto& t : producers) t.join();
    for (auto& t : consumers) t.join();

    printf("মোট push হয়েছে: %d, মোট pop হয়েছে: %ld, unique দেখা গেছে: %zu\n",
           NTHREADS * PER_THREAD, total_popped.load(), seen.size());
    printf("%s\n", (long)seen.size() == (long)NTHREADS * PER_THREAD
                    ? "সঠিক -- কোনো lost বা duplicate item নেই"
                    : "*** ব্যর্থ ***");
    return 0;
}

g++ -O2 -pthread -std=c++17 -o stack_test stack_test.cpp && ./stack_test

প্রত্যাশিত output:

মোট push হয়েছে: 800000, মোট pop হয়েছে: 800000, unique দেখা গেছে: 800000
সঠিক -- কোনো lost বা duplicate item নেই

৮টা producer, ৮টা consumer, ৮ লক্ষ item, কোনো lock, কোনো lost বা duplicate নেই। এটাই lock-free correctness-এর প্রত্যক্ষ প্রমাণ — এই নির্দিষ্ট বেঞ্চমার্কে ABA ধরা পড়েনি কারণ এখানে delete করা memory প্রায় সবসময় দ্রুত reuse হয় না এই ছোট স্কেলে সেই নির্দিষ্ট সরু window-এ পড়ার মতো — এটাই ঠিক আগের সেকশনের সতর্কতা: ABA-র অনুপস্থিতি একটা টেস্টে প্রমাণ করে না algorithm ABA-প্রতিরোধী, শুধু বলে এই নির্দিষ্ট রান-এ window মিস হয়েছে।

এটা কী প্রমাণ করে

একটা সঠিকভাবে লেখা CAS-loop বহু thread-এর concurrent push/pop-এও কোনো lost update বা duplicate ছাড়া সঠিক ফলাফল দেয় -- কোনো lock ছাড়াই।

EXPERIMENT

Contention-এর প্রভাব -- CAS retry সংখ্যা মাপা

Linux/macOS, g++· ১৫ মিনিট

উপরের push()-এ একটা global atomic counter যোগ করুন যা প্রতিটা ব্যর্থ CAS চেষ্টায় বাড়ে:

std::atomic<long> retry_count{0};

void push(T value) {
    Node* n = new Node{value, nullptr};
    Node* old_head = head.load(std::memory_order_relaxed);
    while (!head.compare_exchange_weak(old_head, n,
               std::memory_order_release, std::memory_order_relaxed)) {
        n->next = old_head;
        retry_count.fetch_add(1, std::memory_order_relaxed);
    }
}

NTHREADS ১, ২, ৪, ৮, ১৬ করে চালিয়ে retry_count / মোট push সংখ্যা অনুপাত দেখুন। প্রত্যাশিত ধরনের প্যাটার্ন:

থ্রেড   গড় retry/push
   1         0.00
   2         0.31
   4         0.89
   8         2.14
  16         5.87

thread সংখ্যা বাড়ার সাথে গড় retry বাড়ে — ঠিক futex লেসনের contention-cliff experiment-এর মতোই একটা প্যাটার্ন, যদিও প্রক্রিয়াটা সম্পূর্ণ ভিন্ন (সেখানে thread block/wake হচ্ছিল, এখানে thread CPU-তেই থেকে বারবার retry করছে)। এটাই এই লেসনের misconception সেকশনের সবচেয়ে গুরুত্বপূর্ণ দাবির পরিমাপযোগ্য প্রমাণ — lock-free মানে বিনামূল্যে না, উচ্চ contention-এ এটাও ব্যয়বহুল হতে পারে, শুধু ভিন্নভাবে (CPU cycle পোড়ানো, syscall না)।

এটা কী প্রমাণ করে

thread সংখ্যা বাড়ার সাথে CAS retry (ব্যর্থ চেষ্টা) সংখ্যা বাড়ে -- lock-free-এর 'lock-free মানে বিনামূল্যে' ভুল ধারণার সরাসরি খণ্ডন, futex লেসনের contention-cliff-এর সমান্তরাল।

নিজে বানান

BUILD IT

Tagged pointer দিয়ে ABA-প্রতিরোধী stack

C++ · ●●●●●

উপরের LockFreeStack-এ ABA প্রবণতা যাচাই করার জন্য একটা ইচ্ছাকৃত delay ইনজেক্ট করুন pop()-এর CAS-এর ঠিক আগে
একটা কাস্টম allocator বানান যা freed node দ্রুত reuse করে (ABA window বড় করতে, শিক্ষার উদ্দেশ্যে)
দেখান এই কম্বিনেশনে stack করাপ্ট হয় (একটা assertion বা crash দিয়ে ধরা)
head-কে TaggedPtr{Node*, uint64_t}-এ পাল্টান, std::atomic<TaggedPtr> ব্যবহার করে (double-word CAS)
একই stress test আবার চালিয়ে নিশ্চিত করুন করাপশন আর ঘটছে না

/* aba_fix.cpp -- g++ -O2 -pthread -std=c++17 -o aba_fix aba_fix.cpp */
#include <atomic>
#include <cstdint>

template <typename T>
struct ABASafeStack {
    struct Node { T data; Node* next; };

    struct TaggedPtr {
        Node* ptr;
        uint64_t tag;
        bool operator==(const TaggedPtr& o) const { return ptr == o.ptr && tag == o.tag; }
    };
    static_assert(sizeof(TaggedPtr) == 16, "double-word CAS দরকার");

    std::atomic<TaggedPtr> head{TaggedPtr{nullptr, 0}};

    void push(T value) {
        Node* n = new Node{value, nullptr};
        TaggedPtr old_head = head.load(std::memory_order_relaxed);
        TaggedPtr new_head;
        do {
            n->next = old_head.ptr;
            new_head = TaggedPtr{n, old_head.tag + 1};   /* প্রতিটা চেষ্টায় tag বাড়ে */
        } while (!head.compare_exchange_weak(old_head, new_head,
                     std::memory_order_release, std::memory_order_relaxed));
    }

    bool pop(T& out) {
        TaggedPtr old_head = head.load(std::memory_order_acquire);
        while (old_head.ptr) {
            TaggedPtr new_head{old_head.ptr->next, old_head.tag + 1};
            if (head.compare_exchange_weak(old_head, new_head,
                    std::memory_order_acquire, std::memory_order_acquire)) {
                out = old_head.ptr->data;
                delete old_head.ptr;
                return true;
            }
        }
        return false;
    }
};

static_assert(sizeof(TaggedPtr) == 16, ...) নিশ্চিত করে pointer (৮ বাইট) আর tag (৮ বাইট) মিলিয়ে ঠিক ১৬ বাইট (১২৮ বিট) — x86-64-এ cmpxchg16b (DWCAS — Double-Width CAS) instruction দিয়ে এই পুরো struct-টা একটা একক atomic অপারেশনে compare/swap করা সম্ভব, std::atomic<TaggedPtr>::is_lock_free() সাধারণত true রিটার্ন করবে যদি compiler DWCAS সমর্থিত target-এ compile করে।

এখন উপরের ABA দৃশ্যকল্প (t0–t5) আবার ট্রেস করুন: t3-এ নতুন push node একই ঠিকানা A-তে বসলেও, তার tag পূর্বের push/pop সিরিজের কারণে বেড়ে গেছে (প্রতিটা push/pop tag+1 করে) — t4-এ Thread 1-এর CAS-এ expected-এর ঠিকানা A, tag ৫ ধরে চেক করবে, বাস্তব মান ঠিকানা A, tag ৮ (উদাহরণস্বরূপ) — ঠিকানা মিললেও tag মেলে না, CAS ব্যর্থ হয়, memory corruption ঘটে না।

সীমাবদ্ধতা যা সৎভাবে বলা দরকার: ৬৪-বিট tag ব্যবহারিকভাবে কখনো overflow করে “wrap around” করে পুরনো মানে ফিরবে না (২⁶⁴ push/pop লাগবে) — তাই এই সমাধান কার্যত সম্পূর্ণ নিরাপদ। কিন্তু এটা cmpxchg16b-জাতীয় hardware সমর্থনের উপর নির্ভরশীল (সব architecture-এ নেই, আর কিছু পুরনো/embedded target-এ অনুপস্থিত) — যেখানে DWCAS নেই, hazard pointer-জাতীয় সমাধানই একমাত্র পথ।

বাস্তব সিস্টেমে

Lock-free ডেটা স্ট্রাকচার যেখানে সত্যিই ব্যবহৃত হয়

Treiber stack নিজেই — ঠিক এই লেসনের algorithm। ১৯৮৬-এ IBM-এর technical report হিসেবে প্রকাশিত, আজও memory allocator-এর ভেতরে free-list বা thread-pool-এর task queue-র মতো জায়গায় সরাসরি ব্যবহৃত হয়, বিশেষত যেখানে LIFO order গ্রহণযোগ্য।

Michael-Scott queue। java.util.concurrent.ConcurrentLinkedQueue-এর ভিত্তি — এই লেসনের stack-এর একই মূলনীতি (CAS-loop, linked node), কিন্তু FIFO order-এর জন্য head আর tail দুইটা আলাদা atomic pointer সামলাতে হয়, যা যথেষ্ট বেশি জটিল কিন্তু একই ABA সমস্যার মুখোমুখি হয়।

Windows SLIST — InterlockedPushEntrySList/InterlockedPopEntrySList। OS-স্তরে একটা built-in lock-free stack, tagged pointer-ভিত্তিক ABA সুরক্ষা সরাসরি hardware/OS-স্তরে বিল্ট-ইন — এই লেসনের “সমাধান ১”-এর একটা প্রোডাকশন-গ্রেড বাস্তবায়ন।

Facebook Folly-র hazard pointer library (folly::hazptr)। এই লেসনের “সমাধান ২”-এর একটা industrial-strength, ব্যাপকভাবে ব্যবহৃত বাস্তবায়ন — বড় স্কেলের C++ সার্ভিসে lock-free ডেটা স্ট্রাকচারের নিরাপদ memory reclamation-এর জন্য standard টুল।

Linux kernel RCU (Read-Copy-Update)। ধারণাগতভাবে সম্পর্কিত কিন্তু ভিন্ন কৌশল — memory reclamation বিলম্বিত করা একটা “grace period” পার হওয়া পর্যন্ত (সব CPU অন্তত একবার context switch না করা পর্যন্ত), hazard pointer-এর মতো explicit per-thread ঘোষণার বদলে। উভয়ই একই মূল সমস্যা সমাধান করে — “lock-free ডেটা এখনো ব্যবহৃত হতে পারে এমন memory কখন নিরাপদে free করা যায়।”

Intel TBB (Threading Building Blocks)-এর concurrent_queue/concurrent_stack। Production-grade C++ concurrency library, এই লেসনের algorithm-গুলোর ভিত্তির উপর built, কিন্তু ব্যাপক engineering (backoff strategy, memory pool integration) সহ।

LMAX Disruptor-এর lock-free ring buffer। আগের false-sharing লেসনে এই library-র padding কৌশল দেখা হয়েছিল — এর মূল sequence-tracking mechanism-ও CAS-loop-ভিত্তিক, কোনো lock ছাড়াই একাধিক producer/consumer সমন্বয় করে।

Garbage-collected ভাষায় (Java, Go) ABA-র ঝুঁকি কম, শূন্য না। GC থাকা মানে “object সত্যিকারের memory address-এ কখনো পুনর্ব্যবহার হবে না যতক্ষণ কোনো reference বেঁচে আছে” — এটা classic pointer-reuse-based ABA-কে অনেকটাই দূর করে। কিন্তু logical ABA (একই object-এর মান A→B→A হওয়া, ঠিকানা না বদলে) তখনও সম্ভব — Java-র AtomicStampedReference ক্লাস ঠিক এই কারণে বিদ্যমান, এই লেসনের tagged-pointer সমাধানের সরাসরি ভাষা-স্তরের প্রতিফলন।

যে ভুলগুলো সবাই করে

“Lock-free মানে thread কখনো spin/retry করবে না -- সত্যিকারের 'instant' অপারেশন।”

এই লেসনের সবচেয়ে গুরুত্বপূর্ণ সংশোধন, আর concept সেকশনেই আগে থেকে সতর্ক করা হয়েছে। Lock-free একটা progress guarantee — “কেউ না কেউ, বাউন্ডেড সময়ে এগোবে” — গতির প্রতিশ্রুতি না। Contention-experiment-এ দেখা গেছে thread সংখ্যা বাড়ার সাথে retry সংখ্যা বাড়ে, প্রতিটা retry মানে CPU cycle খরচ হচ্ছে কোনো দৃশ্যমান অগ্রগতি ছাড়াই সেই নির্দিষ্ট thread-এর জন্য। “Lock-free” নামের মধ্যে “free” শব্দটা lock-এর অনুপস্থিতি বোঝায় (blocking-এর কাঠামোগত ঝুঁকি নেই), “বিনামূল্যে দ্রুত” বোঝায় না।

“Lock-free কোড লেখা মানে শুধু mutex-এর জায়গায় std::atomic বসিয়ে দেওয়া -- বাকিটা একই রকম সহজ।”

সম্পূর্ণ উল্টো — lock-free কোড সঠিক প্রমাণ করা mutex-ভিত্তিক কোডের চেয়ে উল্লেখযোগ্যভাবে কঠিন। একটা mutex-এ, critical section-এর ভেতরে কোড sequentially চলে ধরে নেওয়া যায় — reasoning সহজ। একটা CAS-loop-এ, প্রতিটা লাইনের মাঝখানে অন্য thread হস্তক্ষেপ করতে পারে (এই লেসনের ABA দৃশ্যকল্পটাই তার প্রমাণ) — প্রতিটা সম্ভাব্য interleaving নিজে থেকে চিন্তা করে দেখতে হয়। এই কারণেই বাস্তবে বেশিরভাগ ইঞ্জিনিয়ার নিজে নতুন lock-free algorithm উদ্ভাবন করেন না — প্রমাণিত, ভালোভাবে-পরীক্ষিত algorithm (Treiber stack, Michael-Scott queue) ব্যবহার করেন, অথবা TBB/Folly-র মতো library-র উপর নির্ভর করেন। “নিজে থেকে একটা lock-free ডেটা স্ট্রাকচার ডিজাইন করা” একটা research-level কাজ, “mutex সরিয়ে atomic বসানো” না।

“ABA problem এড়াতে শুধু delete()-কে দেরি করে ডাকলেই (যেমন, কখনো free না করে) যথেষ্ট।”

এটা আসলে ABA-র একটা বৈধ (যদিও ব্যয়বহুল) সমাধান — যদি memory কখনো পুনর্ব্যবহার না হয় (leak করা হয়, বা garbage collector-এর হাতে ছেড়ে দেওয়া হয়), ঠিকানা কখনো পুনরাবৃত্তি হবে না, তাই classic ABA ঘটতেই পারে না। কিন্তু এটা একটা trade-off, “বিনামূল্যে সমাধান” না — দীর্ঘ-চলা প্রোগ্রামে unbounded memory growth একটা গুরুতর সমস্যা (দীর্ঘমেয়াদে OOM)। হাজার্ড পয়েন্টার/tagged pointer-এর আসল মূল্য হলো তারা memory reclaim করতে দেয়, শুধু নিরাপদ সময়ে — মেমরি অসীম বাড়তে না দিয়েই ABA এড়ানো। “কখনো free না করা” শুধু সেই ক্ষেত্রেই যুক্তিসঙ্গত যেখানে node সংখ্যা ছোট এবং bounded (যেমন একটা fixed-size object pool পুনর্ব্যবহার করা, কখনো OS-কে ফেরত না দিয়ে)।

“একটা wait-free ডেটা স্ট্রাকচার সবসময় lock-free-এর চেয়ে ভালো পছন্দ, যেহেতু এটা শক্তিশালী গ্যারান্টি দেয়।”

আনুষ্ঠানিকভাবে শক্তিশালী গ্যারান্টি সবসময় বাস্তবে ভালো পছন্দ না। Wait-free algorithm সাধারণত উল্লেখযোগ্যভাবে বেশি জটিল (প্রতিটা thread-এর জন্য bounded-step গ্যারান্টি প্রমাণ করতে প্রায়ই প্রতিটা অপারেশনে অতিরিক্ত bookkeeping/helping mechanism লাগে — অন্য thread-এর কাজ “সাহায্য করে” শেষ করে দেওয়া, নিজের কাজ শুরু করার আগে), যা গড় (average-case) latency আর memory overhead বাড়ায়। বাস্তবে বেশিরভাগ প্রোডাকশন lock-free লাইব্রেরি (TBB, Folly, java.util.concurrent) lock-free স্তরে থামে, wait-free-এ যায় না, কারণ বাস্তব workload-এ extreme starvation (একটা নির্দিষ্ট thread বারবার হারতে থাকা) practically বিরল, আর wait-free-এর অতিরিক্ত জটিলতার খরচ প্রায়ই সেই বিরল সুবিধার চেয়ে বেশি। Wait-free সত্যিই প্রয়োজনীয় হয় শুধু hard-real-time সিস্টেমে (যেমন কিছু audio-processing বা flight-control কোড) যেখানে worst-case latency-র একটা কঠোর, প্রমাণযোগ্য সীমা আইনত/নিরাপত্তাগতভাবে বাধ্যতামূলক।

বুঝেছেন কি না দেখুন

compare_exchange_weak আর compare_exchange_strong-এর মধ্যে পার্থক্য এক লাইনে বলুন, আর একটা নিয়ম দিন কখন কোনটা ব্যবহার করা উচিত।

স্মরণ

পার্থক্য: weak মাঝেমধ্যে spuriously fail করতে পারে (memory-র মান সত্যিই expected-এর সমান থাকলেও false রিটার্ন করতে পারে, বিশেষত LL/SC-ভিত্তিক architecture যেমন ARM-এ), যেখানে strong কখনো spuriously fail করে না — ভেতরে ভেতরে নিজেই retry করে সেই সম্ভাবনা লুকিয়ে ফেলে।

নিয়ম: যদি CAS ইতিমধ্যে একটা loop-এর ভেতরে থাকে (এই লেসনের সব উদাহরণ, push/pop CAS-loop) — weak ব্যবহার করুন, কারণ spurious failure শুধু loop-টাকে একবার বেশি ঘোরাবে, আর ARM-জাতীয় hardware-এ strong-এর নিজস্ব internal retry-loop-এর সাথে double-looping এড়িয়ে সামান্য দ্রুততর হবে। যদি CAS একবারই ডাকা হচ্ছে, কোনো loop-এর বাইরে (যেমন একটা one-shot initialization flag সেট করা) — strong ব্যবহার করুন, কারণ সেখানে caller-কে নিজে retry-loop লিখতে হবে না।

এই লেসনে বলা হয়েছে CAS-এর consensus number অসীম, যেখানে fetch_add (atomic increment)-এর consensus number মাত্র ২। কিন্তু futex লেসনের contention-cliff experiment-এ atomic_fetch_add ৪টা thread থেকেই নিরাপদে ব্যবহৃত হয়েছিল, কোনো সমস্যা ছাড়াই। এই দুইটা তথ্য কি একে অপরের বিরোধিতা করে?

যুক্তি

না, বিরোধিতা করে না — কারণ “consensus number কম” মানে “এই primitive দিয়ে কোনো কাজ ২ জনের বেশি thread-এ করা যায় না”, এই ভুল ব্যাখ্যা এড়ানো জরুরি।

Consensus number নির্দিষ্ট করে একটা primitive দিয়ে কতজন thread-এর মধ্যে একটা arbitrary consensus protocol (যেকোনো জটিল, multi-way সিদ্ধান্ত, যেমন “এই N জনের মধ্যে কে প্রথম পৌঁছেছে তা সবাই একমত হোক”) lock-free ভাবে বানানো সম্ভব — এটা primitive-এর একটা তাত্ত্বিক ঊর্ধ্বসীমা শক্তি পরিমাপ, “এই primitive দিয়ে কী কাজ করা নিরাপদ” তার তালিকা না।

fetch_add দিয়ে একটা counter বাড়ানো (ঠিক যা contention-cliff experiment করেছিল) সম্পূর্ণ নিরাপদ, যতজন thread থাকুক না কেন — কারণ increment একটা commutative, conflict-free অপারেশন: প্রতিটা thread-এর increment স্বাধীনভাবে সফল হতে পারে, কারো “জেতা” বা “হারা”-র প্রশ্নই নেই, hardware নিজেই সব increment-কে serialize করে সঠিক যোগফল নিশ্চিত করে। এই কাজের জন্য কোনো “কে জিতল” সিদ্ধান্তের দরকারই নেই — তাই এখানে consensus number-এর সীমাবদ্ধতা প্রাসঙ্গিকই না।

Consensus number-এর সীমাবদ্ধতা তখনই প্রকাশ পায় যখন আপনার এমন একটা কাজ দরকার যেখানে একজনের সাফল্য অন্যদের ব্যর্থতা বোঝায় — যেমন এই লেসনের push(): “শুধু আমার node-টাই head হবে, যদি stack এখনো আমি যেভাবে দেখেছিলাম সেভাবে থাকে, নাহলে আমি সম্পূর্ণ ব্যর্থ, আবার শুরু করতে হবে।” এই ধরনের conditional, all-or-nothing, arbitrary-N-thread সিদ্ধান্তের জন্যই CAS-এর অসীম consensus number দরকার — fetch_add দিয়ে এটা বানানো (৩ বা তার বেশি thread-এ) প্রমাণিতভাবে অসম্ভব।

সাধারণ শিক্ষা: সঠিক primitive বেছে নেওয়ার প্রশ্নটা “কতজন thread” না, বরং “আমার অপারেশনটা কি conflict-free (সবাই স্বাধীনভাবে সফল হতে পারে, যেমন increment), নাকি conditional (কারো সাফল্য অন্যের ব্যর্থতা মানে, যেমন ‘এই নির্দিষ্ট node-টাই head হোক’)”।

এই লেসনের pop()-এ যদি delete old_head; লাইনটা সরিয়ে দেওয়া হয় (ইচ্ছাকৃতভাবে node-গুলো কখনো free না করে, শুধু memory leak হতে দিয়ে), তাহলে কি এই stack ABA-প্রতিরোধী হয়ে যাবে? যুক্তি দিন।

প্রয়োগ

হ্যাঁ — এই নির্দিষ্ট, সরলীকৃত অর্থে, হ্যাঁ। এটাই misconception সেকশনে আলোচিত “কখনো free না করা” কৌশলের সরাসরি প্রয়োগ, আর যুক্তিটা লেসনের ABA বিশ্লেষণ থেকেই সরাসরি অনুসরণ করে।

ABA problem ঘটার জন্য দুইটা শর্ত একসাথে দরকার: (ক) একটা node free হওয়া, আর (খ) সেই একই ঠিকানায় একটা নতুন, ভিন্ন node পরে allocate হওয়া। যদি কখনো delete না করা হয়, শর্ত (ক) কখনো পূরণ হয় না — allocator কখনো সেই ঠিকানা পুনরায় বরাদ্দ করার সুযোগই পাবে না, কারণ পুরনো node-টা এখনো “in use” হিসেবে বইয়ে আছে (allocator-এর দৃষ্টিতে), যদিও logically stack থেকে সেটা সরে গেছে। ঠিকানা A চিরকাল সেই একই, মূল node-কেই নির্দেশ করবে — কখনো একটা ভিন্ন, নতুন node-কে না। তাই head-এর মান A-তে “ফিরে আসা” মানেই আক্ষরিক অর্থে “একই, অপরিবর্তিত node-এ ফিরে আসা” — যেটা আসলে কোনো সমস্যাই না, CAS-এর ধরে নেওয়া অনুমান (“যদি ঠিকানা একই থাকে, কিছু বদলায়নি”) এখানে প্রকৃতপক্ষে সত্য।

কিন্তু এটা একটা বাস্তবসম্মত সমাধান না, বেশিরভাগ প্রোডাকশন ব্যবহারে:

একটা দীর্ঘ-চলা সার্ভার প্রোসেসে (যেমন একটা web server যেটা মাসের পর মাস চলে), প্রতিটা pop() একটা node leak করলে memory usage unboundedly বাড়তে থাকবে — শেষমেশ OOM।
এই কৌশল শুধু কার্যকর যখন node সংখ্যা প্রকৃতিগতভাবে ছোট এবং bounded — যেমন একটা fixed-size object pool যেখানে node-গুলো stack-এ push/pop হতে থাকে কিন্তু কখনো OS-কে ফেরত যায় না, শুধু পুনর্ব্যবহৃত হয় stack-এর নিজস্ব free-list হিসেবে (এই ক্ষেত্রে “leak” আসলে “pool-এ ফেরত রাখা”, প্রকৃত leak না)।

সাধারণ শিক্ষা: এই প্রশ্নটা দেখায় ABA problem-এর মূল কারণ “ঠিকানা পুনরাবৃত্তি হওয়া” — memory reclamation বন্ধ করা এই কারণটা সরাসরি দূর করে, কিন্তু একটা ভিন্ন, প্রায়ই আরও গুরুতর সমস্যা (unbounded memory growth) তৈরি করে। এই কারণেই hazard pointer-এর মতো কৌশল প্রয়োজন — memory reclaim করা যায়, শুধু নিরাপদ প্রমাণিত হওয়ার পরে, “কখনো reclaim না করা”-র extreme trade-off ছাড়াই।

একটা lock-free stack (এই লেসনের) বনাম একটা futex-ভিত্তিক mutex-দিয়ে-সুরক্ষিত stack (আগের লেসনের) — একটা নির্দিষ্ট পরিস্থিতিতে কোনটা বেছে নেবেন, আর কোনটাতে? দুইটা বিপরীত পরিস্থিতি দিন, প্রতিটার জন্য যুক্তি দিন।

ডিজাইন

পরিস্থিতি ১ — একটা real-time audio-processing thread, যেখানে এই thread-কে কখনো, কোনো কারণেই, block হতে দেওয়া যাবে না (একটা missed audio buffer deadline মানে শ্রোতা একটা “click” শব্দ শুনবে)।

পছন্দ: lock-free। এই পরিস্থিতির মূল প্রয়োজনীয়তা হলো এই লেসনের progress-guarantee টেবিলের ঠিক কেন্দ্রীয় পার্থক্য — একটা futex-ভিত্তিক mutex-এ, যদি lock-ধারী thread OS scheduler দ্বারা preempt হয় (অন্য কোনো higher-priority process-এর কারণে, বা page fault-এর কারণে), audio thread অনির্দিষ্টকালের জন্য ব্লক হয়ে যেতে পারে — এমনকি যদি সেই ব্লকিং শুধু কয়েক মিলিসেকেন্ড হয়, একটা real-time audio deadline-এর জন্য সেটা বিপর্যয়কর। Lock-free stack-এ এই ঝুঁকি কাঠামোগতভাবে অনুপস্থিত — কোনো thread কখনো “lock ধরে রাখে” না, তাই কেউ কারো descheduling-এর শিকার হয় না।

পরিস্থিতি ২ — একটা সাধারণ ওয়েব সার্ভারের request queue, যেখানে contention মাঝারি-উচ্চ (শত শত worker thread), আর critical section (queue-তে item যোগ/বিয়োগ) তুলনামূলক জটিল (একাধিক ফিল্ড আপডেট, একটা invariant বজায় রাখতে হয়)।

পছন্দ: mutex-ভিত্তিক (futex)। দুইটা কারণ। প্রথমত, correctness-এর ঝুঁকি — এই লেসনের misconception সেকশন অনুযায়ী, lock-free কোড সঠিক প্রমাণ করা উল্লেখযোগ্যভাবে কঠিন, বিশেষত জটিল multi-field আপডেটে (একটা single CAS দিয়ে একাধিক field একসাথে atomically বদলানো প্রায়ই সম্ভবই না, যদি না সবগুলো এক pointer-এর পেছনে থাকে) — একটা ভুল lock-free বাস্তবায়ন একটা subtle, প্রোডাকশনে-মাসের-পর-মাস-লুকিয়ে-থাকা bug (যেমন ABA) তৈরির ঝুঁকি রাখে, যেখানে একটা mutex-ভিত্তিক সমাধান অনেক সহজে সঠিক প্রমাণ করা যায় (critical section-এর ভেতরে sequential reasoning যথেষ্ট)। দ্বিতীয়ত, futex-এর নিজস্ব ডিজাইন (আগের লেসন) ইতিমধ্যে uncontended path-কে প্রায় বিনামূল্যে করে দিয়েছে — তাই সাধারণ (কম contention মুহূর্তে) ওয়েব-সার্ভার workload-এ mutex আর lock-free-এর গতির পার্থক্য প্রায়ই নগণ্য, কিন্তু correctness-এর সরলতা বিশাল সুবিধা।

সাধারণ সিদ্ধান্ত-নীতি: lock-free বেছে নিন যখন progress guarantee নিজেই একটা hard requirement (real-time, বা একটা thread-এর ক্ষণিক descheduling সিস্টেম-ব্যাপী cascading delay তৈরি করতে পারে এমন পরিস্থিতি — যেমন kernel-এর নিজস্ব critical path)। Mutex/futex বেছে নিন যখন critical section জটিল, আর correctness-এর সরলতা speed-এর প্রান্তিক লাভের চেয়ে বেশি গুরুত্বপূর্ণ — যা বাস্তবে বেশিরভাগ সাধারণ সার্ভার/অ্যাপ্লিকেশন কোডের ক্ষেত্রে সত্য।

এই মডিউলের শুরুর driving question ছিল: “একই algorithm, একই complexity — তবু একটা ১০ গুণ দ্রুত কেন?” এই লেসনের বিষয়বস্তু (atomics, lock-free, CAS) কি সরাসরি এই প্রশ্নের একটা নতুন উদাহরণ দেয়, নাকি এই লেসনটা মূলত একটা ভিন্ন ধরনের প্রশ্নের (correctness/progress-guarantee) উত্তর দেয়?

যুক্তি

দুটোই সত্য, কিন্তু ভিন্ন অনুপাতে — এবং এই পার্থক্যটা স্পষ্ট করে বলা এই লেসনের একটা ভালো সংক্ষিপ্তসার।

এই মডিউলের আগের লেসনগুলো (false sharing, NUMA) সরাসরি driving-question-এর “একই algorithm, ভিন্ন গতি” প্যাটার্নের বিশুদ্ধ উদাহরণ — সেখানে কোনো correctness প্রশ্নই ছিল না, শুধু hardware-সচেতনতার অভাবে গতি হারানো। Contention-experiment-এ (এই লেসনে) সেই একই প্যাটার্নের একটা প্রতিধ্বনি আছে — thread সংখ্যা বাড়লে retry বাড়ে, throughput কমে — কিন্তু এখানে মূল তুলনাটা “lock-free বনাম lock-based” গতির তুলনা, “সঠিক বনাম ভুল layout” না।

কিন্তু এই লেসনের কেন্দ্রীয় অবদান আসলে ভিন্ন প্রকৃতির — এটা মূলত একটা progress-guarantee এবং correctness প্রশ্নের উত্তর: “একটা descheduled thread কি বাকি সবাইকে থামিয়ে দিতে পারে?” (progress guarantee), আর “CAS-এর ঠিকানা-ভিত্তিক তুলনা কখন প্রতারিত হতে পারে?” (ABA, correctness)। এই দুইটা প্রশ্নের কোনোটাই সরাসরি “একই algorithm দশগুণ ধীর কেন” প্যাটার্নে পড়ে না — এগুলো ভিন্ন মাত্রার প্রশ্ন: গতি না, বরং আচরণের গ্যারান্টি (কখন, কীভাবে ব্যর্থ হতে পারে)।

তবু একটা গভীর সংযোগ আছে: উভয় ধরনের প্রশ্নই একই মূল উৎস থেকে আসে — hardware-এর প্রকৃত আচরণ প্রোগ্রামারের সরল মানসিক মডেলের চেয়ে বেশি জটিল। False sharing-এ প্রোগ্রামার ভাবেন “দুইটা independent variable = independent performance”, বাস্তবতা ভিন্ন (cache line গ্রানুলারিটি)। এখানে প্রোগ্রামার ভাবতে পারেন “ঠিকানা মিলেছে = কিছু বদলায়নি”, বাস্তবতা ভিন্ন (মান পরিবর্তন হয়ে আবার একই জায়গায় ফিরে আসতে পারে)। এই পুরো মডিউলের আসল driving থিম তাই শুধু “গতি” না, বরং আরও গভীর: hardware কী প্রতিশ্রুতি দেয়, আর কী দেয় না — এবং সেই ফাঁকে ঠিক কোন ভুল ধারণাগুলো লুকিয়ে থাকে। গতি (false sharing, NUMA) আর correctness/progress (memory ordering, ABA) — দুটোই সেই একই কেন্দ্রীয় থিমের ভিন্ন প্রকাশ।

এরপর কী

Level 11-এর এই পর্যায়ের শেষে

চারটা লেসনে আমরা একটা একক থ্রেড নেমেছি — MESI coherence-এর তাত্ত্বিক টিজার থেকে শুরু করে (আগের agent-এর লেসন), সেই coherence traffic-এর বাস্তব দাম (false sharing), তারপর একটা সম্পূর্ণ ভিন্ন হার্ডওয়্যার বাস্তবতা (NUMA-র দূরত্ব), তারপর একটা সূক্ষ্মতর প্রশ্ন (memory consistency-র ক্রম), আর সবশেষে সেই সবকিছুর ভিত্তিতে দাঁড়ানো একটা পুরো programming paradigm (lock-free, CAS-ভিত্তিক)।

এই চারটা লেসন মিলিয়ে একটা বার্তা স্পষ্ট হওয়ার কথা: **“correct” কোড লেখা যথেষ্ট না মাল্টি-কোর হার্ডওয়্যারে — hardware ঠিক কী প্রতিশ্রুতি দেয় (coherence, কিন্তু consistency না, কিন্তু progress guarantee-ও না বিনামূল্যে) সেটা নির্ভুলভাবে জানাটাই পার্থক্য তৈরি করে একটা প্রোগ্রামের মধ্যে যেটা “টেস্টে কাজ করে” আর একটা প্রোগ্রামের মধ্যে যেটা প্রমাণিতভাবে সঠিক, যেকোনো architecture-এ, যেকোনো contention-এ।

মডিউলের বাকি অংশ (অন্য agent-দের লেসনে) এবার performance-এর আরেকটা মাত্রায় যাবে — branch prediction, speculative execution, SIMD, আর শেষমেশ GPU-র সম্পূর্ণ ভিন্ন parallelism মডেল। কিন্তু এই লেসনের CAS, memory_order, আর progress-guarantee-র ভাষা — এগুলো সেখানেও ফিরে আসবে, কারণ প্রতিটা concurrent primitive, প্রতিটা parallel algorithm, শেষ পর্যন্ত এই একই মৌলিক প্রশ্নে নেমে আসে: hardware কবে, কাকে, কী দেখায়।

Atomics ও Lock-Free Programming — CAS দিয়ে lock ছাড়াই ডেটা স্ট্রাকচার

এই লেসন শেষে আপনি পারবেন

আগে যা বোঝা থাকা দরকার

আগে এটা বুঝি

মূল ধারণা

Compare-And-Swap — নির্ভুল সংজ্ঞা

`_strong` বনাম `_weak`

CAS কেন “universal” — সংক্ষেপে

Progress guarantee — চারটা টায়ার

ভেতরে কী ঘটছে

Treiber Stack — একটা lock-free stack, ধাপে ধাপে

Memory ordering-এর যুক্তি — গত লেসনের সরাসরি প্রয়োগ

ABA Problem — যখন CAS “সফল” হয় কিন্তু ভুলভাবে

সমাধান ১ — Tagged pointer (versioned CAS)

সমাধান ২ — Hazard pointer (memory reclamation বিলম্বিত করা)

উদাহরণ

একটা সঠিক interleaving — কোনো ABA ছাড়া

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

Lock-free stack সঠিকতা যাচাই -- বহু thread, কোনো lost/duplicate item নেই

Contention-এর প্রভাব -- CAS retry সংখ্যা মাপা

নিজে বানান

Tagged pointer দিয়ে ABA-প্রতিরোধী stack

বাস্তব সিস্টেমে

Lock-free ডেটা স্ট্রাকচার যেখানে সত্যিই ব্যবহৃত হয়

যে ভুলগুলো সবাই করে

বুঝেছেন কি না দেখুন

এরপর কী

Level 11-এর এই পর্যায়ের শেষে

আরও পড়ুন

এই লেসন শেষে আপনি পারবেন

আগে যা বোঝা থাকা দরকার

◔আগে এটা বুঝিWhy this matters

◆মূল ধারণাCore concept

Compare-And-Swap — নির্ভুল সংজ্ঞা

_strong বনাম _weak

CAS কেন “universal” — সংক্ষেপে

Progress guarantee — চারটা টায়ার

⚙ভেতরে কী ঘটছেUnder the hood

Treiber Stack — একটা lock-free stack, ধাপে ধাপে

Memory ordering-এর যুক্তি — গত লেসনের সরাসরি প্রয়োগ

ABA Problem — যখন CAS “সফল” হয় কিন্তু ভুলভাবে

সমাধান ১ — Tagged pointer (versioned CAS)

সমাধান ২ — Hazard pointer (memory reclamation বিলম্বিত করা)

▶উদাহরণExample

একটা সঠিক interleaving — কোনো ABA ছাড়া

⌘নিজে চালিয়ে দেখুনExperiment

Lock-free stack সঠিকতা যাচাই -- বহু thread, কোনো lost/duplicate item নেই

Contention-এর প্রভাব -- CAS retry সংখ্যা মাপা

⚒নিজে বানানBuild it yourself

Tagged pointer দিয়ে ABA-প্রতিরোধী stack

◉বাস্তব সিস্টেমেReal-world usage

Lock-free ডেটা স্ট্রাকচার যেখানে সত্যিই ব্যবহৃত হয়

⚠যে ভুলগুলো সবাই করেMisconceptions

?বুঝেছেন কি না দেখুনCheck understanding

→এরপর কীNext step

Level 11-এর এই পর্যায়ের শেষে

আরও পড়ুন

আগে এটা বুঝি

মূল ধারণা

`_strong` বনাম `_weak`

ভেতরে কী ঘটছে

উদাহরণ

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

নিজে বানান

বাস্তব সিস্টেমে

যে ভুলগুলো সবাই করে

বুঝেছেন কি না দেখুন

এরপর কী