Synchronization Primitives — mutex, semaphore, condition variable: কোনটা ঠিক কীসের জন্য

Critical section problem — সমস্যাটার আনুষ্ঠানিক রূপ

উপরের counter++ কেন হারায়, সেই মেকানিজম পরের লেসনের বিষয় (সংক্ষেপে: এটা একটা instruction না, তিনটা)। এখানে আমরা সমস্যাটার আকারটা ঠিক করে নিই, কারণ সব primitive-ই এই একই আকারের সমস্যার উত্তর।

একটা critical section হলো কোডের এমন একটা অংশ যেখানে shared state পড়া-লেখা হচ্ছে এবং যেটা একবারে একটার বেশি thread চালালে invariant ভেঙে যায়। সমাধান মানে এমন একটা entry/exit protocol যা তিনটা শর্ত মানে — এই তিনটা Dijkstra-র ১৯৬৫ সালের formulation থেকে আসা, আর আজও ঠিক এগুলোই মাপকাঠি:

একটা অনানুষ্ঠানিক চতুর্থ শর্তও বাস্তবে সমান গুরুত্বপূর্ণ — performance। যে সমাধান তিনটা শর্তই মানে কিন্তু প্রতিবার ১০ মাইক্রোসেকেন্ড খরচ করে, সেটা কাগজে সঠিক আর বাস্তবে অকেজো। পুরো লেসনের অর্ধেকটা আসলে এই চতুর্থ শর্তের গল্প।

Mutex — মালিকানা-সহ lock

Mutex (MUTual EXclusion) সবচেয়ে সরল আর সবচেয়ে বেশি ব্যবহৃত primitive। দুইটা অপারেশন: lock আর unlock। কিন্তু mutex-এর যে বৈশিষ্ট্যটা তাকে অন্য সবার থেকে আলাদা করে, সেটা API-তে দেখা যায় না — ownership।

একটা locked mutex-এর একজন মালিক আছে: যে thread তাকে lock করেছে। আর নিয়মটা হলো — শুধু মালিকই unlock করতে পারে। POSIX-এ অন্য thread থেকে unlock করা undefined behaviour; PTHREAD_MUTEX_ERRORCHECK type ব্যবহার করলে EPERM ফেরত আসে।

pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;

pthread_mutex_lock(&m);
counter++;                 /* critical section */
pthread_mutex_unlock(&m);

Ownership কোনো শৌখিন নিয়ম নয় — এর উপর তিনটা বাস্তব সুবিধা দাঁড়িয়ে আছে:

1. Error checking। Runtime জানে কে ধরে আছে, তাই “নিজের ধরা lock আবার lock করার” চেষ্টা (self-deadlock) ধরা যায়, “না-ধরা lock unlock করা” ধরা যায়।
2. Priority inheritance। কম-priority thread একটা mutex ধরে আছে, আর বেশি-priority thread সেটার জন্য অপেক্ষা করছে — kernel জানে মালিক কে, তাই মালিকের priority সাময়িকভাবে বাড়িয়ে দিতে পারে। মালিক না জানলে এটা অসম্ভব। (এটাই ১৯৯৭-এ Mars Pathfinder-এর বিখ্যাত reset-loop-এর সমাধান ছিল — নিচে realworld সেকশনে বিস্তারিত।)
3. Deadlock detection। কে কোন lock ধরে আছে আর কার জন্য অপেক্ষা করছে — এই দুইটা জানলে wait-for graph বানানো যায়। পরের লেসনের build ঠিক এটাই করবে।

POSIX mutex-এর কয়েকটা type আছে, আর ডিফল্টটা সবচেয়ে কম সহনশীল:

Semaphore — শুধু একটা counter, কোনো মালিক নেই

Semaphore এসেছে Dijkstra-র কাছ থেকে (১৯৬৫, THE operating system), আর ধারণাগতভাবে এটা mutex-এর চেয়েও সরল — এটা একটা অঋণাত্মক পূর্ণসংখ্যা যার উপর দুইটা atomic অপারেশন সংজ্ঞায়িত:

লক্ষ করুন কী নেই — কোনো মালিকানা নেই। যেকোনো thread sem_post() করতে পারে, তার আগে কখনো sem_wait() করেছে কি না তার কোনো সম্পর্ক নেই। এটা দুর্বলতা নয়, এটাই semaphore-এর মূল শক্তি: semaphore একটা signalling primitive, mutual-exclusion primitive না।

দুইটা সম্পূর্ণ ভিন্ন ব্যবহার এই একই যন্ত্র দিয়ে হয়:

(ক) Counting semaphore — সীমিত সম্পদের পুল। আপনার কাছে ৫টা database connection আছে, ২০টা thread সেগুলো চায়:

sem_t pool;
sem_init(&pool, 0, 5);        /* ৫টা resource */

sem_wait(&pool);              /* একটা নাও, না থাকলে অপেক্ষা */
use_connection();
sem_post(&pool);              /* ফেরত দাও */

(খ) Signalling — এক thread থেকে আরেক thread-এ ঘটনার খবর। এখানেই mutex সম্পূর্ণ অক্ষম:

sem_t ready;
sem_init(&ready, 0, 0);       /* শুরুতে শূন্য */

/* thread A */                          /* thread B */
prepare_data();                         sem_wait(&ready);   /* অপেক্ষা */
sem_post(&ready);                       consume_data();

Thread A ঘটনার খবর দিচ্ছে, thread B খবরটা পাচ্ছে। কোনো mutual exclusion এখানে জড়িতই নয়। এটা mutex দিয়ে করা যায় না — কারণ B যদি A-র lock unlock করতে চায় তো সেটা ownership নিয়ম ভাঙে।

কেন binary semaphore মোটেও mutex নয়

সবচেয়ে বেশি ছড়ানো ভুল ধারণাটা হলো — “১ দিয়ে initialize করা semaphore = mutex”। উপর থেকে দেখতে একই: sem_wait = lock, sem_post = unlock, একবারে একজন ঢুকতে পারে। কিন্তু চারটা জায়গায় এরা আলাদা, আর প্রতিটাই বাস্তব:

শেষ সারিটা সবচেয়ে বিপজ্জনক। একটা binary semaphore-এ ভুল করে দুইবার sem_post() করলে তার মান হয়ে যায় ২, এবং তারপর দুইটা thread একসাথে critical section-এ ঢুকে পড়ে — কোনো error, কোনো warning ছাড়া। Mutex-এ একই ভুল সাথে সাথে ধরা পড়ে। এজন্যই নিয়মটা সহজ: mutual exclusion চাইলে mutex, thread-এর মধ্যে signalling চাইলে semaphore। নাম দুইটা যেন ব্যবহার ঠিক করে দেয়।

Condition variable — “একটা শর্ত সত্য হওয়া পর্যন্ত অপেক্ষা করো”

Mutex উত্তর দেয় “কে ঢুকবে” প্রশ্নের। কিন্তু বাস্তব কোডে প্রায়ই প্রশ্নটা ভিন্ন: “queue-টা খালি, আমি ঢুকতে চাই না — আমি চাই queue-তে কিছু ঢোকা পর্যন্ত ঘুমাতে।” এটাই condition variable-এর কাজ।

একটা condvar কোনো state ধরে রাখে না — এটা শুধু একটা wait queue। তিনটা অপারেশন:

pthread_cond_wait(&cv, &mutex);   /* mutex ছেড়ে ঘুমাও; জাগলে mutex আবার ধরো */
pthread_cond_signal(&cv);         /* অপেক্ষমাণদের মধ্যে অন্তত একজনকে জাগাও */
pthread_cond_broadcast(&cv);      /* সবাইকে জাগাও */

সবচেয়ে গুরুত্বপূর্ণ অংশটা pthread_cond_wait()-এর দ্বিতীয় প্যারামিটার। একটা condvar সবসময় একটা mutex-এর সঙ্গে জোড়া, কখনো একা নয়, আর wait() তিনটা কাজ করে:

1. mutex টা ছেড়ে দেয়,
2. নিজেকে condvar-এর wait queue-তে ঢোকায় — ধাপ ১ আর ২ atomically,
3. জেগে ওঠার পর ফেরত দেওয়ার আগে mutex আবার ধরে।

