Futex — কীভাবে একটা mutex আসলে বানানো হয়

Lost wakeup race — একটা classic synchronization bug, আর এই check ছাড়া futex ব্যবহারযোগ্যই হতো না।

কল্পনা করুন val check ছাড়া একটা সরলীকৃত FUTEX_WAIT:

void naive_wait(atomic_int *state) {
    /* এখানে কোনো check নেই — সরাসরি ঘুমাতে যাচ্ছে */
    syscall(SYS_futex, state, FUTEX_WAIT, NULL, NULL, 0);
}

এখন race scenario:

Thread A (lock করতে চায়):          Thread B (unlock করছে):

state পড়ে — মান LOCKED_WAITERS
                                     state = UNLOCKED (exchange)
                                     FUTEX_WAKE ডাকে — কিন্তু
                                     A এখনো ঘুমায়ইনি, তাই এই
                                     wake "হারিয়ে যায়" — কেউ
                                     শুনছে না তখনও
FUTEX_WAIT ডাকে — এখন ঘুমাতে যাচ্ছে,
কিন্তু lock ইতিমধ্যে UNLOCKED!
                                     
এখন A চিরকাল ঘুমিয়ে থাকবে — যদিও
lock আসলে মুক্ত, কেউ তাকে জাগাবে না

সমস্যাটা: “state পড়া” আর “ঘুমাতে যাওয়া” — এই দুইটা ধাপের মাঝখানে একটা window আছে, আর সেই window-এ যদি unlock() ঘটে যায় এবং FUTEX_WAKE ডাকা হয়ে যায় (কিন্তু তখনও A ঘুমায়নি, তাই wake-এর কিছু “শোনার” নেই), সেই wake signal হারিয়ে যায়। A পরে ঘুমাতে গেলে, তাকে জাগানোর কেউ নেই।

val check কীভাবে এটা রোধ করে:

syscall(SYS_futex, state, FUTEX_WAIT, LOCKED_WAITERS, NULL, NULL, 0);

Kernel atomically — একটাই ধাপে, kernel-এর নিজস্ব lock নিয়ে — *state == LOCKED_WAITERS যাচাই করে এবং thread-কে wait queue-তে যোগ করে। যদি unlock() ইতিমধ্যে state-কে UNLOCKED করে ফেলে থাকে, kernel এই check-এ সেটা ধরে ফেলবে আর FUTEX_WAIT সাথে সাথে ফিরে আসবে (EAGAIN দিয়ে), thread কখনো ঘুমাবেই না — lost wakeup সম্পূর্ণ এড়ানো গেল।

সাধারণ নীতি: “check যে অবস্থা এখনো বৈধ” আর “সেই অবস্থার উপর ভিত্তি করে ব্লক করা” — এই দুইটা ধাপ atomically একসাথে হতেই হবে। গত-গত লেসনে condition variable-এর pthread_cond_wait() একই কারণে mutex ও sleep-কে একটা atomic operation-এ বান্ডিল করে — এটা একই সমস্যার একই সমাধান, ভিন্ন primitive-এ।

এটা সম্পূর্ণ প্রত্যাশিত, আর এটাই futex ডিজাইনের সাফল্যের প্রমাণ — বেশিরভাগ lock/unlock uncontended (fast path), শুধু খুব বিরল ২টা ক্ষেত্রে contention ঘটেছে।

তিনটা প্রশংসনীয় ব্যাখ্যা:

১. Single-threaded প্রোগ্রাম, বা কার্যত single-threaded। যদি প্রোগ্রামে মাত্র একটা thread lock ব্যবহার করছে (অন্য thread-রা সেই lock কখনো ছোঁয় না), তাহলে কখনো কোনো contention ঘটবেই না — তাত্ত্বিকভাবে futex syscall সংখ্যা শূন্য হওয়া উচিত।

