Race Condition ও Deadlock — যখন সমান্তরালতা ভুল হয়ে যায়

Mutual exclusion ভাঙলে: যদি একটা resource একসাথে একাধিক thread ব্যবহার করতে পারে (যেমন read-only ডেটা, বা একটা semaphore যার count > 1), তাহলে কোনো thread-কে সেই resource-এর জন্য চিরকাল অপেক্ষা করতে হয় না — সে যখনই চায় (capacity থাকা পর্যন্ত) resource পেতে পারে। Hold-and-wait ঘটতেই পারে না যদি wait-এর কোনো কারণই না থাকে।

Hold-and-wait ভাঙলে: যদি একটা thread একবারে সব প্রয়োজনীয় resource চায় (একসাথে, atomically, “সব পাবো নাহলে কিছুই না”), তাহলে সে কখনো একটা resource ধরে রেখে আরেকটার জন্য অপেক্ষা করে না। হয় সে সাথে সাথে সব পায় (progress), নয় কিছুই পায় না (কিন্তু তখন সে কিছুই ধরেও নেই, তাই কারো পথে বাধা দিচ্ছে না)।

/* একবারে সব lock নেওয়া — trylock দিয়ে */
if (pthread_mutex_trylock(&A) == 0) {
    if (pthread_mutex_trylock(&B) == 0) {
        /* কাজ করুন */
        pthread_mutex_unlock(&B);
    }
    pthread_mutex_unlock(&A);
}
/* B না পেলে A-ও ছেড়ে দিন, retry করুন — কখনো ধরে রেখে অপেক্ষা নয় */

No preemption ভাঙলে: যদি একটা thread-এর কাছ থেকে জোর করে resource কেড়ে নেওয়া যায় (একটা timeout-এর পর, বা একটা higher- priority thread-এর জন্য), তাহলে একটা “চিরকাল অপেক্ষা” অবস্থা টিকতে পারে না — এক পর্যায়ে সিস্টেম হস্তক্ষেপ করে অবস্থা ভেঙে দেবে। Database-এর deadlock detector ঠিক এটাই করে — একটা transaction-কে জোর করে rollback করে তার lock ছেড়ে দিতে বাধ্য করে।

Circular wait ভাঙলে (এই লেসনের মূল কৌশল): যদি সব resource request একটা total order মেনে চলে (সবসময় নিচু-rank আগে), তাহলে wait-for graph-এ প্রতিটা edge শুধু “কম rank → বেশি rank” দিকে যায়। একটা directed graph যেখানে প্রতিটা edge একটা strictly increasing quantity-র দিকে যায়, সেখানে cycle থাকতে পারে না — কারণ cycle-এ ফিরে আসতে হলে কোনো এক পর্যায়ে “বেশি → কম” যেতে হবে, যা নিয়ম ভাঙে। এটাই একটা formal প্রমাণ, শুধু অন্তর্জ্ঞান নয় (Level 0-এর well-ordering principle-এর সরাসরি প্রয়োগ)।

সাধারণ প্যাটার্ন: চারটা প্রমাণই একই কাঠামো অনুসরণ করে — প্রতিটাতে দেখানো হয় “শর্তটা ভাঙলে, deadlock-এর সংজ্ঞার জন্য প্রয়োজনীয় একটা উপাদান অনুপস্থিত থাকে, তাই deadlock-এর সংজ্ঞাই পূরণ হয় না”। এটাই কেন চারটা শর্ত প্রয়োজনীয় (necessary) — deadlock ঘটতে চারটাই লাগে, একটা কম হলেও চলবে না।

এটা একটা data race, আর এটা একটা race condition-ও — দুইটাই, এবং একটা সূক্ষ্ম কারণে দ্বিতীয় সমস্যাও আছে।

Data race: shared_flag-এ একটা thread write করছে (writer), আরেকটা read করছে (reader), কোনো synchronization primitive (mutex, atomic) ছাড়া। C11-এর সংজ্ঞা অনুযায়ী এটা সরাসরি data race — এবং তাই undefined behaviour।

Compiler কী করতে পারে (বাস্তবিক পরিণতি):

reader()-এ compiler দেখতে পারে shared_flag এই function-এর মধ্যে কখনো বদলায় না (কোনো write নেই এই function-এর ভেতরে), তাই সে অনুমান করে নিতে পারে এটা loop-এর বাইরে একবার পড়লেই যথেষ্ট, বারবার memory থেকে পড়ার দরকার নেই — আর পুরো while loop-টাকে হয় একটা infinite loop-এ পরিণত করতে পারে (যদি প্রথম read 0 দেয়), অথবা সম্পূর্ণ বাদ দিতে পারে (যদি অন্য কোনো প্রমাণে মনে করে এটা সবসময় true)। এটা কাল্পনিক নয় — বাস্তব compiler optimization-এ এই ধরনের ঘটনা রিপোর্ট হয়েছে।

