Systems প্রোগ্রামিং ইন্টারভিউ — concurrency আর C কোডিং সমস্যা

১ · Systems কোডিং ইন্টারভিউ — invariant আগে, race মাথায় রেখে

পর্ব ৬৩-এ আপনি OS-এর ধারণাভিত্তিক ইন্টারভিউ প্রশ্নের অনুশীলন করেছেন। এই পর্ব তার হাতে-কলমে রূপ। Systems, backend, embedded, DevOps বা SRE পদের অনেক ইন্টারভিউতে সাধারণ অ্যালগরিদমের পাশাপাশি একটি ভিন্ন ধরনের সমস্যা আসে: “দুটি থ্রেড দিয়ে পালা করে সংখ্যা ছাপান”, “একটি thread-safe queue লিখুন”, “এই কোডে কী ভুল?”। এখানে Big-O-র চেয়ে বেশি দেখা হয় আপনি race condition চিনতে পারেন কি না, সঠিক primitive বাছতে পারেন কি না, আর ত্রুটি (error) ঠিকমতো সামলান কি না। প্রতিষ্ঠানভেদে ধরন আলাদা, তবে এ ধরনের প্রশ্ন প্রায়ই আসে।

পাঁচ ধাপের পদ্ধতি

সাধারণ কোডিং ইন্টারভিউর “বুঝুন → উদাহরণ → brute force → উন্নতি” রুটিন এখানেও খাটে, তবে concurrency-তে কয়েকটি বাড়তি ধাপ লাগে। একজন অভিজ্ঞ বিদ্যুৎমিস্ত্রি যেমন তার জোড়ার আগে মূল সুইচ বন্ধ করেন, তেমনি আপনিও কোড লেখার আগে ঠিক করে নিন — কোন ডেটা ভাগ হচ্ছে, আর কে তাকে রক্ষা করবে।

1. প্রশ্ন করুন (clarifying question): কতজন producer আর consumer? Queue-র আকার সীমিত? Block করবে, নাকি সঙ্গে সঙ্গে ব্যর্থতা ফেরত দেবে? Timeout লাগবে? Shutdown কীভাবে হবে? কোন OS — POSIX না Windows?
2. Shared state আর invariant লিখুন: “count সবসময় ০ থেকে CAP-এর মধ্যে”, “একসাথে writer থাকলে কোনো reader নেই”, “দুই ওয়ালেটের মোট টাকা বদলায় না”। প্রতিটি shared ভ্যারিয়েবলের পাশে লিখুন কোন mutex তাকে রক্ষা করে।
3. Primitive বাছুন: শুধু পারস্পরিক বর্জন হলে mutex; “শর্ত সত্য না হওয়া পর্যন্ত ঘুমিয়ে থাকা” হলে mutex + condition variable; সম্পদ গোনা হলে semaphore; “সবাই পৌঁছালে একসাথে এগোনো” হলে barrier; একটি সংখ্যা বা flag হলে atomic.
4. কোড লিখুন — কয়েকটি অটল নিয়মে: প্রতিটি wait একটি while-এ; lock ধরে কোনো ধীর কাজ (I/O, callback) নয়; একাধিক lock সবসময় একই ক্রমে; প্রতিটি system call-এর ফেরত মান যাচাই।
5. Race মাথায় রেখে পরীক্ষা: “দুই থ্রেড ঠিক এই লাইনের মাঝে বদলালে কী হয়?” — প্রতিটি lock-ছাড়া জায়গায় এই প্রশ্ন করুন। তারপর পরীক্ষা: অনেক থ্রেড, বড় লুপ, ফল যাচাই, আর ThreadSanitizer.

Concurrent কোডের পরীক্ষা কেন আলাদা

একক থ্রেডের কোডে একই ইনপুটে একই ফল আসে। থ্রেডে তা নয় — scheduler প্রতিবার আলাদা interleaving বাছে। তাই এই পাতার প্রতিটি প্রোগ্রাম তিনটি কৌশল মানে: (১) থ্রেড নিজে ছাপে না, বা ছাপে কঠোর পালায় — ফল ছাপে main, join-এর পরে; (২) “কী ঘটল” নয়, “নিয়ম ভেঙেছে কি না” গোনে — যেমন violations = 0; (৩) ফলের এমন রূপ ছাপে যা interleaving-এর ওপর নির্ভর করে না — মোট যোগফল, সংখ্যা, “yes/no”. ইন্টারভিউতেও এভাবেই test-এর কথা বলুন। মনে রাখবেন, data race থাকলে C-তে আচরণ undefined; একবার ঠিক ফল আসা কিছুই প্রমাণ করে না (পর্ব ২২)।

নিচের টেবিলে ১৪টি সমস্যার মানচিত্র। প্রতিটির শুরুতে কোন পর্ব রিভিশন করবেন, তা-ও দেওয়া আছে।

২ · পালা আর দল বাঁধার ধাঁধা — বিজোড়-জোড় আর H2O

সমস্যা ১ · দুই থ্রেডে পালা করে ১ থেকে ১০ (সহজ)

রিভিশন: পর্ব ২৫ · Condition variable আর monitor, পর্ব ১৫ · POSIX thread হাতে-কলমে

সমস্যা: “দুটি থ্রেড আছে — একটি শুধু বিজোড় সংখ্যা ছাপে, অন্যটি শুধু জোড়। মিলে তারা ঠিক ক্রমে ১, ২, ৩ … ১০ ছাপবে। কোনো থ্রেড busy-wait করবে না।”

পদ্ধতি: একটি shared ভ্যারিয়েবল next — পরের যে সংখ্যা ছাপা হবে। Invariant: “next-এর parity যার, পালা তার”। প্রতিটি থ্রেড mutex ধরে while-এ অপেক্ষা করে যতক্ষণ পালা তার নয়; পালা এলে ছাপে, next++ করে, অন্যজনকে জাগায়। পালা হস্তান্তরের ঘটনাটা হলো “next বদলানো + signal” — দুটোই mutex ধরে।

• ফাঁদ ১ — busy waiting: while (next % 2 != me) ; লুপে ঘোরা CPU পোড়ায়, আর lock ছাড়া পড়া একটি data race. তাই condition variable.
• ফাঁদ ২ — if-এ wait: spurious wakeup-এ থ্রেড পালা ছাড়াই জেগে উঠতে পারে; while শর্ত আবার দেখে নেয়।
• ফাঁদ ৩ — শেষের সমস্যা: ১০ ছাপার পর অন্য থ্রেড চিরকাল ঘুমিয়ে থাকতে পারে। তাই wait-এর শর্তে next <= MAX, আর বের হওয়ার আগে শেষ signal.
• ফাঁদ ৪ — signal হারানো: শর্তের ভ্যারিয়েবল mutex ছাড়া বদলালে বা wait-এর আগে শর্ত না দেখলে lost wakeup হয় (পর্ব ২৫)।

#include <pthread.h>
#include <stdio.h>
enum { MAX = 10 };
static pthread_mutex_t mu = PTHREAD_MUTEX_INITIALIZER;
static pthread_cond_t turn = PTHREAD_COND_INITIALIZER;
static int next = 1;                 /* invariant: next = the number to print now */

static void *run(void *arg) {
    int parity = *(int *)arg;        /* 1 = odd thread, 0 = even thread */
    pthread_mutex_lock(&mu);
    for (;;) {
        while (next <= MAX && next % 2 != parity)
            pthread_cond_wait(&turn, &mu);    /* not my turn: sleep, mutex released */
        if (next > MAX) break;
        printf("%s thread: %d\n", parity ? "odd " : "even", next);
        next++;                               /* hand the turn over ... */
        pthread_cond_signal(&turn);           /* ... and wake the other thread */
    }
    pthread_mutex_unlock(&mu);
    return NULL;
}

int main(void) {
    pthread_t t[2];
    int parity[2] = {0, 1};          /* start the even thread first on purpose */
    for (int i = 0; i < 2; i++) pthread_create(&t[i], NULL, run, &parity[i]);
    for (int i = 0; i < 2; i++) pthread_join(t[i], NULL);
    printf("both threads finished, next = %d\n", next);
    return 0;
}

odd  thread: 1
even thread: 2
odd  thread: 3
even thread: 4
odd  thread: 5
even thread: 6
odd  thread: 7
even thread: 8
odd  thread: 9
even thread: 10
both threads finished, next = 11

পালা হস্তান্তরের পুরো নাচটি ধাপে ধাপে দেখুন — কে mutex ধরে আছে, কে ঘুমিয়ে, কে জেগে mutex-এর অপেক্ষায়:

1lock(&mu);2while (next <= MAX && next % 2 != parity)3    cond_wait(&turn, &mu);  // sleep, unlock4if (next > MAX) break;5printf("%d", next);6next++;7cond_signal(&turn);   // wake the other8unlock(&mu);  // after the loop

সঠিকতা ও জটিলতা: invariant — “next শুধু mutex ধরে বদলায়, আর যে থ্রেড ছাপে তার parity next-এর parity-র সমান”। তাই কোনো সংখ্যা দুবার বা ভুল থ্রেড থেকে ছাপা হয় না। প্রতিটি সংখ্যায় একটি হস্তান্তর, মোট O(MAX) কাজ; কিন্তু প্রতিটি হস্তান্তরে একটি থ্রেড ঘুমায় আর আরেকটি জাগে — সাধারণত একটি context switch-সহ — তাই এটি আসলে ধীর। ইন্টারভিউয়ারকে বলুন: এই সমস্যা সমন্বয় দেখানোর জন্য, গতির জন্য নয়।