২. দুইটা futex call কেন তাহলে আছে? সবচেয়ে সম্ভাব্য ব্যাখ্যা: প্রোগ্রাম শুরুতে বা শেষে একবার contention ঘটেছে — হয়তো pthread_create() করার ঠিক পরে, main thread আর নতুন thread একটা init lock-এ সংক্ষিপ্তভাবে প্রতিদ্বন্দ্বিতা করেছে (startup race), অথবা shutdown-এর সময় একটা cleanup lock-এ।

৩. Thread-রা মূলত ভিন্ন সময়ে কাজ করছে (temporal separation)। যদি একাধিক thread থাকে কিন্তু তারা lock-টা এমনভাবে ব্যবহার করে যে বাস্তবে কখনোই একসাথে সেটার জন্য প্রতিযোগিতা করে না (যেমন, একটা thread শুধু সকালে কাজ করে, আরেকটা রাতে — একটা কৃত্রিম উদাহরণ, কিন্তু নীতিটা বাস্তব: যদি critical section এত ছোট ও বিরল হয় যে দুইটা thread কখনো একই মুহূর্তে সেখানে পৌঁছায় না), তাহলে গাণিতিকভাবে বহু lock ব্যবহারেও প্রায় শূন্য contention সম্ভব।

যা এই সংখ্যা থেকে বলা যায়:

• এই lock bottleneck নয় — futex-এর slow path প্রায় কখনো সক্রিয় হয়নি, তাই এই lock নিয়ে performance optimization করার কোনো প্রয়োজন নেই
• Contention-cliff experiment-এর বিপরীত পরিস্থিতি — সেখানে হাজার হাজার futex call দেখা গিয়েছিল কারণ সত্যিকারের heavy contention ছিল

ব্যবহারিক প্রয়োগ: যদি একটা প্রোগ্রামের perf/strace profile দেখায় নির্দিষ্ট একটা lock-এ প্রচুর futex call (contended), সেটাই optimization-এর লক্ষ্য — lock granularity কমানো, বা critical section ছোট করা, বা lock-free ডেটা structure বিবেচনা করা। কিন্তু যদি futex call সংখ্যা কম হয়, সেই lock নিয়ে চিন্তা করার দরকার নেই — আরো গুরুত্বপূর্ণ জায়গায় সময় দেওয়া উচিত।

এই সমস্যায় মূল ধারণা — একটা কেন্দ্রীয় lock/counter সরিয়ে দেওয়া, contention-এর উৎসটাই বাদ দেওয়া, শুধু faster lock খোঁজা নয়।

সমাধান ১ — একটা atomic counter (lock-ই বাদ)।

atomic_long counter = 0;
atomic_fetch_add_explicit(&counter, 1, memory_order_relaxed);

Mutex-এর বদলে সরাসরি একটা lock xadd (atomic add) — কোনো futex syscall কখনোই লাগবে না, কারণ hardware-স্তরেই এই operation atomic। কিন্তু উচ্চ contention-এ (অনেক core একই cache line-এ লিখছে) এখনো cache-line bouncing-এর খরচ থেকে যায় — গত misconception-এ যা আলোচনা করা হয়েছিল।

সমাধান ২ — Per-thread (বা per-CPU) counter, শেষে merge।

#define NCPU 64
atomic_long per_cpu_counter[NCPU];   /* cache-line-aligned! */

void increment(void) {
    int cpu = sched_getcpu();
    atomic_fetch_add_explicit(&per_cpu_counter[cpu], 1, memory_order_relaxed);
}

long total(void) {
    long sum = 0;
    for (int i = 0; i < NCPU; i++)
        sum += atomic_load(&per_cpu_counter[i]);
    return sum;
}

এখন প্রতিটা CPU তার নিজের cache line-এ লিখছে — কোনো cross-core contention নেই increment-এ। শুধু total() ডাকলে (যা কম ঘন ঘন হয়, হয়তো শুধু monitoring-এর জন্য প্রতি কয়েক সেকেন্ডে) সব যোগ করা হয়।

