উদ্বোধনী সন্ধ্যা

অ্যাটমিকস

একটি একক ইন্সট্রাকশন দেখতে একটাই অবিভাজ্য কাজের মতো লাগতে পারে, অথচ আসলে তা মোটেই তা নয়। মেমরির একটি মানের সাথে পাঁচ যোগ করার উদাহরণ নেওয়া যাক:

add qword [rel counter], 5

ভেতরে ভেতরে প্রসেসরের মেমরিতে সরাসরি যোগ করার কোনো উপায় নেই। তাই এটি এই একটি ইন্সট্রাকশনকেই ভেঙে দেয় তিনটি ছোট ধাপে, যাদের বলা হয় মাইক্রো-অপারেশন:

1. মেমরি থেকে বর্তমান মান পড়া;
2. রেজিস্টারে এই মানটি পরিবর্তন করা, অর্থাৎ তাতে পাঁচ যোগ করা;
3. ফলাফলটি আবার লেখা।

mov rax, qword [rel counter] ; 1. load the current value
add rax, 5                   ; 2. add five
mov qword [rel counter], rax ; 3. store the result back

এটি একটি কমন প্যাটার্ন, যাকে বলা হয় রিড-মডিফাই-রাইট (RMW)।

লক্ষ্য করুন, পড়া (বা লোড) আর লেখা (বা স্টোর) আলাদা দুটি ঘটনা, তাই এদের মাঝে একটি সময়ের ফাঁক থাকে। একটি একক কোরের ক্ষেত্রে আমরা সাধারণত এটি টের পাই না, কারণ সেখানে প্রতিটি ইন্সট্রাকশন নিশ্চিতভাবেই পরের ইন্সট্রাকশনের আগে তার পুরো প্রভাব ফেলে দেয়। তাই এই ফাঁকটি অদৃশ্য থাকে, আর add একটি অবিভাজ্য একক হিসেবে আচরণ করে।

তবে আধুনিক CPU খুব কমই একক কোরের হয়, আর অ্যাপ্লিকেশনগুলো প্রায়ই একসাথে অনেক কোরেই চলে, তাদের মধ্যে কোনো ক্রমবিন্যাস ছাড়াই। একই মুহূর্তে কয়েকটি কোর চললে, এই কোরের লোডের পরে ও স্টোরের আগে, অন্য একটি কোর ওই ফাঁকের ভেতরে counter পড়তে বা লিখতে পারে। দুটি থ্রেডই একই পুরনো মান লোড করে, দুটিই পাঁচ যোগ করে, আর দুটিই নিজের ফলাফল স্টোর করে। তাহলে দুটি যোগ হয়েছিল, কিন্তু মান বাড়ল মাত্র পাঁচ। একটি আপডেট চুপচাপ হারিয়ে গেল।

এটাই একটি ডেটা রেস, আর মাল্টি-থ্রেডেড কোডে এটি একটি কমন সমস্যা।

সব মানই এভাবে উন্মুক্ত থাকে না। প্রতিটি থ্রেডের নিজের রেজিস্টার ও নিজের স্ট্যাক থাকে, তাই কোনো রেজিস্টারে রাখা মান, বা থ্রেডের স্ট্যাকে থাকা কোনো লোকাল ভ্যারিয়েবল কেবল সেই থ্রেডেরই নিজস্ব, এবং সেটি রেসে জড়াতে পারে না। কেবল থ্রেডগুলো যেসব মেমরি শেয়ার করে, যেমন উপরের counter, সেটিকেই সুরক্ষা দিতে হয়।

x86-64 এই সমস্যার সমাধানে একগুচ্ছ ইন্সট্রাকশন দেয়, যেগুলো একটি ইন্সট্রাকশনকে অবিভাজ্য করে তোলে। এটি শুধু যে কোরটি এটি প্রসেস করে তার কাছেই নয়, বাকি প্রতিটি কোরের কাছেও একটি অবিভাজ্য একক হিসেবে আচরণ করে। যে অপারেশন একসাথে আটকে থাকে, যা অন্য কোনো কোর ভাগ করতে পারে না, তাকে বলা হয় অ্যাটমিক।

অ্যাটমিক এক্সচেঞ্জ