সমস্যা ২ · H2O — দুটি H আর একটি O মিলে অণু (মাঝারি)

রিভিশন: পর্ব ২৪ · Mutex আর semaphore, পর্ব ২৫ (barrier অংশ)

সমস্যা: “অনেকগুলো থ্রেড, প্রতিটি একটি পরমাণু — হাইড্রোজেন (H) বা অক্সিজেন (O). প্রতিটি থ্রেড bond() ডাকবে। শর্ত: bond() ডাকা থ্রেডগুলো তিনজনের দলে ভাগ হবে, প্রতিটি দলে ঠিক দুটি H আর একটি O, আর এক দলের তিনজন bond() শেষ না করা পর্যন্ত পরের দলের কেউ bond() ডাকবে না।” এ ধরনের ক্রম-সাজানোর ধাঁধা Allen Downey-র বিনামূল্যের বই The Little Book of Semaphores-এ “Building H2O” নামে আছে, আর ইন্টারভিউতে প্রায়ই নানা রূপে আসে।

পদ্ধতি: দুটি counting semaphore “আসন” বোঝায় — hseat = 2, oseat = 1 — আর একটি তিনজনের pthread_barrier. প্রতিটি থ্রেড: নিজের ধরনের আসন নেয় → barrier-এ অপেক্ষা → bond() → আসন ফেরত দেয়। মূল কৌশল: আসন ফেরত দেওয়া হয় bond-এর পরে. তাই পরের দলের কোনো সদস্য তখনই আসন পায়, যখন আগের দলের কেউ bond শেষ করে আসন ছেড়েছে — আর পরের দলের তিনটি আসন ভরতে আগের দলের তিনজনকেই আসন ছাড়তে হয়।

#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>
enum { MOL = 5 };
static sem_t hseat, oseat;           /* at most 2 H and 1 O inside a molecule */
static pthread_barrier_t three;      /* the 3 seated atoms wait for each other */
static pthread_mutex_t mu = PTHREAD_MUTEX_INITIALIZER;
static char bonded[3 * MOL]; static int n;

static void *atom(void *arg) {
    char kind = *(char *)arg;
    sem_t *seat = (kind == 'H') ? &hseat : &oseat;
    sem_wait(seat);                  /* take a seat in the current molecule */
    pthread_barrier_wait(&three);    /* wait until 2 H + 1 O are seated */
    pthread_mutex_lock(&mu); bonded[n++] = kind; pthread_mutex_unlock(&mu);
    sem_post(seat);                  /* give the seat back only after bonding */
    return NULL;
}
int main(void) {
    pthread_t t[3 * MOL]; char kind[3 * MOL];
    sem_init(&hseat, 0, 2); sem_init(&oseat, 0, 1); pthread_barrier_init(&three, NULL, 3);
    for (int i = 0; i < 3 * MOL; i++) {
        kind[i] = (i < MOL) ? 'O' : 'H';           /* all O threads are created first */
        pthread_create(&t[i], NULL, atom, &kind[i]);
    }
    for (int i = 0; i < 3 * MOL; i++) pthread_join(t[i], NULL);
    int ok = 1;
    for (int m = 0; m < MOL; m++) ok &= (bonded[3*m] == 'H') + (bonded[3*m+1] == 'H') + (bonded[3*m+2] == 'H') == 2;
    printf("atoms bonded = %d, molecules = %d, every group of 3 is 2H+1O: %s\n", n, n / 3, ok ? "yes" : "no");
}

atoms bonded = 15, molecules = 5, every group of 3 is 2H+1O: yes

• সঠিকতা: (১) গঠন: barrier ছাড়ে ঠিক তিনজনকে, আর তিনজনের প্রত্যেকে একটি আসন ধরে আছে; আসন মোট ২টি H আর ১টি O, তাই দল = ২H + ১O. (২) আলাদা দল: দল k+১-এর তিনটি আসন খালি পেতে দল k-এর তিনজনকেই sem_post করতে হবে, যা তারা করে bond-এর পরে — তাই দল k-এর সব bond দল k+১-এর যেকোনো bond-এর আগে।
• ফাঁদ: আসন bond-এর আগে ফেরত দিলে দল মিশে যেতে পারে। শুধু একটি mutex আর H-এর counter দিয়ে “দুটি H জমলে O-কে ডাকি” ধরনের সমাধানে প্রায়ই ২টির জায়গায় ৩টি H ঢুকে পড়ে।
• OS-এর পার্থক্য: macOS-এ pthread_barrier_t নেই, আর unnamed semaphore (sem_init) কাজ করে না; সেখানে mutex + condition variable দিয়ে barrier নিজে বানাতে হয়, বা Grand Central Dispatch-এর semaphore ব্যবহার করতে হয়। Windows-এ SYNCHRONIZATION_BARRIER আর CreateSemaphore আছে।
• জটিলতা: প্রতিটি থ্রেডে ধ্রুব সংখ্যক সমন্বয়-কাজ, মোট O(n); কিন্তু প্রতিটি দল barrier-এ অন্তত একবার ঘুম-জাগরণ নেয়।

৩ · Producer–consumer — blocking queue আর semaphore

সমস্যা ৩ · Thread-safe bounded blocking queue (মাঝারি)

রিভিশন: পর্ব ২৬ · ক্লাসিক সমস্যা, পর্ব ২৫, পর্ব ১৫ (thread pool অংশ)

সমস্যা: “নির্দিষ্ট ধারণক্ষমতার (CAP) একটি queue লিখুন, যাতে put(x) আর take() আছে। Queue ভর্তি থাকলে put অপেক্ষা করবে, খালি থাকলে take অপেক্ষা করবে। একাধিক producer আর একাধিক consumer একসাথে ব্যবহার করবে।” এটিই সম্ভবত সবচেয়ে বেশি আসা concurrency প্রশ্ন — thread pool, logging, নেটওয়ার্ক সার্ভার, সবখানে এর ব্যবহার। এর আরেক নাম bounded buffer.

পদ্ধতি: একটি বৃত্তাকার array (head, count), একটি mutex যা তিনটিকেই রক্ষা করে, আর দুটি condition variable — not_full (producer এখানে ঘুমায়) আর not_empty (consumer এখানে ঘুমায়)। Invariant: ০ ≤ count ≤ CAP, আর উপাদানগুলো buf[head] থেকে পরের countটি ঘরে।

• কেন দুটি condition variable: একটি cv-তে producer আর consumer দুজনেই ঘুমালে signal হয়তো ভুল দলের কাউকে জাগাবে (consumer জাগাল আরেক consumer-কে) — আসল অপেক্ষমাণ চিরকাল ঘুমাতে পারে। একটি cv রাখলে broadcast লাগবে, যা অপচয়।
• কেন while: দুজন consumer অপেক্ষায়, একটি উপাদান এল; একজন জাগল, কিন্তু mutex পাওয়ার আগেই তৃতীয় একজন consumer এসে উপাদানটি নিয়ে গেল (“চুরি যাওয়া জাগরণ”)। while আবার দেখে, আবার ঘুমায়।
• Signal lock ধরে নাকি ছেড়ে? দুটোই সঠিক। lock ছাড়ার পরে signal দিলে জাগা থ্রেড সঙ্গে সঙ্গে mutex পায় বলে কখনো একটু দ্রুত, তবে lock ধরে signal দেওয়া কোড পড়তে সহজ।

#include <pthread.h>
#include <stdio.h>
enum { CAP = 4, PER = 1000 };
static int buf[CAP], head, count, peak;      /* invariant: 0 <= count <= CAP */
static pthread_mutex_t mu = PTHREAD_MUTEX_INITIALIZER;
static pthread_cond_t not_full = PTHREAD_COND_INITIALIZER, not_empty = PTHREAD_COND_INITIALIZER;
static void put(int x) {
    pthread_mutex_lock(&mu);
    while (count == CAP) pthread_cond_wait(&not_full, &mu);    /* full: producer sleeps */
    buf[(head + count++) % CAP] = x; if (count > peak) peak = count;
    pthread_cond_signal(&not_empty);
    pthread_mutex_unlock(&mu);
}
static int take(void) {
    pthread_mutex_lock(&mu);
    while (count == 0) pthread_cond_wait(&not_empty, &mu);     /* empty: consumer sleeps */
    int x = buf[head]; head = (head + 1) % CAP; count--;
    pthread_cond_signal(&not_full);
    pthread_mutex_unlock(&mu);
    return x;
}
static void *producer(void *a) { int base = *(int *)a; for (int i = 1; i <= PER; i++) put(base + i); return NULL; }
static void *consumer(void *a) { long *s = a; for (int i = 0; i < PER; i++) *s += take(); return NULL; }
int main(void) {
    pthread_t p[2], c[2]; int base[2] = {0, PER}; long sum[2] = {0, 0};
    for (int i = 0; i < 2; i++) { pthread_create(&p[i], NULL, producer, &base[i]); pthread_create(&c[i], NULL, consumer, &sum[i]); }
    for (int i = 0; i < 2; i++) { pthread_join(p[i], NULL); pthread_join(c[i], NULL); }
    printf("sum taken = %ld, expected 1+..+%d = %d\n", sum[0] + sum[1], 2 * PER, PER * (2 * PER + 1));
    printf("peak <= CAP: %s, left in queue = %d\n", peak <= CAP ? "yes" : "no", count);
}

sum taken = 2001000, expected 1+..+2000 = 2001000
peak <= CAP: yes, left in queue = 0