গুরুত্বপূর্ণ সতর্কতা — false sharing। per_cpu_counter array-টা যদি প্রতিটা long একে অপরের ঠিক পাশে থাকে, একই cache line-এ একাধিক CPU-র counter পড়তে পারে — তখন ভিন্ন counter হলেও, একই cache line-এ লেখালেখি করলে সেই line-টাই bounce করবে (false sharing)। সমাধান: প্রতিটা counter-কে alignas(64) (সাধারণ cache line size) দিয়ে আলাদা করা।

struct alignas(64) padded_counter { atomic_long value; };
struct padded_counter per_cpu_counter[NCPU];

সমাধান ৩ — Sharded counter with dynamic sizing (production-grade)।

Java-র LongAdder, বা Go-র sharded counter library-গুলো এই ধারণাটা আরো উন্নত করে — thread সংখ্যা অনুযায়ী shard সংখ্যা dynamically বাড়ায়/কমায়, high contention-এ বেশি shard, low contention-এ কম (memory সাশ্রয়ের জন্য)।

কখন কোনটা:

মূল শিক্ষা: এই লেসনের futex optimization “একটা lock-কে দ্রুততর করা” — কিন্তু সবচেয়ে বড় performance জয় প্রায়ই আসে “lock-এর দরকারই নেই এমন নকশা” থেকে। Contention কমানোর সবচেয়ে কার্যকর উপায় প্রায়ই আর্কিটেকচার বদলানো, primitive optimize করা নয়।

কারণ CAS-এর “compare” অংশটা একটা optimistic concurrency প্যাটার্ন সম্ভব করে যা অন্য simpler atomic instruction-এ করা যায় না — এটা একমাত্র সাধারণ primitive যা দিয়ে “শুধু যদি এখনো আমার ধারণা করা মানই থাকে, তবেই বদলাও” — এই যুক্তি প্রকাশ করা যায়।

lock add আর lock xchg-এর সীমাবদ্ধতা:

lock add [counter], 1     ; সবসময় সফল, কিন্তু শুধু "যোগ করো" করতে পারে
lock xchg [state], eax    ; সবসময় সফল, পুরনো মান রিটার্ন করে

দুটোই unconditional — এরা সবসময় কাজটা করেই ফেলে, কোনো শর্ত ছাড়াই। এটা counter increment-এর জন্য যথেষ্ট, কিন্তু জটিল data structure আপডেটের জন্য নয়।

CAS-এর শক্তি — শর্তসাপেক্ষ আপডেট:

int expected = old_value;
int success = atomic_compare_exchange_strong(&var, &expected, new_value);
/* শুধু var == old_value হলেই var = new_value হবে */

এই “যদি এখনো একই থাকে” শর্তটাই lock-free data structure-এর ভিত্তি — একটা linked list-এর head pointer আপডেট করতে চাইলে:

node_t *old_head = atomic_load(&list_head);
node_t *new_node = create_node(data);
new_node->next = old_head;

/* যদি এই মুহূর্তে অন্য কোনো thread ইতিমধ্যে head বদলে ফেলে,
   আমাদের CAS ব্যর্থ হবে — আমরা আবার চেষ্টা করব (retry loop) */
while (!atomic_compare_exchange_weak(&list_head, &old_head, new_node)) {
    new_node->next = old_head;   /* old_head এখন নতুন প্রকৃত মান — CAS নিজেই আপডেট করেছে */
}

এই প্যাটার্ন — read, compute, CAS, ব্যর্থ হলে retry — হলো lock-free algorithm-এর সার্বজনীন কাঠামো। এটাই futex-এর নিজের mutex implementation-এও ব্যবহৃত হয়েছে (আজকের my_mutex_lock-এর প্রথম ধাপ, atomic_compare_exchange_strong)।

