এই পর্বে যা শিখবেন
- একটি litmus test-এর সব সম্ভাব্য ফল গুনে বলা কোনটি sequential consistency-তে সম্ভব, আর কোনটি শুধু store buffer বা reordering-এর জন্য আসে
- C++-এর
memory_orderআর acquire/release দিয়ে happens-before সম্পর্ক তৈরি করা, আর vector clock দিয়ে data race ধরা - DRF-SC নিশ্চয়তার অর্থ আর সীমা বোঝা, আর C/C++, Java, Go, Rust ও Python-এর চুক্তি পাশাপাশি তুলনা করা
- Async runtime-এর event loop, future আর executor কীভাবে কাজ চালায়, আর M:N green thread থেকে তার পার্থক্য Haat-এর bytecode-এ দেখানো
- Structured concurrency দিয়ে কাজ বাতিল আর ভুল সামলানো, আর AI-এর দেওয়া concurrent কোডের দাবি litmus test ও race detector দিয়ে যাচাই করা
১ · পর্ব ১১-এর পরে — “কে কখন কী দেখে” প্রশ্নটি
পর্ব ১১-এ আপনি concurrency-র চারটি মডেল দেখেছেন: shared memory আর lock, actor, CSP আর dataflow. সেখানে একটি নীরব ধারণা ছিল: প্রতিটি পড়া memory-র “সর্বশেষ” মান পায়, আর প্রতিটি thread নিজের লাইনগুলো লেখা ক্রমেই চালায়। এই পর্বে সেই ধারণাটিই প্রশ্নের মুখে। Compiler optimization-এর জন্য পড়া-লেখার ক্রম বদলায়, আর CPU লেখাগুলো কিছুক্ষণ নিজের কাছে জমিয়ে রাখে। তাহলে “সর্বশেষ মান” মানে কী, তা ঠিক করে দেওয়ার দায়িত্ব ভাষার। সেই নিয়মগুচ্ছের নাম memory model.
উপমা — দুই শাখার খাতা: বাজারঘরের ঢাকা আর খুলনা শাখার দুই হিসাবরক্ষক একটি কেন্দ্রীয় খাতা ভাগ করেন। দুজনেই নতুন হিসাব প্রথমে নিজের চিরকুটে লেখেন, পরে সময় পেলে কেন্দ্রীয় খাতায় তোলেন। ঢাকার হিসাবরক্ষক চিরকুটে লিখলেন “ঢাকার অর্ডার এসেছে”, তারপর কেন্দ্রীয় খাতায় খুলনার খবর দেখলেন: কিছু নেই। খুলনার জনও একই সময়ে একই কাজ করলেন। দুজনেই সিদ্ধান্ত নিলেন “অন্য শাখায় কিছু ঘটেনি”, অথচ দুই শাখাতেই ঘটেছে। কেউ মিথ্যা বলেননি; চিরকুট (store buffer) থেকে খাতায় ওঠার আগেই পড়া হয়েছে। অংশ ২-এর store buffering পরীক্ষা ঠিক এই ঘটনা।
Haat v1 একটি sequential ভাষা: thread নেই, তাই এর memory model তুচ্ছ। Reference বাস্তবায়নের spec সিদ্ধান্ত ১২ বলে evaluation বাঁ থেকে ডানে; এক thread-এর ভেতরে এটুকুই যথেষ্ট। এই পর্বের Haat-এর সব concurrent নির্মাণ (spawn, await, atomic) তাই স্পষ্টভাবে Haat-এর বর্ধিত রূপ, reference-এ নেই। তবে Haat-এর একটি ছোট function-এর আসল bytecode দিয়েই শুরু করা যায়, কারণ সমস্যার বীজ সেখানেই। Reference-এর সত্যিকারের dis run (CPython 3.14.4):
var total = 0;
fn deposit(t: Int) {
total = total + t;
}
deposit(936);
deposit(1190);
print(total);~/haat $ python haat.py dis deposit.haat (deposit অংশটুকু)
== deposit (arity 1, locals 1) ==
0 LOAD_GLOBAL 1 ; total
1 LOAD_LOCAL 0 ; t
2 ADD
3 STORE_GLOBAL 1 ; total
4 CONST 0 ; ()
5 RETURN
~/haat $ python haat.py run deposit.haat
2126
এক লাইনের total = total + t; চারটি instruction: পড়া, স্থানীয় মান আনা, যোগ, লেখা (পর্ব ৫৮-এর opcode). Sequential run-এ 936 + 1190 = 2126. দুটি deposit একসাথে চললে কী হয়, তা অংশ ৭-এ নিজের scheduler-এ চালিয়ে দেখবেন। তার আগে প্রশ্নটি আরও নিচের স্তরে: একটি লেখা অন্য thread-এর চোখে কখন পৌঁছায়?
২ · Sequential consistency আর litmus test
একটি concurrent execution sequentially consistent, যদি এর ফল এমন হয় যেন সব thread-এর সব memory-কাজ কোনো একটি একক ক্রমে (একটি interleaving-এ) ঘটেছে, আর সেই ক্রমে প্রতিটি thread-এর কাজগুলো তার নিজের program order-এ আছে। প্রতিটি পড়া সেই একক ক্রমে তার আগের শেষ লেখার মান পায়।
Leslie Lamport ১৯৭৯ সালের একটি ছোট গবেষণাপত্রে (“How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs”) এই সংজ্ঞা দেন। পর্ব ৪০-এর small-step semantics-এ এটি দুটি নিয়ম মাত্র। S1 ∥ S2 মানে দুটি statement একসাথে চলছে, σ হলো ভাগ করা memory (state), আর ⟶ মানে একটি ধাপ:
এই inference rule দুটি বলে: প্রতি ধাপে যেকোনো একটি দিক এক পা এগোয়, আর দুজনেই একই σ দেখে। কোন দিক এগোবে তা নিয়ম ঠিক করে না, তাই একটি program-এর অনেক ফল হতে পারে; SC হলো এই সব interleaving-এর ফলের সেট। একটি memory model-কে পরীক্ষা করার প্রচলিত উপায় ছোট litmus test: দুই-তিন লাইনের program, আর প্রশ্ন “এই নির্দিষ্ট ফলটি কি সম্ভব?” সবচেয়ে বিখ্যাত দুটি (সব variable শুরুতে 0):
| নাম | Thread A | Thread B | প্রশ্ন |
|---|---|---|---|
| SB (store buffering) | x = 1; r1 = y; | y = 1; r2 = x; | r1 = 0 আর r2 = 0 একসাথে? |
| MP (message passing) | data = 42; flag = 1; | r1 = flag; r2 = data; | r1 = 1 অথচ r2 = 0? |
SB-তে SC-র যুক্তি সরল: একক ক্রমে যে লেখা প্রথমে আসে (ধরুন x = 1), তার পরে B-এর r2 = x আসবেই, তাই r2 = 1. দুটিই 0 অসম্ভব। MP-তে B যদি flag = 1 দেখে, তাহলে A-এর flag = 1 আগে ঘটেছে, তার আগে data = 42, তাই r2 = 42. কিন্তু হাতে যুক্তি দেওয়ার চেয়ে সব execution গোনা ভালো। নিচের explorer তিনটি “যন্ত্রে” litmus test চালায়: (১) SC, প্রতিটি interleaving; (২) x86-এর মতো যন্ত্র, যেখানে প্রতিটি thread-এর লেখা প্রথমে একটি FIFO store buffer-এ যায় আর যেকোনো সময় memory-তে নামে; (৩) একটি খেলনা “reordering” যন্ত্র, যেখানে fence ছাড়া একটি thread-এর দুটি কাজ জায়গা বদল করতে পারে (ARM বা POWER-এর মতো দুর্বল মডেলের অতি সরল রূপ)।
from itertools import permutations, product
# a thread = list of ops: ("st", var, value), ("ld", var, reg), ("fence",)
F = ("fence",)
SB = [[("st","x",1), ("ld","y","r1")], [("st","y",1), ("ld","x","r2")]]
MP = [[("st","data",42), ("st","flag",1)], [("ld","flag","r1"), ("ld","data","r2")]]
MPF = [[MP[0][0], F, MP[0][1]], [MP[1][0], F, MP[1][1]]]
def explore(ths, buffered): # every execution; buffered=True: x86-like store buffers
out, runs = set(), [0]
def go(pcs, mem, bufs, regs):
moves = []
for i, t in enumerate(ths):
nxt, put = pcs[:i] + (pcs[i] + 1,) + pcs[i+1:], lambda b: bufs[:i] + (b,) + bufs[i+1:]
if bufs[i]: # oldest buffered store -> memory
(v, a), = bufs[i][:1]; moves.append((pcs, {**mem, v: a}, put(bufs[i][1:]), regs))
if pcs[i] == len(t) or (t[pcs[i]] == F and bufs[i]): continue # fence waits
op = t[pcs[i]]
if op[0] == "st" and buffered: moves.append((nxt, mem, put(bufs[i] + (op[1:],)), regs))
elif op[0] == "st": moves.append((nxt, {**mem, op[1]: op[2]}, bufs, regs))
elif op[0] == "ld": # own newest buffered value first
own = [a for v, a in bufs[i] if v == op[1]] or [mem.get(op[1], 0)]
moves.append((nxt, mem, bufs, {**regs, op[2]: own[-1]}))
else: moves.append((nxt, mem, bufs, regs))
if not moves: runs[0] += 1; out.add((regs["r1"], regs["r2"]))
for m in moves: go(*m)
go((0,) * len(ths), {}, ((),) * len(ths), {})
return runs[0], out
def reordered(ths): # toy ARM-like model: without a fence, a thread's ops may swap
ways = lambda t: [t] if F in t else [list(p) for p in permutations(t)]
return set().union(*(explore([a, b], False)[1] for a, b in product(*map(ways, ths))))
for name, test in (("SB", SB), ("MP", MP), ("MP+fence", MPF)):
runs, sc = explore(test, False)
print(f"{name:8} SC: {runs} interleavings, (r1, r2) in {sorted(sc)}")
print(f"{'':8} store buffers add {sorted(explore(test, True)[1] - sc)},"
f" reordering adds {sorted(reordered(test) - sc)}")আসল আউটপুট (ব্রাউজারের Python):
SB SC: 6 interleavings, (r1, r2) in [(0, 1), (1, 0), (1, 1)]
store buffers add [(0, 0)], reordering adds [(0, 0)]
MP SC: 6 interleavings, (r1, r2) in [(0, 0), (0, 42), (1, 42)]
store buffers add [], reordering adds [(1, 0)]
MP+fence SC: 20 interleavings, (r1, r2) in [(0, 0), (0, 42), (1, 42)]
store buffers add [], reordering adds []
প্রতিটি দুই-কাজের thread জোড়ায় C(4, 2) = 6টি interleaving, আর SC কখনো SB-র (0, 0) বা MP-র (1, 0) দেয় না। Store buffer SB-তে (0, 0) যোগ করে, কিন্তু MP-তে কিছু যোগ করে না: buffer FIFO, তাই A-এর দুটি লেখা memory-তে লেখা ক্রমেই নামে। এটিই x86-এর total store order (TSO)-এর মূল কথা। Reordering যন্ত্রে MP-ও ভাঙে: B flag = 1 দেখেও পুরোনো data = 0 পড়ে। শেষ সারিতে প্রতিটি thread-এ একটি fence বসানো হয়েছে (fence নিজেও একটি ধাপ, তাই ৩ + ৩ ধাপে C(6, 3) = 20টি interleaving); fence buffer খালি না হওয়া পর্যন্ত অপেক্ষা করে আর reordering আটকায়, তাই অদ্ভুত ফল আর নেই।
Store buffer কীভাবে SB-তে দুটি শূন্য তৈরি করে, ধাপে ধাপে দেখুন। এই ক্রমটি explorer-এর খুঁজে পাওয়া execution-গুলোর একটি:
1A: x = 12A: r1 = y3B: y = 14B: r2 = x
| memory x | |
| memory y | |
| A-এর buffer | |
| B-এর buffer | |
| r1 | |
| r2 |
- শুরু। memory-তে x = 0, y = 0; দুটি store buffer খালি।
- A লেখে x = 1. লেখাটি A-এর buffer-এ যায়; memory-তে x এখনো 0. A অপেক্ষা না করে পরের লাইনে যায়, এটিই buffer-এর গতির সুবিধা।
- B লেখে y = 1. একইভাবে B-এর buffer-এ; memory-তে y এখনো 0.
- A পড়ে y. A আগে নিজের buffer-এ y খোঁজে, পায় না, তাই memory থেকে পড়ে: r1 = 0.
- B পড়ে x. B-এর buffer-এ x নেই; memory-তে x এখনো 0, কারণ A-এর লেখা buffer-এ আটকে: r2 = 0.
- A-এর buffer নামে। এখন memory-তে x = 1, কিন্তু r2 আগেই 0 পড়ে ফেলেছে।
- B-এর buffer নামে। y = 1. শেষ ফল r1 = 0, r2 = 0: কোনো একক interleaving এই ফল দিতে পারে না। প্রতিটি thread-এর নিজের চোখে ক্রম ঠিকই ছিল; অন্যের চোখে লেখাটি পড়ার পরে পৌঁছেছে।
৩ · সত্যিকারের CPU-তে — C++ atomics আর memory_order
খেলনা যন্ত্রের দাবি সত্যিকারের হার্ডওয়্যারে যাচাই করুন। নিচের C++ program SB পরীক্ষাটি ২০ হাজার রাউন্ড চালায়। প্রতি রাউন্ডে দুটি thread একটি ছোট barrier-এ মিলিত হয়, x আর y শূন্য করা হয়, তারপর দুজনে একসাথে লেখে আর পড়ে। x আর y হলো std::atomic<int>, তাই এখানে কোনো data race নেই, program পুরোপুরি বৈধ C++; প্রশ্ন শুধু কোন ক্রম অনুমোদিত। প্রথমবার সব কাজ memory_order_relaxed, দ্বিতীয়বার memory_order_seq_cst. প্রথম লাইনের #pragma GCC-কে এই ফাইল -O2-এ compile করতে বলে, কারণ in-page runner flag নিতে পারে না।
// Store buffering (SB) litmus test, two threads, many rounds
#pragma GCC optimize("O2")
#include <atomic>
#include <cstdio>
#include <thread>
using namespace std;
atomic<int> x, y, arrive{0}, phase{0};
const int N = 20000;
void barrier() { // both threads meet here
int p = phase.load();
if (arrive.fetch_add(1) == 1) { arrive = 0; phase++; }
else while (phase.load() == p) {}
}
template <memory_order MO> int rounds() {
int r1 = 0, r2 = 0, both_zero = 0;
thread b([&] { for (int i = 0; i < N; i++) {
barrier(); barrier();
y.store(1, MO); r2 = x.load(MO); // thread B
barrier(); } });
for (int i = 0; i < N; i++) {
barrier(); x = 0; y = 0; barrier();
x.store(1, MO); r1 = y.load(MO); // thread A
barrier();
if (r1 == 0 && r2 == 0) both_zero++;
}
b.join();
return both_zero;
}
int main() {
printf("relaxed: r1 == 0 && r2 == 0 in %d of %d rounds\n",
rounds<memory_order_relaxed>(), N);
printf("seq_cst: r1 == 0 && r2 == 0 in %d of %d rounds\n",
rounds<memory_order_seq_cst>(), N);
}আসল আউটপুট (Wandbox, GCC 17 experimental, একটি run):
relaxed: r1 == 0 && r2 == 0 in 1 of 20000 rounds
seq_cst: r1 == 0 && r2 == 0 in 0 of 20000 rounds
সংখ্যাগুলো এক run-এর গণনা, নিয়ম নয়, আর এরা খুব ওঠানামা করে: এই run-এ relaxed সারিতে মাত্র 1, লেখকের আগের দুটি run-এ একই কোডে 5646 আর 6394, আর -O2 ছাড়া দুটি run-এ 0. কিন্তু গুণগত কথাটি স্থির: relaxed-এ SC-তে অসম্ভব ফলটি সত্যিই ঘটে, আর seq_cst-এ একবারও ঘটেনি। x86-এ seq_cst store সাধারণত একটি xchg বা mov + mfence হয়ে compile হয়, যা store buffer খালি করে; relaxed store একটি সাধারণ mov. এখানে CPU-র store buffer, compiler-এর reordering নাকি দুটিই দায়ী, তা এই run থেকে আলাদা করা যায় না; standard দুটিকেই অনুমতি দেয়, আর সেটিই আসল কথা। নিজে চালালে আপনার সংখ্যা আলাদা হবে, এমনকি 0-ও আসতে পারে।
C11 আর C++11 থেকে প্রতিটি atomic কাজ একটি ordering নেয়। সংক্ষেপে (C++20 অনুযায়ী):
| ordering | কোথায় | নিশ্চয়তা |
|---|---|---|
relaxed | যেকোনো atomic | শুধু অবিভাজ্যতা আর একটি variable-এর নিজের লেখার একক ক্রম; অন্য variable-এর সঙ্গে কোনো ক্রম নেই (কাউন্টারের জন্য যথেষ্ট) |
release | store | এর আগের সব পড়া-লেখা এর পরে সরানো যাবে না; যে acquire এই মান পড়ে, তার কাছে আগের সব লেখা দৃশ্যমান |
acquire | load | এর পরের পড়া-লেখা এর আগে সরানো যাবে না; release-এর জোড়া |
acq_rel | read-modify-write (যেমন fetch_add) | একসাথে acquire আর release |
seq_cst | সব (ডিফল্ট) | acquire/release-এর সব, আর সব seq_cst কাজের একটি একক মোট ক্রম; তাই SB-র (0, 0) নিষেধ |
consume | load | নির্ভরশীল পড়ার জন্য হালকা acquire; বাস্তবে compiler-গুলো একে acquire হিসেবেই চালায়, আর C++17 থেকে এর ব্যবহার নিরুৎসাহিত |
ডিফল্ট কেন seq_cst? কারণ নিরাপদ পছন্দটিই সহজ হওয়া উচিত: দুর্বল ordering একটি optimization, যা প্রমাণ সহ ব্যবহার করতে হয়। Atomic-এর হার্ডওয়্যার দিক (lock prefix, compare-and-swap, cache coherence) আছে অপারেটিং সিস্টেম কোর্সের পর্ব ২৩-এ, আর C++-এর std::atomic, std::async আর future ব্যবহারের দিক আছে C++ কোর্সের পর্ব ৪৭-এ.
৪ · Happens-before আর DRF-SC — চুক্তির গণিত
প্রতিটি litmus test আলাদা করে মুখস্থ রাখা অসম্ভব। আধুনিক memory model তাই একটি সম্পর্ক দিয়ে কথা বলে: happens-before. এর উপাদান তিনটি।
(১) Sequenced-before (sb): একই thread-এ a যদি program order-এ b-এর আগে থাকে। (২) Synchronizes-with (sw): একটি release-store W আর একটি acquire-load R, যেখানে R ঠিক W-এর লেখা মানটি পড়ে; একইভাবে mutex-এর unlock থেকে পরের lock, thread শুরু থেকে তার প্রথম কাজ, আর thread-এর শেষ থেকে join. (৩) Happens-before (hb): sb ∪ sw-এর transitive closure, অর্থাৎ a থেকে b-এ sb আর sw তীরের একটি পথ থাকলে a hb b. দুটি memory-ছোঁয়া সংঘাতপূর্ণ (conflicting), যদি একই non-atomic ঘর ছোঁয় আর অন্তত একটি লেখা হয়। সংঘাতপূর্ণ দুটি ছোঁয়ার কোনোটি অন্যটির hb-তে না থাকলে, সেটি একটি data race.
ছবি ৭৭.১ — MP-তে happens-before
বাঁয়ে thread A, ডানে thread B. ওপর থেকে নিচে program order.
data = 42 sb flag.store sw flag.load sb print(data): একটি পথ আছে, তাই data-র লেখা happens-before data-র পড়া, আর পড়াটি 42 দেখতে বাধ্য। flag যদি সাধারণ variable হতো, সবুজ sw তীরটি থাকত না; তখন data-র দুই ছোঁয়ার মাঝে কোনো পথ নেই, অর্থাৎ data race.যদি একটি program-এর প্রতিটি sequentially consistent execution data-race-free হয়, তাহলে memory model-এর অধীনে তার প্রতিটি execution-এর ফল কোনো একটি SC execution-এর ফলের সমান। ধারণাটি Sarita Adve ও Mark Hill-এর ১৯৯০ সালের “weak ordering” কাজ থেকে; C++11 (Boehm ও Adve), Java 5 আর Go-র ২০২২ সালের সংশোধিত memory model সবাই এই নিশ্চয়তা দেয় (প্রতিটি ভাষার নিজস্ব শর্ত সহ)।
প্রমাণের রূপরেখা।
- Compiler আর CPU-কে অনুমতি দেওয়া হয় শুধু synchronization-এর মাঝের সাধারণ পড়া-লেখা নিজেদের মধ্যে সরাতে; release-এর আগের কিছু তার পরে যায় না, acquire-এর পরের কিছু তার আগে আসে না।
- Race-free program-এ একটি সাধারণ ছোঁয়া যে ঘরের, সেই ঘরের প্রতিটি সংঘাতপূর্ণ ছোঁয়া hb দিয়ে এর আগে বা পরে বাঁধা; তাই অন্য thread সেই ঘর দেখতে পায় কেবল একটি synchronization পার হয়ে।
- অতএব দুটি synchronization বিন্দুর মাঝের কাজগুলো অন্য কোনো thread-এর চোখে আলাদা করে দেখা যায় না; সেগুলোকে একটি অবিভাজ্য টুকরো ধরা যায়। Synchronization কাজগুলো নিজেরা একটি একক ক্রমে ঘটে (যেমন সব
seq_cstকাজের মোট ক্রম)। - সেই ক্রমে টুকরোগুলো সাজালে একটি সাধারণ interleaving পাওয়া যায়, যার প্রতিটি পড়া একই মান দেখে। এটিই খোঁজা SC execution. ∎
চুক্তির দুই দিক লক্ষ করুন। প্রোগ্রামারের দায়: race না রাখা। Compiler আর হার্ডওয়্যারের পুরস্কার: race-free অংশে প্রায় সব optimization চালানোর স্বাধীনতা। শর্তটিও লক্ষ করুন: “প্রতিটি SC execution-এ race নেই” — race খুঁজতে আপনাকে দুর্বল মডেলের অদ্ভুত execution ভাবতে হয় না, সাধারণ interleaving ভাবলেই চলে। নিচের stepper hb কীভাবে vector clock দিয়ে চলার সময় হিসাব করা যায়, তা দেখায়। প্রতিটি thread-এর একটি vector: [A-এর জানা ধাপ, B-এর জানা ধাপ]. Release তার vector flag-এ রেখে যায়, acquire সেটি নিজের vector-এর সঙ্গে মেলায় (প্রতিটি ঘরে বড়টি)। একটি পুরোনো ছোঁয়া p বর্তমান thread-এর hb-তে আছে ঠিক তখন, যখন p-এর vector ≤ বর্তমান vector (প্রতিটি ঘরে)।
1A: data = 422A: flag.store(1, release)3B: flag.load(acquire) == 14B: print(data)
| A-এর vector | |
| B-এর vector | |
| flag-এ রাখা vector | |
| data-র লেখা |
- A লেখে data. A-এর vector [1,0]; data-র লেখাটি এই vector সহ মনে রাখা হয়।
- A-এর release. A নিজের vector [1,0] flag-এ রেখে যায় (“এ পর্যন্ত আমি যা করেছি, তা প্রকাশ করলাম”), তারপর নিজের ঘর বাড়ায়: [2,0].
- B-এর acquire 1 পড়ে। পড়া মানটি সেই release-এর লেখা, তাই sw তীর তৈরি হয়। B নিজের [0,1] আর flag-এর [1,0] মেলায়: প্রতিটি ঘরে বড়টি, [1,1].
- B পড়ে data. data-র লেখার vector [1,0] ≤ [1,1], প্রতিটি ঘরে। তাই লেখাটি এই পড়ার hb-তে, race নেই, আর পড়াটি 42 দেখতে বাধ্য।
- যদি flag সাধারণ variable হতো। Release নেই, তাই A-এর vector [1,0]-এ থাকে আর flag-এ কিছু রাখা হয় না; acquire নেই, তাই B [0,1]-এ থাকে। [1,0] ≤ [0,1] মিথ্যা (A-এর ঘরে 1 > 0): data-র দুই ছোঁয়া hb-তে বাঁধা নয়, এটি data race, এমনকি এই run-এ B 42 দেখলেও।
একই হিসাব কোডে। নিচের ছোট checker একটি ঘটনার তালিকা (trace) নিয়ে vector clock চালায় আর race জানায়। ThreadSanitizer আর Go-র race detector এই ধারণার অনেক দক্ষ রূপ ব্যবহার করে (যেমন Flanagan ও Freund-এর FastTrack কৌশল, ২০০৯; বাস্তবায়নের খুঁটিনাটি tool-ভেদে আলাদা)।
"use strict";
// vector-clock happens-before checker (the idea inside TSan and Go's -race)
function check(trace) {
const C = { A: { A: 1, B: 0 }, B: { A: 0, B: 1 } }; // one clock per thread
const L = {}, seen = {}, races = []; // L: clock released on a sync var
const leq = (u, v) => Object.keys(u).every(k => u[k] <= v[k]);
for (const [t, op, v] of trace) {
if (op === "release") { // publish everything t did so far
L[v] = { ...C[t] }; C[t][t]++;
} else if (op === "acquire") { // learn what the releaser did
for (const k in L[v] || {}) C[t][k] = Math.max(C[t][k], L[v][k]);
} else { // plain read or write
for (const p of seen[v] || [])
if (p.t !== t && (p.op === "write" || op === "write") && !leq(p.vc, C[t]))
races.push(`${v}: ${p.t} ${p.op} || ${t} ${op}`);
(seen[v] = seen[v] || []).push({ t, op, vc: { ...C[t] } });
}
}
return races.length ? races.join("; ") : "no data race";
}
const plain = [["A", "write", "data"], ["A", "write", "flag"],
["B", "read", "flag"], ["B", "read", "data"]];
const synced = [["A", "write", "data"], ["A", "release", "flag"],
["B", "acquire", "flag"], ["B", "read", "data"]];
console.log("plain flag :", check(plain));
console.log("release/acquire :", check(synced));
// the acquire happens before A's release in this run: no edge, so a race
console.log("acquire too early:", check([synced[2], synced[0], synced[1], synced[3]]));আসল আউটপুট (ব্রাউজারের JavaScript; Node.js 24.15-এও একই):
plain flag : flag: A write || B read; data: A write || B read
release/acquire : no data race
acquire too early: data: A write || B read
প্রথম trace-এ flag আর data দুটিতেই race. দ্বিতীয়টিতে release/acquire জোড়া একটি sw তীর বানায়, তাই কোনো race নেই। তৃতীয়টি সূক্ষ্ম: একই কাজগুলো, কিন্তু B-এর acquire A-এর release-এর আগে ঘটেছে, তাই সে পুরোনো 0 পড়েছে আর কিছু শেখেনি। sw তৈরি হয় শুধু তখন, যখন acquire ঠিক release-এর লেখা মান পড়ে; “acquire লিখে দিয়েছি” যথেষ্ট নয়, পড়া মানটি পরীক্ষা করে তবেই data ছুঁতে হয় (সাধারণত while (!flag.load(acquire)) loop দিয়ে)।
৫ · পাঁচ ভাষার পাঁচ চুক্তি — C/C++, Java, Go, Rust আর Python
DRF-SC প্রায় সবার ভিত্তি, কিন্তু race থাকলে কী হবে, সেখানে ভাষাগুলো একেবারে আলাদা। পর্ব ১১ Java-র lost update আর Python-এর GIL-এর সত্যিকারের run দেখিয়েছে; এখানে চুক্তির দিক।
| ভাষা | race-free হলে | race থাকলে | মূল হাতিয়ার |
|---|---|---|---|
| C11 / C++11 থেকে | SC (শুধু seq_cst atomic ব্যবহার করলে); দুর্বল ordering-এ তার চেয়ে কম | undefined behavior | atomic, memory_order, mutex; ThreadSanitizer |
| Java (Java 5 থেকে, JSR-133) | SC | সীমিত নিশ্চয়তা: ভুল মান আসতে পারে, কিন্তু “শূন্য থেকে” মান বা type-নিরাপত্তা ভাঙা নয় | volatile (seq_cst-এর মতো), synchronized, final field-এর বিশেষ নিয়ম, java.util.concurrent |
| Go (১.১৯-এ সংশোধিত, ২০২২) | SC; Go-র atomic সবই sequentially consistent | program অবৈধ; runtime race জানিয়ে থামতে পারে, তবে সাধারণত race-এর প্রভাব সীমিত (একটি word-আকারের পড়া কোনো একটি সত্যিকারের লেখার মান পায়) | channel, sync, sync/atomic; -race |
| Rust (safe অংশ) | SC-সহ C++-এর মতো atomic ordering | safe কোডে data race compile হয় না; unsafe-এ C++-এর মতো UB | Send, Sync, Mutex<T>, Arc, atomic |
| Python (CPython 3.14) | ভাষার আনুষ্ঠানিক memory model নেই | interpreter ভেঙে পড়ে না; প্রচলিত build-এ GIL, আলাদা free-threaded build-এ object-এর ভেতরে নিজস্ব lock | threading.Lock, queue, asyncio |
Rust: race-কে type error বানানো
Rust দুটি marker trait দিয়ে কাজটি করে (Send আর Sync নামে)। T: Send মানে T-এর মালিকানা অন্য thread-এ পাঠানো নিরাপদ; T: Sync মানে &T কয়েকটি thread একসাথে ধরে রাখতে পারে। নিয়মটি এক লাইনে: T: Sync ঠিক তখন, যখন &T: Send. Compiler এগুলো struct-এর field দেখে নিজে বের করে, আর thread::spawn-এর signature closure-এর ওপর Send দাবি করে। দুটি সত্যিকারের ভুল, Wandbox-এ rustc 1.82.0 (path-এর একটি লাইন বাদ দেওয়া):
use std::rc::Rc;
use std::thread;
fn main() {
let total = Rc::new(936); // Rc: count is not atomic
let h = thread::spawn(move || {
println!("{}", total);
});
h.join().unwrap();
}error[E0277]: `Rc<i32>` cannot be sent between threads safely
--> prog.rs:6:27
|
6 | let h = thread::spawn(move || {
| ------------- ^------
| | |
| _____________|_____________within this `{closure@prog.rs:6:27: 6:34}`
| | |
| | required by a bound introduced by this call
7 | | println!("{}", total);
8 | | });
| |_____^ `Rc<i32>` cannot be sent between threads safely
|
= help: within `{closure@prog.rs:6:27: 6:34}`, the trait `Send` is not implemented for `Rc<i32>`, which is required by `{closure@prog.rs:6:27: 6:34}: Send`
...
error: aborting due to 1 previous error
Rc-এর reference count একটি সাধারণ (non-atomic) সংখ্যা; দুই thread একসাথে বাড়ালে-কমালে পর্ব ১১-এর lost update হতো, আর count ভুল করে শূন্য হলে memory মুক্ত হয়ে যেত। তাই Rc Send নয়; atomic count-ওয়ালা Arc Send. দ্বিতীয় উদাহরণে thread::scope (Rust 1.63 থেকে) দিয়ে দুটি thread একটি Cell ভাগ করতে চায়:
use std::cell::Cell;
use std::thread;
fn main() {
let total = Cell::new(0); // Cell: mutation without a lock
thread::scope(|s| {
for t in [936, 1190] {
s.spawn(|| total.set(total.get() + t));
}
});
println!("{}", total.get());
}error[E0277]: `Cell<i32>` cannot be shared between threads safely
--> prog.rs:8:21
|
8 | s.spawn(|| total.set(total.get() + t));
| ----- ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ `Cell<i32>` cannot be shared between threads safely
| |
| required by a bound introduced by this call
|
= help: the trait `Sync` is not implemented for `Cell<i32>`, which is required by `{closure@prog.rs:8:21: 8:23}: Send`
= note: if you want to do aliasing and mutation between multiple threads, use `std::sync::RwLock` or `std::sync::atomic::AtomicI32` instead
= note: required for `&Cell<i32>` to implement `Send`
শেষ note-টিই নিয়মটি: closure &Cell ধরে, &Cell: Send হতে হলে Cell: Sync লাগত, আর Cell lock ছাড়া বদলায় বলে Sync নয়। ঠিক রূপে ডেটা তালার ভেতরে বা atomic-এ (Wandbox, rustc 1.82.0, সত্যিকারের run):
use std::sync::Mutex;
use std::sync::atomic::{AtomicI64, Ordering};
use std::thread;
fn main() {
let locked = Mutex::new(0); // the data lives inside the lock
let atomic = AtomicI64::new(0);
thread::scope(|s| { // structured: all threads end here
for t in [936, 1190] {
let (locked, atomic) = (&locked, &atomic);
s.spawn(move || {
*locked.lock().unwrap() += t;
atomic.fetch_add(t, Ordering::Relaxed);
});
}
});
println!("mutex {}", locked.into_inner().unwrap());
println!("atomic {}", atomic.load(Ordering::Relaxed));
}mutex 2126
atomic 2126
সীমাটিও মনে রাখুন: Rust data race আটকায়, race condition বা deadlock নয়। দুটি আলাদা lock()-এ পড়া আর লেখা ভাগ করলে lost update আবার সম্ভব, আর দুই তালা উল্টো ক্রমে নিলে deadlock. Ownership আর borrowing-এর পুরো কাঠামো পর্ব ৭৬-এর (Memory safety আর ownership — Rust-এর borrow checker) বিষয়।
Go: “race আছে, তবু ঠিক এসেছে”
নিচের Go program-এ দুটি goroutine কোনো synchronization ছাড়া একই total বদলায়: একটি নিশ্চিত data race. Wandbox-এ Go 1.23.2-এ একটি সত্যিকারের run:
package main
import (
"fmt"
"sync"
)
func main() {
total := 0 // shared by two goroutines
var wg sync.WaitGroup
for _, part := range [][]int{{936, 0}, {990, 200}} {
wg.Add(1)
go func(p []int) {
defer wg.Done()
for _, t := range p {
total = total + t // unsynchronized read and write
}
}(part)
}
wg.Wait()
fmt.Println("Dhaka total:", total)
}Dhaka total: 2126
ফল ঠিক এসেছে, কারণ এই ছোট কাজে প্রথম goroutine সম্ভবত দ্বিতীয়টি শুরুর আগেই শেষ। এটিই race-এর সবচেয়ে বিপজ্জনক রূপ: test পাস করে। Go-র উত্তর go run -race বা go test -race, যা ThreadSanitizer-এর runtime দিয়ে প্রতিটি ছোঁয়ার hb হিসাব রাখে আর এই ক্রমেও “WARNING: DATA RACE” জানায়। লেখক Wandbox-এ -race flag দিয়ে চালানোর চেষ্টা করেছিলেন, কিন্তু সেখানে flag-টি কার্যকর হয়েছে কি না নিশ্চিত হওয়া যায়নি (আউটপুটে কোনো সতর্কবার্তা আসেনি), তাই এখানে কোনো race-report দেখানো হলো না; নিজের যন্ত্রে Go install করে চালিয়ে দেখুন।
Python: কোন build, তা আগে দেখুন
লেখকের যন্ত্রের CPython 3.14.4-এ sysconfig.get_config_var("Py_GIL_DISABLED") দিয়েছে 0 আর sys._is_gil_enabled() দিয়েছে True: এটি প্রচলিত GIL-ওয়ালা build. Free-threaded build (PEP 703) 3.14-এ আনুষ্ঠানিকভাবে সমর্থিত, কিন্তু ডিফল্ট নয়, আর সেখানে এক thread-এর +=-এর ফাঁকে অন্য thread সত্যিই একই মুহূর্তে চলতে পারে। কোন build-এ চালাচ্ছেন, তা না জেনে race নিয়ে কোনো দাবি করবেন না; বিস্তারিত Python কোর্সের পর্ব ৪৪-এ.
৬ · Async runtime-এর ভেতরে — future, executor আর event loop
এ পর্যন্ত প্রতিটি সমস্যা এসেছে কারণ OS thread-কে যেকোনো মুহূর্তে থামানো যায়, আর একাধিক core একসাথে চলে। Async runtime অন্য পথ নেয়: একটি (বা অল্প কয়েকটি) thread, আর হাজারো ছোট কাজ, যারা নিজেরাই await-এ থেমে নিয়ন্ত্রণ ছেড়ে দেয় (cooperative multitasking পদ্ধতি)। পর্ব ৩১-এ আপনি দেখেছেন compiler কীভাবে একটি async function-কে state machine-এ নামায় আর একটি ছোট event loop লিখেছেন। এখানে runtime-এর তিনটি অংশ, ভাষার চোখে:
Future / promise
এখনো না আসা একটি ফলের বাক্স। JavaScript-এর Promise আর Python-এর Task তৈরি হওয়ামাত্র চলতে শুরু করে (eager); Rust-এর Future অলস: কেউ poll না করলে কিছুই চলে না।
Executor
কোন কাজ কখন কোন thread-এ চলবে, সেই সিদ্ধান্তদাতা। Rust-এ ভাষা শুধু Future trait দেয়, executor দেয় library (যেমন Tokio); Python-এ asyncio-র event loop, JavaScript-এ engine নিজে।
Reactor / event loop
OS-কে জিজ্ঞেস করে কোন socket প্রস্তুত, কোন timer বাজল (epoll, kqueue, IOCP), তারপর সংশ্লিষ্ট কাজকে আবার “প্রস্তুত” সারিতে তোলে। Rust-এ এই খবর পৌঁছায় একটি Waker দিয়ে।
Python-এর asyncio-তে পুরো চক্রটি সত্যিকারের run-এ দেখুন। দুটি “worker” ঢাকার অর্ডারগুলো ভাগ করে নেয়: w1 পায় 936, w2 পায় 990 আর 200; প্রত্যেকে প্রতিটি যোগের পর একটি অপেক্ষায় (await asyncio.sleep) নিয়ন্ত্রণ ছাড়ে। দ্বিতীয় অংশটি পরের অংশ ৮-এর জন্য:
import asyncio, sys
async def branch(name, parts, wait):
total = 0
for t in parts:
total += t
print(f" {name}: +{t} -> {total}, await sleep({wait})")
await asyncio.sleep(wait) # hand control back to the event loop
print(f" {name}: done {total}")
return total
async def courier(name, wait, fail):
await asyncio.sleep(wait)
if fail: raise ConnectionError(f"{name} courier offline")
print(f" {name}: delivered")
async def main():
print("gather:")
a, b = await asyncio.gather(branch("w1", [936], 0.1),
branch("w2", [990, 200], 0.01))
print(" results", [a, b], "-> Dhaka =", a + b)
print("TaskGroup:")
try:
async with asyncio.TaskGroup() as tg:
fast = tg.create_task(courier("Dhaka", 0.01, False))
bad = tg.create_task(courier("Sylhet", 0.05, True))
slow = tg.create_task(courier("Khulna", 0.5, False))
except* ConnectionError as eg:
print(" failed:", [str(e) for e in eg.exceptions])
print(" cancelled:", fast.cancelled(), bad.cancelled(), slow.cancelled())
print(sys.version.split()[0], "GIL enabled:", sys._is_gil_enabled())
asyncio.run(main())~/conc $ python loop_trace.py (লেখকের যন্ত্রে পাঁচবার, প্রতিবার হুবহু একই)
3.14.4 GIL enabled: True
gather:
w1: +936 -> 936, await sleep(0.1)
w2: +990 -> 990, await sleep(0.01)
w2: +200 -> 1190, await sleep(0.01)
w2: done 1190
w1: done 936
results [936, 1190] -> Dhaka = 2126
TaskGroup:
Dhaka: delivered
failed: ['Sylhet courier offline']
cancelled: False False True
লক্ষ করুন total += t লাইনে কোনো lock নেই, তবু কোনো lost update হয়নি: দুটি await-এর মাঝের কোড একটানা চলে, কারণ event loop শুধু await-এর বিন্দুতেই কাজ বদলায়। আর total প্রতিটি coroutine-এর নিজের local variable, তাই ভাগও হয়নি। নিচের stepper gather অংশটি event loop-এর চোখে দেখায়। সময়গুলো প্রায়-মান (timer-এর resolution যন্ত্রভেদে আলাদা); ক্রমটি সত্যিকারের run-এর।
1async def branch(...):2 for t in parts:3 total += t; print4 await sleep(wait)5 print("done")6await gather(w1, w2)
| ready সারি | |
| timer |
- gather. main দুটি coroutine-কে Task বানায়; দুটিই ready সারিতে। main নিজে gather-এর ফলের অপেক্ষায় থামে।
- w1 চলে। 936 যোগ করে ছাপে, তারপর
sleep(0.1): loop ০.১ সেকেন্ড পরের একটি timer রাখে, আর w1 থামে। - w2 চলে। 990 যোগ করে
sleep(0.01). ready সারি এখন খালি; দুটি timer অপেক্ষায়। - Loop অপেক্ষা করে। কিছুই প্রস্তুত নেই, তাই loop OS-এর selector-এ সবচেয়ে কাছের timer (≈০.০১) পর্যন্ত ঘুমায়। Timer বাজলে w2 আবার ready.
- w2 আবার। ঠিক
await-এর পর থেকে চলে: 200 যোগ, মোট 1190, আবারsleep(0.01). - w2 শেষ। ≈০.০২-এ loop শেষ করে “done 1190” ছাপে; তার future-এ ফল বসে। gather এখনো w1-এর অপেক্ষায়।
- w1 শেষ। ০.১-এ w1 জাগে, “done 936”. দুটি ফল হাজির, তাই gather main-কে ready সারিতে তোলে।
- main চলে। ফলগুলো আসে ইনপুটের ক্রমে, [936, 1190], শেষ হওয়ার ক্রমে নয়; যোগফল 2126.
এই মডেলের নিশ্চয়তা আর দাম দুটিই স্পষ্ট। নিশ্চয়তা: দুই await-এর মাঝে interleaving নেই। দাম: (১) কোনো কাজ await ছাড়া লম্বা হিসাব করলে পুরো loop আটকে যায়; (২) total = total + await fetch()-এর মতো লাইনে পড়া আর লেখার মাঝেই একটি await, তাই lost update ফিরে আসে (অনুশীলন ৩); (৩) async function শুধু async function থেকে সহজে ডাকা যায়, যাকে Bob Nystrom ২০১৫ সালের একটি লেখায় function-এর “রং” সমস্যা বলেছিলেন।
৭ · Green thread, goroutine আর virtual thread — M:N scheduling
দ্বিতীয় পথ: প্রোগ্রামার সাধারণ blocking কোড লেখেন, আর runtime নিজে লাখো হালকা thread-কে অল্প কয়েকটি OS thread-এ ভাগ করে চালায়। একে বলে M:N (M-টি ভাষা-স্তরের thread চলে N-টি OS thread-এর ওপর)। প্রতিটি হালকা thread-এর নিজের ছোট, প্রয়োজনে বাড়ে এমন stack (stackful), তাই যেকোনো গভীরতা থেকে থামা যায়, কোনো await লাগে না।
| ভাষা | নাম | পালা বদল কখন |
|---|---|---|
| Go | goroutine | channel, lock, system call, function call-এর বিন্দুতে; Go 1.14 (২০২০) থেকে লম্বা loop-কেও runtime signal দিয়ে asynchronous-ভাবে থামাতে পারে (preemption) |
| Java 21 (JEP 444) | virtual thread | blocking I/O, lock-এ অপেক্ষা ইত্যাদিতে carrier OS thread থেকে নেমে যায়; Java 24-এর JEP 491-এর আগে synchronized-এর ভেতরে অপেক্ষা carrier-কে আটকে রাখত (pinning) |
| Erlang/Elixir | process | নির্দিষ্ট সংখ্যক কাজ (reduction) পরপর, তাই লম্বা হিসাবও অন্যদের আটকায় না |
| Java ১.১-এর যুগ | green thread | সব একটি OS thread-এ (M:1); একাধিক core কাজে লাগাতে না পারায় পরে বাদ পড়ে |
এর মানে, Go বা Java-র হালকা thread-এ data race-এর সব সমস্যা অংশ ৪-এর মতোই থাকে, কারণ পালা যেকোনো instruction-এ বদলাতে পারে আর একাধিক core একসাথে চলে। পার্থক্যটি নিজের scheduler-এ চালিয়ে দেখুন। নিচে Haat-এর বর্ধিত রূপ: অংশ ১-এর deposit-এর আসল চারটি instruction দুটি green thread-এ চলে (একটি 936, একটি 1190 নিয়ে), প্রত্যেকের নিজের operand stack. তিনটি নীতি: cooperative (শুধু YIELD, অর্থাৎ await-এ পালা বদল), preemptive (প্রতি q-টি instruction পরপর), আর একটি নতুন অবিভাজ্য opcode ADD_GLOBAL.
from itertools import combinations
from collections import Counter
# body of Haat's deposit(t) as the reference compiler emits it (haat.py dis)
DEPOSIT = [("LOAD_GLOBAL", "total"), ("LOAD_LOCAL", "t"), ("ADD", None), ("STORE_GLOBAL", "total")]
WITH_AWAIT = DEPOSIT[:1] + [("YIELD", None)] + DEPOSIT[1:] # extension: an await in the middle
ATOMIC = [("LOAD_LOCAL", "t"), ("ADD_GLOBAL", "total")] # extension: one indivisible opcode
def step(task, g): # one instruction; each green thread has its own stack
op, arg = task["code"][task["ip"]]; task["ip"] += 1; s = task["stack"]
if op == "LOAD_GLOBAL": s.append(g[arg])
elif op == "LOAD_LOCAL": s.append(task["t"])
elif op == "ADD": b, a = s.pop(), s.pop(); s.append(a + b)
elif op == "STORE_GLOBAL": g[arg] = s.pop()
elif op == "ADD_GLOBAL": g[arg] += s.pop()
return op
def run(code, policy, order=None):
g = {"total": 0}
tasks = [{"t": t, "code": code, "ip": 0, "stack": []} for t in (936, 1190)]
ready, k = list(tasks), 0 # order: a fixed list of task numbers
while (ready if order is None else k < len(order)):
task = ready.pop(0) if order is None else tasks[order[k]]; k += 1; n = 0
while task["ip"] < len(task["code"]):
op = step(task, g); n += 1
if op == "YIELD" or (policy != "coop" and n == policy): break
if order is None and task["ip"] < len(task["code"]): ready.append(task)
return g["total"]
print("cooperative, no await :", run(DEPOSIT, "coop"))
print("cooperative, one await:", run(WITH_AWAIT, "coop"))
print("preemptive, slice 1..4:", [run(DEPOSIT, q) for q in (1, 2, 3, 4)])
orders = lambda n: [[0 if i in p else 1 for i in range(2 * n)] for p in combinations(range(2 * n), n)]
print("all", len(orders(4)), "one-step orders:", dict(Counter(run(DEPOSIT, 1, o) for o in orders(4))))
print("atomic ADD_GLOBAL, all", len(orders(2)), "orders:", dict(Counter(run(ATOMIC, 1, o) for o in orders(2))))আসল আউটপুট (ব্রাউজারের Python):
cooperative, no await : 2126
cooperative, one await: 1190
preemptive, slice 1..4: [1190, 1190, 1190, 2126]
all 70 one-step orders: {2126: 2, 1190: 34, 936: 34}
atomic ADD_GLOBAL, all 6 orders: {2126: 6}
প্রথম লাইন async-এর নিশ্চয়তা: await না থাকলে পুরো deposit একটানা। দ্বিতীয় লাইনে পড়া আর লেখার মাঝে একটি await বসাতেই cooperative scheduler-এও lost update. তৃতীয় লাইনে preemptive scheduler: চার instruction-এর কম slice হলেই ভুল; ঠিক আসে শুধু slice 4-এ, অর্থাৎ ভাগ্যক্রমে পালা বদল পুরো function-এর পরে পড়লে। চতুর্থ লাইন সব সম্ভাব্য ক্রম গোনে: C(8, 4) = 70টির মাত্র ২টিতে 2126; বাকিগুলোতে একটি জমা হারায়, আর কোনটি হারায় তা ক্রমের ওপর নির্ভর করে (1190 আসে ৩৪টিতে, 936 আসে ৩৪টিতে)। শেষ লাইনে পড়া-যোগ-লেখা একটি opcode, তাই দুটি thread-এর দুটি করে instruction-এর C(4, 2) = 6টি ক্রমের সবকটিতে 2126: ভাষা-স্তরের atomic মানে VM-এর একটি অবিভাজ্য ধাপ।
1LOAD_GLOBAL total2LOAD_LOCAL t3ADD4STORE_GLOBAL total
| চলছে | |
| A-এর stack | |
| B-এর stack | |
| total (global) |
- A পড়ে total. A-এর stack-এ 0. Slice শেষ, scheduler B-তে যায়।
- B-ও পড়ে total. A এখনো লেখেনি, তাই B-এর stack-এও 0. ক্ষতি এখানেই হয়ে গেছে।
- A আনে t. A-এর stack [0, 936].
- B আনে t. B-এর stack [0, 1190]. প্রতিটি green thread-এর stack আলাদা, ঠিক যেমন প্রতিটি goroutine-এর।
- A যোগ করে। [936].
- B যোগ করে। [1190]. B-এর হিসাব পুরোনো 0-এর ওপর।
- A লেখে। total = 936.
- B লেখে, A-এর জমা মুছে যায়। total = 1190, অথচ দুটি জমা মিলে 2126 হওয়ার কথা। explorer-এর “slice 1” ফলটির হুবহু মিল।
এর দুটি নকশা-শিক্ষা। প্রথম, stackless async (Rust, JavaScript, Python) আর stackful green thread (Go, Java virtual thread) একই সমস্যার দুই সমাধান: প্রথমটিতে compiler প্রতিটি async function-কে state machine বানায়, পালা বদলের জায়গা কোডে দেখা যায়, কিন্তু function দুই “রঙে” ভাগ হয়; দ্বিতীয়টিতে runtime পুরো stack রাখে, কোড সাধারণ দেখায়, কিন্তু পালা বদল অদৃশ্য, তাই সাধারণ thread-এর সব শৃঙ্খলা লাগে। দ্বিতীয়, ভাষার “atomic” প্রতিশ্রুতি আসলে VM বা হার্ডওয়্যারের একটি অবিভাজ্য ধাপের প্রতিশ্রুতি। Go-র goroutine আর scheduler-এর OS-স্তরের দিক আছে অপারেটিং সিস্টেম কোর্সের পর্ব ১৪-এ, আর Java-র virtual thread হাতে-কলমে Java কোর্সের পর্ব ৪২-এ.
৮ · Structured concurrency — কাজের জীবনকাল একটি block-এ
Go-র go f() বা JavaScript-এ await না করা একটি Promise একটি “ছুটে যাওয়া” কাজ তৈরি করে: যে function কাজটি শুরু করল, সে ফেরত চলে গেলেও কাজটি চলতে থাকে, তার ভুল কোথাও পৌঁছায় না, আর তাকে বাতিল করার পথও কেউ জানে না। এটি অনেকটা পর্ব ২৭-এর goto-র সমস্যার মতো, আর ঠিক এই তুলনা টেনে Nathaniel J. Smith ২০১৮ সালে “Notes on structured concurrency, or: Go statement considered harmful” লেখেন (তাঁর Python library Trio-র “nursery” ধারণা)।
একটি block যত concurrent কাজ শুরু করে, block থেকে বের হওয়ার আগে সবকটি শেষ বা বাতিল হবে। একটি কাজ ব্যর্থ হলে বাকিগুলো বাতিল হয়, আর ভুলটি block-এর বাইরে ছোড়া হয়। ফলে concurrent কাজের জীবনকাল কোডের গঠনের সঙ্গে মেলে, ঠিক যেমন পর্ব ১৫-এর lexical scope variable-এর জীবনকালকে block-এ বাঁধে।
অংশ ৬-এর program-এর দ্বিতীয় অংশটিই Python 3.11 থেকে আসা TaskGroup: তিনটি courier, Dhaka ০.০১ সেকেন্ডে পৌঁছায়, Sylhet ০.০৫-এ ব্যর্থ হয়, Khulna-র লাগত ০.৫. আউটপুটের শেষ তিন লাইন: Dhaka পৌঁছেছে, Sylhet-এর ভুলটি একটি ExceptionGroup হয়ে except*-এ এসেছে, আর Khulna বাতিল (cancelled: False False True; Sylhet-এর False কারণ সে বাতিল হয়নি, নিজেই ভুল নিয়ে শেষ হয়েছে)। async with block শেষ হওয়ার পর কোনো courier আর চলছে না, এটিই নিশ্চয়তা। Rust-এর thread::scope (অংশ ৫-এর ok.rs) OS thread-এর জন্য একই নীতি: scope শেষ মানে সব thread-এর join, তাই borrow checker নিরাপদে স্থানীয় variable-এর reference thread-কে দিতে পারে। Java-তে StructuredTaskScope Java 21-এ preview, আর JDK 25-এও পঞ্চম preview হিসেবে আছে, তাই এর API এখনো বদলাতে পারে।
Haat-এর বর্ধিত রূপ হিসেবে নকশা (reference-এ নেই, চালানো হয়নি):
// Haat-এর বর্ধিত রূপ: scope, spawn আর atomic var (নকশা, reference-এ নেই)
atomic var total = 0;
fn deposit(t: Int) { total = total + t; } // কম্পাইল হয় ADD_GLOBAL-এ
scope {
spawn deposit(936);
spawn deposit(1190);
} // দুটি spawn শেষ না হলে এখানে পৌঁছায় না
print(total); // সবসময় 2126এখানে type checker-এর দুটি নতুন নিয়ম লাগে: spawn শুধু একটি scope-এর ভেতরে বৈধ (resolver-এর scope chain দিয়ে যাচাই), আর spawn-করা function কোনো সাধারণ var ছুঁতে পারবে না, শুধু let বা atomic var. দ্বিতীয় নিয়মটি Rust-এর Send/Sync-এর অতি সরল রূপ; এর বিস্তারিত নকশা অনুশীলন ১-এ।
আরও গভীরে: C++11-এর memory model গাণিতিকভাবে লেখা হয়েছিল, আর Mark Batty, Peter Sewell ও সহকর্মীরা (২০১১) একে theorem prover-এ রূপ দিয়ে কয়েকটি অসঙ্গতি খুঁজে পান, যার কিছু পরের standard-এ ঠিক হয়। Relaxed atomic-এর “out-of-thin-air” সমস্যা (একটি মান চক্রাকার যুক্তিতে নিজেকেই ন্যায্যতা দেয়) এখনো পুরোপুরি সমাধান হয়নি; standard শুধু একটি অনানুষ্ঠানিক নিষেধ দেয়। Compiler-এর দিক থেকে LLVM IR-এর load atomic … acquire, fence seq_cst আর cmpxchg ঠিক C++-এর ordering নেয়, আর optimizer-এর প্রতিটি pass (পর্ব ৬৫–৬৮) জানে কোন সাধারণ load এদের পার হয়ে সরানো যায় না।
পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:
- Sequential consistency কী? সব thread-এর কাজ যেন একটি একক ক্রমে, প্রতিটি thread-এর নিজের ক্রম ঠিক রেখে, ঘটেছে; প্রতিটি পড়া সেই ক্রমে আগের শেষ লেখা দেখে।
- SB litmus test-এ r1 = r2 = 0 কেন সম্ভব? প্রতিটি core-এর store buffer লেখাকে কিছুক্ষণ নিজের কাছে রাখে, তাই পড়াটি অন্যের লেখার আগে memory থেকে পুরোনো 0 পায়;
seq_cstবা fence দিলে বন্ধ হয়। - Release/acquire কী নিশ্চিত করে? Acquire যদি release-এর লেখা মান পড়ে, release-এর আগের সব লেখা acquire-এর পরের সব পড়ার কাছে দৃশ্যমান।
- DRF-SC কী? SC execution-এ data race না থাকলে program SC-র মতো আচরণ করে; race থাকলে ভাষাভেদে UB (C/C++) বা সীমিত নিশ্চয়তা (Java-তে)।
- Async আর green thread-এর পার্থক্য? Async-এ পালা বদল শুধু
await-এ (stackless, compiler-এর state machine); green thread-এ runtime যেকোনো বিন্দুতে বদলাতে পারে (stackful, M:N ধরনের)।
৯ · AI-এর যুগে memory model আর async কোড
Concurrency-র দাবি যাচাই করা কঠিন, কারণ ভুল কোডও প্রায়ই সঠিক ফল দেয় (অংশ ৫-এর Go run মনে করুন)। এই বিষয়ে AI-এর বারবার দেখা ভুল:
| AI-এর ভুল | কীভাবে ধরবেন |
|---|---|
এক ভাষার নিয়ম সবখানে: “volatile দিলে thread-safe” (C/C++-এর volatile thread-এর জন্য নয়, Java-র volatile আলাদা জিনিস) | ভাষা আর version ধরে standard বা specification-এর অংশ খোঁজা |
| “x86-এ চলে, তাই relaxed যথেষ্ট”: হার্ডওয়্যারের আচরণকে ভাষার নিশ্চয়তা ভাবা | ভাষার memory model-এ hb পথ আঁকা; compiler-ও reorder করতে পারে মনে রাখা |
| ভুল ordering: data-র আগে relaxed flag, বা acquire-এর পর মান পরীক্ষা না করা | প্রতিটি সাধারণ ছোঁয়ার জন্য sb + sw পথ খোঁজা; vector-clock বা TSan দিয়ে চালানো |
| “একবার চালিয়ে ঠিক এসেছে” বা “০ বার ঘটেছে, তাই অসম্ভব” | litmus-ধাঁচের ছোট পরীক্ষা হাজারো রাউন্ড; সম্ভব হলে সব interleaving গোনা; race detector |
| “async-এ race হয় না” বা উল্টো “async-এ lock লাগে” | পড়া আর লেখার মাঝে কোনো await আছে কি না দেখা |
বানানো API বা flag (যেমন অস্তিত্বহীন একটি memory_order বা Java preview API-কে স্থিতিশীল বলা) | compiler-এ compile করে দেখা; JEP বা documentation-এ অবস্থা মেলানো |
AI-কে ভালোভাবে কাজে লাগানোর উপায়: কোডের সঙ্গে প্রতিটি ভাগ করা ঘরের hb যুক্তি আর যাচাইয়ের পরিকল্পনা চাওয়া, তারপর নিজে চালানো।
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১Lamport ১৯৭৯ সালেই sequential consistency সংজ্ঞায়িত করেছিলেন। তাহলে আজকের CPU-গুলো SC দেয় না কেন?
Lamport-এর লক্ষ্য ছিল একটি সঠিকতার মানদণ্ড: একটি multiprocessor-কে “সঠিক” বলা যাবে, যদি তার আচরণ কোনো একক interleaving দিয়ে ব্যাখ্যা করা যায়। মানদণ্ডটি প্রোগ্রামারের জন্য আদর্শ, কারণ পর্ব ৪০-এর small-step semantics দিয়েই সব যুক্তি চলে। সমস্যা হলো গতি।
একটি memory-লেখা cache-এ পৌঁছাতে, বিশেষত যখন cache line অন্য core-এর কাছে আছে, অনেক cycle লাগে। প্রতিটি লেখায় core থেমে থাকলে বেশির ভাগ সময় যেত অপেক্ষায়। Store buffer এই অপেক্ষা লুকায়: লেখা সারিতে রেখে core এগিয়ে যায়। কিন্তু অংশ ২-এর stepper দেখিয়েছে, এতে SB-র (0, 0) সম্ভব হয়, অর্থাৎ SC ভাঙে। x86 এই একটি ছাড় দেয় (পরের পড়া আগের লেখাকে টপকাতে পারে); Peter Sewell ও সহকর্মীরা এই আচরণকে x86-TSO নামে আনুষ্ঠানিক মডেলে লেখেন (২০১০ সালের কাছাকাছি প্রকাশিত)। ARM আর POWER আরও এগিয়ে লেখা-লেখা আর পড়া-পড়ার ক্রমও বদলাতে দেয়, তাই সেখানে MP-ও fence ছাড়া ভাঙে।
Compiler-ও একই পথে হাঁটে। Register-এ একটি মান রেখে বারবার memory না পড়া, loop থেকে load বাইরে আনা, দুটি স্বাধীন লেখার ক্রম বদলানো: এক thread-এর চোখে এগুলো নিরীহ, অন্য thread-এর চোখে নয়। প্রতিটি সাধারণ পড়া-লেখায় SC রাখলে এই সব optimization বন্ধ হতো।
সমাধান ছিল একটি আপস, যা DRF-SC নামে পরিচিত: হার্ডওয়্যার আর compiler সাধারণ কাজ যেমন খুশি সরাক, কিন্তু প্রোগ্রামার synchronization-এর জায়গা চিহ্নিত করবেন (atomic, lock), আর সেই বিন্দুগুলোতে বাধা বসবে। এর ফলে race-free program SC দেখে, আর বাকি কোড পূর্ণ গতি পায়। অংশ ৩-এর run-এ seq_cst সংস্করণে ০ এসেছে ঠিক এই বাধার জন্য।
মূল উপলব্ধি: SC হারায়নি; সেটি হার্ডওয়্যারের ডিফল্ট থেকে সরে ভাষার চুক্তিতে চলে গেছে। প্রোগ্রামার synchronization ঠিকমতো দিলে SC ফেরত পান, আর না দিলে কোনো স্তরই তা দেয় না।
প্র ০২Java race-ওয়ালা program-কেও কিছু নিশ্চয়তা দিতে চেয়েছিল। কাজটি এত কঠিন হলো কেন, আর “out-of-thin-air” সমস্যা কী?
Java ১৯৯৫ থেকেই thread-সহ ভাষা, আর এর প্রথম memory model (Java Language Specification-এর মূল অধ্যায়) পরে ত্রুটিপূর্ণ প্রমাণিত হয়: কিছু নিয়ম সাধারণ compiler optimization নিষেধ করত, আবার কিছু জায়গায় প্রত্যাশিত নিশ্চয়তা দিত না, যেমন final field-এর একটি object অন্য thread-এ আধা-তৈরি দেখা যেতে পারত। William Pugh-এর নেতৃত্বে JSR-133 প্রকল্প মডেলটি নতুন করে লেখে, যা Java 5 (২০০৪)-এ আসে; Jeremy Manson, Pugh আর Sarita Adve ২০০৫ সালে এর আনুষ্ঠানিক রূপ প্রকাশ করেন।
C++ race-কে UB বলে দায় মিটিয়েছে। Java তা পারেনি, কারণ একই JVM-এ অবিশ্বস্ত কোড চলতে পারত, আর race-এর ফলে একটি reference হঠাৎ এমন object দেখাতে পারত, যা নিরাপত্তা-ব্যবস্থাকে ফাঁকি দেয়। তাই Java চাইল: race থাকলেও প্রতিটি পড়া এমন কোনো মান পাবে, যা সত্যিই কোনো লেখা থেকে এসেছে।
এখানেই out-of-thin-air সমস্যা। দুই thread কল্পনা করুন: A করে r1 = x; y = r1;, B করে r2 = y; x = r2;, শুরুতে সব 0. সাধারণ বুদ্ধিতে r1 = r2 = 42 অসম্ভব, কারণ কেউ 42 লেখেই না। কিন্তু একটি অতি-উদার reordering-এর যুক্তি চক্রাকারে চলতে পারে: “ধরি A 42 পড়ল, তাহলে y = 42, তাহলে B 42 পড়ল, তাহলে x = 42, তাই A-এর 42 পড়া ন্যায্য।” এমন চক্র নিষেধ করতে Java “causality” নিয়ম আনে, যা এত জটিল যে পরে গবেষকেরা দেখান কিছু বৈধ ও প্রচলিত optimization সেটি ভাঙে।
C++11 relaxed atomic-এ একই সমস্যার মুখোমুখি হয়, আর standard আজও শুধু একটি অনানুষ্ঠানিক বাক্যে এমন মান নিষেধ করে। একটি পূর্ণাঙ্গ, optimization-বান্ধব, thin-air-মুক্ত আনুষ্ঠানিক মডেল খোঁজা এখনো সক্রিয় গবেষণা।
মূল উপলব্ধি: race-এর আচরণ নির্ধারণ করা race না রাখার নিয়ম বলার চেয়ে অনেক কঠিন। সেই কারণেই সব ভাষার ব্যবহারিক পরামর্শ এক: DRF-SC-র সীমার ভেতরে থাকুন, সীমার বাইরের সূক্ষ্মতায় নির্ভর করবেন না।
প্র ০৩Rust কীভাবে type system দিয়ে data race আটকায়, আর এই নিশ্চয়তার সীমা কোথায়?
Rust-এর ভিত্তি একটি নিয়ম: একটি মানের হয় অনেকগুলো শেয়ার করা reference (&T) থাকতে পারে, নয়তো ঠিক একটি বদলানোর reference (&mut T); দুটি একসাথে নয় (পর্ব ৭৬)। Data race-এর সংজ্ঞা মনে করুন: একই ঘর, অন্তত একটি লেখা, synchronization নেই। “একজন লেখক অথবা অনেক পাঠক” নিয়ম সংজ্ঞাটির দ্বিতীয় শর্তকে এক thread-এর ভেতরেই অসম্ভব করে।
কিন্তু thread-এর সীমা পার হওয়া আলাদা প্রশ্ন, আর সেখানে আসে Send আর Sync. এগুলো “auto trait”: compiler একটি struct-এর সব field Send হলে struct-কেও Send ধরে। ব্যতিক্রমগুলো হাতে লেখা: Rc Send নয় (non-atomic count), Cell আর RefCell Sync নয় (lock ছাড়া ভেতরের বদল), raw pointer দুটির কোনোটিই নয়। thread::spawn-এর signature closure আর তার ফলের ওপর Send + 'static দাবি করে, তাই অংশ ৫-এর দুটি ভুল compile time-এই ধরা পড়ে, run time-এর কোনো tool ছাড়াই।
লক্ষণীয় দিক হলো এই নিয়মগুলো ভাষার core-এ নয়, standard library-তে লেখা। Mutex<T> নিজের ভেতরে unsafe কোড দিয়ে বানানো, আর unsafe impl Sync লিখে library-লেখক প্রতিশ্রুতি দেন যে তালার কারণে ভাগ করা নিরাপদ। অর্থাৎ নিশ্চয়তাটি শর্তসাপেক্ষ: সব unsafe অংশ সঠিক হলে safe কোডে race অসম্ভব। RustBelt প্রকল্প (Ralf Jung ও সহকর্মী, ২০১৮) এই যুক্তির একটি অংশ আনুষ্ঠানিকভাবে প্রমাণ করে।
সীমাও স্পষ্ট। Deadlock আটকায় না: দুটি Mutex উল্টো ক্রমে নিলে চিরকাল অপেক্ষা। Race condition আটকায় না: পড়া আর লেখা দুটি আলাদা lock()-এ করলে lost update ফেরে, কারণ প্রতিটি ছোঁয়া আলাদাভাবে সুরক্ষিত, পুরো কাজটি নয়। আর atomic-এর ordering ভুল বাছলে (যেমন যেখানে acquire লাগত সেখানে relaxed) Rust কিছুই বলে না, কারণ সেটি data race নয়, যুক্তির ভুল।
মূল উপলব্ধি: type system একটি নির্দিষ্ট, ভালোভাবে সংজ্ঞায়িত ভুলের শ্রেণি পুরোপুরি মুছতে পারে। কোন শ্রেণিটি মুছেছে আর কোনটি রয়ে গেছে, তা নিখুঁতভাবে জানাই সেই নিশ্চয়তা ঠিকমতো কাজে লাগানোর শর্ত।
প্র ০৪Rust-এর অলস future আর Go-র goroutine: একই সমস্যার দুটি সমাধান কেন এত আলাদা দেখায়?
দুই ভাষারই লক্ষ্য একটি: লাখো একসাথে চলা নেটওয়ার্ক-কাজ, প্রতিটির জন্য একটি OS thread ছাড়াই। পার্থক্য হলো থামার অবস্থা কোথায় রাখা হয়।
Go (২০০৯) প্রতিটি goroutine-কে একটি ছোট stack দেয়, যা দরকার হলে বড় হয়। Goroutine যেকোনো গভীরতার function call থেকে থামতে পারে, কারণ পুরো stack রাখা থাকে। প্রোগ্রামার সাধারণ blocking কোড লেখেন; runtime-এর scheduler (M:N) নেটওয়ার্কের অপেক্ষায় goroutine-টি সরিয়ে অন্যটি চালায়। শুরুর দিকে পালা বদল হতো শুধু function call-এর মতো বিন্দুতে, তাই call-হীন একটি লম্বা loop অন্যদের আটকাতে পারত; Go 1.14 (২০২০) signal-ভিত্তিক asynchronous preemption এনে এটি মেটায়। দাম: প্রতিটি goroutine-এর জন্য কিছু memory, আর C library ডাকার সময় stack বদলের খরচ।
Rust (async/await স্থিতিশীল হয় 1.39-এ, ২০১৯) উল্টো পথে যায়। Compiler প্রতিটি async fn-কে একটি state machine-এ নামায় (পর্ব ৩১), যার আকার compile time-এ জানা, তাই একটি future-এর জন্য আলাদা stack লাগে না, আর heap-এ বসানোও ঐচ্ছিক। Future অলস: executor poll না করলে চলে না, আর প্রস্তুত না থাকলে একটি Waker রেখে Pending ফেরত দেয়। ভাষা কোনো runtime বেঁধে দেয় না, তাই ছোট embedded যন্ত্র থেকে বড় server পর্যন্ত একই মডেল চলে। দাম: async আর sync function-এর “রং” আলাদা (Bob Nystrom-এর ২০১৫ সালের লেখার ভাষায়), আর lifetime, Pin ও Send-এর নিয়ম async কোডে বেশ জটিল হয়।
Java ২০২৩ সালে (Java 21, virtual thread) Go-র পথ বেছে নেয়, কারণ তার বিশাল বিদ্যমান blocking কোড নতুন করে লেখা সম্ভব ছিল না। C# আর JavaScript Rust-এর কাছাকাছি stackless async বেছেছে, যদিও তাদের Task আর Promise eager.
মূল উপলব্ধি: stackful বনাম stackless হলো “কোড সরল, runtime ভারী” বনাম “runtime হালকা, কোড-এ দাগ” এর আপস। ভাষার লক্ষ্য-ক্ষেত্র (server, embedded, বিদ্যমান কোড) ঠিক করে কোন দামটি সহনীয়।
প্র ০৫Structured concurrency কোথা থেকে এল, আর কেন একে “concurrency-র structured programming” বলা হয়?
১৯৬৮ সালে Dijkstra-র “Go To Statement Considered Harmful” চিঠি একটি সরল কথা বলেছিল: goto থাকলে কোডের গঠন দেখে নিয়ন্ত্রণের প্রবাহ বোঝা যায় না। Structured programming-এর সমাধান ছিল প্রতিটি নিয়ন্ত্রণ-গঠনের একটি প্রবেশ আর একটি প্রস্থান (পর্ব ২৭)।
Nathaniel J. Smith ২০১৮ সালের লেখায় দেখান, go f() বা একটি অপেক্ষাহীন background task ঠিক একই সমস্যা আনে: নিয়ন্ত্রণ দুই ভাগ হয়, আর একটি ভাগ function-এর প্রস্থান পেরিয়ে চলতে থাকে। ফলে তিনটি জিনিস ভাঙে। প্রথম, ভুলের প্রবাহ: ছুটে যাওয়া কাজের exception কার কাছে যাবে? দ্বিতীয়, resource: with open(...) block শেষ হলো, অথচ background কাজ তখনো ফাইল ব্যবহার করছে। তৃতীয়, বাতিল করা: ব্যবহারকারী অনুরোধ বাতিল করলেন, কিন্তু কোন কোন কাজ সেই অনুরোধের, তা কেউ জানে না। তাঁর Trio library-র “nursery” একটি block, যার ভেতরেই কাজ শুরু করা যায়, আর block সব কাজ শেষ না হলে ছাড়ে না। Martin Sústrik-এর C library libdill (২০১৬-র দিকে) একই নামের ধারণা আগেই ব্যবহার করেছিল বলে উল্লেখ পাওয়া যায়।
এরপর ধারণাটি দ্রুত ছড়ায়। Kotlin-এর coroutine-এ coroutineScope, Swift-এর TaskGroup, Python 3.11-এর asyncio.TaskGroup (অংশ ৮-এর run), Rust-এর thread::scope, আর Java-র StructuredTaskScope (JDK 25-এও preview অবস্থায়)। এর সঙ্গে আসে ভুল একত্র করার নতুন ভাষা-সুবিধা: Python-এর ExceptionGroup আর except* ঠিক এই প্রয়োজনে 3.11-এ যোগ হয়, কারণ কয়েকটি concurrent কাজ একসাথে ব্যর্থ হতে পারে।
Compiler আর ভাষা-নকশার চোখে লাভটি গুরুত্বপূর্ণ: একটি কাজের জীবনকাল lexical scope-এ বাঁধা থাকলে borrow checker বা escape analysis জানে কোন স্থানীয় variable-এর reference কাজকে দেওয়া নিরাপদ। Rust-এর thread::scope ঠিক এ কারণেই 'static-এর দাবি তুলে দিতে পারে।
মূল উপলব্ধি: যে নীতি sequential কোডে goto সরিয়েছিল, সেই নীতিই concurrent কোডে “ছুটে যাওয়া” কাজ সরায়: কোডের গঠন দেখে আচরণ বোঝা যাওয়া উচিত।
অনুশীলন
প্রথমে নিজে করুন, তারপর উত্তর খুলে মেলান। আউটপুটগুলো এই পর্বের scheduler, CPython 3.14.4 আর Haat reference-এ চালিয়ে মেলানো।
-
নকশা — Haat-এ
scope,spawnআরatomic var(Haat-এর বর্ধিত রূপ): অংশ ৮-এর নকশাটি বাস্তবায়নের পরিকল্পনা লিখুন। (ক) Lexer, parser আর AST-এ কী যোগ হবে? (খ) Resolver আর type checker-এর নতুন নিয়ম কী, আর error message কেমন হবে? (গ) Bytecode compiler আর VM-এ কী বদলাবে, যাতেatomic var-এtotal = total + t;সবসময় অবিভাজ্য হয়?(ক) তিনটি নতুন keyword:
scope,spawn,atomic(keyword তালিকা বাড়লে এই নামের পুরোনো variable ভাঙবে, পর্ব ০৬-এর backward compatibility). Parser-এ দুটি নতুন statement:scope Blockআরspawn Call ;, আর declaration-এ ঐচ্ছিকatomicশুধুvar-এর আগে। AST-এScope(body)আরSpawn(call)node, আরLet-এর মতো declaration node-এ একটিatomicflag.(খ) Resolver scope chain-এ “এখন কোনো
scope-এর ভেতরে আছি কি না” রাখে; না থাকলে3:5: error: 'spawn' outside of a scope block(Haat-এর ফরম্যাট, spec সিদ্ধান্ত ২৪-এর মতো keyword-এর অবস্থানে)। Type checker দেখেSpawn-এর call-টির ফল Unit কি না। Capture নিয়ম: spawn-করা function বা তার nested closure যদি কোনো non-atomicvar-এ লেখে বা পড়ে, তাহলেerror: spawned function 'deposit' uses mutable variable 'total' that is not atomic. Resolver আগেই জানে প্রতিটি নাম কোন declaration-এর (পর্ব ৫১), তাই এটি একটি ছোট pass.atomic var-এর type শুধু Int (সরলতার জন্য)।(গ) Compiler একটি ছক চিনবে: atomic global g-তে
g = g + e;যেখানে e-তে g নেই। তখন সে আগের চার instruction-এর বদলেe-এর কোড, তারপরADD_GLOBAL gদেবে (এই পর্বের scheduler-এর মতো)। অন্য যেকোনো রূপে atomic-এ লেখা (যেমনg = g * 2;) হয় compile error, নয়তো একটি সাধারণCAS_GLOBALloop. VM-এSpawnএকটি নতুন green thread (নিজের stack আর frame) scheduler-এর সারিতে রাখে, আরScope-এর শেষে একটিJOIN_SCOPEopcode সেই scope-এর সব thread শেষ না হওয়া পর্যন্ত বর্তমান thread-কে থামিয়ে রাখে। কোনো spawn-করা thread runtime error দিলে বাকিদের বাতিল করে error-টি scope-এর অবস্থানে ছোড়া হয়: structured concurrency. -
ভুল খুঁজুন আর প্রমাণ করুন: একজন C++20-এ লিখলেন: thread A —
order_total = 2126; ready.store(true, std::memory_order_relaxed);আর thread B —while (!ready.load(std::memory_order_relaxed)) {} std::printf("%d\n", order_total);, যেখানেorder_totalএকটি সাধারণintআরreadyএকটিstd::atomic<bool>. তাঁর যুক্তি: “x86-এ চালিয়ে হাজারবার 2126 পেয়েছি।” ভুলটি কী? ঠিক করুন, আর hb-এর সংজ্ঞা থেকে প্রমাণ করুন যে ঠিক করা রূপে B সবসময় 2126 ছাপে।ভুল: relaxed store আর relaxed load-এর মাঝে কোনো synchronizes-with তৈরি হয় না। তাই A-এর
order_total = 2126(sb-তে store-এর আগে) আর B-এরorder_totalপড়ার মাঝে কোনো hb পথ নেই: দুটি সংঘাতপূর্ণ non-atomic ছোঁয়া, অর্থাৎ data race, আর C++-এ পুরো program-এর আচরণ undefined. x86-এ হাজারবার ঠিক আসা কোনো প্রমাণ নয়: x86 MP-তে store-store বা load-load reorder করে না (litmus explorer-এর “store buffers add []”), কিন্তু compiler করতে পারে, আর ARM-এ হার্ডওয়্যারও করে (explorer-এর “reordering adds [(1, 0)]” সারি দেখুন)।ঠিক রূপ:
ready.store(true, std::memory_order_release);আরwhile (!ready.load(std::memory_order_acquire)) {}.প্রমাণ। W = A-এর
order_totalলেখা, S = release store, L = loop-এর শেষ acquire load (যেটি true পড়ে loop ভাঙে), R = B-এরorder_totalপড়া।- W sb S, কারণ A-এর program order-এ W আগে।
ready-এ true লেখে শুধু S, আর L true পড়েছে, তাই L ঠিক S-এর মান পড়ে; S release, L acquire, অতএব S sw L.- L sb R, B-এর program order-এ।
- hb হলো sb ∪ sw-এর transitive closure, তাই W hb R.
order_total-এ আর কোনো লেখা নেই, তাই কোনো সংঘাতপূর্ণ জোড়া ক্রমহীন নয়: program data-race-free. - একটি non-atomic পড়া তার hb-তে থাকা শেষ লেখার মান পায় (আর race-free বলে অন্য কোনো লেখা প্রতিদ্বন্দ্বী নয়); তাই R পায় 2126. ∎
-
আউটপুট অনুমান করুন: (ক) অংশ ৭-এর green-thread scheduler-এ
run(DEPOSIT, 2)(slice 2, round robin, A আগে) কী দেয়? প্রতিটি slice-এর পরে total আর দুই stack লিখুন। (খ) Python asyncio-তে নিচের কোড কী ছাপে?import asyncio;total = 0;async def get(t): await asyncio.sleep(0.01); return t;async def deposit(t): global total; total = total + await get(t);async def main(): await asyncio.gather(deposit(936), deposit(1190)); print(total);asyncio.run(main()).(ক) 1190 (scheduler-এর আউটপুটের “slice 1..4” তালিকার দ্বিতীয় মান)। Slice ১ (A):
LOAD_GLOBAL,LOAD_LOCAL→ A-এর stack [0, 936], total 0. Slice ২ (B): একই → B [0, 1190]. Slice ৩ (A):ADD,STORE_GLOBAL→ total 936, A শেষ। Slice ৪ (B):ADD→ [1190],STORE_GLOBAL→ total 1190. B 936 লেখার আগেই 0 পড়েছিল।(খ) CPython 3.14.4-এ লেখকের সত্যিকারের run ছাপে
1190.total + await get(t)-এ Python বাঁ থেকে ডানে চলে: আগেtotalপড়ে (0), তারপরawait-এ থামে। দুটি task-ই থামার আগে 0 পড়েছে। ঘুম শেষে প্রথম task লেখে 0 + 936, দ্বিতীয়টি লেখে 0 + 1190, তাই শেষে 1190. Async কোডে lost update ফেরে, কারণ পড়া আর লেখার মাঝে একটিawait. সমাধান: আগেv = await get(t), তারপরtotal = total + v(মাঝে কোনো await নেই), আর তখন ছাপে 2126. -
Litmus test গুনুন: “2+2W” পরীক্ষাটি নিন (শুরুতে x = y = 0): thread A —
x = 1; y = 2;, thread B —y = 1; x = 2;. দুটি thread শেষ হলে (x, y) কী কী হতে পারে sequential consistency-তে? প্রমাণ করুন যে (x, y) = (1, 1) SC-তে অসম্ভব। FIFO store buffer-ওয়ালা x86-ধাঁচের যন্ত্রে কি (1, 1) সম্ভব?এই পর্বের explorer-এর মতো একটি ছোট গণনায় (শেষে memory পড়ে) SC-র ৬টি interleaving থেকে ফল তিনটি: (1, 2), (2, 1) আর (2, 2). x-এর শেষ মান x-এ শেষ লেখকের, y-এরও তাই।
- ধরি শেষে x = 1. তাহলে A-এর
x = 1একক ক্রমে B-এরx = 2-এর পরে। - B-এর program order-এ
y = 1আসেx = 2-এর আগে, আর A-এরy = 2আসেx = 1-এর পরে। তাই ক্রমে: B-এরy = 1→ B-এরx = 2→ A-এরx = 1→ A-এরy = 2. - তাহলে y-এর শেষ লেখা A-এর
y = 2, অর্থাৎ y = 2, y = 1 নয়। তাই (1, 1) অসম্ভব। ∎
FIFO store buffer-এ এটি বদলায় না: প্রতিটি thread-এর লেখা memory-তে program order-এই নামে, আর শেষ ফল নির্ভর করে শুধু memory-তে নামার ক্রমের ওপর, যা আবার দুই thread-এর FIFO ক্রমের একটি interleaving. তাই x86-TSO-তে (1, 1) নিষেধ। Store-store reorder করতে দেয় এমন দুর্বল মডেলে (অংশ ২-এর খেলনা “reordering” যন্ত্রের মতো) এটি সম্ভব; সেখানে আটকাতে প্রতিটি thread-এর দুই লেখার মাঝে একটি fence লাগে।
- ধরি শেষে x = 1. তাহলে A-এর
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমPython asyncio-তে async def branch(name, parts, wait) প্রতিটি অংশ যোগ করে ছাপে আর await asyncio.sleep(wait) করে, শেষে “done” ছাপে। await asyncio.gather(branch("w1", [936], 0.1), branch("w2", [990, 200], 0.01)) চালালে লাইনগুলো কোন ক্রমে ছাপা হয়, সাজান (▲▼ চেপে সরান):
- w1: +936
- w2: +990
- w2: +200
- w2: done 1190
- w1: done 936
Store buffering litmus test (শুরুতে x = y = 0): thread A — x = 1; r1 = y;, thread B — y = 1; r2 = x;. Sequential consistency-তে কোন ফলটি অসম্ভব?
- r1 = 0, r2 = 1
- r1 = 1, r2 = 1
- r1 = 0, r2 = 0
- r1 = 1, r2 = 0
C++-এ thread A একটি সাধারণ variable-এ লিখে তারপর flag.store(1, std::memory_order_release) করে। Thread B flag.load(std::memory_order_acquire)-এ 1 পায়, তারপর সেই variable পড়ে। কোনটি ঠিক?
- B পুরোনো মান পেতে পারে, কারণ সাধারণ variable atomic নয়
- B নতুন মানটিই পায়, কারণ লেখাটি পড়ার happens-before-এ
- নিশ্চয়তার জন্য দুটিকেই seq_cst করতে হবে
- এটি data race, তাই আচরণ undefined
“DRF-SC” নিশ্চয়তা কী বলে?
- Compiler সব data race খুঁজে compile error দেয়
- যেকোনো program, race থাকুক বা না থাকুক, sequentially consistent আচরণ করে
- আধুনিক CPU নিজেই সব সময় SC দেয়
- Program-এর SC execution-গুলোতে data race না থাকলে তার আচরণ sequentially consistent
Rust-এ let total = std::rc::Rc::new(936); তারপর std::thread::spawn(move || println!("{}", total)); লিখলে কী ঘটে?
- Compile error, কারণ
RcSendনয় - Program চলে, কিন্তু মাঝে মাঝে ভুল সংখ্যা ছাপে
- Run time-এ panic
- ঠিকঠাক 936 ছাপে, কারণ move closure মালিকানা নিয়েছে
Python asyncio-তে দুটি task একটি global total-এ জমা দেয়। কোন লাইনটি lost update ঘটাতে পারে?
total = total + t(মাঝে কোনো await নেই)total = total + await get(t)v = await get(t)তারপরtotal = total + v- প্রতিটি task-এর নিজের local
s = s + t
Python 3.11+-এর asyncio.TaskGroup block-এর ভেতরে তিনটি task-এর একটি exception দিয়ে ব্যর্থ হলো। কী ঘটে?
- ব্যর্থ task-টি চুপচাপ বাদ যায়, বাকিরা শেষ হলে block স্বাভাবিকভাবে শেষ হয়
- Block সঙ্গে সঙ্গে শেষ হয়, বাকি task-গুলো পেছনে চলতেই থাকে
- বাকি অসমাপ্ত task বাতিল হয়, আর ভুলটি ExceptionGroup হয়ে block-এর বাইরে আসে
- পুরো program সঙ্গে সঙ্গে বন্ধ হয়ে যায়
Go-র goroutine আর Java 21-এর virtual thread সম্পর্কে কোন বাক্যটি সঠিক?
- প্রতিটি goroutine বা virtual thread একটি আলাদা OS thread
- এগুলো এক core-এ পালা করে চলে, তাই data race অসম্ভব
- এগুলো ব্যবহার করতে প্রতিটি function-কে async লিখতে হয়
- Runtime অনেক হালকা thread অল্প OS thread-এ চালায় (M:N), আর shared memory-তে synchronization লাগে
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন — অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- Memory model একটি চুক্তি: SC মানে একটি একক interleaving; SB-তে (0, 0) আর MP-তে (1, 0) SC-তে অসম্ভব, কিন্তু store buffer আর reordering এগুলো আনে। Fence বা
seq_cstআটকায়। - সত্যিকারের run: Wandbox-এর C++ SB পরীক্ষায় relaxed-এ r1 = r2 = 0 এসেছে (তিন run-এ ২০ হাজারের মধ্যে 1, 5646, 6394 বার),
seq_cst-এ একবারও নয়। সংখ্যা এক run-এর; শূন্য পাওয়াও নিরাপত্তার প্রমাণ নয়। - Happens-before = sb ∪ sw-এর transitive closure: sw তৈরি হয় শুধু যখন acquire ঠিক release-এর মান পড়ে। ক্রমহীন সংঘাতপূর্ণ ছোঁয়া data race; DRF-SC বলে race-free program SC দেখে।
- ভাষাভেদে চুক্তি: C/C++-এ race UB, Java-তে সীমিত নিশ্চয়তা, Go-তে race detector, safe Rust-এ
Send/Syncদিয়ে compile error, Python-এ build দেখে কথা বলা। - Runtime: async = stackless, পালা বদল শুধু
await-এ; green thread = stackful M:N, পালা বদল যেকোনো জায়গায়; structured concurrency = কাজের জীবনকাল আর ভুল একটি block-এ বাঁধা।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ৭৮ · Metaprogramming — macro, template আর reflectionপরবর্তী পর্বযে code অন্য code লেখে।
- প্রোগ্রামিং ভাষা ও কম্পাইলার · কোর্স হোম৮৬টি পর্বপুরো কোর্সের মানচিত্র আর Haat প্রজেক্টের পথ।
- পর্ব ১১ · Concurrent programming-এর মডেল — thread, actor, CSP আর dataflowআগের ভিত্তিচারটি মডেল আর lost update-এর গণনা।
- Hardware support — atomic instruction, spinlock আর memory orderingপাশের ট্র্যাকAtomic আর ordering-এর হার্ডওয়্যার দিক।
- async, future আর atomics — পেছনে কাজ, পরে ফলপাশের ট্র্যাকC++-এ std::atomic আর future হাতে-কলমে।
- asyncio — এক thread-এ অনেক অপেক্ষা, async আর awaitপাশের ট্র্যাকPython-এর event loop, task আর TaskGroup.