সঠিকতা ও জটিলতা: প্রতিটি put/take mutex ধরে count একবার বদলায়, আর while-এর পরে শর্ত (count < CAP বা count > 0) সত্য — তাই invariant রক্ষা পায়। প্রতিটি কাজ O(1). Deadlock নেই, কারণ একটিই mutex. Progress-এর যুক্তি: একজন producer ঘুমায় শুধু queue ভর্তি থাকলে; তখন অন্তত একটি উপাদান আছে, তাই কোনো consumer কখনো not_empty-এ চিরকাল ঘুমাবে না, আর প্রতিটি take একটি not_full signal দেয়।

সমস্যা ৪ · Semaphore দিয়ে producer–consumer (মাঝারি)

রিভিশন: পর্ব ২৬ (তিনটি semaphore-এর সমাধান আর wait-এর ক্রম), পর্ব ২৪

সমস্যা: “একই bounded buffer, তবে condition variable ছাড়া — শুধু semaphore দিয়ে। আর ব্যাখ্যা করুন wait-এর ক্রম উল্টালে কী হয়।” পাঠ্যবইয়ের ক্লাসিক সমাধান: empty = CAP (খালি ঘরের সংখ্যা), full = 0 (ভরা ঘরের সংখ্যা), আর ঘরে লেখা-পড়ার জন্য একটি mutex.

#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>
enum { CAP = 3, ITEMS = 500 };
static int buf[CAP], in, out;
static sem_t empty, full;            /* empty = free slots, full = filled slots */
static pthread_mutex_t mu = PTHREAD_MUTEX_INITIALIZER;
static void *producer(void *unused) {
    for (int i = 1; i <= ITEMS; i++) {
        sem_wait(&empty);            /* 1. reserve a free slot (may sleep) */
        pthread_mutex_lock(&mu);     /* 2. only then take the lock */
        buf[in] = i; in = (in + 1) % CAP; pthread_mutex_unlock(&mu);
        sem_post(&full);             /* 3. announce one more item */
    }
    return unused;
}
static void *consumer(void *sum) {
    for (int i = 0; i < ITEMS; i++) {
        sem_wait(&full);             /* wait for an item */
        pthread_mutex_lock(&mu); *(long *)sum += buf[out]; out = (out + 1) % CAP; pthread_mutex_unlock(&mu);
        sem_post(&empty);            /* one slot is free again */
    }
    return NULL;
}
int main(void) {
    pthread_t p, c; long sum = 0; int e, f; sem_init(&empty, 0, CAP); sem_init(&full, 0, 0);
    pthread_create(&p, NULL, producer, NULL); pthread_create(&c, NULL, consumer, &sum);
    pthread_join(p, NULL); pthread_join(c, NULL); sem_getvalue(&empty, &e); sem_getvalue(&full, &f);
    printf("sum = %ld (expected %d), empty = %d, full = %d\n", sum, ITEMS * (ITEMS + 1) / 2, e, f);
}

sum = 125250 (expected 125250), empty = 3, full = 0

• ক্রমের ফাঁদ: producer যদি আগে mutex নেয়, তারপর sem_wait(&empty) — আর buffer ভর্তি থাকে — তাহলে সে mutex ধরে ঘুমায়। Consumer sem_wait(&full) পেরিয়ে mutex চায়, পায় না; empty কখনো বাড়ে না: deadlock. নিয়ম: আগে গোনার semaphore, তারপর mutex; ছাড়ার সময় ক্রম গুরুত্বপূর্ণ নয়।
• Mutex কেন, যদি একজন producer আর একজন consumer হয়? তখন in শুধু producer আর out শুধু consumer ছোঁয়, আর একই ঘরে একসাথে পৌঁছানো semaphore-ই আটকায় — mutex ছাড়াও চলে। একাধিক producer হলে in-এ race হবে, তাই সাধারণ সমাধানে mutex রাখুন।
• EINTR: sem_wait signal handler-এ বাধা পেলে −১ ফেরত দেয় আর errno = EINTR — handler SA_RESTART ছাড়া বসানো হলে (Linux 2.6.22 থেকে SA_RESTART থাকলে এটি নিজে আবার শুরু হয়; অন্য OS-এ নিয়ম আলাদা হতে পারে)। বাস্তব কোডে while (sem_wait(&s) == -1 && errno == EINTR) ; লিখুন। Pthread mutex আর condition variable কখনো EINTR দেয় না।
• Semaphore বনাম condition variable: semaphore “গোনা” মনে রাখে, তাই সম্পদ-গণনায় সরল। কিন্তু জটিল শর্তে (“queue-তে অন্তত ৫টি আর shutdown নয়”) condition variable বেশি নমনীয়। Mutex-এর একজন মালিক থাকে; semaphore যেকোনো থ্রেড post করতে পারে — তাই semaphore দিয়ে mutex-এর মালিকানা-নিয়ম বা priority inversion-এর প্রতিকার পাওয়া যায় না।

৪ · নিজের lock বানানো — reader–writer lock আর spinlock

সমস্যা ৫ · Reader–writer lock, লেখক-অগ্রাধিকারসহ (কঠিন)

রিভিশন: পর্ব ২৬ · Readers–writers (প্রথম সমাধান, লেখকের starvation, লেখক-অগ্রাধিকার)

সমস্যা: “একটি mutex আর condition variable দিয়ে rlock, runlock, wlock, wunlock বানান। একসাথে অনেক reader পড়তে পারবে, কিন্তু writer একা। কোনো writer অপেক্ষায় থাকলে নতুন reader ঢুকবে না।” এটি readers–writers problem-এর “দ্বিতীয়” রূপ — Courtois, Heymans আর Parnas ১৯৭১ সালে দুটি রূপই প্রকাশ করেছিলেন।

পদ্ধতি: mutex-রক্ষিত তিনটি সংখ্যা — readers (এখন পড়ছে), writing (০/১), waiting_writers (অপেক্ষায়)। Invariant: writing == 1 হলে readers == 0, আর writing ≤ ১. Reader ঢোকে শুধু যখন কেউ লিখছে না এবং কোনো writer অপেক্ষায় নেই — এটিই writer preference. শেষ reader বেরোলে একজন writer-কে জাগায়; writer বেরোলে আগে অপেক্ষমাণ writer-কে, না থাকলে সব reader-কে (broadcast).

#include <pthread.h>
#include <stdatomic.h>
#include <stdio.h>
static pthread_mutex_t mu = PTHREAD_MUTEX_INITIALIZER;
static pthread_cond_t can_read = PTHREAD_COND_INITIALIZER, can_write = PTHREAD_COND_INITIALIZER;
static int readers, writing, waiting_writers;  /* invariant: !(writing && readers > 0) */
static atomic_int in_r, in_w, bad;             /* only for checking the invariant */
static long value;

static void rlock(void) { pthread_mutex_lock(&mu);
    while (writing || waiting_writers > 0) pthread_cond_wait(&can_read, &mu);  /* writers first */
    readers++; pthread_mutex_unlock(&mu); }
static void runlock(void) { pthread_mutex_lock(&mu);
    if (--readers == 0) pthread_cond_signal(&can_write);       /* last reader lets a writer in */
    pthread_mutex_unlock(&mu); }
static void wlock(void) { pthread_mutex_lock(&mu); waiting_writers++;
    while (writing || readers > 0) pthread_cond_wait(&can_write, &mu);
    waiting_writers--; writing = 1; pthread_mutex_unlock(&mu); }
static void wunlock(void) { pthread_mutex_lock(&mu); writing = 0;
    if (waiting_writers > 0) pthread_cond_signal(&can_write); else pthread_cond_broadcast(&can_read);
    pthread_mutex_unlock(&mu); }

static void *reader(void *a) { for (int i = 0; i < 20000; i++) { rlock(); in_r++; if (in_w) bad++; in_r--; runlock(); } return a; }
static void *writer(void *a) { for (int i = 0; i < 5000; i++) { wlock(); in_w++; if (in_r || in_w > 1) bad++; value++; in_w--; wunlock(); } return a; }
int main(void) {
    pthread_t t[6];
    for (int i = 0; i < 6; i++) pthread_create(&t[i], NULL, i < 4 ? reader : writer, NULL);
    for (int i = 0; i < 6; i++) pthread_join(t[i], NULL);
    printf("4 readers, 2 writers: value = %ld (expected 10000), violations = %d\n", value, bad);
}

4 readers, 2 writers: value = 10000 (expected 10000), violations = 0

• Starvation: writer preference-এ লেখা অবিরাম চললে reader-এর starvation হয়; reader preference-এ উল্টো। ন্যায্য সমাধান: আসার ক্রমে টিকিট (ticket), বা “একজন writer শেষে অপেক্ষমাণ সব reader আগে ঢুকবে” ধরনের পালা।
• বাস্তবে: glibc-র pthread_rwlock_t ডিফল্টে reader-দের অগ্রাধিকার দেয়; pthread_rwlockattr_setkind_np(..., PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP) দিয়ে writer preference নেওয়া যায় (glibc-নির্দিষ্ট, _np = non-portable). Windows-এর SRWLOCK আর Linux kernel-এর rwsem-এর নিজস্ব নীতি আছে। rwlock তখনই লাভজনক যখন পড়ার কাজ দীর্ঘ আর অনেক; ছোট critical section-এ এর বাড়তি হিসাব একটি সাধারণ mutex-এর চেয়ে ধীরও হতে পারে।
• Upgrade-এর ফাঁদ: দুজন reader একসাথে “write-এ upgrade” চাইলে দুজনেই অন্যজনের বেরোনোর অপেক্ষা করে — deadlock. তাই বেশিরভাগ API upgrade দেয় না; read lock ছেড়ে write lock নিন আর শর্ত আবার যাচাই করুন।