দ্বিতীয় সমস্যা, এমনকি যদি atomic_int ব্যবহার করা হতো:

ধরুন shared_flag-কে atomic_int করা হলো। তাহলে data race-টা সমাধান হয়ে যায় — compiler আর এই optimization করতে পারবে না। কিন্তু একটা memory ordering প্রশ্ন থেকে যায়: write_important_data()-এর লেখা কি নিশ্চিতভাবে reader()-এ use_important_data() চালানোর আগে দৃশ্যমান?

Default atomic operation (C11-এ memory_order_seq_cst) এই নিশ্চয়তা দেয় — shared_flag = 1 লেখার আগের সব write “happens-before” সম্পর্কে shared_flag == 1 পড়ার পরের কোডের আগে দৃশ্যমান হবে। কিন্তু যদি কেউ কম কঠোর memory order (memory_order_relaxed) ব্যবহার করত, শুধু flag নিজে সঠিকভাবে দেখা যেত, কিন্তু write_important_data()-এর প্রভাব এখনো পুরনো (stale) দেখা যেতে পারত — যদিও flag বলছে “রেডি”।

সঠিক সমাধান:

#include <stdatomic.h>
atomic_int shared_flag = 0;

void writer(void) {
    write_important_data();
    atomic_store_explicit(&shared_flag, 1, memory_order_release);
}

void reader(void) {
    while (atomic_load_explicit(&shared_flag, memory_order_acquire) == 0) {}
    use_important_data();
}

release/acquire জোড়া নিশ্চিত করে: writer-এর store-এর আগের সব write, reader-এর load-এর পরের সব read-এর কাছে দৃশ্যমান — ঠিক যা দরকার, seq_cst-এর চেয়ে সস্তা।

Level 11-এ আমরা memory ordering আর MESI cache coherence protocol বিস্তারিত দেখব — এই প্রশ্নটার সম্পূর্ণ hardware-স্তরের ব্যাখ্যা সেখানে।

এখানে “সবসময় lower-address আগে” পদ্ধতিটা প্রযোজ্য (node-এর memory address বা একটা persistent ID দিয়ে rank করা যায়, node সংখ্যা যত বড়ই হোক), কিন্তু আরো তিনটা বাস্তবসম্মত বিকল্প আছে, আর সবচেয়ে ভালো সমাধান সাধারণত একাধিক কৌশলের মিশ্রণ।

বিকল্প ১ — Node ID দিয়ে total order (সহজ, কিন্তু সীমাবদ্ধ)।

নিয়ম: যদি traversal-এ node A আর B দুটোই lock করতে হয়,
সবসময় ছোট node-ID আগে lock করুন — traversal-এর প্রকৃত ক্রম যাই হোক

সমস্যা: এতে graph traversal-এর স্বাভাবিক ক্রম ভাঙতে হয় (আগে জানতে হবে কোন node-গুলো লাগবে, তারপর সাজিয়ে lock নিতে হবে) — যা অনেক algorithm-এর জন্য অস্বাভাবিক (traversal প্রায়ই adaptive, আগে থেকে জানা যায় না কোন node দরকার হবে)।

বিকল্প ২ — Try-lock + backoff (হার্ডওয়্যার lock-free অ্যালগরিদমেও ব্যবহৃত)।

Ordering মানার বদলে, কখনো ব্লক করবেন না — শুধু চেষ্টা করুন, ব্যর্থ হলে সব ছেড়ে দিয়ে পরে আবার চেষ্টা করুন:

while (1) {
    if (try_lock(node_a)) {
        if (try_lock(node_b)) {
            /* উভয়ই পেয়েছি — কাজ করুন, তারপর release */
            break;
        }
        unlock(node_a);   /* B না পেলে A-ও ছেড়ে দিন */
    }
    random_backoff();      /* একটু অপেক্ষা, retry storm এড়াতে */
}

এটা Coffman-এর hold-and-wait শর্ত ভাঙে — কখনো একটা lock ধরে রেখে অন্যটার জন্য ব্লক করা হচ্ছে না। Livelock-এর সামান্য ঝুঁকি থাকে (দুই thread বারবার একে অপরকে ব্যর্থ করে দিতে পারে), তাই random exponential backoff জরুরি — নেটওয়ার্কের collision avoidance-এর মতোই একই নীতি (Level 7-এ Ethernet-এ এই একই কৌশল দেখব)।

