Compare-and-Swap
কম্পেয়ার-অ্যান্ড-সোয়াপ
একটা atomic hardware অপারেশন — memory location-এর মান expected-এর সমান হলেই নতুন মান বসায়, নাহলে কিছুই বদলায় না; সব lock-free ডেটা স্ট্রাকচারের ভিত্তি।
also: CAS, atomic, cmpxchg, compare_exchange
CAS(location, expected, desired) — তিনটা ধাপ অবিভাজ্যভাবে:
মান পড়ো, expected-এর সাথে তুলনা করো, সমান হলেই desired
লিখে সফলতা রিটার্ন করো (নাহলে কিছুই বদলায় না, ব্যর্থতা রিটার্ন)।
x86-এ lock cmpxchg, ARM-এ LL/SC (ldrex/strex) জোড়া।
int expected = 10;
loc.compare_exchange_strong(expected, 20);
/* সফল: loc=20। ব্যর্থ: expected এখন loc-এর প্রকৃত মান */_weak বনাম _strong: weak মাঝেমধ্যে spuriously fail
করতে পারে (ARM LL/SC-তে reservation ভেঙে যাওয়ার কারণে) —
loop-এর ভেতরে weak পছন্দনীয়, একবারই ডাকলে strong।
কেন “universal”: Herlihy (1991)-এর consensus-number
hierarchy-তে CAS-এর consensus number অসীম — যেকোনো
সংখ্যক thread-এর মধ্যে lock-free consensus বানানো যায়, যেখানে
fetch_add/test_and_set-এর consensus number মাত্র ২।
CAS-loop প্যাটার্ন (সব lock-free ডেটা স্ট্রাকচারের কঙ্কাল): পড়ো → নতুন মান গণনা করো → CAS চেষ্টা → ব্যর্থ হলে আবার শুরু।
ABA problem: একটা location A→B→A হয়ে ফিরে এলে CAS “কিছু বদলায়নি” ভাবে, কিন্তু underlying memory reuse হয়ে থাকতে পারে — সমাধান: tagged pointer (versioned CAS) বা hazard pointer।