সমস্যা ৬ · C11 atomic দিয়ে spinlock, আর memory ordering (কঠিন)

রিভিশন: পর্ব ২৩ · Atomic instruction, spinlock আর memory ordering

সমস্যা: “<stdatomic.h> দিয়ে একটি spinlock লিখুন। প্রতিটি atomic কাজে কোন memory order দিলেন আর কেন, ব্যাখ্যা করুন।” প্রশ্নটির আসল লক্ষ্য দ্বিতীয় অংশ — memory ordering বোঝেন কি না।

পদ্ধতি: একটি atomic_bool held. Lock: atomic_exchange(&held, true) — পুরোনো মান false হলে lock আমাদের (এটিই test-and-set). ব্যর্থ হলে সাধারণ load-এ ঘুরি যতক্ষণ held সত্য — একে বলে test-and-test-and-set: প্রতিটি ঘোরায় লেখা হয় না, তাই cache line বারবার এক core থেকে আরেক core-এ লাফায় না। Unlock: atomic_store(&held, false).

#include <pthread.h>
#include <sched.h>
#include <stdatomic.h>
#include <stdbool.h>
#include <stdio.h>
typedef struct { atomic_bool held; } spinlock_t;

static void spin_lock(spinlock_t *s) {
    for (;;) {
        /* test-and-set; acquire: nothing in the critical section moves above this */
        if (!atomic_exchange_explicit(&s->held, true, memory_order_acquire)) return;
        while (atomic_load_explicit(&s->held, memory_order_relaxed))
            sched_yield();           /* test-and-test-and-set: wait with plain reads */
    }
}
static void spin_unlock(spinlock_t *s) {
    atomic_store_explicit(&s->held, false, memory_order_release);  /* publish our writes */
}
static spinlock_t lk;                /* static storage: held starts false */
static long counter;                 /* a plain variable, protected only by lk */
static void *work(void *a) {
    for (int i = 0; i < 100000; i++) { spin_lock(&lk); counter++; spin_unlock(&lk); }
    return a;
}
int main(void) {
    pthread_t t[4];
    for (int i = 0; i < 4; i++) pthread_create(&t[i], NULL, work, NULL);
    for (int i = 0; i < 4; i++) pthread_join(t[i], NULL);
    printf("counter = %ld (expected 400000)\n", counter);
}

counter = 400000 (expected 400000)

• Relaxed দিলে কী হতো: x86-এ হয়তো কাজ করত, কারণ x86-এর মডেল (TSO) প্রায় সব reordering আটকায় — কিন্তু ARM বা POWER-এ critical section-এর লেখা unlock-এর পরে দৃশ্যমান হতে পারে, ফলে অন্য থ্রেড পুরোনো মান পড়বে। Compiler-ও relaxed পেলে load/store সরাতে পারে। “আমার ল্যাপটপে চলে” এখানে কিছুই প্রমাণ করে না।
• seq_cst দিলে? সবসময় সঠিক (sequential consistency), শুধু কিছু architecture-এ সামান্য ধীর। ইন্টারভিউতে ভালো উত্তর: “ডিফল্ট seq_cst দিয়ে শুরু, প্রমাণ করতে পারলে তবেই acquire/release-এ নামি।”
• volatile কেন নয়: volatile atomicity বা ordering দেয় না — শুধু compiler-কে প্রতিবার মেমরি ছুঁতে বাধ্য করে।
• Spinlock কখন খারাপ: lock-ধারী থ্রেড preempt হলে বাকিরা পুরো time slice ঘুরে নষ্ট করে। তাই user space-এ সাধারণত mutex (Linux-এ futex-ভিত্তিক — আগে অল্প ঘোরে, তারপর kernel-এ ঘুমায়)। Kernel-এ spinlock নেওয়ার সময় preemption বন্ধ থাকে, আর interrupt handler-ও একই lock নিলে interrupt-ও বন্ধ করতে হয় (spin_lock_irqsave).

৫ · Data structure-কে thread-safe করা — LRU cache আর token bucket

সমস্যা ৭ · Thread-safe LRU cache (মাঝারি থেকে কঠিন)

রিভিশন: পর্ব ৩৬ · Page replacement (LRU), DSA · Hash table, DSA · Linked list

সমস্যা: “ধারণক্ষমতা CAP-এর একটি cache — get(key) আর put(key, value), দুটোই O(1). জায়গা ফুরালে সবচেয়ে কম সম্প্রতি ব্যবহৃত (LRU) উপাদান বাদ যাবে। তারপর: অনেক থ্রেড থেকে নিরাপদ করুন।”

পদ্ধতি: একটি hash map (key → node) আর একটি doubly linked list (MRU সামনে, LRU পেছনে)। Hit হলে node-কে তালিকা থেকে খুলে সামনে বসাই — দুই দিকের পয়েন্টার থাকায় O(1). জায়গা ফুরালে পেছনের node বাদ দিই আর map থেকেও মুছি। একটি sentinel (ডামি head) রাখলে খালি তালিকার আলাদা কেস লাগে না। নিচের ছোট মূল অংশে map-টি সরাসরি একটি array (key ০–৯৯) — আসল hash table বসালে বাকি কোড একই থাকে।

#include <pthread.h>
#include <stdio.h>
enum { CAP = 3, KEYS = 100 };
typedef struct node { int key, val; struct node *prev, *next; } node;
static node *map[KEYS];                       /* key -> node; in real code a hash table */
static node head = { 0, 0, &head, &head };    /* sentinel: head.next = MRU, head.prev = LRU */
static node slots[CAP]; static int used;
static pthread_mutex_t mu = PTHREAD_MUTEX_INITIALIZER;   /* ONE lock guards map + list */
static void unlink_node(node *n) { n->prev->next = n->next; n->next->prev = n->prev; }
static void push_front(node *n) { n->next = head.next; n->prev = &head; head.next->prev = n; head.next = n; }
static int get(int k) {
    pthread_mutex_lock(&mu);
    node *n = map[k]; int v = -1;
    if (n) { unlink_node(n); push_front(n); v = n->val; }   /* a hit becomes MRU */
    pthread_mutex_unlock(&mu); return v;
}
static void put(int k, int v) {
    pthread_mutex_lock(&mu);
    node *n = map[k];
    if (n) unlink_node(n);                                   /* update in place */
    else if (used < CAP) n = &slots[used++];
    else { n = head.prev; unlink_node(n); map[n->key] = NULL; printf("evict %d\n", n->key); }
    n->key = k; n->val = v; map[k] = n; push_front(n); pthread_mutex_unlock(&mu);
}
int main(void) {
    int ops[][2] = { {1,10}, {2,20}, {3,30}, {1,0}, {4,40}, {2,0}, {3,0}, {5,50}, {1,0}, {4,0}, {5,0} };
    for (int i = 0; i < 11; i++) if (ops[i][1]) put(ops[i][0], ops[i][1]); else printf("get %d -> %d\n", ops[i][0], get(ops[i][0]));
    printf("MRU..LRU:"); for (node *n = head.next; n != &head; n = n->next) printf(" %d", n->key);
    printf("\n");
}

get 1 -> 10
evict 2
get 2 -> -1
get 3 -> 30
evict 1
get 1 -> -1
get 4 -> 40
get 5 -> 50
MRU..LRU: 5 4 3

• Thread-safety-র মূল কথা: map আর list একসাথে একটি invariant — “map-এ যে key আছে, তার node তালিকায় আছে, আর উল্টোটাও” — তাই দুটোকে একই lock রক্ষা করবে। আলাদা lock দিলে (একটি map-এ, একটি list-এ) মাঝখানে অন্য থ্রেড অর্ধেক-বদলানো অবস্থা দেখবে।
• rwlock কেন সহজে চলে না: get শুধু “পড়া” মনে হলেও node সামনে আনে — অর্থাৎ লেখে। তাই get-এও exclusive lock লাগে; read lock নিলে দুই reader একই তালিকা একসাথে বদলাবে।
• Lock ধরে ধীর কাজ নয়: miss হলে ডেটাবেস থেকে আনার কাজ lock ছেড়ে করুন, তারপর lock নিয়ে put — নইলে একটি ধীর query পুরো cache থামিয়ে দেবে। একই key-র জন্য বহু থ্রেড একসাথে miss করলে (“cache stampede”) প্রতি key-তে একটি “লোড হচ্ছে” চিহ্ন রাখুন।
• জটিলতা: গড়ে O(1) প্রতি কাজ (hash-এর কারণে “গড়ে”), মেমরি O(CAP). একটি lock-এ throughput সীমিত — বড় সিস্টেমে key-এর hash দিয়ে cache-কে ১৬ বা ৬৪টি আলাদা ভাগে (shard) ভাঙা হয়, প্রতিটির নিজের lock আর নিজের LRU.

সমস্যা ৮ · Rate limiter — token bucket (মাঝারি)

রিভিশন: পর্ব ২৪ · Mutex, পর্ব ৫৩ (clock), পর্ব ৫১ (cgroup দিয়ে সম্পদ সীমা)

সমস্যা: “একটি কাল্পনিক অ্যাপের OTP-SMS API-তে প্রতি ব্যবহারকারী সেকেন্ডে গড়ে ২টি অনুরোধের বেশি পাঠাতে পারবেন না, তবে হঠাৎ একসাথে ৩টি পর্যন্ত চলবে। allow(user, now) লিখুন।” স্বাভাবিক সমাধান token bucket: একটি বালতিতে সর্বোচ্চ ৩টি টোকেন, প্রতি সেকেন্ডে ২টি করে ভরে; প্রতিটি অনুরোধ একটি টোকেন খরচ করে, টোকেন না থাকলে প্রত্যাখ্যান।