বিকল্প ৩ — Timeout-সহ lock, আর transaction abort/retry।

if (pthread_mutex_timedlock(&node_lock, &timeout) == ETIMEDOUT) {
    rollback_transaction();
    retry_with_backoff();
}

এটা Coffman-এর no preemption শর্ত ভাঙে — timeout মানে কার্যকরভাবে একটা resource জোর করে ছেড়ে দিতে বাধ্য করা। এটাই বেশিরভাগ প্রকৃত graph database (Neo4j-এর মতো) ব্যবহার করে — deadlock detection-এর বদলে timeout-ভিত্তিক abort, কারণ detection-এর জটিলতা (একটা distributed graph-এ প্রতিটা node-এর lock-order ট্র্যাক করা) ব্যবহারিকভাবে costly।

বিকল্প ৪ — Optimistic concurrency control, লক-ই এড়ানো।

সবচেয়ে র‍্যাডিক্যাল সমাধান: lock না নিয়ে, প্রতিটা node-এ একটা version number রাখা। Transaction পড়ে, কাজ করে, তারপর commit করার সময় যাচাই করে কোনো version বদলেছে কি না — বদলালে পুরো transaction retry। এটা read-heavy workload-এ চমৎকার কাজ করে, কিন্তু write-heavy-তে অনেক retry হতে পারে। Level 8-এ MVCC (Multi-Version Concurrency Control) হিসেবে এটা database-এর প্রধান কৌশল হিসেবে বিস্তারিত দেখব।

বাস্তব সুপারিশ: ছোট, predictable lock set-এ (২-৩টা node) বিকল্প ১ বা ২ ব্যবহার করুন। বড়, unpredictable traversal-এ বিকল্প ৩ বা ৪ — deadlock prevent করার চেষ্টার বদলে, deadlock হলে দ্রুত সনাক্ত করে সহজে recover করার নকশা করাই বাস্তবসম্মত এই স্কেলে।

সমস্যা: file_exists, is_owned_by_user, delete_file — তিনটা আলাদা syscall, তিনটা আলাদা মুহূর্ত। এই মুহূর্তগুলোর মাঝখানে attacker path-কে অন্য কোনো ফাইলে (symlink দিয়ে) redirect করতে পারে — check হয়েছিল একটা ফাইলে, delete হবে অন্য একটায়।

/* বিপজ্জনক ধারণা: */
/* t=0: check হচ্ছে "myfile.txt" — ব্যবহারকারীর নিজের ফাইল */
/* t=1: attacker path-কে symlink দিয়ে /etc/shadow-এ পরিবর্তন করে */
/* t=2: delete_file(path) আসলে /etc/shadow মুছে ফেলে */

সঠিক সমাধান — fd-স্তরে কাজ করা, path-স্তরে বারবার নয়:

int fd = open(path, O_RDONLY | O_NOFOLLOW);
if (fd < 0) {
    /* symlink হলে বা না পেলে এখানেই থেমে যায় */
    return -1;
}

struct stat st;
fstat(fd, &st);              /* fd-র উপর stat — এখন race-মুক্ত,
                                 কারণ fd একটা নির্দিষ্ট inode-কে
                                 আটকে রেখেছে, path আর প্রাসঙ্গিক নয় */

if (st.st_uid != getuid()) {
    close(fd);
    return -1;                /* মালিক নয় — প্রত্যাখ্যান */
}

/* এখন delete-ও fd-নির্ভর করা উচিত, কিন্তু POSIX-এ unlink()
   সরাসরি fd নেয় না — তাই unlinkat() ব্যবহার করা হয় directory
   fd-র সাথে, যা directory-স্তরের race-ও কমায় */
close(fd);
unlink(path);   /* এখনো path-based, কিন্তু আমরা আগেই যাচাই করে
                    ফেলেছি — সম্পূর্ণ atomic নয়, কিন্তু windows
                    অনেক ছোট */

আরো শক্তিশালী — openat() + unlinkat() একই directory fd দিয়ে:

int dirfd = open(dirname, O_RDONLY | O_DIRECTORY);
int fd = openat(dirfd, basename, O_RDONLY | O_NOFOLLOW);
fstat(fd, &st);
if (st.st_uid == getuid()) {
    unlinkat(dirfd, basename, 0);   /* একই directory fd প্রসঙ্গে */
}
close(fd);
close(dirfd);

মূল নীতি: যেকোনো “check তারপর act” প্যাটার্ন-কে যতটা সম্ভব একটা atomic operation-এ (বা একটা fd-বাঁধা reference-এ) নামিয়ে আনা, যাতে check-এর মুহূর্ত আর act-এর মুহূর্তের মাঝখানে কোনো ফাঁক না থাকে যেখানে filesystem বদলে যেতে পারে।