ধাপ ১ আর ২-এর atomicity-ই পুরো design-এর ভিত্তি। যদি ওরা আলাদা হতো, তাহলে mutex ছাড়ার আর queue-তে ঢোকার ফাঁকে অন্য thread শর্তটা সত্য করে signal() পাঠিয়ে দিতে পারত — আর সেই signal কেউ শুনত না, কারণ আপনি তখনো queue-তে ঢোকেননি। ফলাফল: চিরকালের ঘুম। একে বলে lost wakeup।

wait সবসময় while-এ, কখনো if-এ — দুইটা স্বাধীন কারণ

এটা এই লেসনের সবচেয়ে গুরুত্বপূর্ণ একক নিয়ম:

pthread_mutex_lock(&m);
while (!predicate())              /* while — if নয়, কখনোই নয় */
    pthread_cond_wait(&cv, &m);
/* এখানে predicate() নিশ্চিতভাবে সত্য, আর mutex আমার হাতে */
pthread_mutex_unlock(&m);

কারণ দুইটা, এবং এরা সম্পূর্ণ স্বাধীন — একটা জানলেও অন্যটা মিস হয়ে যেতে পারে:

কারণ ১ — spurious wakeup। POSIX স্পেসিফিকেশন আক্ষরিকভাবে অনুমতি দেয় যে pthread_cond_wait() কোনো signal ছাড়াই ফেরত আসতে পারে। এটা কোনো bug না, এটা ইচ্ছাকৃত ছাড় — এতে implementation দ্রুততর হয় (Linux-এ একটা signal handler বা process migration futex wait ভেঙে দিতে পারে, আর তখন ফের ঘুমানোর চেয়ে কল ফেরত দেওয়া সস্তা)। স্পেসিফিকেশনের ভাষায়: “spurious wakeups… may occur”।

কারণ ২ — reacquire race (এটাই বেশি ঘটে, অথচ কম আলোচিত)। ধরুন signal সত্যিই এসেছে, কোনো spurious কিছু না। তবু:

   Consumer C1              Producer P               Consumer C2
   (cond_wait-এ ঘুমন্ত)
        |                        |                        |
        |                   lock(m)                       |
        |                   queue-তে ১টা item রাখল        |
        |                   signal(cv)  ──────┐           |
        |                   unlock(m)         |           |
        |                                     |      lock(m)  ← C2 আগে পেল!
        |  ← জেগে উঠল, কিন্তু                 |      item নিয়ে নিল
        |    mutex-এর জন্য অপেক্ষা করছে       |      unlock(m)
        |                                     |           |
   lock(m) পেল ✔                              |           |
   কিন্তু queue এখন আবার খালি!                            |

signal() শুধু বলে “যাও, চেষ্টা করে দেখো” — এটা কোনো প্রতিশ্রুতি দেয় না যে জেগে ওঠার সময় শর্তটা এখনো সত্য থাকবে। জেগে ওঠা thread-কে mutex আবার ধরতে হয়, আর সেই ধরার প্রতিযোগিতায় সে হেরে যেতে পারে অন্য কারো কাছে, যে ইতিমধ্যে item-টা নিয়ে চলে গেছে। একে বলা হয় Mesa semantics — প্রায় সব বাস্তব সিস্টেম (POSIX, Java, C++, Go, .NET) এটাই ব্যবহার করে। এর বিকল্প Hoare semantics (signal দিলে signaler সাথে সাথে CPU ছেড়ে waiter-কে দেয়, তাই শর্ত অবশ্যই সত্য থাকে) তাত্ত্বিকভাবে সুন্দর কিন্তু বাস্তবায়ন ব্যয়বহুল — বাস্তবে কেউ ব্যবহার করে না।

তাই while লেখা শুধু “সাবধানতা” না — Mesa semantics-এ এটাই একমাত্র সঠিক লেখা। মনে রাখার সূত্র: cond_wait() মানে “predicate সত্য হয়েছে” নয়, মানে “predicate আবার চেক করার মতো কিছু একটা ঘটেছে”।

signal বনাম broadcast