পদ্ধতি: একটি টাইমার থ্রেড দিয়ে প্রতি মুহূর্তে টোকেন ভরার দরকার নেই — lazy refill: প্রতিটি allow-এ শেষ হিসাবের পর কত সময় গেছে দেখে টোকেন যোগ করুন (সর্বোচ্চ cap পর্যন্ত)। ভগ্নাংশ টোকেনের rounding এড়াতে হিসাব পূর্ণসংখ্যায় — “মিলি-টোকেন”-এ। পরীক্ষা নির্ধারিত রাখতে আসল ঘড়ির বদলে সময় argument হিসেবে দেওয়া হয়েছে; বাস্তবে সেটি আসবে monotonic clock থেকে।

#include <pthread.h>
#include <stdio.h>
/* token bucket in integer milli-tokens (mt), so there is no floating-point rounding */
typedef struct {
    long tokens_m, cap_m, rate_m_per_ms;   /* cap 3 tokens = 3000 mt; 2 tokens/s = 2 mt per ms */
    long last_ms;
    pthread_mutex_t mu;                    /* one bucket may be shared by many threads */
} bucket;

static int allow(bucket *b, long now_ms) {
    pthread_mutex_lock(&b->mu);
    b->tokens_m += (now_ms - b->last_ms) * b->rate_m_per_ms;   /* lazy refill */
    if (b->tokens_m > b->cap_m) b->tokens_m = b->cap_m;
    b->last_ms = now_ms;
    int ok = b->tokens_m >= 1000;
    if (ok) b->tokens_m -= 1000;                               /* one request costs 1 token */
    pthread_mutex_unlock(&b->mu);
    return ok;
}
int main(void) {
    bucket b = { 3000, 3000, 2, 0, PTHREAD_MUTEX_INITIALIZER };   /* starts full */
    long t[] = { 0, 0, 0, 0, 100, 400, 500, 900, 1000, 1000, 3000, 3000, 3000, 3000 };
    int n = sizeof t / sizeof t[0], passed = 0;
    for (int i = 0; i < n; i++) {
        int ok = allow(&b, t[i]); passed += ok;
        printf("t=%4ld ms  %s  tokens left=%ld.%03ld\n", t[i], ok ? "ALLOW" : "deny ", b.tokens_m / 1000, b.tokens_m % 1000);
    }
    printf("allowed %d of %d\n", passed, n);
}

t=   0 ms  ALLOW  tokens left=2.000
t=   0 ms  ALLOW  tokens left=1.000
t=   0 ms  ALLOW  tokens left=0.000
t=   0 ms  deny   tokens left=0.000
t= 100 ms  deny   tokens left=0.200
t= 400 ms  deny   tokens left=0.800
t= 500 ms  ALLOW  tokens left=0.000
t= 900 ms  deny   tokens left=0.800
t=1000 ms  ALLOW  tokens left=0.000
t=1000 ms  deny   tokens left=0.000
t=3000 ms  ALLOW  tokens left=2.000
t=3000 ms  ALLOW  tokens left=1.000
t=3000 ms  ALLOW  tokens left=0.000
t=3000 ms  deny   tokens left=0.000
allowed 8 of 14

• Thread-safety: refill আর খরচ — পড়া, হিসাব, লেখা — একটি read-modify-write; দুই থ্রেড একসাথে করলে দুজনেই শেষ টোকেনটি খরচ করে ফেলবে। তাই প্রতিটি বালতির নিজের mutex (বহু ব্যবহারকারী হলে প্রতি বালতিতে আলাদা lock, পুরো map-এর জন্য আরেকটি)। Lock-free রূপ: পুরো অবস্থা একটি ৬৪-বিট শব্দে ভরে CAS লুপ — সম্ভব, তবে প্রথম উত্তর হিসেবে mutex-ই ভালো।
• ঘড়ি: CLOCK_REALTIME নয় — NTP বা মানুষ ঘড়ি পিছিয়ে দিলে now − last ঋণাত্মক হবে। clock_gettime(CLOCK_MONOTONIC) ব্যবহার করুন, আর সময় কখনো পিছালে refill শূন্য ধরুন।
• অন্য কৌশল: fixed window (“এই মিনিটে ১০০টি” — মিনিটের সীমায় দ্বিগুণ burst হয়), sliding window log (নিখুঁত, কিন্তু প্রতি অনুরোধের সময় রাখতে হয়), leaky bucket (নির্দিষ্ট হারে বের করে, queue-তে রাখে)। Linux-এর tc-তে নেটওয়ার্ক traffic আকার দেওয়ার জন্য token bucket filter (tbf) আছে।
• জটিলতা: প্রতি অনুরোধ O(1), প্রতি বালতিতে O(1) মেমরি — এ কারণেই token bucket এত জনপ্রিয়।

৬ · মেমরি আর deadlock — memory pool আর ওয়ালেট ট্রান্সফার

সমস্যা ৯ · নির্দিষ্ট আকারের memory pool allocator (মাঝারি)

রিভিশন: পর্ব ৩৮ · Linux-এ মেমরি (slab), পর্ব ৩১ (fragmentation), পর্ব ৫৯ (নিজের malloc)

সমস্যা: “একটি নেটওয়ার্ক সার্ভার প্রতি সেকেন্ডে হাজার হাজার একই আকারের (ধরুন ৪৮ বাইট) struct বানায় আর মুছে। malloc-এর চেয়ে দ্রুত, fragmentation-হীন একটি memory pool লিখুন — pool_alloc() আর pool_free(p), দুটোই O(1).”

পদ্ধতি: একটি বড় array-কে সমান block-এ ভাগ করুন। খালি block-গুলো একটি একমুখী free list-এ যুক্ত — আর লিংকটি রাখা হয় block-এর ভেতরেই (খালি block-এর মেমরি তো অব্যবহৃত), তাই বাড়তি মেমরি শূন্য। Alloc = তালিকার মাথা তোলা, free = মাথায় বসানো — দুটোই O(1), একটি stack-এর মতো। union-এর alignas(max_align_t) নিশ্চিত করে প্রতিটি block যেকোনো ধরনের ডেটার জন্য যথেষ্ট aligned.

#include <stdalign.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
enum { BLK = 48, NBLK = 4 };
typedef union block {                 /* a FREE block keeps the "next" link inside itself */
    union block *next;
    alignas(max_align_t) unsigned char data[BLK];
} block;
static block arena[NBLK], *free_list;
static void pool_init(void) {
    for (int i = 0; i < NBLK - 1; i++) arena[i].next = &arena[i + 1];
    arena[NBLK - 1].next = NULL; free_list = &arena[0];
}
static void *pool_alloc(void) {       /* O(1): pop the head; NULL = pool exhausted */
    block *b = free_list; if (b) free_list = b->next; return b;
}
static void pool_free(void *p) {      /* O(1): push back on the head */
    block *b = p; b->next = free_list; free_list = b;
}
static int idx(void *p) { return p ? (int)((block *)p - arena) : -1; }
int main(void) {
    pool_init(); void *a[5];
    for (int i = 0; i < 5; i++) a[i] = pool_alloc();
    printf("5 allocs -> blocks %d %d %d %d %d (-1 = NULL)\n", idx(a[0]), idx(a[1]), idx(a[2]), idx(a[3]), idx(a[4]));
    pool_free(a[1]); pool_free(a[3]);
    void *x = pool_alloc(), *y = pool_alloc();
    printf("free 1, free 3 -> next allocs %d %d (LIFO reuse)\n", idx(x), idx(y));
    printf("block size %zu bytes, 16-byte aligned: %s\n", sizeof(block), (uintptr_t)x % 16 == 0 ? "yes" : "no");
}

5 allocs -> blocks 0 1 2 3 -1 (-1 = NULL)
free 1, free 3 -> next allocs 3 1 (LIFO reuse)
block size 48 bytes, 16-byte aligned: yes

• Thread-safety: সবচেয়ে সরল — একটি mutex দিয়ে alloc আর free ঘিরে দেওয়া। দ্রুততর: প্রতি-থ্রেড ছোট cache (glibc-র tcache বা jemalloc-এর thread cache-এর মতো) আর মাঝে মাঝে কেন্দ্রীয় pool থেকে একসাথে কয়েকটি আনা। Lock-free free list (CAS দিয়ে মাথা বদলানো) সম্ভব, কিন্তু সেখানে ABA সমস্যা ঠিক এই কাঠামোতেই দেখা দেয় — তাই tagged pointer বা hazard pointer লাগে।
• ফাঁদ: double free হলে একই block তালিকায় দুবার ঢোকে, পরে দুজন একই মেমরি পায় — নীরব দুর্নীতি। ডিবাগ build-এ প্রতিটি block-এ একটি “used” চিহ্ন বা magic সংখ্যা রাখুন, free-র সময় যাচাই করুন; pool-এর বাইরের পয়েন্টার free হচ্ছে কি না-ও দেখুন (ঠিকানা arena-র সীমার মধ্যে আর block-আকারের গুণিতকে)।
• বাস্তবে: এটিই slab allocator-এর মূল ধারণা — Jeff Bonwick ১৯৯৪ সালে SunOS-এর জন্য প্রকাশ করেন, আর Linux kernel-এর kmem_cache (SLUB) একই পথে চলে (পর্ব ৩৮)। Internal fragmentation শুধু তখন, যখন ব্যবহৃত struct block-এর চেয়ে ছোট।