O_NOFOLLOW নিশ্চিত করে final path component symlink হলে open ব্যর্থ হবে (attacker সেই সহজ পথটা ব্যবহার করতে পারবে না)। fstat() (path-based stat() নয়) fd-র উপর কাজ করে, তাই একবার open হওয়ার পর সেটা আর বদলাতে পারে না, path যাই ঘটুক।

এই সমস্যাটা misconception-এর অংশে সংক্ষেপে উল্লেখ করা হয়েছিল — এখানে পূর্ণ বিশ্লেষণ।

Resource এখানে কী: থ্রেড pool-এর একটা slot (একটা free worker thread)।

চারটা শর্ত এখানে কীভাবে প্রযোজ্য:

Mutual exclusion: একটা thread slot একবারে শুধু একটা task চালাতে পারে — স্পষ্টতই সত্য, কারণ এটাই thread-এর সংজ্ঞা।

Hold and wait: একটা task যখন .get() ডেকে sub-task-এর ফলাফলের জন্য block করে, সে নিজের thread slot ধরে রেখেই অপেক্ষা করছে — সে সেই thread ছেড়ে দিচ্ছে না, শুধু ব্লক করছে।

No preemption: কোনো mechanism নেই যা একটা blocked task-এর কাছ থেকে জোর করে তার thread slot কেড়ে নেবে অন্য কাউকে চালানোর জন্য।

Circular wait: যদি ৪টা thread-ই একসাথে নতুন sub-task submit করে আর তাদের ফলাফলের জন্য অপেক্ষা করে, আর সেই sub-task গুলো চালানোর জন্য কোনো thread free নেই (সবাই parent task-এ ব্লক), তাহলে:

T1 (busy, .get()-এ অপেক্ষা) → চায় একটা free thread sub-task-এর জন্য
T2 (busy, .get()-এ অপেক্ষা) → চায় একটা free thread sub-task-এর জন্য
T3, T4 — একই অবস্থা

কিন্তু কোনো free thread নেই কারণ সবাই ব্যস্ত (অপেক্ষা করছে)

এটা একটা circular wait — যদিও প্রযুক্তিগতভাবে কোনো একটা নির্দিষ্ট thread অন্য একটা নির্দিষ্ট thread-এর জন্য অপেক্ষা করছে না (mutex-এর ABBA প্যাটার্নের মতো সরাসরি নয়), বরং সবাই “pool-এর কোনো একটা free slot”-এর জন্য অপেক্ষা করছে, যা কখনো আসবে না কারণ তৈরির শর্তই পূরণ হচ্ছে না।

সমাধান, তিনটা ভিন্ন কোণ থেকে:

১. Hold-and-wait ভাঙা — কাজটাকে non-blocking করা:

// ব্লক করার বদলে একটা callback/future রিটার্ন করুন
CompletableFuture<Result> future = pool.submit(subTask);
future.thenAccept(result -> continueWork(result));
// এই thread এখনই free হয়ে যায়, sub-task-এর অপেক্ষায় ব্লক করছে না

২. No preemption ভাঙা — একটা unbounded বা কাজ-চুরি করা (work-stealing) pool ব্যবহার:

ForkJoinPool-এর মতো implementation এই সমস্যা সমাধান করে একটা work-stealing algorithm দিয়ে — একটা thread যখন .get()-এ ব্লক করে, সে আসলে সেই সময়টায় অন্য pending task নিজেই চালাতে পারে (নিজের thread ছেড়ে না দিয়েও), কার্যকরভাবে নিজেকে recursive করে তোলে।

৩. আলাদা pool রাখা — “producer” আর “worker” task-এর জন্য:

Task যেগুলো sub-task submit করে (এবং block করতে পারে) তাদের একটা আলাদা, বড় pool-এ রাখা, আর যেগুলো কখনো sub-task submit করে না (leaf task) তাদের অন্য pool-এ — যাতে “সবাই ব্লক” অবস্থা গঠনগতভাবে অসম্ভব হয়ে যায়।

মূল শিক্ষা: Coffman-এর চারটা শর্ত শুধু mutex_lock()-এর জন্য নয় — এটা যেকোনো সীমিত resource আর blocking wait-এর সাধারণ তত্ত্ব। Thread pool slot, database connection pool, file descriptor, semaphore count — সবকিছুতেই একই বিশ্লেষণ প্রযোজ্য, আর একই চারটা প্রশ্ন জিজ্ঞেস করে সমাধান খুঁজতে হয়।