আরেকটা কারণ CAS জনপ্রিয় — এটা “universal” primitive হিসেবে প্রমাণিত। Computer science-এর একটা তত্ত্ব (Herlihy-র consensus hierarchy) দেখায় CAS দিয়ে যেকোনো lock-free data structure বানানো যায়, যেখানে add/xchg-এর মতো সরল atomic instruction (যাদের “consensus number” কম) দিয়ে তা সম্ভব নয় বহু thread-এর ক্ষেত্রে। এই কারণেই আধুনিক CPU সবাই cmpxchg-কে একটা প্রথম-শ্রেণির instruction হিসেবে রাখে, আর প্রায় সব high-level atomic API (C11 stdatomic.h, C++ std::atomic, Java AtomicInteger) CAS-কে কেন্দ্রীয় primitive হিসেবে প্রকাশ করে।

Level 6-এ আমরা lock-free data structure (queue, stack) নিজে বানাব ঠিক এই CAS-retry প্যাটার্ন দিয়ে।

দুইটা সমস্যা — একটা performance, একটা সম্ভাব্য race।

সমস্যা ১ — performance-এর ক্ষতি, correctness নয়।

atomic_store পুরনো মান রিটার্ন করে না — তাই আমরা জানতেই পারছি না আগের state LOCKED_NO_WAITERS (কোনো waiter ছিল না) নাকি LOCKED_WAITERS (waiter ছিল)। তাই কোড সবসময় FUTEX_WAKE ডাকতে বাধ্য হচ্ছে, “নিরাপদ” থাকার জন্য।

এটা সরাসরি এই লেসনের কেন্দ্রীয় optimization নষ্ট করে দেয় — uncontended path-এও এখন প্রতিটা unlock() একটা syscall করছে। আজকের প্রথম experiment-এ যে “শূন্য futex call” দেখেছিলাম, এই bug-যুক্ত সংস্করণে সেটা হতো “প্রতিবার একটা futex call” — দশ লক্ষ syscall, যেখানে সঠিক সংস্করণে শূন্য ছিল।

সমস্যা ২ — সম্ভাব্য race, correctness-এও প্রভাব।

আরো সূক্ষ্ম সমস্যা: atomic_store আর তারপরের FUTEX_WAKE-এর মাঝখানে একটা window আছে যেখানে অন্য কোনো thread ইতিমধ্যে এই lock-টা নতুন করে নিয়ে নিতে পারে (যদি LOCKED_NO_WAITERS-এ CAS করে), তারপর সেই নতুন lock-ধারী নিজেই দ্রুত unlock() ডেকে ফেলতে পারে — এবং তখন দুইটা FUTEX_WAKE call হতে পারে একটা প্রকৃত unlock-এর জন্য, যা নিরাপদ (harmless বাড়তি wake) কিন্তু অপ্রয়োজনীয় ওভারহেড।

সঠিক সংস্করণ কেন atomic_exchange ব্যবহার করে:

void my_mutex_unlock(atomic_int *state) {
    if (atomic_exchange(state, UNLOCKED) == LOCKED_WAITERS)
        futex(state, FUTEX_WAKE, 1);
}

atomic_exchange একটা atomic ধাপে দুইটা কাজ করে: নতুন মান বসায়, এবং পুরনো মান রিটার্ন করে। এই তথ্যটাই ব্যবহার করে সিদ্ধান্ত নেওয়া হয় FUTEX_WAKE লাগবে কি না — কোনো বাড়তি read-then-write দরকার নেই (যা নিজেই একটা নতুন race window তৈরি করত)।

সাধারণ শিক্ষা — lock-free/futex কোড লেখার সময় “কোন atomic operation ঠিক কী তথ্য দেয়” এটা মনোযোগ দিয়ে বাছতে হয়:

এই তিনটার মধ্যে সঠিকটা না বাছলে — যেমন এই প্রশ্নের bug-টা — হয় শুধু performance নষ্ট হয় (এই ক্ষেত্রে), অথবা আরো খারাপ ক্ষেত্রে প্রকৃত correctness bug (lost wakeup, race condition) তৈরি হতে পারে। প্রতিটা atomic operation বাছার সময় প্রশ্ন করুন: “আমার এই মুহূর্তে ঠিক কোন তথ্যটা দরকার — শুধু লিখতে, নাকি পুরনো মানও জানতে, নাকি একটা শর্ত যাচাই করতে?”