সমস্যা ১০ · ওয়ালেট থেকে ওয়ালেটে টাকা — deadlock-মুক্ত transfer (মাঝারি)

রিভিশন: পর্ব ২৭ · Deadlock (চারটি শর্ত, lock hierarchy), DBMS · Concurrency control

সমস্যা: “একটি কাল্পনিক মোবাইল-ওয়ালেট অ্যাপ (bKash বা Nagad-ধাঁচের) — প্রতিটি ওয়ালেটে একটি mutex আর balance. transfer(from, to, amount) লিখুন, যা একসাথে হাজার থ্রেড থেকে ডাকা হবে: টাকা হারাবে না, balance ঋণাত্মক হবে না, আর কখনো deadlock হবে না।”

প্রথমে সবাই যা লেখেন — দেখতে ঠিক, অথচ বিপজ্জনক:

/* naive version -- looks right, can deadlock */
void transfer(wallet *from, wallet *to, long amount) {
    pthread_mutex_lock(&from->mu);      /* T1: lock A    T2: lock B   */
    pthread_mutex_lock(&to->mu);        /* T1: wants B   T2: wants A  -> stuck forever */
    if (from->balance >= amount) { from->balance -= amount; to->balance += amount; }
    pthread_mutex_unlock(&to->mu);
    pthread_mutex_unlock(&from->mu);
}

রহিম করিমকে টাকা পাঠাচ্ছেন (T1: A → B), আর একই মুহূর্তে করিম রহিমকে (T2: B → A). T1 A ধরে, T2 B ধরে, তারপর দুজনেই অন্যজনেরটির জন্য চিরকাল অপেক্ষা। ধাপে ধাপে দেখুন, আর সমাধানে কী বদলায়:

1// naive: lock(from); lock(to);2lock(&from->mu);3lock(&to->mu);      // may wait forever4// fixed: lower address first5first = min(from, to); second = max(from, to);6lock(&first->mu); lock(&second->mu);7check balance; move; unlock(second); unlock(first);

#include <pthread.h>
#include <stdio.h>

typedef struct { pthread_mutex_t mu; long balance; } wallet;
static wallet w[2] = { { PTHREAD_MUTEX_INITIALIZER, 5000 }, { PTHREAD_MUTEX_INITIALIZER, 5000 } };

static int transfer(wallet *from, wallet *to, long amount) {
    if (from == to) return 0;                       /* same wallet: never lock it twice */
    wallet *first  = from < to ? from : to;         /* global order: lower address first */
    wallet *second = from < to ? to : from;         /* (both are elements of one array) */
    pthread_mutex_lock(&first->mu);
    pthread_mutex_lock(&second->mu);
    int ok = from->balance >= amount;               /* check and move under BOTH locks */
    if (ok) { from->balance -= amount; to->balance += amount; }
    pthread_mutex_unlock(&second->mu);
    pthread_mutex_unlock(&first->mu);
    return ok;
}

static void *a_to_b(void *x) { (void)x; for (int i = 0; i < 200000; i++) transfer(&w[0], &w[1], 3); return NULL; }
static void *b_to_a(void *x) { (void)x; for (int i = 0; i < 200000; i++) transfer(&w[1], &w[0], 2); return NULL; }

int main(void) {
    pthread_t t1, t2;
    pthread_create(&t1, NULL, a_to_b, NULL); pthread_create(&t2, NULL, b_to_a, NULL);
    pthread_join(t1, NULL); pthread_join(t2, NULL);           /* returns => no deadlock */
    printf("both threads finished; total = %ld (started with 10000)\n", w[0].balance + w[1].balance);
    printf("no wallet negative: %s\n", w[0].balance >= 0 && w[1].balance >= 0 ? "yes" : "no");
    return 0;
}

both threads finished; total = 10000 (started with 10000)
no wallet negative: yes

• ঠিকানা তুলনার সূক্ষ্মতা: C-তে < দিয়ে দুটি পয়েন্টার তুলনা তখনই সংজ্ঞায়িত, যখন দুটি একই array-র ঘর — এখানে তাই। আলাদা malloc করা ওয়ালেট হলে প্রতিটি ওয়ালেটের একটি অনন্য id (অ্যাকাউন্ট নম্বর) দিয়ে ক্রম ঠিক করুন — এটিই বেশি পরিষ্কার, আর আলাদা সার্ভারেও কাজ করে। (uintptr_t)-এ রূপান্তর করে তুলনাও বাস্তবে চলে।
• from == to: একই non-recursive mutex দুবার নিলে থ্রেড নিজেই নিজেকে আটকায়। তাই শুরুতে আলাদা কেস।
• অন্য পথ: pthread_mutex_trylock দিয়ে দ্বিতীয়টি চেষ্টা — না পেলে প্রথমটি ছেড়ে কিছুক্ষণ পরে আবার (backoff); এতে deadlock নেই, কিন্তু livelock-এর ঝুঁকি। বা একটি global lock — সঠিক, কিন্তু সব transfer এক লাইনে। ডেটাবেসে একই সমস্যা transaction-এর lock-এ হয়, আর DBMS সাধারণত deadlock ধরে একটি transaction বাতিল করে।
• বাস্তবে: Linux kernel-এ একসাথে দুটি একই ধরনের lock নিতে হলে (যেমন দুটি runqueue) একটি নির্দিষ্ট ক্রম মানা হয়, আর lockdep টুল চালানোর সময় lock-ক্রমের লঙ্ঘন ধরে (পর্ব ২৭)। User space-এ TSan-ও “lock-order-inversion” সতর্কবার্তা দেয়।

৭ · System call-এর কোড — cp আর ls | wc -l

সমস্যা ১১ · cp লিখুন — partial write আর EINTR সামলে (মাঝারি)

রিভিশন: পর্ব ৪১ · File descriptor, open/read/write, পর্ব ১৩ · Signal

সমস্যা: “শুধু open, read, write, close দিয়ে একটি ফাইল কপি করুন। যেকোনো আকারের ফাইল, আর কোনো বাইট হারাবে না।” সহজ মনে হয় — কিন্তু ইন্টারভিউয়ার দেখতে চান আপনি জানেন যে write চাওয়ার চেয়ে কম লিখতে পারে, আর signal এসে read/write-কে বাধা দিতে পারে।

পদ্ধতি: দুটি লুপ। বাইরের লুপ: read যত বাইট দেয় (r), r == 0 মানে EOF. ভেতরের write_all: যতক্ষণ বাকি থাকে, write; যা লেখা হলো ততটুকু সরে যান — একে বলে short write সামলানো। দুই জায়গাতেই −১ আর errno == EINTR হলে শুধু আবার চেষ্টা; অন্য ত্রুটিতে থামুন। শেষে close-এর ফেরত মানও দেখুন — কিছু ফাইল সিস্টেম (যেমন NFS) লেখার ত্রুটি সেখানে জানায়।

#include <errno.h>
#include <fcntl.h>
#include <stdio.h>
#include <unistd.h>
static int write_all(int fd, const char *p, size_t n) {
    while (n > 0) {
        ssize_t w = write(fd, p, n);
        if (w < 0) { if (errno == EINTR) continue; return -1; }   /* interrupted: retry */
        p += w; n -= (size_t)w;                                    /* short write: go on */
    }
    return 0;
}
static long copy_fd(int in, int out) {
    char buf[4096]; long total = 0;
    for (;;) {
        ssize_t r = read(in, buf, sizeof buf);
        if (r == 0) return total;                                  /* EOF */
        if (r < 0) { if (errno == EINTR) continue; return -1; }
        if (write_all(out, buf, (size_t)r) < 0) return -1;
        total += r;
    }
}
int main(void) {
    static char big[100000]; int p[2]; pipe(p); fcntl(p[1], F_SETFL, O_NONBLOCK);  /* nobody reads p[0] */
    printf("one write() of %zu bytes into a pipe returned %zd\n", sizeof big, write(p[1], big, sizeof big));
    int src = open("src.txt", O_WRONLY | O_CREAT | O_TRUNC, 0644); write_all(src, big, sizeof big); close(src);
    int in = open("src.txt", O_RDONLY), out = open("dst.txt", O_WRONLY | O_CREAT | O_TRUNC, 0644);
    long n = copy_fd(in, out); int rc = close(out); close(in);      /* close() can report errors too */
    printf("copied %ld bytes, close(out) = %d\n", n, rc);
}

one write() of 100000 bytes into a pipe returned 65536
copied 100000 bytes, close(out) = 0

• EINTR কখন আসে: একটি signal handler চলার সময় যদি থ্রেডটি ধীর কোনো system call-এ (pipe, socket, terminal থেকে read) আটকে থাকে, kernel কলটি ফিরিয়ে দেয় −১ আর EINTR দিয়ে — অথবা handler SA_RESTART দিয়ে বসানো হলে অনেক কল নিজে আবার শুরু হয় (পর্ব ১৩)। কোন কল restart হয়, তা OS আর কলভেদে আলাদা — তাই নির্ভরযোগ্য কোড দুই ক্ষেত্রেই কাজ করে।
• Buffer-এর আকার: ৪ KiB কাজ করে; ৬৪–১২৮ KiB-এ system call কম লাগে। আরও দ্রুত: Linux-এ copy_file_range বা sendfile — ডেটা user space-এ না এনে kernel-এর ভেতরেই কপি, কিছু ফাইল সিস্টেমে (যেমন Btrfs, XFS) নতুন kernel-এ ব্লক ভাগাভাগি করেও (reflink) কপি হতে পারে।
• সত্যিই ডিস্কে? write সফল মানে ডেটা page cache-এ পৌঁছেছে, ডিস্কে নয়। বিদ্যুৎ গেলে হারাতে পারে। নিশ্চিত হতে fsync(out), আর নিরাপদ “replace” করতে অস্থায়ী নামে লিখে fsync, তারপর rename (পর্ব ৪১, ৪৪)।
• জটিলতা: O(n) বাইট, O(n / buffer) system call; মেমরি O(buffer).