xchg ইন্সট্রাকশন দুটি অপারেন্ড সোয়াপ করে। ডেস্টিনেশন অপারেন্ডটি সোর্স অপারেন্ডের আগের মানের সমান হয়ে যায়, আর সোর্স অপারেন্ডটি ডেস্টিনেশন অপারেন্ডের আগের মানের সমান হয়ে যায়। ধারণাগতভাবে এটিকে একসাথে ঘটে যাওয়া দুটি mov ইন্সট্রাকশন হিসেবে ভাবা যায়।

বরাবরের মতোই, এটি দুটি রেজিস্টার অপারেন্ড দিয়ে, অথবা একটি মেমরি অপারেন্ড ও একটি রেজিস্টার অপারেন্ড দিয়ে ব্যবহার করা যায়:

mov  eax, 1
xchg dword [rdi], eax ; [rdi] = 1, eax = the old value of [rdi]
mov ecx, 2
mov edx, 3
xchg edx, ecx         ; edx = 2, ecx = 3

মেমরি অপারেন্ডের সাথে ব্যবহার করলে xchg সবসময়ই অ্যাটমিক।

লক প্রিফিক্স

x86-64-এ একটি ইন্সট্রাকশনকে অ্যাটমিক করার সবচেয়ে কমন উপায় হলো lock প্রিফিক্স যোগ করা। এটি পড়া, পরিবর্তন আর লেখাকে জুড়ে দিয়ে একটি অবিভাজ্য ধাপ বানায়। এর মানে হলো, পুরো প্রক্রিয়া জুড়ে কোরটি মেমরিটিকে একচেটিয়াভাবে ধরে রাখে, তাই মাঝখানে অন্য কোনো কোর সেই লোকেশন পড়তে বা লিখতে পারে না।

lock add qword [rel counter], 5 ; the read, the modify, and the write are one step

lock কেবল তখনই কাজ করে যখন ডেস্টিনেশন মেমরি হয়, আর কেবল সেই ইন্সট্রাকশনগুলোর উপরই কাজ করে যেগুলো সেই মেমরিতে রিড-মডিফাই-রাইট করে:

1. অ্যারিথমেটিক অপারেশন, যেমন add, sub, inc, dec, neg;
2. বিটওয়াইজ অপারেশন, যেমন and, or, xor, not;
3. বিট অপারেশন bts, btr, btc;
4. আরও কিছু বিশেষ ইন্সট্রাকশন, যেমন xadd ও cmpxchg, যেগুলোর কথা নিচে বলা হয়েছে।

এক্সচেঞ্জ ও অ্যাড

সাধারণ lock add মেমরি আপডেট করে, কিন্তু পুরনো মানটি ফেলে দেয়। অনেক সময় পুরনো মানটিই দরকার হয়, যেমন প্রতিটি থ্রেডকে আলাদা একটি টিকিট নম্বর দিতে।

xadd ইন্সট্রাকশনটি (x মানে এক্সচেঞ্জ) যোগ করার সাথে সাথে আগের মানটিও রিটার্ন করে। এটি যোগফলটি ডেস্টিনেশনে লেখে আর ডেস্টিনেশনের মূল মানটি সোর্স রেজিস্টারে রেখে দেয়।

mov  rax, 1
lock xadd qword [rdi], rax ; [rdi] = [rdi] + rax = [rdi] + 1
                           ; rax = the old value of [rdi]

lock প্রিফিক্সের সাথে এটি একটি অ্যাটমিক ফেচ-অ্যান্ড-অ্যাড। একই কাউন্টারে অনেক থ্রেড এটি চালালে প্রতিটি কল আলাদা একটি পুরনো মান রিটার্ন করে।

lock add-এর মতোই, কলের ঠিক সংখ্যাতেই কাউন্টার শেষ হয়। তবে lock add-এর বিপরীতে, এখানে মাঝের প্রতিটি মানও রিটার্ন হয়, প্রতিটি কলকারী একটি করে পায়।

কম্পেয়ার অ্যান্ড এক্সচেঞ্জ