নিরাপদ ডিফল্ট নিয়ম: সব waiter একই predicate-এর জন্য অপেক্ষা করলে, আর একটা event একজনকেই এগোতে দিলে — signal()। সন্দেহ হলে broadcast()। broadcast() ধীর কিন্তু কখনো ভুল না; signal() দ্রুত কিন্তু ভুল জায়গায় ব্যবহার করলে thread চিরতরে ঘুমিয়ে থাকতে পারে। এই কারণেই আমাদের bounded queue-তে দুইটা condvar থাকবে — একটা “খালি জায়গা আছে”-র জন্য, একটা “item আছে”-র জন্য — যাতে signal() নিরাপদে ব্যবহার করা যায়।

Read-write lock — অসম অ্যাক্সেসের সুযোগ নেওয়া

অনেক ডেটা স্ট্রাকচার ৯৫% পড়া হয়, ৫% লেখা (রাউটিং টেবিল, কনফিগ ক্যাশ, DNS ক্যাশ)। সব পাঠককে একে একে ঢোকানো নিছক অপচয় — পাঠকরা একে অপরের কোনো ক্ষতি করে না।

pthread_rwlock_rdlock(&rw);   /* একসাথে অনেকে */
pthread_rwlock_wrlock(&rw);   /* একা, exclusive */
pthread_rwlock_unlock(&rw);   /* দুইটার জন্যই একই unlock */

নিয়ম: N জন reader একসাথে, অথবা ১ জন writer একা — কখনো মিশ্রণ নয়।

Writer starvation এখানে আসল বিপদ। Reader-preferring implementation-এ, একজন writer অপেক্ষা করার সময় নতুন reader ঢুকতে দেওয়া হয় — উচ্চ read-লোডে reader-এর সংখ্যা কখনো শূন্য হয় না, তাই writer কখনো ঢুকতে পারে না। এটা সরাসরি bounded waiting শর্তের লঙ্ঘন।

glibc-তে এটা একটা attribute দিয়ে নিয়ন্ত্রণযোগ্য:

pthread_rwlockattr_t attr;
pthread_rwlockattr_init(&attr);
pthread_rwlockattr_setkind_np(&attr,
    PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP);
pthread_rwlock_init(&rw, &attr);

ডিফল্ট PTHREAD_RWLOCK_PREFER_READER_NP — অর্থাৎ glibc-র ডিফল্ট আচরণে writer starve করতে পারে। এটা জানা থাকা দরকার, কারণ ডিফল্টেই সবাই ব্যবহার করে।

Barrier — সবাই এখানে পৌঁছানো পর্যন্ত

Barrier একটা সম্পূর্ণ ভিন্ন আকারের সমস্যার উত্তর — mutual exclusion না, phase synchronization। N-টা thread একটা barrier-এ wait() করে; প্রথম N−1 জন ব্লক হয়; N-তম জন এলে সবাই একসাথে ছাড়া পায়।

pthread_barrier_t b;
pthread_barrier_init(&b, NULL, 4);   /* ৪টা thread */

/* প্রতিটা thread-এ */
compute_phase_1();
pthread_barrier_wait(&b);            /* সবাই phase 1 শেষ করা পর্যন্ত */
compute_phase_2();                   /* এখন phase 1-এর সব ফলাফল নিরাপদে পড়া যাবে */

এটা iterative সংখ্যাগত হিসাবের মূল কাঠামো — matrix multiplication, stencil computation, physics simulation, আর neural network training-এর প্রতিটা layer-এর সীমানা। MPI-র MPI_Barrier আর CUDA-র __syncthreads() ঠিক একই ধারণা, ভিন্ন স্কেলে। একটা barrier আসলে mutex + condvar + একটা counter দিয়ে ১৫ লাইনে লেখা যায় — এই লেসনের build-এর একটা extension হিসেবে সেটাই করতে বলব।

Spinlock বনাম sleeping lock — অপেক্ষার দুই কৌশল

Lock না পেলে কী করবেন? দুইটা কৌশল:

সিদ্ধান্ত-নিয়মটা এক লাইনে বলা যায় — critical section-এর দৈর্ঘ্য যদি দুইটা context switch-এর খরচের চেয়ে কম হয়, তবেই spin করো। লেসন ১১-এ context switch-এর খরচ মেপেছিলাম: সরাসরি খরচ ১–৩ µs, TLB আর cache pollution ধরলে কার্যকর খরচ ৫–২০ µs।

সংখ্যাগুলো বসালেই ছবিটা পরিষ্কার:

$T_{\text{spin}} = T_{\text{cs}} \qquad\text{বনাম}\qquad T_{\text{sleep}} \approx 2 \times T_{\text{ctx}} \approx 3\text{–}10\ \mu s$

অর্থাৎ spin জেতে যখন critical section কয়েক শ ন্যানোসেকেন্ডের কম — একটা counter বাড়ানো, একটা linked-list node যোগ করা, একটা pointer বদলানো। এর বাইরে যেকোনো কিছুতে sleeping lock জেতে।

কিন্তু userspace-এ একটা মারাত্মক অতিরিক্ত সমস্যা আছে যা kernel-এ নেই: preemption। আপনার thread lock ধরে আছে, তারপর scheduler তাকে preempt করল (লেসন ১২-র CFS/EEVDF মনে করুন — একটা timeslice সাধারণত ১–১০ ms)। অন্য thread এখন সেই lock-এর জন্য spin করছে — পুরো একটা timeslice ধরে, ১ মিলিসেকেন্ড ধরে একটা core পুড়িয়ে, এমন একটা lock-এর জন্য যার মালিক এই মুহূর্তে CPU-তেই নেই। এটাকে বলে lock convoy, আর এটাই কারণ যে:

Userspace-এ pure spinlock প্রায় কখনোই সঠিক পছন্দ নয়। Kernel-এ spinlock ঠিক আছে, কারণ kernel spinlock ধরার আগে preemption বন্ধ করে দেয় (preempt_disable()) — userspace-এ সেই সুযোগ আপনার নেই।

Adaptive mutex এই দুই জগতের সেরাটা নেওয়ার চেষ্টা: প্রথমে অল্প কিছুক্ষণ spin করো (glibc-তে PTHREAD_MUTEX_ADAPTIVE_NP, Go runtime-এ ৩০ বার, JVM-এ HotSpot-এর adaptive spinning), তারপরও না পেলে ঘুমাও। যুক্তি: বেশিরভাগ critical section ছোট, তাই সাধারণত অল্প spin-এই কাজ হয়ে যায়; আর যেগুলো ছোট না, সেগুলোতে অল্প কিছু cycle নষ্ট করে ঘুমিয়ে পড়া যায়। Linux kernel-এর mutex আরও এক ধাপ এগিয়ে MCS-based optimistic spinning ব্যবহার করে — এবং spin করার আগে চেক করে lock-এর মালিক এই মুহূর্তে সত্যিই কোনো CPU-তে চলছে কি না (owner->on_cpu); না চললে spin করাই অর্থহীন, তাই সরাসরি ঘুমিয়ে পড়ে। এটা একটা অসাধারণ সুন্দর heuristic।

Lock granularity — কতটুকু একসাথে আটকাবেন

শেষ ধারণা, আর ডিজাইনের দিক থেকে সবচেয়ে ফলপ্রসূ। ধরুন একটা hash table, ১০২৪টা bucket:

Java-র ConcurrentHashMap জাভা ৭ পর্যন্ত ঠিক এই striped কৌশলই ব্যবহার করত (ডিফল্ট ১৬টা segment)। জাভা ৮-এ তারা per-bucket CAS + শুধু collision-এর সময় lock-এ চলে গেছে — আরও সূক্ষ্ম, আরও জটিল, আর মাপা-প্রমাণিতভাবে দ্রুততর।

গুরুত্বপূর্ণ যে সত্যটা এই টেবিলটা লুকিয়ে রাখে: fine-grained locking শুধু “দ্রুততর” নয়, এটা “বেশি বিপজ্জনক”ও। এক lock ধরে আরেকটা নিতে গেলেই lock-ordering-এর প্রশ্ন আসে, আর সেখান থেকেই deadlock। সেটাই পরের লেসনের পুরো বিষয়বস্তু।