সমস্যা ১২ · Shell-এর মতো ls | wc -l চালান — fork, pipe, dup2 (মাঝারি)

রিভিশন: পর্ব ১০ · fork, exec আর wait, পর্ব ১১ · Shell, পর্ব ১২ · Pipe

সমস্যা: “একটি C প্রোগ্রাম লিখুন, যা shell-এর মতো ls demo | wc -l চালায়: প্রথম প্রোগ্রামের stdout যাবে দ্বিতীয়টির stdin-এ, আর parent দুজনের শেষের অপেক্ষা করবে।” এটি ছোট একটি shell-এর হৃদয় (পর্ব ৫৯-এর ক্যাপস্টোন)।

পদ্ধতি: (১) pipe(fd) — fd[0] পড়ার মুখ, fd[1] লেখার মুখ। (২) প্রথম child: dup2(fd[1], 1) — stdout এখন pipe; তারপর দুটি মুখই বন্ধ, তারপর exec. (৩) দ্বিতীয় child: dup2(fd[0], 0), দুটি মুখ বন্ধ, exec. (৪) Parent: দুটি মুখ বন্ধ, তারপর দুজনকে waitpid. fork-এর আগে fflush(stdout) — নইলে parent-এর buffer-এ থাকা লেখা child-এর কপিতেও থাকে আর দুবার ছাপা হতে পারে।

#include <stdio.h>
#include <sys/stat.h>
#include <sys/wait.h>
#include <unistd.h>

int main(void) {
    mkdir("demo", 0755);                                   /* a folder with exactly 3 files */
    const char *names[] = { "demo/a.txt", "demo/b.txt", "demo/c.txt" };
    for (int i = 0; i < 3; i++) { FILE *f = fopen(names[i], "w"); if (f) fclose(f); }

    int fd[2];
    if (pipe(fd) < 0) { perror("pipe"); return 1; }
    fflush(stdout);                                        /* nothing buffered gets copied by fork */
    pid_t left = fork();
    if (left == 0) {                                       /* child 1: ls demo  -> pipe */
        dup2(fd[1], STDOUT_FILENO); close(fd[0]); close(fd[1]);
        execlp("ls", "ls", "demo", (char *)NULL); perror("exec ls"); _exit(127);
    }
    pid_t right = fork();
    if (right == 0) {                                      /* child 2: pipe -> wc -l */
        dup2(fd[0], STDIN_FILENO); close(fd[0]); close(fd[1]);
        execlp("wc", "wc", "-l", (char *)NULL); perror("exec wc"); _exit(127);
    }
    close(fd[0]); close(fd[1]);                            /* parent: else wc never sees EOF */
    int s1, s2;
    waitpid(left, &s1, 0); waitpid(right, &s2, 0);
    printf("ls exit = %d, wc exit = %d\n", WEXITSTATUS(s1), WEXITSTATUS(s2));
    return 0;
}

3
ls exit = 0, wc exit = 0

• সবচেয়ে সাধারণ বাগ — মুখ খোলা রাখা: wc থামে তখনই, যখন pipe-এর সব লেখার মুখ বন্ধ হয় (তখন সে EOF পায়)। Parent বা দ্বিতীয় child যদি fd[1] খোলা রাখে, wc চিরকাল অপেক্ষা করবে আর parent-এর waitpid-ও। নিয়ম: যে প্রসেসের যে মুখ লাগে না, সেটি সঙ্গে সঙ্গে বন্ধ।
• উল্টো দিক: পড়ার সব মুখ বন্ধ থাকলে লেখক SIGPIPE পায় (ডিফল্টে মারা যায়) — yes | head -1 এভাবেই থামে।
• exec-এর পরে কোড: exec সফল হলে আর ফেরে না; তাই তার পরের লাইন শুধু ব্যর্থতায় চলে — perror আর _exit(127) (127 = “কমান্ড পাওয়া যায়নি”-র প্রচলিত কোড)। Child-এ exit নয়, _exit — যাতে parent থেকে কপি হওয়া stdio buffer আবার flush না হয়।
• N কমান্ডের pipeline: N−১টি pipe; i-তম child আগের pipe-এর পড়ার মুখ stdin-এ আর পরের pipe-এর লেখার মুখ stdout-এ নেয়; প্রতিটি প্রসেসে বাকি সব মুখ বন্ধ। File descriptor ফাঁস রোধে pipe2(fd, O_CLOEXEC) দারুণ (Linux). Windows-এ fork নেই — CreatePipe আর CreateProcess-এ handle উত্তরাধিকার দিয়ে একই কাজ হয়।

৮ · ডিজাইন আর ডিবাগ — timer scheduler আর racy কোডের বাগ

সমস্যা ১৩ · Timer scheduler — “এত মিলিসেকেন্ড পরে এই ফাংশন চালানো” (কঠিন, ডিজাইন)

রিভিশন: DSA · Heap, পর্ব ২৫, পর্ব ৪ (timer interrupt)

সমস্যা: “schedule(delay_ms, fn, arg) লিখুন — যেকোনো থ্রেড থেকে ডাকা যাবে, আর delay পেরোলে fn(arg) চলবে। হাজার হাজার টাইমার একসাথে থাকতে পারে।” এটি সাধারণত কোড-আর-আলোচনা মিশ্র প্রশ্ন: ইন্টারভিউয়ার data structure, থ্রেড-মডেল আর ঘড়ির পছন্দ শুনতে চান।

নকশা: (১) Data structure: deadline অনুযায়ী min-heap — সবচেয়ে কাছের টাইমার O(1)-এ দেখা, যোগ আর তোলা O(log n). (২) একটি timer thread: heap খালি হলে cond_wait; নইলে সবচেয়ে কাছের deadline পর্যন্ত pthread_cond_timedwait. (৩) নতুন টাইমার heap-এ ঢুকিয়ে signal — কারণ সেটি হয়তো এখনকার ঘুমের চেয়ে আগের। (৪) Callback চলে lock ছেড়ে — নইলে callback ভেতর থেকে schedule ডাকলে নিজেকেই আটকাবে, আর ধীর callback সবাইকে আটকাবে। (৫) ঘড়ি: condition variable-কে CLOCK_MONOTONIC-এ বাঁধা — ডিফল্ট CLOCK_REALTIME, যা NTP বা ব্যবহারকারী বদলালে লাফায়।

#include <pthread.h>
#include <stdio.h>
#include <time.h>

typedef void (*callback)(void *);
typedef struct { long long due_ns; callback fn; void *arg; } timer;

enum { MAXT = 64 };
static timer heap[MAXT]; static int nheap;          /* min-heap ordered by due_ns */
static pthread_mutex_t mu = PTHREAD_MUTEX_INITIALIZER;
static pthread_cond_t cv;                            /* uses CLOCK_MONOTONIC, see init */
static int stopping;

static long long now_ns(void) {
    struct timespec ts; clock_gettime(CLOCK_MONOTONIC, &ts);
    return ts.tv_sec * 1000000000LL + ts.tv_nsec;
}
static void swap(int i, int j) { timer t = heap[i]; heap[i] = heap[j]; heap[j] = t; }
static void sift_up(int i) { while (i > 0 && heap[(i - 1) / 2].due_ns > heap[i].due_ns) { swap(i, (i - 1) / 2); i = (i - 1) / 2; } }
static void sift_down(int i) {
    for (;;) {
        int l = 2 * i + 1, r = l + 1, m = i;
        if (l < nheap && heap[l].due_ns < heap[m].due_ns) m = l;
        if (r < nheap && heap[r].due_ns < heap[m].due_ns) m = r;
        if (m == i) return;
        swap(i, m); i = m;
    }
}

/* returns 0 on success, -1 if the heap is full */
int schedule(long delay_ms, callback fn, void *arg) {
    pthread_mutex_lock(&mu);
    if (nheap == MAXT) { pthread_mutex_unlock(&mu); return -1; }
    heap[nheap] = (timer){ now_ns() + delay_ms * 1000000LL, fn, arg };
    sift_up(nheap++);
    pthread_cond_signal(&cv);           /* the earliest deadline may have changed */
    pthread_mutex_unlock(&mu);
    return 0;
}

static void *timer_thread(void *unused) {
    pthread_mutex_lock(&mu);
    for (;;) {
        while (!stopping && nheap == 0) pthread_cond_wait(&cv, &mu);
        if (stopping) break;
        long long due = heap[0].due_ns;
        if (now_ns() < due) {                           /* sleep until the earliest deadline */
            struct timespec ts = { due / 1000000000LL, due % 1000000000LL };
            pthread_cond_timedwait(&cv, &mu, &ts);      /* may wake early: loop re-checks */
            continue;
        }
        timer t = heap[0]; heap[0] = heap[--nheap]; sift_down(0);
        pthread_mutex_unlock(&mu);
        t.fn(t.arg);                                    /* run the callback WITHOUT the lock */
        pthread_mutex_lock(&mu);
    }
    pthread_mutex_unlock(&mu);
    return unused;
}

static void say(void *s) { printf("fired: %s\n", (const char *)s); fflush(stdout); }