xadd যোগ করে আর xchg উপরিলিখে দেয়, কিন্তু কোনোটিই নতুন মানকে বর্তমান মানের উপর নির্ভরশীল করে, আর ভেতরে কিছু না বদলালে তবেই তা প্রয়োগ করতে পারে না। সেই শর্তসাপেক্ষ আপডেটটাই cmpxchg, বা কম্পেয়ার-অ্যান্ড-এক্সচেঞ্জ দেয়, আর এই প্রিমিটিভগুলোর মধ্যে এটিই সবচেয়ে ব্যাপক।

cmpxchg dest, src একটি অন্তর্নিহিত অ্যাকুমুলেটর হিসেবে rax ব্যবহার করে, আর সেটিকে dest অপারেন্ডের সাথে তুলনা করে:

• dest == rax হলে dest = src এবং ZF = 1।
• dest != rax হলে rax = dest এবং ZF = 0।

লক্ষ্য করুন, dest কেবল তখনই আপডেট হয় যখন সেটি আগে rax রেজিস্টারে লোড করা প্রত্যাশিত মানের সমান হয়। এই সমতা নিশ্চিত করে যে dest এখনো সেই মানটিই ধরে আছে যা থেকে নতুন মানটি হিসাব করা হয়েছিল, তাই পুরনো মান পড়ে করা আপডেট কখনোই প্রয়োগ হয় না। এটিই cmpxchg ইন্সট্রাকশনটিকে একটি অ্যাটমিক আপডেটের বিল্ডিং ব্লক বানায়, যাকে কম্পেয়ার-অ্যান্ড-সোয়াপ (CAS)-ও বলা হয়:

    mov rax, qword [rdi]          ; rax = the value we expect to find
.retry:
    lea rcx, [rax + 10]           ; rcx = the new value we want to install
    lock cmpxchg qword [rdi], rcx ; if [rdi] still equals rax, store rcx and set ZF
                                  ; otherwise reload rax with the current value, clear ZF
    jnz  .retry                   ; ZF is cleared, so another thread won the race. Recompute and retry

এই রিট্রাই লুপটিই লক-ফ্রি আপডেটের প্রাণ। পড়া আর কম্পেয়ার-অ্যান্ড-এক্সচেঞ্জের মাঝের ফাঁকটিই ঠিক সেই মুহূর্ত যখন অন্য একটি থ্রেড মাঝখানে ঢুকে পড়তে পারে, আর পুরনো মান পড়ে হিসাব করা কোনো মান স্টোর করতে অস্বীকার করে cmpxchg সেটি ধরে ফেলে।

মেমরি অর্ডারিং

এখন পর্যন্ত প্রতিটি অপারেশন কেবল একটি লোকেশনেই হাত দিয়েছে। থ্রেডগুলো যখন একাধিক লোকেশনের মাধ্যমে সমন্বয় করে, তখন নতুন একটি প্রশ্ন ওঠে: একটি থ্রেডের লেখাগুলো কোন ক্রমে অন্যটির কাছে দৃশ্যমান হয়। এই প্রশ্নের উত্তর দেয় প্রসেসরের মেমরি অর্ডারিং।

ব্রাঞ্চলেস-কোড কনসেপ্টে যে ধারণাটি এসেছিল, তা হলো একটি আধুনিক কোর একবারে একটি করে ইন্সট্রাকশন ধরে ধীরে ধীরে এগোয় না। এটি একসাথে অনেক ইন্সট্রাকশন চালু রাখে আর যেখানে পারে সেখানে আগে এগিয়ে যায়। এর মানে হলো, প্রোগ্রাম যা বোঝায় তার চেয়ে দেরিতেও একটি লেখা অন্য কোরগুলোর কাছে দৃশ্যমান হতে পারে, অথচ তার পরের ইন্সট্রাকশনগুলো ইতিমধ্যেই এগিয়ে গেছে।

x86-64 সাধারণ লোড ও স্টোরের মধ্যে একটি স্ট্রং মেমরি অর্ডারিং মেনে চলে, যাতে প্রতিটি কোরের ক্ষেত্রে:

1. একটি লোড কখনোই তার পরে আসা লোডের পরে পুনর্বিন্যস্ত হয় না;
2. একটি স্টোর কখনোই তার পরে আসা স্টোরের পরে পুনর্বিন্যস্ত হয় না;
3. একটি লোড কখনোই তার পরে আসা স্টোরের পরে পুনর্বিন্যস্ত হয় না।

একমাত্র সম্ভাব্য পুনর্বিন্যাস হলো, একটি স্টোর অন্য একটি অ্যাড্রেসের পরের লোডের পরে সম্পন্ন হয়েছে বলে মনে হওয়া।

lock প্রিফিক্সযুক্ত একটি ইন্সট্রাকশন, বা মেমরি অপারেন্ডসহ একটি xchg, একটি পূর্ণ ব্যারিয়ার: কোনোকিছুই এর আড়াআড়ি কোনো দিকেই সরে যেতে পারে বলে মনে হয় না। এজন্যই বেশিরভাগ পরিস্থিতিতে পূর্ণ অর্ডারিং নিশ্চিত করার জন্য এগুলোই যথেষ্ট।

স্পিনিং আর pause

যে ইন্সট্রাকশনগুলো একটি ফ্ল্যাগ সেট করার সাথে সাথে তার আগের অবস্থাও রিটার্ন করে, তাদের বলা হয় টেস্ট-অ্যান্ড-সেট। এগুলোকে একটি স্পিনলকের ভিত্তি হিসেবে ব্যবহার করা যায়, যাতে একটি কোর কোডের কোনো অংশে একচেটিয়া প্রবেশাধিকার পায়।

বাইনারি ফ্ল্যাগের সাথে xchg ইন্সট্রাকশন ব্যবহার করে সামগ্রিক অ্যালগরিদমটি এমন:

1. ফ্ল্যাগটি শুরু হয় 0 দিয়ে।
2. লক নিতে একটি কোর ফ্ল্যাগের মানটি 1 দিয়ে সোয়াপ করে।
3. রিটার্ন করা মানটি 1 হলে, এর মানে লকটি অন্য একটি কোর ধরে রেখেছে। তখন বর্তমান কোরটি অপেক্ষা করে এবং আবার লক নেওয়ার চেষ্টা করে।
4. রিটার্ন করা মানটি 0 হলে, এর মানে লকটি খালি ছিল। xchg এখন এটিকে 1 করে রেখেছে, আর অন্য কোরগুলো অপেক্ষা করবে যতক্ষণ না এই কোরটি এটিকে ছেড়ে দেয়।
5. বর্তমান কোরটি কাজ শেষ করলে, ফ্ল্যাগটি 0 দিয়ে আপডেট করলেই লকটি ছেড়ে দেওয়া হয়।

acquire:
    mov  eax, 1
    xchg dword [rdi], eax ; try to take the lock; eax = its old value
    test eax, eax
    jnz  .held            ; old value was 1: someone else holds it
    ret                   ; old value was 0: the lock is ours
.held:
    pause                 ; wait before trying again
    jmp  acquire

অপেক্ষার লুপে থাকা pause ইন্সট্রাকশন কোডটি কী হিসাব করে তা বদলায় না। এটি প্রসেসরকে ইঙ্গিত দেয় যে এটি একটি স্পিন-ওয়েট। তখন CPU অপেক্ষারত থ্রেডের বিদ্যুৎ খরচ কমাতে পারে এবং একই কোর শেয়ার করা অন্য একটি থ্রেডকে জায়গা ছেড়ে দিতে পারে। pause ছাড়া একটি স্পিন লুপ এখনো সঠিকই থাকে, শুধু অপচয় বেশি হয়।

থ্রেডটি কাজ শেষ করলে, mov দিয়ে সাধারণ একটি স্টোর করে 0 লিখেই লকটি ছেড়ে দিতে পারে। mov ছাড়া আর কিছুই দরকার নেই, কারণ x86-64-এ লোড ও স্টোর কখনোই তার পরে আসা স্টোরের পরে পুনর্বিন্যস্ত হয় না। যে স্টোর তার আগের অ্যাক্সেসগুলোকে কখনো ছাপিয়ে যায় না, তাকে বলা হয় রিলিজ অর্ডারিং আছে, আর x86-এ প্রতিটি সাধারণ স্টোর তা বহন করে।