এই পর্বে যা শিখবেন
- Concurrency আর parallelism-এর পার্থক্য উদাহরণ দিয়ে বলা, আর চারটি বড় মডেল (shared memory, actor, CSP, dataflow) চেনা
- Interleaving গুনে আর ধাপে ধাপে চালিয়ে দেখানো কেন lost update হয়, আর mutex ও atomic operation কীভাবে তা ঠেকায়
- Actor আর CSP মডেলে বাজারঘরের হিসাব কয়েকটি worker-এ ভাগ করে আবার জোড়া লাগানো, আর ফল কেন ক্রমের ওপর নির্ভর করে না তা প্রমাণ করা
- JavaScript-এর event loop-এ কোন কাজ কখন চলে তা আগে থেকে হিসাব করা
- AI-এর দেওয়া concurrent কোড “একবার চালিয়ে ঠিক এসেছে” দেখে মেনে না নিয়ে বারবার চালানো, সব ক্রম ভাবা আর ভাষার নিয়ম মিলিয়ে যাচাই করা
১ · Concurrency বনাম parallelism — এক ওয়েটার, অনেক টেবিল
পুরান ঢাকার একটি রেস্তোরাঁয় দুপুরে একজন ওয়েটার পাঁচটি টেবিল সামলান। এক টেবিলের অর্ডার নিয়ে রান্নাঘরে স্লিপ দেন, রান্না হওয়ার অপেক্ষায় না দাঁড়িয়ে আরেক টেবিলে পানি দেন, তারপর তৃতীয় টেবিলের বিল আনেন। কোনো মুহূর্তে তিনি একটিই কাজ করছেন, তবু পাঁচটি টেবিলের কাজ একসাথে এগোচ্ছে। এটি concurrency. এবার রান্নাঘরে তিনজন রাঁধুনি তিনটি চুলায় একই মুহূর্তে তিনটি পদ রাঁধছেন: এটি parallelism.
Concurrency program-এর গঠনের গুণ: program কয়েকটি স্বাধীনভাবে এগোতে পারা কাজে ভাগ করা, যাদের জীবনকাল একে অপরের সঙ্গে মিশে যেতে পারে। Parallelism চালানোর (execution) গুণ: একাধিক হিসাব একই মুহূর্তে আলাদা হার্ডওয়্যারে চলে। Concurrent program এক core-এ পালা করে চলতে পারে; আবার একটি sequential program-এর ভেতরেও compiler বা CPU parallelism আনতে পারে (যেমন SIMD নির্দেশ)।
ছবি ১১.১ — একই দুটি কাজ, এক core বনাম দুই core
A = ঢাকার অর্ডার গোনা, B = রাজশাহীর অর্ডার গোনা। সময় বাঁ থেকে ডানে।
এই পর্ব concurrency-কে একটি programming paradigm-এর চোখে দেখে: ভাষা কোন ধারণা দেয় (thread, actor, channel, promise), আর সেই ধারণা কোন ভুল সম্ভব করে বা অসম্ভব করে। Thread কীভাবে OS-এ তৈরি হয় আর scheduler কীভাবে বেছে নেয়, তা অপারেটিং সিস্টেম কোর্সের পর্ব ১৪-এ আছে; memory model আর async runtime-এর ভাষা-স্তরের গভীর আলোচনা আসবে পর্ব ৭৭-এ (ভাষার স্তরে concurrency).
মডিউল ২-এর চলমান কাজটি এখানেও আছে: চারটি অর্ডার, ঢাকা (চাল 2 × 520), রাজশাহী (ডাল 3 × 120, তেল 1 × 180), ঢাকা (চিনি 4 × 150, চা 2 × 250), ঢাকা (লবণ 5 × 40); মোট ১০০০ টাকা বা বেশি হলে ১০% ছাড়; ঢাকার অর্ডারগুলোর যোগফল। পর্ব ০৯-এ উত্তর এসেছিল 2126. এবার কাজটি কয়েকটি worker-এ ভাগ হবে, আর প্রশ্ন হবে: ভাগ করার পরও কি সবসময় 2126 আসে?
Haat v1-এ thread বা channel নেই; Haat একটি sequential ভাষা। তবু ভাগ করার মূল যুক্তি Haat-এ দেখানো যায়: দুই worker দুই ভাগের যোগফল দেয়, তারপর জোড়া। কোর্সের Haat reference বাস্তবায়নে সত্যিকারের run (CPython 3.14.4; run আর vm দুটিতেই একই আউটপুট):
// বাজারঘর: কাজ দুই worker-এ ভাগ, তারপর জোড়া
fn discounted(t: Int) -> Int {
if t >= 1000 { return t - t / 10; }
return t;
}
fn keep(d: Str, t: Int) -> Int {
if d == "Dhaka" { return discounted(t); }
return 0;
}
// worker 1 পায় প্রথম দুই অর্ডার, worker 2 পায় শেষ দুই অর্ডার
fn worker1() -> Int { return keep("Dhaka", 2 * 520) + keep("Rajshahi", 3 * 120 + 1 * 180); }
fn worker2() -> Int { return keep("Dhaka", 4 * 150 + 2 * 250) + keep("Dhaka", 5 * 40); }
let p1 = worker1();
let p2 = worker2();
print(p1);
print(p2);
print(p1 + p2);
print(p2 + p1);~/haat $ python haat.py run split.haat
936
1190
2126
2126
দুই worker-এর মধ্যে কোনো ভাগ করা variable নেই: প্রত্যেকে নিজের অংশ পড়ে একটি মান ফেরত দেয়, আর ফল let-এ বসে। যোগ সংযোজী আর বিনিময়যোগ্য, তাই কে আগে শেষ করল তাতে কিছু আসে যায় না (শেষ দুই লাইন)। এটিই সব নিরাপদ parallel হিসাবের ছক: ভাগ করুন, কিছু ভাগাভাগি করবেন না, শেষে সংযোজী operation দিয়ে জোড়া লাগান। সমস্যা শুরু হয় যখন worker-রা একটি বদলানো যায় এমন variable ভাগ করে।
২ · Shared memory আর thread — যোগ কেন হারিয়ে যায়
Shared-memory concurrency সবচেয়ে পুরোনো আর এখনো সবচেয়ে প্রচলিত মডেল: একটি process-এর কয়েকটি thread একই memory দেখে, আর সাধারণ পড়া-লেখা দিয়েই তথ্য আদান-প্রদান করে। C-এর pthreads, Java-র Thread, Python-এর threading সবই এই মডেলের। বিপদ: একটি সরল লাইন আসলে কয়েকটি ধাপ।
ধরুন বাজারঘরের দুটি thread প্রতিটি নতুন অর্ডারে count = count + 1 করে। Compiler এই লাইনকে অন্তত তিনটি যন্ত্র-ধাপে নামায় (পর্ব ০৫-এর code generation): memory থেকে register-এ পড়া, register-এ যোগ, register থেকে memory-তে লেখা। দুই thread-এর ধাপগুলো যেকোনো ক্রমে মিশতে পারে; এমন প্রতিটি মিশ্র ক্রমকে বলে একটি interleaving. নিচের stepper একটি খারাপ ক্রম দেখায়।
1A: r = count // পড়া2A: r = r + 1 // যোগ3A: count = r // লেখা4B: r = count // পড়া5B: r = r + 1 // যোগ6B: count = r // লেখা
| count (memory) | |
| A-এর r | |
| B-এর r |
- A পড়ে। Thread A memory থেকে count = 0 নিজের register r-এ নেয়। এখনো কিছু বদলায়নি।
- B-ও পড়ে। Scheduler এখানে A-কে থামিয়ে B চালায়। B-ও count = 0 পড়ে, কারণ A এখনো কিছু লেখেনি। ক্ষতিটি এই মুহূর্তেই হয়ে গেছে, যদিও দেখা যাচ্ছে না।
- A যোগ করে। A-এর r = 0 + 1 = 1. প্রতিটি thread-এর register আলাদা, তাই B-এর r এখনো 0.
- A লেখে। count = 1. A-এর কাজ শেষ, ফল ঠিক।
- B যোগ করে। B-এর r = 0 + 1 = 1. B যে 0 পড়েছিল তা এখন পুরোনো, কিন্তু B তা জানে না।
- B লেখে, A-এর কাজ মুছে যায়। count = 1, অথচ দুটি অর্ডার এসেছে। একে বলে lost update: দুজনেই পুরোনো মান পড়ে আলাদা করে বদলেছে, আর পরের লেখা আগেরটিকে চাপা দিয়েছে।
Haat-এ thread নেই, কিন্তু এই ক্রমটি আমরা হাতে লিখে sequential program বানাতে পারি: interleaving মানে শেষ পর্যন্ত একটি sequential ক্রম, যা scheduler বেছে নেয়। Reference-এর সত্যিকারের run:
// দুই "thread" একই var count বাড়ায়; ক্রমটি আমরা হাতে লিখছি
var count = 0;
let a = count; // A পড়ে: 0
let b = count; // B পড়ে: 0 (A লেখার আগেই)
count = a + 1; // A লেখে: 1
count = b + 1; // B লেখে: 1 (A-র কাজ মুছে গেল)
print(count);
var safe = 0;
let a2 = safe; // A পড়ে, যোগ করে, লেখে — একটানা
safe = a2 + 1;
let b2 = safe; // তারপর B
safe = b2 + 1;
print(safe);~/haat $ python haat.py run lost.haat
1
2
কতগুলো ক্রম সম্ভব, আর কতগুলো ঠিক?
Thread A-তে m-টি আর thread B-তে n-টি অবিভাজ্য ধাপ থাকলে, আর প্রতিটি thread-এর নিজের ধাপের ক্রম অপরিবর্তিত থাকলে, সম্ভাব্য interleaving-এর সংখ্যা C(m + n, m) = (m + n)! / (m! · n!).
প্রমাণ।
- একটি interleaving হলো m + n দৈর্ঘ্যের একটি সারি, যার প্রতিটি ঘরে A বা B-এর একটি ধাপ।
- A-এর ধাপগুলো কোন m-টি ঘরে বসবে, তা ঠিক করলেই পুরো সারি ঠিক হয়ে যায়: সেই ঘরগুলোতে A-এর ধাপ নিজের ক্রমে, বাকি ঘরে B-এর ধাপ নিজের ক্রমে।
- আলাদা ঘর-বাছাই আলাদা সারি দেয়, আর প্রতিটি সারি ঠিক একটি বাছাই থেকে আসে। তাই সংখ্যাটি m + n থেকে m-টি ঘর বাছাইয়ের উপায়, C(m + n, m). ∎
m = n = 3 হলে C(6, 3) = 20. মাত্র দশটি করে ধাপে C(20, 10) = 184756; তিনটি thread হলে সংখ্যাটি আরও দ্রুত বাড়ে। এই কারণেই concurrent bug “মাঝে মাঝে” দেখা দেয়: test-এ যে কয়েকটি ক্রম আসে, তাতে খারাপটি না-ও পড়তে পারে। কোনটি ঠিক?
দুই thread-এর প্রতিটি একবার পড়া-যোগ-লেখা করলে শেষে count = 2 হয় শুধু AAABBB আর BBBAAA ক্রমে; বাকি ১৮টিতে count = 1.
প্রমাণ।
- যে thread পরে লেখে, শেষ মান তারই r. সেই r = (সে যা পড়েছিল) + 1.
- শেষ মান 2 হতে হলে শেষ লেখক যেন 1 পড়ে থাকে, অর্থাৎ তার পড়া যেন অন্য thread-এর লেখার পরে হয়।
- শেষ লেখক B ধরি। B-এর পড়া A-এর লেখার পরে, আর B-এর যোগ ও লেখা তার পড়ার পরে; তাই B-এর তিন ধাপই A-এর তিন ধাপের পরে: ক্রম AAABBB. A শেষ লেখক হলে একইভাবে BBBAAA.
- অন্য যেকোনো ক্রমে শেষ লেখক 0 পড়েছিল, তাই শেষ মান 1. মোট ২০ − ২ = ১৮টি। ∎
দাবিটি সব ২০টি ক্রম চালিয়ে যাচাই করুন। নিচের কোড ছোট একটি “যন্ত্র” বানায়, যেখানে প্রতিটি thread-এর আলাদা register; তারপর random scheduler দিয়ে ১০০০টি করে বৃদ্ধি চালায় (seed ঠিক করা, তাই প্রতিবার একই ফল)।
from itertools import combinations
from collections import Counter
import random
STEPS = ("read", "add", "write") # one increment = three machine steps
def run(schedule, seed=None, n=1): # schedule like "ABAABB", or random
rng = random.Random(seed)
left = {"A": 3 * n, "B": 3 * n}
count, reg, pc = 0, {"A": 0, "B": 0}, {"A": 0, "B": 0}
for i in range(6 * n):
t = schedule[i] if schedule else rng.choice([x for x in "AB" if left[x]])
step = STEPS[pc[t] % 3]; pc[t] += 1; left[t] -= 1
if step == "read": reg[t] = count # copy into a register
if step == "add": reg[t] = reg[t] + 1
if step == "write": count = reg[t] # store back
return count
schedules = ["".join("A" if i in pos else "B" for i in range(6))
for pos in combinations(range(6), 3)] # where A's 3 steps go
print("interleavings:", len(schedules), " final count ->",
dict(Counter(run(s) for s in schedules)))
print("correct ones:", [s for s in schedules if run(s) == 2])
print("lost update, e.g.:", "ABAABB ->", run("ABAABB"))
print("with a lock (read-add-write in one go):", {run("AAABBB"), run("BBBAAA")})
print("1000 + 1000 increments, 3 random schedules:",
[run(None, seed, 1000) for seed in (1, 2, 3)])আসল আউটপুট (ব্রাউজারের Python):
interleavings: 20 final count -> {2: 2, 1: 18}
correct ones: ['AAABBB', 'BBBAAA']
lost update, e.g.: ABAABB -> 1
with a lock (read-add-write in one go): {2}
1000 + 1000 increments, 3 random schedules: [1123, 1110, 1103]
প্রথম তিন লাইন উপপাদ্য ১১.১ আর ১১.২-এর হুবহু মিল: ২০টি ক্রম, ঠিক দুটিতে 2. চতুর্থ লাইন lock-এর মূল কথা: পড়া-যোগ-লেখা যদি একটানা হয়, অন্য thread মাঝে ঢুকতে না পারে, তাহলে শুধু দুটি ক্রমই সম্ভব, আর দুটিই ঠিক। শেষ লাইনে খেলনা scheduler প্রতিটি ধাপে thread বদলায়, তাই ২০০০-এর জায়গায় ১১০০-র মতো; সত্যিকারের OS scheduler অনেক কম বদলায়, তাই ক্ষতি কম কিন্তু অনিয়মিত (পরের অংশ)।
৩ · Lock, atomic আর data race — সত্যিকারের Java আর Python run
সমস্যার মূলে একটি critical section: পড়া থেকে লেখা পর্যন্ত অংশ, যেখানে একবারে একটিই thread থাকা উচিত। ভাষাগুলো তিন ধরনের হাতিয়ার দেয়: (১) mutex বা lock, যা একটি thread নিলে বাকিরা অপেক্ষা করে; (২) atomic operation, যেখানে হার্ডওয়্যারের একটি অবিভাজ্য নির্দেশ (যেমন x86-এর lock xadd বা compare-and-swap) পুরো পড়া-যোগ-লেখা একসাথে করে; (৩) ভাগ না করা, যা পরের তিন অংশের actor, CSP আর dataflow-এর পথ।
নিচের Java program দুই thread-এ প্রতিটি ১০ লাখ বার তিনটি counter বাড়ায়: একটি কোনো সুরক্ষা ছাড়া, একটি synchronized block-এ (Java-র প্রতিটি object-এর ভেতরের lock), একটি AtomicInteger দিয়ে। এই মুহূর্তে কোর্সের in-page Java runner (Wandbox) সাড়া দিচ্ছে না, তাই program-টি লেখকের যন্ত্রে সত্যিকারের Eclipse Temurin JDK 21.0.13 (javac 21.0.13, GPLv2 + Classpath Exception) দিয়ে চালানো হয়েছে:
import java.util.concurrent.atomic.AtomicInteger;
class Main {
static int plain = 0; // shared, no protection
static int locked = 0; // shared, guarded by LOCK
static final Object LOCK = new Object();
static final AtomicInteger atomic = new AtomicInteger();
static final int N = 1_000_000; // orders per worker
static void work() {
for (int i = 0; i < N; i++) {
plain = plain + 1; // read, add, write: 3 steps
synchronized (LOCK) { locked = locked + 1; }
atomic.incrementAndGet(); // one indivisible step
}
}
public static void main(String[] args) throws InterruptedException {
Thread a = new Thread(Main::work), b = new Thread(Main::work);
a.start(); b.start();
a.join(); b.join();
System.out.println("expected " + 2 * N);
System.out.println("plain " + plain);
System.out.println("synchronized " + locked);
System.out.println("atomic " + atomic.get());
}
}~/cc $ javac Main.java && java Main
expected 2000000
plain 1987132
synchronized 2000000
atomic 2000000
~/cc $ for i in 2 3 4 5; do java Main | grep plain; done
plain 1992690
plain 1960199
plain 1989665
plain 1997172
সত্যিকারের run, পাঁচবার: সুরক্ষাহীন counter প্রতিবার আলাদা আর প্রতিবার কম (১৯ লাখ ৬০ হাজার থেকে ১৯ লাখ ৯৭ হাজারের মধ্যে), কিন্তু synchronized আর atomic প্রতিবার ঠিক 2000000. সংখ্যাগুলো এক যন্ত্রের পর্যবেক্ষণ, নিয়ম নয়; কখনো 2000000 এলেও program ঠিক প্রমাণ হয় না। একই যন্ত্রে static volatile int count দিয়ে count++ চালালে তিনবারে এসেছে 1155721, 1271731, 1376890: volatile দৃশ্যমানতা দেয়, কিন্তু ++-কে অবিভাজ্য করে না।
Python-এ একই পরীক্ষা (CPython 3.14.4, প্রচলিত build, যেখানে GIL চালু), লেখকের যন্ত্রে তিনবার:
~/cc $ python py_threads.py
Python 3.14.4 GIL enabled: True
count += 1 : 2000000 of 2000000
read/sleep/write: 1339 of 2000
same, with Lock : 2000 of 2000
(আরও দুবার: 2000000, 1143, 2000 এবং 2000000, 1186, 2000)
এখানে একটি সৎ কথা জরুরি। তিনবারই count += 1 সব ২০ লাখ গুনেছে। কারণ GIL একবারে একটি thread-কেই Python bytecode চালাতে দেয়, আর নতুন CPython thread বদলায় শুধু কিছু নির্দিষ্ট বিন্দুতে; এই loop-এ সেই বিন্দু পড়া আর লেখার মাঝে পড়েনি। কিন্তু Python ভাষা +=-কে atomic বলে কোনো প্রতিশ্রুতি দেয় না। পড়া আর লেখার মাঝে একটি time.sleep(0) (thread বদলের সুযোগ) রাখলেই ২০০০-এর জায়গায় ১১০০–১৩০০, আর threading.Lock দিলে আবার ঠিক ২০০০. বিস্তারিত Python কোর্সের পর্ব ৪৪-এ; Java-র synchronized, volatile আর AtomicInteger আছে Java কোর্সের পর্ব ৪০-এ.
Race condition: program-এর ফল thread-গুলোর আপেক্ষিক ক্রমের ওপর নির্ভর করে, আর কোনো কোনো ক্রমে ভুল হয়। Data race: দুটি thread একই memory-ঘর ছোঁয়, অন্তত একটি লেখে, আর মাঝে কোনো synchronization (lock, atomic, join) নেই। ওপরের plain দুটোরই উদাহরণ। কিন্তু দুটি এক নয়: lock দিয়ে প্রতিটি পড়া আর লেখা আলাদা আলাদা সুরক্ষিত করলে data race থাকে না, তবু মাঝে অন্য thread ঢুকে race condition রেখে দিতে পারে।
ভাষাভেদে data race-এর পরিণতি খুব আলাদা, আর এটি একটি memory model-এর প্রশ্ন। C11 আর C++11 থেকে data race মানে undefined behavior: compiler ধরে নেয় race নেই, আর সেই ধারণায় optimization করে, তাই ফল যা খুশি হতে পারে। Java-র memory model (Java 5-এ নতুন করে লেখা) race-ওয়ালা program-কেও কিছু নিশ্চয়তা দেয়, ফলে উপরের plain শুধু ভুল সংখ্যা দেয়, program ভেঙে পড়ে না। Rust-এর safe অংশে type system data race-কে compile time-এই অসম্ভব করে। এই তিন পথের বিস্তারিত তুলনা পর্ব ৭৭-এর বিষয়।
Lock-এর নিজের বিপদও আছে। Thread A তালা ১ ধরে তালা ২ চায়, thread B তালা ২ ধরে তালা ১ চায়: দুজনেই চিরকাল অপেক্ষা করে, একে বলে deadlock. প্রচলিত প্রতিকার সব thread-এ একই ক্রমে তালা নেওয়া। Critical section, mutex আর deadlock-এর OS-স্তরের বিস্তারিত আছে অপারেটিং সিস্টেম কোর্সের পর্ব ২২, ২৪ আর ২৭-এ.
৪ · Actor model — নিজের খাতা, নিজের ডাকবাক্স
বাজারঘরের তিনটি শাখার তিনজন হিসাবরক্ষক কল্পনা করুন। কেউ অন্যের খাতায় হাত দেন না। কিছু জানাতে হলে চিরকুট লিখে অন্যজনের ডাকবাক্সে ফেলেন, তারপর নিজের কাজে ফিরে যান। প্রত্যেকে নিজের ডাকবাক্স থেকে একবারে একটি চিরকুট তুলে কাজ করেন। এটিই actor model: ভাগ করা অবস্থা নেই, তাই lock-ও নেই।
একটি actor হলো (১) একটি ব্যক্তিগত অবস্থা, যা আর কেউ ছুঁতে পারে না; (২) একটি mailbox, যেখানে আসা বার্তা জমে; (৩) একটি আচরণ, যা একবারে একটি বার্তা নিয়ে তিনটি কাজ করতে পারে: অন্য actor-কে বার্তা পাঠানো (অপেক্ষা না করে, asynchronous), নতুন actor তৈরি, আর পরের বার্তার জন্য নিজের অবস্থা বা আচরণ ঠিক করা। মডেলটি Carl Hewitt, Peter Bishop ও Richard Steiger-এর ১৯৭৩ সালের গবেষণাপত্র থেকে; Erlang ভাষা (১৯৮০-এর দশকের দ্বিতীয় ভাগ থেকে) আর Akka library এর সবচেয়ে পরিচিত বাস্তবায়ন।
বাজারঘরের কাজে তিনটি actor: দুটি worker (w1, w2) আর একটি summer, যে একাই চলমান মোটের মালিক। অর্ডারগুলো পালা করে w1, w2-তে যায় (w1: ঢাকা 1040, ঢাকা 1100; w2: রাজশাহী 540, ঢাকা 200), শেষে প্রত্যেকের কাছে একটি “done”. Worker ঢাকার অর্ডারের ছাড়-পরবর্তী মোট summer-কে পাঠায়। Scheduler প্রতিবার random-ভাবে একটি অ-ফাঁকা mailbox-ওয়ালা actor বেছে তার একটি বার্তা চালায়।
import random
from collections import deque
ORDERS = [("Dhaka", 2*520), ("Rajshahi", 3*120 + 1*180),
("Dhaka", 4*150 + 2*250), ("Dhaka", 5*40)] # (district, total)
def discounted(t): return t - t // 10 if t >= 1000 else t
def worker(me, msg, send): # an actor's behaviour: one message at a time
if msg[0] == "order" and msg[1] == "Dhaka":
send("sum", ("total", discounted(msg[2]), me["name"]))
elif msg[0] == "done":
send("sum", ("done", 0, me["name"]))
def summer(me, msg, send): # the ONLY owner of the running total
me["sum"] += msg[1]
me["done"] += msg[0] == "done"
me["log"].append(f"{msg[2]}:{msg[1]}")
def run(seed):
rng = random.Random(seed)
actors = {"w1": dict(name="w1", act=worker), "w2": dict(name="w2", act=worker),
"sum": dict(name="sum", act=summer, sum=0, done=0, log=[])}
for a in actors.values(): a["box"] = deque() # mailboxes
send = lambda to, msg: actors[to]["box"].append(msg) # never waits
for i, (d, t) in enumerate(ORDERS): # split the work
send("w1" if i % 2 == 0 else "w2", ("order", d, t))
send("w1", ("done",)); send("w2", ("done",))
while any(a["box"] for a in actors.values()): # scheduler
a = rng.choice([a for a in actors.values() if a["box"]])
a["act"](a, a["box"].popleft(), send)
return actors["sum"]
for seed in (15, 21, 11):
s = run(seed)
print(f"seed {seed}: Dhaka = {s['sum']} arrivals:", " ".join(s["log"]))
runs = [run(seed) for seed in range(200)]
print("200 seeds:", len({" ".join(s["log"]) for s in runs}), "arrival orders,",
"Dhaka totals", {s["sum"] for s in runs})আসল আউটপুট (ব্রাউজারের Python):
seed 15: Dhaka = 2126 arrivals: w1:936 w1:990 w1:0 w2:200 w2:0
seed 21: Dhaka = 2126 arrivals: w1:936 w2:200 w2:0 w1:990 w1:0
seed 11: Dhaka = 2126 arrivals: w2:200 w2:0 w1:936 w1:990 w1:0
200 seeds: 10 arrival orders, Dhaka totals {2126}
তিনটি seed-এ summer-এর কাছে বার্তা তিন রকম ক্রমে এসেছে; ২০০টি seed মিলিয়ে ১০টি আলাদা ক্রম। তবু মোট প্রতিবার 2126, পর্ব ০৯-এর সঙ্গে হুবহু। এখানে কোনো lock নেই, কারণ চলমান মোট শুধু summer ছোঁয়, আর summer একবারে একটি বার্তাই চালায়: actor-এর ভেতরে কোড sequential. ক্রমের ওপর ফল নির্ভর করে না, কারণ যোগ সংযোজী আর বিনিময়যোগ্য (অনুশীলন ৪-এ প্রমাণ)। “এখন পর্যন্ত কত অর্ডার এসেছে” ধরনের ক্রম-নির্ভর প্রশ্নের উত্তর অবশ্য seed-ভেদে আলাদা হতো।
Seed 21-এর ভেতরে কী ঘটে, ধাপে ধাপে দেখুন। লক্ষ করুন, কোনো ধাপে দুটি actor একই অবস্থা ছোঁয় না।
1w1: order → summer-কে total2w2: order → (ঢাকা হলে) total3w1/w2: done → summer-কে done4summer: sum += total5summer: done == 2 → ফল
| w1-এর box | |
| w2-এর box | |
| summer-এর box | |
| sum · done |
- শুরু। w1-এর box-এ ঢাকা 1040, ঢাকা 1100; w2-এর box-এ রাজশাহী 540, ঢাকা 200; দুজনের শেষে done. summer-এর box ফাঁকা।
- w1 চলে। D1040 তুলে নেয়: 1040 ≥ 1000, তাই 936. summer-এর box-এ 936 ফেলে, অপেক্ষা করে না।
- w2 চলে। R540: রাজশাহী, তাই কিছুই পাঠায় না।
- summer চলে। 936 তুলে sum = 936. চলমান মোট শুধু এখানেই বদলায়।
- w2 আবার। D200: ছাড় নেই, 200 পাঠায়। w1-এর D1100 এখনো অপেক্ষায়; কে কখন চলবে তা scheduler-এর হাতে।
- summer: 1136. 936 + 200 = 1136. এই seed-এ 990-এর আগে 200 পৌঁছেছে; অন্য seed-এ উল্টো।
- w2 শেষ। done তুলে summer-কে done(w2) পাঠায়। w2-এর box এখন ফাঁকা।
- summer গোনে। done = 1. একজন worker শেষ, আরেকজন বাকি; তাই summer এখনো ফল ঘোষণা করে না।
- w1: D1100. 1100 − 110 = 990, summer-এর box-এ।
- summer: 2126. 1136 + 990 = 2126.
- w1 শেষ। done(w1) পাঠায়।
- ফল। summer done = 2 দেখে জানে আর কিছু আসবে না: ঢাকা = 2126. মোট ১১টি বার্তা চলেছে, কোনো lock ছাড়া।
দাম: প্রতিটি বার্তা একটি কপি বা সারিতে ঢোকানো, যা সরাসরি memory পড়ার চেয়ে ধীর। লাভ: বার্তা নেটওয়ার্ক দিয়েও যেতে পারে, তাই গঠনটি কয়েকটি যন্ত্রে ছড়ানো সহজ। Message queue-র system design দিক আছে System Design কোর্সের পর্ব ৩১-এ; object-oriented ভাষায় “message passing” শব্দটি অন্য অর্থে (method call) এসেছিল পর্ব ০৮-এ, যদিও Hewitt-এর চিন্তায় Smalltalk-এর প্রভাব ছিল।
৫ · CSP আর channel — হাতে হাতে হস্তান্তর
পোস্ট অফিসের রেজিস্ট্রি চিঠির কথা ভাবুন: পিয়ন চিঠি দরজায় ফেলে চলে যান না, প্রাপক নিজে এসে সই করে না নেওয়া পর্যন্ত দাঁড়িয়ে থাকেন। প্রাপক আগে এলে তিনিও পিয়নের অপেক্ষায় থাকেন। হাতবদলের মুহূর্তে দুজনেই একই জায়গায়। Tony Hoare-এর ১৯৭৮ সালের গবেষণাপত্র “Communicating Sequential Processes” (CSP) এই ধারণাকে concurrency-র ভিত্তি করে।
CSP-তে program কয়েকটি sequential process, যারা কোনো variable ভাগ করে না। যোগাযোগ শুধু channel-এ: ch ! v (v পাঠানো) আর ch ? x (একটি মান নিয়ে x-এ রাখা)। Unbuffered channel-এ পাঠানো আর নেওয়া দুটিই অপেক্ষা করে যতক্ষণ না অন্য পক্ষ হাজির হয়; মিলনের মুহূর্তটিকে বলে rendezvous. তাই একটি হাতবদল একসাথে ডেটা পাঠানো আর synchronization.
Actor-এর সঙ্গে দুটি মূল পার্থক্য: actor-এর নাম আছে আর বার্তা পাঠানো অপেক্ষা করে না (mailbox জমায়); CSP-তে process-গুলো নামহীন হতে পারে, channel-এর নাম থাকে, আর unbuffered পাঠানো অপেক্ষা করে। CSP-র সরাসরি বংশধর occam (১৯৮৩), আর Go ভাষার (২০০৯) goroutine ও channel. Go-তে বাজারঘরের pipeline দেখতে এরকম হতো (উদাহরণ, চালানো হয়নি):
orders, totals := make(chan Order), make(chan int) // unbuffered
go func() { for _, o := range all { orders <- o }; close(orders) }()
go func() {
for o := range orders {
if o.District == "Dhaka" { totals <- discounted(o.Total) }
}
close(totals)
}()
sum := 0
for t := range totals { sum += t }
fmt.Println("Dhaka =", sum)এই পাতায় Go চালানোর ব্যবস্থা নেই, তাই একই গঠন Python generator দিয়ে বানানো একটি ছোট CSP scheduler-এ চালান। প্রতিটি process একটি generator, যা ("send", ch, v) বা ("recv", ch) yield করে থামে; scheduler দুই পক্ষ মিলিয়ে হাতবদল ঘটায়। Go-র close-এর বদলে এখানে None মানে “আর কিছু নেই”।
from collections import deque
ORDERS = [("Dhaka", 1040), ("Rajshahi", 540), ("Dhaka", 1100), ("Dhaka", 200)]
log = []
class Chan: # unbuffered: sender waits for a receiver
def __init__(self, name): self.name, self.senders, self.receivers = name, deque(), deque()
def producer(out):
for o in ORDERS: yield ("send", out, o)
yield ("send", out, None) # None = no more orders
def worker(inp, out):
while (o := (yield ("recv", inp))) is not None:
if o[0] == "Dhaka": yield ("send", out, o[1] - o[1] // 10 if o[1] >= 1000 else o[1])
yield ("send", out, None)
def collector(inp):
total = 0
while (t := (yield ("recv", inp))) is not None: total += t
log.append(f"Dhaka = {total}")
def run(procs): # a tiny round-robin CSP scheduler
ready = deque((p, None) for p in procs)
while ready:
p, val = ready.popleft()
try: op = p.send(val)
except StopIteration: continue
ch = op[1]
if op[0] == "send":
if ch.receivers: # rendezvous: hand the value over now
r = ch.receivers.popleft(); log.append(f"{ch.name}: {op[2]}")
ready += [(r, op[2]), (p, None)]
else: ch.senders.append((p, op[2]))
elif ch.senders:
s, v = ch.senders.popleft(); log.append(f"{ch.name}: {v}")
ready += [(p, v), (s, None)]
else: ch.receivers.append(p)
orders, totals = Chan("orders"), Chan("totals")
run([producer(orders), worker(orders, totals), collector(totals)])
print("\n".join(log))আসল আউটপুট (ব্রাউজারের Python); অর্ডারগুলোতে লাইনের দাম আগেই যোগ করে রাখা:
orders: ('Dhaka', 1040)
totals: 936
orders: ('Rajshahi', 540)
orders: ('Dhaka', 1100)
totals: 990
orders: ('Dhaka', 200)
totals: 200
orders: None
totals: None
Dhaka = 2126
প্রতিটি লাইন একটি হাতবদল। লক্ষ করুন orders আর totals-এর হাতবদল প্রায় পালা করে আসে: unbuffered channel-এ producer worker-কে ছাড়িয়ে যেতে পারে না, কারণ worker নেওয়ার জন্য হাজির না হলে পরের অর্ডার পাঠানোই যায় না। এই স্বয়ংক্রিয় গতি-নিয়ন্ত্রণকে বলে backpressure. রাজশাহীর অর্ডারের পর কোনো totals নেই, তাই দুটি orders পরপর। ফল আবার 2126.
1P: orders ! অর্ডার2W: orders ? o3W: totals ! ছাড়ের পর মোট4C: totals ? t; total += t
| কে অপেক্ষায় | |
| হাতবদল | |
| C-এর total |
- P আগে আসে। Producer D1040 পাঠাতে চায়, কিন্তু
orders-এ কেউ নিতে আসেনি; জমার জায়গা নেই, তাই P অপেক্ষা করে। - প্রথম rendezvous. Worker নিতে আসে, P আগে থেকেই দাঁড়িয়ে: D1040 এখন W-এর হাতে, আর দুজনেই আবার চলতে পারে।
- C অপেক্ষায়। Collector
totals-এ নিতে আসে, কিন্তু W এখনো হিসাব করছে। এবার নেওয়ার পক্ষ অপেক্ষা করে। - দ্বিতীয় rendezvous. W 1040 − 104 = 936 পাঠায়; C আগে থেকে দাঁড়িয়ে, তাই সঙ্গে সঙ্গে হাতবদল। total = 936.
- Backpressure. P পরের অর্ডার R540 নিয়ে আসে, কিন্তু W তখনো ফেরেনি, তাই P অপেক্ষায়; C-ও আবার দাঁড়িয়ে।
- রাজশাহী। W R540 নেয়; জেলা মেলে না, তাই
totals-এ কিছু পাঠায় না, সরাসরি পরের অর্ডারের জন্যorders-এ আসে। C অপেক্ষা চালিয়ে যায়। - D1100. এবার W আগে দাঁড়িয়ে, P এসে সঙ্গে সঙ্গে হাতবদল করে।
- 990. 1100 − 110 = 990, C-এর কাছে; total = 936 + 990 = 1926.
- D200. একইভাবে D200 যায় W-এর কাছে, ছাড় ছাড়া 200 যায় C-এর কাছে; total = 2126.
- শেষের সংকেত। P None পাঠায়, W সেটি পেয়ে loop ছেড়ে
totals-এ None পাঠায়, C সেটি পেয়ে ফল লেখে: Dhaka = 2126. কোনো process কোনো variable ভাগ করেনি।
যোগাযোগ শুধু channel-এ বলে CSP মডেলে deadlock গাণিতিকভাবে খোঁজা যায় (FDR-এর মতো tool). বিপদ: কেউ নিতে না এলে পাঠানো চিরকাল আটকে থাকে (অনুশীলন ৩)। Go-র runtime সব goroutine আটকে গেলে fatal error: all goroutines are asleep - deadlock! বার্তা দিয়ে থামে।
৬ · Dataflow আর reactive — ডেটা হাজির হলেই হিসাব
একটি স্প্রেডশিটে C1 ঘরে লেখা =A1+B1. A1 বদলালে C1 নিজে থেকে নতুন হয়; কে আগে, কে পরে, তা আপনি বলেন না, বলে ঘরগুলোর নির্ভরতা। Dataflow programming এই চিন্তাকে program-এ আনে: program একটি গ্রাফ, প্রতিটি নোড একটি হিসাব, আর নোড চলে যখন তার সব ইনপুট হাজির। দুটি নোড একে অপরের ওপর নির্ভর না করলে স্বাভাবিকভাবেই parallel চলতে পারে; কোনো lock লাগে না, কারণ নোডগুলো মান পাঠায়, ভাগ করা variable বদলায় না।
বাজারঘরের কাজ একটি dataflow গ্রাফ হিসেবে: চারটি অর্ডার → চারটি স্বাধীন “লাইনের দাম যোগ” নোড → চারটি “ছাড়” নোড → “ঢাকা ছাঁকো” → একটি “যোগ” নোড। প্রথম তিন স্তরের নোডগুলো একে অপরের অপেক্ষা করে না; শুধু শেষ যোগ সবার জন্য অপেক্ষা করে। পর্ব ০৯-এর map/filter/fold ঠিক এই গ্রাফ, আর pure function বলেই নোডগুলো যেকোনো ক্রমে চলতে পারে।
Gilles Kahn (১৯৭৪) এমন একটি মডেল বর্ণনা করেন, যেখানে প্রতিটি process sequential, process-গুলো শুধু অসীম FIFO channel দিয়ে যুক্ত, আর channel থেকে পড়া মান না আসা পর্যন্ত অপেক্ষা করে (কোন channel-এ আগে মান আসে, তা “উঁকি দিয়ে দেখা” নিষেধ)। এমন network-এর আউটপুট scheduler-এর ক্রমের ওপর নির্ভর করে না। রূপরেখা: প্রতিটি process ইনপুট-ইতিহাস থেকে আউটপুট-ইতিহাসের একটি monotone (আরও ইনপুট মানে আরও আউটপুট, আগের আউটপুট না বদলে) আর continuous function; পুরো network এই function-গুলোর সমীকরণ, যার একটি অনন্য সবচেয়ে ছোট fixpoint আছে, আর যেকোনো ন্যায্য scheduler সেই fixpoint-এই পৌঁছায়। Fixpoint আর lattice-এর ধারণা আসবে পর্ব ৪১ আর ৬৪-এ।
শর্তটি সূক্ষ্ম: “যে channel-এ আগে মান আসে সেটি নাও” ধরনের নির্বাচন (Go-র select, Erlang-এর যেকোনো বার্তা নেওয়া) অনুমতি দিলে নির্ধারিত ফলের নিশ্চয়তা চলে যায়। এজন্যই actor-এর উদাহরণে বার্তার ক্রম seed-ভেদে বদলেছে, আর ফল টিকেছে শুধু যোগের গাণিতিক গুণে।
Reactive programming dataflow-কে সময়ের সঙ্গে বদলানো মানে প্রয়োগ করে: একটি “stream” (যেমন প্রতিটি নতুন অর্ডার) আর তার ওপর বাঁধা হিসাব, যা উৎস বদলালে নিজে থেকে চলে। ReactiveX-এর মতো library এই ধারার। Dataflow-এর শিকড় ১৯৭০-এর দশকের Lucid আর MIT-র dataflow যন্ত্রের গবেষণায়; সঠিক সাল নিয়ে উৎসভেদে পার্থক্য আছে।
৭ · এক thread-এর concurrency — JavaScript-এর event loop আর async/await
JavaScript-এর প্রচলিত মডেলে আপনার কোড একটিই thread-এ চলে। তবু একটি web server হাজারো অনুরোধ সামলায়, কারণ বেশির ভাগ সময় যায় নেটওয়ার্ক বা ডিস্কের অপেক্ষায়। Event loop সেই অপেক্ষার ফাঁকে অন্য কাজ চালায়, ঠিক অংশ ১-এর একজন ওয়েটারের মতো। নিয়মটি সংক্ষেপে: (১) বর্তমান কোড শেষ পর্যন্ত চলে, কেউ মাঝে ঢোকে না; (২) তারপর সব microtask (Promise-এর then, await-এর পরের অংশ, queueMicrotask) চলে, নতুন microtask এলে সেগুলোও; (৩) তারপর একটি সাধারণ task, যেমন একটি timer, আর আবার (২)।
এই নিয়মের একটি বড় ফল: দুটি await-এর মাঝের কোড কখনো ভাঙে না, তাই অংশ ২-এর মতো “পড়া আর লেখার মাঝে অন্য কেউ” ঘটে না, যদি না মাঝে একটি await থাকে। async/await এই মডেলের ওপর মোড়ক: await function-কে থামিয়ে বাকি অংশকে একটি microtask বানায়। Generator, coroutine আর async/await-এর বাস্তবায়ন আসবে পর্ব ৩১-এ (Generator, coroutine আর async/await).
"use strict";
const orders = [["Dhaka", 1040], ["Rajshahi", 540], ["Dhaka", 1100], ["Dhaka", 200]];
const discounted = t => (t >= 1000 ? t - Math.trunc(t / 10) : t);
const log = [];
// 1) who runs first? synchronous code, then microtasks, then timers
setTimeout(() => log.push("timeout"), 0);
Promise.resolve().then(() => log.push("then 1")).then(() => log.push("then 2"));
queueMicrotask(() => log.push("microtask"));
log.push("sync");
// 2) the running task split across two async "workers"
const sleep = ms => new Promise(r => setTimeout(r, ms));
async function worker(name, part, delay) {
await sleep(delay); // pretend to wait for a network
const sum = part.filter(([d]) => d === "Dhaka")
.reduce((a, [, t]) => a + discounted(t), 0);
log.push(`${name} finished: ${sum}`);
return sum;
}
async function main() {
const parts = await Promise.all([
worker("w1", orders.slice(0, 2), 30), // finishes second
worker("w2", orders.slice(2), 10), // finishes first
]);
log.push(`parts ${JSON.stringify(parts)} -> Dhaka = ${parts[0] + parts[1]}`);
console.log(log.join("\n"));
}
main();আসল আউটপুট (ব্রাউজারের JavaScript; Node.js 24-এও একই):
sync
then 1
microtask
then 2
timeout
w2 finished: 1190
w1 finished: 936
parts [936,1190] -> Dhaka = 2126
প্রথম পাঁচ লাইনের ক্রম নিচের stepper-এ ধাপে ধাপে। দ্বিতীয় অংশে w2 আগে শেষ করেছে (১০ ms বনাম ৩০ ms অপেক্ষা), কিন্তু Promise.all ফলগুলো দেয় ইনপুটের ক্রমে, শেষ হওয়ার ক্রমে নয়: [936, 1190]. দুই ভাগ, 936 + 1190 = 2126, Haat-এর split.haat-এর হুবহু। JavaScript-এর event loop-এর বিস্তারিত আছে JavaScript কোর্সের পর্ব ৩১-এ.
1setTimeout(() => "timeout", 0)2Promise.resolve().then("then 1").then("then 2")3queueMicrotask(() => "microtask")4log.push("sync")
| microtask সারি | |
| timer সারি |
- Timer নিবন্ধন।
setTimeout(…, 0)callback-টি শুধু timer সারিতে রাখে; “0 ms” মানে “এখন নয়”। - Promise. ইতিমধ্যে পূর্ণ একটি Promise-এর
then-ও সঙ্গে সঙ্গে চলে না; “then 1” microtask সারিতে যায়। “then 2” এখনো কোথাও নেই, কারণ সেটি “then 1”-এর ফলের ওপর নির্ভর করে। - queueMicrotask. “microtask” সারিতে “then 1”-এর পেছনে।
- Sync কোড। “sync” সরাসরি log-এ। Script-এর শেষ: বর্তমান কোড শেষ না হওয়া পর্যন্ত কোনো সারির কাজ চলেনি।
- প্রথম microtask. “then 1” চলে; সে শেষ হতেই তার পরের
then, অর্থাৎ “then 2”, সারির পেছনে ঢোকে। - দ্বিতীয় microtask. “microtask” চলে। সারিতে বাকি শুধু “then 2”.
- সারি খালি না হওয়া পর্যন্ত। “then 2” চলে। Microtask সারি এখন খালি; কেবল এখন event loop timer-এর দিকে তাকায়।
- Timer. “timeout” সবশেষে: কোডে প্রথম লাইন, চলার ক্রমে শেষ।
৮ · চার মডেল পাশাপাশি — কোনটি কোন ভুল অসম্ভব করে
ছবি ১১.২ — তিন ধরনের যোগাযোগ
ওপরে ভাগ করা memory, মাঝে actor-এর mailbox, নিচে CSP-র channel.
| মডেল | যোগাযোগ | যা অসম্ভব বা কঠিন করে | নিজের বিপদ | ভাষা/উদাহরণ |
|---|---|---|---|---|
| Shared memory + lock | একই variable পড়া-লেখা | কিছুই না, শৃঙ্খলা প্রোগ্রামারের | data race, lost update, deadlock | C/pthreads, Java, C++, Python threading |
| Actor | asynchronous বার্তা, mailbox | ভাগ করা অবস্থায় data race | বার্তার ক্রম অনিশ্চিত, mailbox উপচে পড়া | Erlang, Elixir, Akka |
| CSP | channel-এ হাতবদল | ভাগ করা অবস্থায় data race (যদি সত্যিই কিছু ভাগ না হয়) | কেউ না নিলে চিরকাল আটকে থাকা | occam, Go |
| Dataflow / reactive | ইনপুট হাজির হলে নোড চলে | ক্রম-নির্ভর ফল (Kahn-এর শর্ত মানলে) | চক্রাকার নির্ভরতা, গ্রাফ বোঝা কঠিন | স্প্রেডশিট, Lucid, stream library |
| Event loop + async | Promise, callback, await | দুই await-এর মাঝে interleaving | লম্বা কাজ পুরো loop আটকায় | JavaScript, Python asyncio |
লক্ষ করুন Go-র মতো ভাষা CSP দেয়, কিন্তু shared memory নিষেধ করে না: একটি pointer channel দিয়ে পাঠিয়ে দুই goroutine-এ একই struct বদলালে আবার data race. তাই “Go-তে channel আছে, তাই data race হয় না” দাবিটি ভুল; Go-র নির্দেশিকার বিখ্যাত বাক্যটি একটি পরামর্শ: “Do not communicate by sharing memory; instead, share memory by communicating.” Erlang-এ process-গুলোর heap সত্যিই আলাদা, আর safe Rust-এ compiler-ই ভাগাভাগি আটকায়: সেখানে নিশ্চয়তা ভাষার, শুধু উৎসাহ নয়।
আরও গভীরে: Hans Boehm-এর ২০০৫ সালের গবেষণাপত্র “Threads Cannot Be Implemented as a Library” দেখায়, ভাষা যদি thread-এর কথা না জানে, তাহলে compiler-এর সাধারণ optimization (যেমন loop থেকে একটি load বাইরে আনা, বা পাশের field একসাথে লেখা) সঠিক lock-ওয়ালা program-কেও ভেঙে দিতে পারে; এই যুক্তিই C++11-এ (Boehm ও Adve-র কাজের ভিত্তিতে) memory model আনতে বড় ভূমিকা রাখে। Compiler-এর দৃষ্টিতে একটি synchronized বা atomic শুধু একটি function call নয়, বরং একটি বাধা, যার ওপারে memory-র পড়া-লেখা সরানো চলবে না। পর্ব ৬৫–৬৬-এর optimization-গুলো তাই প্রতিটি ধাপে “এখানে কি অন্য thread দেখতে পায়?” প্রশ্নের সামনে দাঁড়ায়।
পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:
- Concurrency আর parallelism-এর পার্থক্য? প্রথমটি গঠন (কয়েকটি কাজ একসাথে এগোয়), দ্বিতীয়টি চালানো (একই মুহূর্তে কয়েকটি core-এ); এক core-এ concurrency সম্ভব, parallelism নয়।
count++কেন thread-safe নয়? এটি পড়া, যোগ, লেখা তিন ধাপ; দুই thread-এর ৬ ধাপের ২০টি ক্রমের ১৮টিতে একটি যোগ হারায়।- Race condition আর data race কি এক? না; data race হলো synchronization ছাড়া একই ঘরে একসাথে পড়া-লেখা (C/C++-এ undefined behavior), race condition হলো ক্রম-নির্ভর ভুল ফল, যা data race ছাড়াও হতে পারে।
- Actor আর CSP-র পার্থক্য? Actor-এর বার্তা asynchronous আর mailbox-এ জমে, প্রাপকের নাম থাকে; CSP-তে channel-এর নাম থাকে আর unbuffered হাতবদল দুই পক্ষকে মেলায়।
- JavaScript-এ
setTimeout(f, 0)আরPromise.resolve().then(g), কোনটি আগে? g, কারণ microtask সারি timer-এর আগে খালি হয়।
৯ · AI-এর যুগে concurrent programming
Concurrent কোডে ভুল প্রায়ই প্রথম run-এ ধরা পড়ে না (অংশ ৩-এর Python run মনে করুন)। এই বিষয়ে AI-এর বারবার দেখা ভুল:
| AI-এর ভুল | কীভাবে ধরবেন |
|---|---|
“Python-এ GIL আছে, তাই += thread-safe” বা “volatile দিলে count++ নিরাপদ” | ভাষার documentation-এ atomicity-র প্রতিশ্রুতি খোঁজা; পড়া আর লেখার মাঝে একটি yield বসিয়ে চালানো (উপরের ১১৪৩) |
| এক ভাষার নিয়ম সবখানে: “data race শুধু ভুল সংখ্যা দেয়” (Java-তে মোটামুটি সত্য, C/C++-এ undefined behavior) | ভাষা আর version ধরে memory model দেখা |
| “একবার চালিয়ে ঠিক এসেছে, তাই কোড ঠিক” | অনেকবার, বেশি thread আর বেশি ডেটা দিয়ে চালানো; ThreadSanitizer-এর মতো tool; সম্ভব হলে সব interleaving গোনা |
| Lock যোগ করে deadlock তৈরি: দুই জায়গায় দুই তালা উল্টো ক্রমে | সব তালা নেওয়ার একটি স্থির ক্রম লিখে মেলানো |
Event loop-এর ক্রম ভুল বলা (“setTimeout 0 সঙ্গে সঙ্গে চলে”), বা Promise.all শেষ হওয়ার ক্রমে ফল দেয় বলা | ছোট log-ওয়ালা কোড চালিয়ে ক্রম দেখা |
| “Go/Erlang/Rust-এ race হয় না” ধরনের ঢালাও দাবি | ভাষা কী নিশ্চিত করে আর কী শুধু পরামর্শ দেয়, আলাদা করা |
AI-কে ভালোভাবে কাজে লাগানোর উপায়: কোডের সঙ্গে ঝুঁকির তালিকা আর যাচাইয়ের পরিকল্পনা চাওয়া, তারপর নিজে বারবার চালানো।
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১Actor model কোথা থেকে এল, আর Erlang-এর “let it crash” দর্শন concurrency-র সঙ্গে কীভাবে যুক্ত?
১৯৭৩ সালে Carl Hewitt, Peter Bishop ও Richard Steiger একটি গবেষণাপত্রে “actor”-কে গণনার মৌলিক একক হিসেবে প্রস্তাব করেন। তাঁদের লক্ষ্য ছিল কৃত্রিম বুদ্ধিমত্তার জন্য একটি সাধারণ কাঠামো, আর প্রভাব ছিল LISP, Simula আর Smalltalk-এর মতো ভাষার “বস্তু একে অপরকে বার্তা পাঠায়” ধারণা থেকে। মূল দাবি ছিল সাহসী: সবকিছুই actor, আর actor-এর মধ্যে যোগাযোগ শুধু asynchronous বার্তা।
তত্ত্ব থেকে শিল্পে নিয়ে যায় Erlang. ১৯৮০-এর দশকের দ্বিতীয় ভাগে Ericsson-এর গবেষণাগারে Joe Armstrong, Robert Virding ও Mike Williams টেলিফোন সুইচের সফটওয়্যারের জন্য ভাষাটি তৈরি করেন; ১৯৯৮ সালে এটি open source হয়। টেলিফোন সুইচের চাহিদা ছিল বিশেষ: লাখো একসাথে চলা কল, আর বছরের পর বছর না থেমে চলা। Erlang-এর process OS-এর thread নয়, বরং runtime-এর খুব হালকা process, যাদের heap আলাদা আর যোগাযোগ শুধু বার্তায়, তাই এক process-এর ভুল আরেকটির memory নষ্ট করতে পারে না।
এই বিচ্ছিন্নতাই “let it crash” দর্শনের ভিত্তি। প্রতিটি সম্ভাব্য ভুল আগেভাগে ধরে সামলানোর চেষ্টা না করে Erlang-এ একটি process কিছু অপ্রত্যাশিত হলে মরে যায়, আর একটি “supervisor” process সেটি টের পেয়ে নতুন করে চালু করে। Shared memory-র জগতে এটি বিপজ্জনক হতো, কারণ মরার সময় একটি thread অর্ধেক-বদলানো ভাগ করা ডেটা রেখে যেতে পারে, বা একটি lock না ছেড়েই চলে যেতে পারে। Actor-এ কোনো ভাগ করা অবস্থা নেই, তাই মৃত actor-এর অবস্থা শুধু তার নিজের, আর সেটি ফেলে দিলেই হয়।
এই পর্বের Pyodide উদাহরণে summer একমাত্র মালিক ছিল চলমান মোটের। যদি একটি worker ভুল ডেটায় ভেঙে পড়ত, summer-এর মোট অক্ষত থাকত; একটি supervisor সেই worker-কে আবার চালু করে বাকি অর্ডার পাঠাতে পারত।
মূল উপলব্ধি: Concurrency মডেল শুধু গতির প্রশ্ন নয়, ভুল সামলানোরও প্রশ্ন। কিছু ভাগ না করলে একটি অংশের ব্যর্থতা সেখানেই আটকে থাকে, আর পুরো ব্যবস্থা টিকে থাকে।
প্র ০২Hoare-এর CSP থেকে Go-র channel পর্যন্ত পথটি কেমন, আর Go কেন CSP বেছে নিল?
Tony Hoare ১৯৭৮ সালে Communications of the ACM-এ “Communicating Sequential Processes” প্রকাশ করেন। তিনি লক্ষ করেছিলেন, সেই সময়ের concurrency-র হাতিয়ার (semaphore, ভাগ করা variable) বিশৃঙ্খল: প্রতিটি নতুন সমস্যায় নতুন কৌশল। তাঁর প্রস্তাব ছিল input আর output-কে ভাষার মৌলিক নির্দেশ বানানো, আর process-গুলোর যোগাযোগকে শুধু এই দুই নির্দেশে সীমিত রাখা। মূল গবেষণাপত্রে process-গুলো একে অপরের নাম ধরে যোগাযোগ করত; নামযুক্ত channel-এর রূপ আসে পরে, আর ১৯৮৫ সালের বইয়ে CSP একটি পূর্ণ process algebra হয়, যেখানে দুটি process “সমান” কি না গাণিতিকভাবে প্রমাণ করা যায়।
প্রথম বড় বাস্তব প্রয়োগ occam (১৯৮৩), যা INMOS কোম্পানির transputer চিপের জন্য তৈরি: প্রতিটি চিপে কয়েকটি হার্ডওয়্যার link, যা সরাসরি CSP channel-এর মতো কাজ করত। Rob Pike-এর ১৯৮০ ও ৯০-এর দশকের Newsqueak, Alef আর Limbo ভাষাতেও channel ছিল, আর সেই অভিজ্ঞতা নিয়ে Robert Griesemer, Rob Pike ও Ken Thompson ২০০৯ সালে Go প্রকাশ করেন।
Go-র নকশাকারীদের যুক্তি ছিল ব্যবহারিক। বড় server program-এ হাজারো একসাথে চলা অনুরোধ; প্রতিটির জন্য একটি OS thread ব্যয়বহুল, আর lock দিয়ে সমন্বয় ভুলপ্রবণ। তাই Go দিল খুব হালকা goroutine (runtime অল্প কয়েকটি OS thread-এ এদের ভাগ করে চালায়) আর ভাষার অংশ হিসেবে channel ও select. Pipeline, fan-out (এক channel থেকে কয়েকটি worker), fan-in (কয়েকটি থেকে এক) এই ছকগুলো channel দিয়ে সরাসরি লেখা যায়, ঠিক এই পর্বের P → W → C-এর মতো।
তবে Go পুরোপুরি CSP নয়: sync.Mutex আছে, ভাগ করা memory নিষেধ নয়, আর buffered channel-ও আছে, যেখানে পাঠানো সঙ্গে সঙ্গে rendezvous চায় না। Go-র data race detector (go test -race) থাকা নিজেই প্রমাণ যে race এখনো সম্ভব।
মূল উপলব্ধি: একটি ভাষা একটি মডেলকে “প্রথম শ্রেণির” বানালে প্রোগ্রামার সেই পথেই বেশি হাঁটেন। কিন্তু উৎসাহ দেওয়া আর নিশ্চয়তা দেওয়া আলাদা; নিশ্চয়তা আসে শুধু যখন ভাষা বা compiler অন্য পথ বন্ধ করে দেয়।
প্র ০৩C ও C++-এ data race undefined behavior, অথচ Java-তে নয়। দুই ভাষা কেন আলাদা পথে গেল?
দীর্ঘদিন C আর C++ standard-এ thread-এর কোনো উল্লেখই ছিল না; thread আসত pthreads বা Windows-এর library থেকে। সমস্যাটি হলো compiler. একটি সাধারণ optimization ভাবুন: loop-এর ভেতরে প্রতিবার flag পড়া হয়, অথচ loop-এর ভেতরে কেউ flag লেখে না; তাই compiler এক thread-এর চোখে নিরাপদভাবে পড়াটি loop-এর বাইরে একবার করে। অন্য thread flag বদলালেও loop আর কখনো তা দেখবে না। Hans Boehm ২০০৫ সালে দেখান, শুধু library দিয়ে এ সমস্যার সমাধান হয় না; ভাষাকেই বলতে হবে কোন পড়া-লেখা অন্য thread দেখতে পায়।
Java এ সমস্যায় আগে পড়ে, কারণ Java ১৯৯৫ থেকেই thread-সহ ভাষা। প্রথম memory model-এ গুরুতর ত্রুটি পাওয়া যায়, আর JSR-133 প্রকল্পে (William Pugh-সহ অনেকের কাজ) সেটি নতুন করে লেখা হয়, যা Java 5 (২০০৪)-এ আসে। Java-র একটি বাধ্যবাধকতা ছিল নিরাপত্তা: একই JVM-এ অবিশ্বস্ত কোডও চলতে পারত, তাই race-ওয়ালা program-কেও “যা খুশি” করতে দেওয়া যেত না, যেমন হঠাৎ কোনো মান “শূন্য থেকে” উদয় হওয়া। ফলে Java race-ওয়ালা program-কেও সীমিত কিছু নিশ্চয়তা দেয়; অংশ ৩-এর plain শুধু ভুল সংখ্যা দিয়েছে।
C++11 আর C11 (২০১১) প্রথমবার memory model আনে, Boehm ও Sarita Adve-র কাজের ভিত্তিতে। এর মূল চুক্তির নাম “data-race-free হলে sequential consistency”: program-এ data race না থাকলে সেটি এমন আচরণ করবে যেন সব thread-এর ধাপ একটি একক ক্রমে মিশে চলেছে (অংশ ২-এর interleaving মডেল)। বিনিময়ে race থাকলে আচরণ undefined, যাতে compiler তার পুরোনো optimization-গুলো রাখতে পারে।
দুই পথ দুই মূল্যবোধ: Java নিরাপত্তা আর পূর্বানুমেয়তা বেছেছে, C++ সর্বোচ্চ গতি আর “যা ব্যবহার করেন না তার দাম দেবেন না” নীতি। Rust তৃতীয় পথ নিয়েছে: type system দিয়ে safe কোডে race-ই অসম্ভব করা। বিস্তারিত তুলনা পর্ব ৭৭-এ।
মূল উপলব্ধি: Concurrency-র নিয়ম শুধু হার্ডওয়্যার বা OS-এর নয়, compiler-এরও। ভাষার memory model compiler আর প্রোগ্রামারের মধ্যে একটি চুক্তি, আর সেই চুক্তি ভাঙলে কী হবে, তা ভাষাভেদে নাটকীয়ভাবে আলাদা।
প্র ০৪CPython-এ GIL কেন এল, আর free-threaded Python concurrency-র নিয়ম কীভাবে বদলায়?
CPython প্রতিটি object-এ একটি reference count রাখে: কতগুলো জায়গা object-টিকে নির্দেশ করছে। দুটি thread একসাথে একই count বাড়ালে-কমালে অংশ ২-এর lost update ঘটত, আর ফল হতো ভয়াবহ: count ভুল করে শূন্য হলে object মুছে যেত, অথচ কেউ তখনো ব্যবহার করছে। প্রতিটি object-এ আলাদা lock দিলে single-thread program অনেক ধীর হতো। ১৯৯০-এর দশকে নেওয়া সরল সমাধান: পুরো interpreter-এর জন্য একটি বড় lock, Global Interpreter Lock. যে thread GIL ধরে, শুধু সে Python bytecode চালায়।
ফল দুই রকম। I/O-নির্ভর কাজে thread ভালোই চলে, কারণ নেটওয়ার্ক বা ডিস্কের অপেক্ষায় thread GIL ছেড়ে দেয়। কিন্তু খাঁটি Python হিসাব একাধিক core-এ ছড়ায় না; ভারী হিসাবের জন্য multiprocessing বা C-তে লেখা library লাগে। আর একটি সূক্ষ্ম ফাঁদ: GIL অনেক ছোট কাজকে কার্যত atomic করে দেয়, তাই race-ওয়ালা কোডও প্রায়ই ঠিক চলে, যেমন অংশ ৩-এ তিনবার ২০ লাখ। কিন্তু ভাষার specification এটির প্রতিশ্রুতি দেয় না, আর thread কোন বিন্দুতে বদলাবে তা CPython-এর version-ভেদে বদলেছে।
২০২৩ সালে Sam Gross-এর PEP 703 গৃহীত হয়: GIL ছাড়া CPython. Python 3.13-এ এটি একটি আলাদা, পরীক্ষামূলক build হিসেবে আসে; 3.14-এ এটি আনুষ্ঠানিকভাবে সমর্থিত হয়, তবে এখনো ডিফল্ট নয় (পরবর্তী ধাপগুলো নিয়ে সিদ্ধান্ত এখনো চলমান)। এই build-এ reference counting-এর জন্য বিশেষ কৌশল (যেমন যে thread object তৈরি করেছে তার জন্য আলাদা দ্রুত count) আর built-in list ও dict-এর ভেতরে নিজস্ব সুরক্ষা আছে, যাতে interpreter নিজে ভেঙে না পড়ে।
কিন্তু আপনার নিজের count += 1-এর সুরক্ষা আপনার দায়িত্বই থেকে যায়। GIL চলে গেলে thread-গুলো সত্যিই একই মুহূর্তে চলে, আর আগে যে race “ঘুমিয়ে” ছিল, তা জেগে উঠতে পারে। পুরোনো কোড free-threaded build-এ নিতে হলে প্রতিটি ভাগ করা অবস্থা আবার খুঁজে দেখতে হয়।
মূল উপলব্ধি: একটি বাস্তবায়নের সিদ্ধান্ত (GIL) বছরের পর বছর ভাষার আচরণের মতো মনে হতে পারে। ভাষার প্রতিশ্রুতি আর একটি বাস্তবায়নের অভ্যাস আলাদা করে চিনুন; বাস্তবায়ন বদলালে শুধু প্রতিশ্রুতিই টেকে।
প্র ০৫Semaphore থেকে monitor, monitor থেকে Java-র synchronized: concurrency কীভাবে library থেকে ভাষার ভেতরে এল?
১৯৬০-এর দশকের মাঝামাঝি Edsger Dijkstra semaphore-এর ধারণা দেন (তাঁর “Cooperating Sequential Processes” লেখা, প্রায় ১৯৬৫ সালের): একটি পূর্ণসংখ্যা, যার ওপর দুটি অবিভাজ্য কাজ, P (কমানো, শূন্য হলে অপেক্ষা) আর V (বাড়ানো)। এটি শক্তিশালী, কিন্তু সম্পূর্ণ শৃঙ্খলা প্রোগ্রামারের হাতে: কোথাও একটি V ভুলে গেলে চিরকাল অপেক্ষা, আর কোন semaphore কোন ডেটা রক্ষা করে তা শুধু মন্তব্যে লেখা থাকে।
১৯৭০-এর দশকের শুরুতে Per Brinch Hansen আর Tony Hoare (Hoare-এর ১৯৭৪ সালের গবেষণাপত্র) monitor প্রস্তাব করেন: ডেটা আর তার ওপর কাজগুলো একটি মডিউলে, আর ভাষা নিশ্চিত করে যে একবারে একটিই process monitor-এর ভেতরে থাকে। অপেক্ষার জন্য condition variable. এখানে নিশ্চয়তা আসে compiler থেকে: ডেটা monitor-এর বাইরে থেকে ছোঁয়াই যায় না। Brinch Hansen-এর Concurrent Pascal (১৯৭৫) প্রথম ভাষাগুলোর একটি, যেখানে monitor ভাষার অংশ।
Java (১৯৯৫) এই ধারণা নেয়, কিন্তু ঢিলেঢালাভাবে: প্রতিটি object-এর একটি ভেতরের lock আর একটি condition (wait/notify), আর synchronized method বা block. কিন্তু কোন field কোন lock-এ রক্ষিত, ভাষা তা যাচাই করে না; একটি method synchronized না লিখলেই সেখান দিয়ে race ঢুকে যায়। Brinch Hansen ১৯৯৯ সালে “Java's Insecure Parallelism” নামে একটি সমালোচনা লেখেন, যার মূল কথা: Java monitor-এর নাম নিয়েছে, কিন্তু monitor-এর নিরাপত্তার নিশ্চয়তা ফেলে দিয়েছে।
এই ইতিহাসে একটি ধারা স্পষ্ট: প্রতিটি প্রজন্মে concurrency-র শৃঙ্খলা প্রোগ্রামারের মাথা থেকে ভাষা আর compiler-এর হাতে আরও বেশি সরে এসেছে। আজ Rust-এ Mutex<T> ডেটাকে তালার ভেতরে রাখে, তালা না ধরে ডেটা পাওয়াই যায় না: monitor-এর মূল প্রতিশ্রুতি type system দিয়ে ফেরত এসেছে। Monitor আর condition variable-এর OS-স্তরের আলোচনা আছে অপারেটিং সিস্টেম কোর্সের পর্ব ২৫-এ.
মূল উপলব্ধি: ভাষার নকশায় “কোন ভুল লেখাই যায় না” সবচেয়ে শক্তিশালী নিশ্চয়তা। একটি নিয়ম মন্তব্যে থাকলে মানুষ ভুলবে; type বা syntax-এ থাকলে compiler মনে রাখবে।
অনুশীলন
প্রথমে নিজে করুন, তারপর উত্তর খুলে মেলান। Java আর JavaScript-এর আউটপুট সত্যিকারের Java 21 আর Node.js-এ, Python-এর আউটপুট Python 3.14-এ চালিয়ে মেলানো।
-
নকশা — Haat-এ channel (Haat-এর বর্ধিত রূপ): Haat v1-এ
spawn f();(একটি function নতুন process-এ চালানো),let c = chan();,send(c, e);আর expressionrecv(c)যোগ করতে চান, শুধু Int-এর channel দিয়ে। (ক) নতুন type আর typing rule লিখুন। (খ) Lexer আর parser-এ কী বদলাবে? (গ) Haat-এর closure বাইরের variable by reference ধরে; এতেspawn-এর সঙ্গে কোন বিপদ আসে, আর একটি সহজ নিয়ম দিয়ে কীভাবে ঠেকাবেন?(ক) নতুন type
Chan(Int-এর channel). Γ মানে type environment, Γ ⊢ e : τ পড়ুন “Γ-তে e-এর type τ”:(T-Chan)(কোনো শর্ত নেই)Γ ⊢ chan() : Chan(T-Send)Γ ⊢ c : Chan Γ ⊢ e : IntΓ ⊢ send(c, e) ঠিক আছে(T-Recv)Γ ⊢ c : ChanΓ ⊢ recv(c) : Int(T-Spawn)Γ ⊢ f : () -> UnitΓ ⊢ spawn f(); ঠিক আছে(খ)
spawn-কে keyword বানাতে হবে (Haat-এর keyword তালিকায় যোগ, তাই আগের program-এspawnনামের variable থাকলে তা ভাঙবে: পর্ব ০৬-এর backward compatibility-র প্রশ্ন)।chan,send,recvkeyword না করে built-in function রাখা যায়, তাহলে parser বদলায় না, শুধু name resolution আর type checker-এ তাদের type জানাতে হয়, ঠিক যেমনIntএকটি নাম, keyword নয়।spawnstatement-টি parser-এ একটি নতুন statement নিয়ম আর একটি নতুন AST node (Spawn) চায়।(গ) Closure by reference মানে
var total = 0; spawn fn() { total = total + 1; }-এর মতো কোডে দুই process একইtotalবদলাবে: অংশ ২-এর data race ফিরে এল। সহজ নিয়ম: spawn-করা function বাইরের কোনোvarধরতে পারবে না; শুধুlet(অপরিবর্তনীয়) আর channel ধরতে পারবে। Resolver ইতিমধ্যে জানে কোন নাম কোন scope-এর আরvarনাlet, তাই এটি একটি ছোট static check. এটি Rust-এরSendনিয়মের সরল রূপ, আর ফলে Haat-এর concurrency হয় খাঁটি CSP: যোগাযোগ শুধু channel-এ। -
ভুল খুঁজুন: একজন বললেন, “Java-তে counter-কে
static volatile int countকরেছি, তাই দুই thread-এcount++এখন নিরাপদ; volatile মানে প্রতিটি পড়া-লেখা সরাসরি memory-তে।” দুই thread প্রতিটি ১০ লাখ বারcount++করলে কী আশা করবেন? ভুল কোথায়, আর ঠিক করার দুটি উপায় কী?লেখকের যন্ত্রে Java 21.0.13-এ সত্যিকারের তিনটি run:
volatile count = 1155721,1271731,1376890(প্রতিবারexpected 2000000). দাবির প্রথম অংশ মোটামুটি ঠিক:volatileনিশ্চিত করে যে একটি thread-এর লেখা অন্য thread দেখতে পাবে, আর সেই পড়া-লেখার ক্রম compiler উল্টাবে না। কিন্তুcount++এখনো তিনটি আলাদা কাজ: volatile পড়া, যোগ, volatile লেখা। দুই thread একই মান পড়ে দুজনেই লিখতে পারে: উপপাদ্য ১১.২-এর ঠিক সেই lost update. Visibility (দৃশ্যমানতা) আর atomicity (অবিভাজ্যতা) আলাদা গুণ। ঠিক করার উপায়: (১)AtomicInteger-এরincrementAndGet(), যা হার্ডওয়্যারের অবিভাজ্য নির্দেশ ব্যবহার করে; (২)synchronizedblock-এ পড়া-যোগ-লেখা একসাথে। অংশ ৩-এর run-এ দুটিই প্রতিবার 2000000 দিয়েছে। তৃতীয়, প্রায়ই সবচেয়ে ভালো উপায়: প্রতিটি thread নিজের local counter রাখুক, আরjoin-এর পর দুটি যোগ হোক; তখন কিছুই ভাগ হয় না। -
আউটপুট অনুমান করুন: (ক) নিচের JavaScript কী ছাপে?
console.log("A"); setTimeout(() => console.log("B"), 0); Promise.resolve().then(() => console.log("C")); (async () => { console.log("D"); await null; console.log("E"); })(); console.log("F");(খ) অংশ ৫-এর CSP program-এ যদিcollectorচালু না করা হয় (শুধু producer আর worker), কী ঘটবে আর কী ছাপা হবে?(ক) Node.js 24-এ চালানো ফল, প্রতি লাইনে একটি:
A D F C E B. A sync. B timer সারিতে যায়। C microtask সারিতে। async function সঙ্গে সঙ্গে চলতে শুরু করে, তাই D sync-এর মতোই এখনই ছাপে;await nullবাকি অংশ (E) microtask সারিতে C-এর পেছনে রাখে। F sync. বর্তমান কোড শেষ, তাই microtask: C, তারপর E. সবশেষে timer: B. মূল ফাঁদ D: “async মানে পরে চলে” ভুল; প্রথমawaitপর্যন্ত async function-এর দেহ সরাসরি চলে।(খ) লেখকের ল্যাবে একই scheduler-এ চালানো ফল: producer D1040 পাঠায়, worker নেয়, তারপর worker 936 পাঠাতে
totals-এ দাঁড়ায়, কিন্তু নেওয়ার কেউ নেই। Producer পরের অর্ডার R540 নিয়েorders-এ দাঁড়ায়, কিন্তু worker তো আটকে আছে। ready সারি খালি হয়ে যায়, scheduler থেমে যায়; শেষেorders-এ P আরtotals-এ W অপেক্ষারত। লগে শুধুorders: ('Dhaka', 1040), আর “Dhaka = …” কখনো ছাপা হয় না: একটি deadlock, কোনো error বার্তা ছাড়াই। Go-তে এমন অবস্থায় runtimefatal error: all goroutines are asleep - deadlock!দিয়ে থামত; একটি buffered channel দিলে কয়েকটি অর্ডার জমত, কিন্তু buffer ভরে গেলে একই অবস্থা হতো। -
প্রমাণ: অংশ ৪-এর summer actor চলমান মোট শুরু করে 0 থেকে, আর প্রতিটি বার্তায় sum := sum + v করে। প্রমাণ করুন: বার্তাগুলো (v1, …, vk) যেকোনো ক্রমে এলেও শেষে sum = v1 + … + vk. কোন দুটি গুণ লাগল? “গড় হিসাব করে প্রতি বার্তায় avg := (avg + v) / 2” করলে প্রমাণটি কোথায় ভাঙে?
একটি আগমন-ক্রম হলো সংখ্যাগুলোর একটি বিন্যাস (permutation) π. summer-এর ফল S(π) = ((0 + vπ(1)) + vπ(2)) + … + vπ(k), অর্থাৎ পর্ব ০৯-এর foldl (+) 0.
- যেকোনো বিন্যাসকে পাশাপাশি দুটি উপাদান অদলবদল করতে করতে অন্য যেকোনো বিন্যাসে আনা যায় (bubble sort-এর মতো)। তাই দেখানোই যথেষ্ট যে পাশাপাশি দুটি বার্তার ক্রম উল্টালে S বদলায় না।
- ধরি i-তম আর (i + 1)-তম বার্তা উল্টানো হলো। তার আগের মোট s একই। আগে: (s + a) + b. পরে: (s + b) + a.
- সংযোজিতা দিয়ে (s + a) + b = s + (a + b), আর বিনিময়যোগ্যতা দিয়ে a + b = b + a, তাই = s + (b + a) = (s + b) + a. তার পরের সব ধাপ একই মান থেকে একই বার্তায় চলে, তাই শেষ ফল একই।
- ধাপ ১ অনুযায়ী সব বিন্যাসে S সমান, আর একটি বিন্যাস (মূল ক্রম) থেকে S = v1 + … + vk. ∎
লাগল যোগের সংযোজিতা (associativity) আর বিনিময়যোগ্যতা (commutativity); Haat বা Java-র wrap করা ৬৪-বিট বা ৩২-বিট যোগেও দুটি টেকে। “avg := (avg + v) / 2” operation-টি বিনিময়যোগ্য নয়: শুরু 0, বার্তা 4 তারপর 8 দিলে (0 + 4) / 2 = 2, (2 + 8) / 2 = 5; উল্টো ক্রমে (0 + 8) / 2 = 4, (4 + 4) / 2 = 4. ধাপ ৩ ভাঙে, ফল ক্রমের ওপর নির্ভর করে: একটি race condition, যদিও কোনো data race নেই! সঠিক উপায়: summer যোগফল আর সংখ্যা দুটিই রাখুক, শেষে একবার ভাগ করুক; (যোগফল, সংখ্যা) জোড়ার যোগ সংযোজী আর বিনিময়যোগ্য।
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমJavaScript-এ এই কোড চললে log-এ কোন ক্রমে লেখা হয়, সাজান (▲▼ চেপে সরান): setTimeout(() => log("timeout"), 0); Promise.resolve().then(() => log("then 1")).then(() => log("then 2")); queueMicrotask(() => log("microtask")); log("sync");
- sync
- then 1
- microtask
- then 2
- timeout
একটি single-core কম্পিউটারে একটি program দুটি thread-এ পালা করে চলে। কোন বাক্যটি সঠিক?
- এটি parallelism, কারণ দুটি thread আছে
- এটি concurrency, কিন্তু parallelism নয়
- এটি concurrency-ও নয়, কারণ একবারে একটিই চলে
- এক core-এ race condition অসম্ভব
দুটি thread একটি ভাগ করা count (শুরু 0)-এ একবার করে পড়া, যোগ, লেখা (প্রতিটি ৩টি অবিভাজ্য ধাপ) করে। সম্ভাব্য interleaving কয়টি, আর কয়টিতে শেষে count = 2?
- 720টি, যার অর্ধেকে 2
- 20টি, সবগুলোতে 2
- 20টি, যার মাত্র 2টিতে 2
- 2টি, দুটিতেই 2
Java 21-এ static volatile int count-এ দুটি thread প্রতিটি ১০ লাখ বার count++ করে, তারপর join. ফল সম্পর্কে কোনটি ঠিক?
- সবসময় ঠিক 2000000, কারণ volatile
- Program crash করবে, কারণ data race undefined behavior
- Compile error, কারণ volatile-এ ++ চলে না
- সাধারণত 2000000-এর কম, আর প্রতি run-এ আলাদা হতে পারে
Actor model সম্পর্কে কোন বাক্যটি সঠিক?
- প্রতিটি actor নিজের অবস্থা রাখে আর mailbox থেকে একবারে একটি বার্তা চালায়, তাই সেই অবস্থায় lock লাগে না
- বার্তা পাঠালে প্রেরক প্রাপকের নেওয়া পর্যন্ত অপেক্ষা করে
- সব বার্তা সবসময় পাঠানোর ক্রমেই পৌঁছায়, তাই ফল কখনো ক্রমের ওপর নির্ভর করে না
- Actor-রা একটি ভাগ করা heap-এ সরাসরি একে অপরের অবস্থা পড়ে
Go-তে ch := make(chan int) (unbuffered). একটি goroutine ch <- 5 লেখে, কিন্তু অন্য কোনো goroutine এখনো <-ch করেনি। কী ঘটে?
- 5 channel-এ জমা থাকে, আর প্রেরক সঙ্গে সঙ্গে পরের লাইনে যায়
- মানটি হারিয়ে যায়, কারণ কেউ নিতে আসেনি
- প্রেরক অপেক্ষা করে, যতক্ষণ না কেউ ওই channel থেকে নেয়
- Compile error, কারণ নেওয়ার কোড নেই
C11/C++11-এর memory model অনুযায়ী একটি program-এ data race থাকলে কী হয়?
- Program sequentially consistent আচরণ করে, শুধু ক্রম অনিশ্চিত
- ফল শুধু কিছুটা ভুল সংখ্যা হতে পারে, এর বেশি কিছু নয়
- Compiler সবসময় compile error দেয়
- আচরণ undefined: standard কোনো ফলের প্রতিশ্রুতি দেয় না
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন — অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- Concurrency গঠন, parallelism চালানো: এক core-এও concurrency আর race condition সম্ভব। নিরাপদ ভাগের ছক: ভাগ করুন, কিছু ভাগাভাগি করবেন না, সংযোজী operation দিয়ে জোড়া লাগান।
- Shared memory:
count++তিন ধাপ; C(6, 3) = 20 ক্রমের মাত্র ২টি ঠিক। সত্যিকারের Java run-এ সুরক্ষাহীন counter প্রতিবার ভুল,synchronizedআর atomic প্রতিবার ঠিক;volatileatomicity দেয় না। - Data race-এর পরিণতি ভাষাভেদে আলাদা: C/C++-এ undefined behavior, Java-তে সীমিত নিশ্চয়তা, safe Rust-এ compile time-এ অসম্ভব; Python-এ GIL একটি বাস্তবায়নের অভ্যাস, প্রতিশ্রুতি নয়।
- Actor আর CSP: actor = ব্যক্তিগত অবস্থা + mailbox + asynchronous বার্তা; CSP = process + channel + rendezvous. দুটিই ভাগ করা অবস্থা সরিয়ে lock-এর দরকার মেটায়, কিন্তু ক্রম-অনিশ্চয়তা আর deadlock পুরো যায় না।
- Dataflow আর event loop: ইনপুট হাজির হলে নোড চলে (Kahn-এর শর্তে ফল নির্ধারিত); JavaScript-এ sync কোড, তারপর সব microtask, তারপর timer.
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ১২ · Scripting আর dynamic ভাষা — duck typing, eval আর reflectionপরবর্তী পর্বচলার সময়ে সিদ্ধান্ত নেওয়া ভাষার শক্তি আর দাম।
- প্রোগ্রামিং ভাষা ও কম্পাইলার · কোর্স হোম৮৬টি পর্বপুরো কোর্সের মানচিত্র আর Haat প্রজেক্টের পথ।
- Race condition আর critical section — Peterson-এর সমাধানপাশের ট্র্যাকOS-এর চোখে race আর তার সমাধান।
- Thread আর synchronization — একসাথে অনেক কাজ, নিরাপদেপাশের ট্র্যাকJava-র synchronized, volatile, atomic আর executor.
- asyncio — এক thread-এ অনেক অপেক্ষা, async আর awaitপাশের ট্র্যাকPython-এর event loop আর coroutine.
- Event loop — task আর microtask: এক thread-এ অনেক কাজপাশের ট্র্যাকJavaScript-এর task আর microtask সারি বিস্তারিত।