int main(void) {
    pthread_condattr_t ca; pthread_condattr_init(&ca);
    pthread_condattr_setclock(&ca, CLOCK_MONOTONIC);    /* wall-clock jumps do not matter */
    pthread_cond_init(&cv, &ca);
    pthread_t th; pthread_create(&th, NULL, timer_thread, NULL);
    schedule(300, say, "C (300 ms)");
    schedule(100, say, "A (100 ms)");
    schedule(200, say, "B (200 ms)");
    schedule(0, say, "now (0 ms)");
    struct timespec half = { 0, 450000000L }; nanosleep(&half, NULL);
    pthread_mutex_lock(&mu); stopping = 1; pthread_cond_signal(&cv); pthread_mutex_unlock(&mu);
    pthread_join(th, NULL);
    printf("pending timers left: %d\n", nheap);
    return 0;
}

এই পূর্ণ সংস্করণটি একই অনলাইন রানারে (Linux, gcc, -Wall -Wextra, কোনো warning নেই) দুবার চালিয়ে প্রতিবার একই ফল পাওয়া গেছে — চারটি টাইমার উল্টোপাল্টা ক্রমে যোগ করা হলেও deadline-এর ক্রমে চলেছে, আর shutdown-এ কিছু বাকি থাকেনি:

fired: now (0 ms)
fired: A (100 ms)
fired: B (200 ms)
fired: C (300 ms)
pending timers left: 0

• সঠিকতার মূল: timedwait থেকে যেকোনো কারণে ফেরা (timeout, signal, spurious) — লুপ আবার heap-এর মাথা দেখে। তাই “কেন জাগলাম” জানার দরকার নেই; প্রতিবার শুধু invariant: “heap-এর মাথা সবচেয়ে কাছের deadline”. ফল নির্ধারিত রাখতে টাইমারগুলোর মধ্যে ১০০ ms ফাঁক রাখা হয়েছে — একই মুহূর্তের দুটি deadline-এর ক্রম heap নিশ্চিত করে না (ক্রম লাগলে একটি sequence নম্বর দিয়ে tie ভাঙুন)।
• Cancel: heap-এর মাঝ থেকে মোছা কঠিন; সাধারণ কৌশল “lazy” — টাইমারে একটি cancelled চিহ্ন, তোলার সময় বাদ। নয়তো প্রতিটি টাইমার heap-এ নিজের index মনে রাখে, যাতে O(log n)-এ মোছা যায়।
• বিপুল টাইমার: লাখ লাখ timeout (যেমন প্রতিটি TCP সংযোগের) হলে timing wheel — ঘড়ির কাঁটার মতো স্লটের বৃত্ত, প্রতি স্লটে একটি তালিকা, যোগ-মোছা O(1). Linux kernel-এর সাধারণ timer এমন চাকার কাঠামো ব্যবহার করে, আর উচ্চ-নির্ভুলতার hrtimer একটি red-black tree. libuv (Node.js-এর নিচে) টাইমার রাখে একটি min-heap-এ।
• OS-এর বিকল্প: Linux-এ timerfd_create টাইমারকে একটি file descriptor বানায়, যা epoll-এ অন্য I/O-র সাথে অপেক্ষা করা যায়; POSIX timer_create signal বা থ্রেড দিয়ে জানায়; Windows-এ thread-pool timer (CreateThreadpoolTimer).

সমস্যা ১৪ · বাগ খুঁজুন — তিনটি racy কোড (মাঝারি থেকে কঠিন)

রিভিশন: পর্ব ২২ · Race condition, পর্ব ২৫, পর্ব ২৩, পর্ব ২৯

সমস্যা: ইন্টারভিউয়ার কোড দেখিয়ে বলেন, “এটি production-এ মাঝে মাঝে ভুল ফল দেয়। কোথায় বাগ, কোন interleaving-এ ঘটে, আর কীভাবে সারাবেন?” উত্তরের তিন অংশই চাই: বাগের নাম, একটি নির্দিষ্ট খারাপ ক্রম, আর সমাধান। প্রতিটি কোড দেখে আগে নিজে উত্তর ভাবুন, তারপর ভাঁজ খুলুন।

/* Bug 1: lost update -- two threads call deposit() at the same time */
static long balance;
void deposit(long amount) {
    long old = balance;          /* load              */
    balance = old + amount;      /* add + store: another deposit in between is lost */
}

/* Bug 2: "if" instead of "while" -- two consumers share one queue */
int take(void) {
    pthread_mutex_lock(&mu);
    if (count == 0)                           /* checked only once */
        pthread_cond_wait(&not_empty, &mu);
    int x = buf[head]; head = (head + 1) % CAP; count--;   /* count may be 0 here! */
    pthread_mutex_unlock(&mu);
    return x;
}

/* Bug 3: broken double-checked locking */
static config *instance;                      /* plain pointer, no atomics */
config *get_config(void) {
    if (instance == NULL) {                   /* 1st check without the lock: a data race */
        pthread_mutex_lock(&mu);
        if (instance == NULL) {
            config *c = malloc(sizeof *c);
            c->ready_value = 42;              /* these stores may become visible ...   */
            instance = c;                     /* ... AFTER this one on another core     */
        }
        pthread_mutex_unlock(&mu);
    }
    return instance;                          /* may see a pointer to unfinished data */
}

/* Fix A: C11 atomics with acquire / release (tested on Wandbox) */
static config *get_config(void) {
    config *c = atomic_load_explicit(&instance, memory_order_acquire);   /* fast path */
    if (c == NULL) {
        pthread_mutex_lock(&mu);
        c = atomic_load_explicit(&instance, memory_order_relaxed);       /* check again */
        if (c == NULL) {
            c = malloc(sizeof *c); c->ready_value = 42; inits++;
            atomic_store_explicit(&instance, c, memory_order_release);   /* publish */
        }
        pthread_mutex_unlock(&mu);
    }
    return c;
}

/* Fix B: usually the best answer -- let the library do it once */
static pthread_once_t once = PTHREAD_ONCE_INIT;
static config *cfg2; static atomic_int inits2;
static void init2(void) { cfg2 = malloc(sizeof *cfg2); cfg2->ready_value = 42; inits2++; }
static config *get_config2(void) { pthread_once(&once, init2); return cfg2; }

Fix A-তে acquire load আর release store একটি জোড়া: যে থ্রেড release-এ লেখা পয়েন্টার acquire-এ পড়ে, সে তার আগের সব লেখাও (ready_value = 42) দেখবে। Fix B আরও ভালো — pthread_once (বা C11-এর call_once) নিজেই এই নিশ্চয়তা দেয়, আর ভুলের জায়গা নেই। ইন্টারভিউতে প্রথমে Fix B বলুন, তারপর দেখান আপনি Fix A-ও বোঝেন।

৯ · কোন সমস্যায় কোন primitive — চিটশিট আর ভাবনার প্রশ্ন

নিচের টেবিল ইন্টারভিউর আগের রাতের রিভিশনের জন্য। বাঁ কলামের ইঙ্গিত সমস্যার বিবরণে দেখলে মাঝের primitive প্রথমে ভাবুন — তবে এটি শুরুর দিকনির্দেশ, নিশ্চিত নিয়ম নয়।

ভাবনার প্রশ্ন

কোড লেখার পরে আলোচনায় প্রায়ই এ ধরনের গভীর প্রশ্ন আসে। প্রতিটি আগে নিজে ভাবুন, তারপর খুলুন।

১০ · AI দিয়ে প্রস্তুতি — mock interview আর race-এর পরীক্ষা

প্রস্তুতির সময় AI একটি ভালো mock-interview সঙ্গী — শর্ত একটাই: উত্তর নয়, প্রশ্ন আর মূল্যায়ন চাইবেন। আর মনে রাখবেন, concurrency-তে AI-এর ভুল প্রায়ই আত্মবিশ্বাসী শোনায়, আর তার কোড “আমার মেশিনে চলে”:

নিজের বা AI-এর লেখা concurrent কোড যাচাইয়ের পদ্ধতি এই পাতার প্রোগ্রামগুলোর মতোই: ফলকে এমন রূপে আনুন যা interleaving-এর ওপর নির্ভর করে না (মোট, গণনা, invariant-ভঙ্গের সংখ্যা), থ্রেড আর পুনরাবৃত্তি বাড়ান, gcc -fsanitize=thread -g -O1 দিয়ে চালান, আর একটি বাগ ইচ্ছা করে ঢুকিয়ে (lock সরিয়ে, while-কে if করে) দেখুন আপনার পরীক্ষা সেটি ধরে কি না — না ধরলে পরীক্ষাটাই দুর্বল।

AI দিয়ে অনুশীলনের চেকলিস্ট

• সমাধান দেখার আগে নিজে অন্তত ২০ মিনিট চেষ্টা করেছি, আর shared state ও invariant খাতায় লিখেছি
• AI-এর কোডের প্রতিটি shared ভ্যারিয়েবলের জন্য বলতে পারি কোন lock তাকে রক্ষা করে, আর প্রতিটি wait while-এ
• অন্তত একটি খারাপ interleaving নিজে হাতে ট্রেস করেছি, আর একাধিক lock থাকলে ক্রম মিলিয়েছি
• -fsanitize=thread দিয়ে, core-এর চেয়ে বেশি থ্রেডে, লাখবার চালিয়ে কোনো সতর্কবার্তা পাইনি
• প্রতিটি system call-এর ফেরত মান, short read/write আর EINTR সামলানো হয়েছে কি না দেখেছি; API আমার OS-এর man page-এ মিলিয়েছি
• একদিন পরে AI ছাড়া একই সমস্যা শূন্য থেকে লিখে পাঁচ মিনিটে জোরে ব্যাখ্যা করতে পারি