عملیات اتمی در

درباره‌ی عملیات اتمی

یک دستور واحد می‌تواند مانند یک کنش تجزیه‌ناپذیر به نظر برسد، در حالی که هیچ‌چنین چیزی نیست. برای نمونه، افزودن پنج به یک مقدار در حافظه را در نظر بگیرید:

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 مانند یک واحد یکپارچه رفتار می‌کند.

اما پردازنده‌های امروزی به‌ندرت تک‌هسته‌ای‌اند، و برنامه‌ها اغلب روی هسته‌های زیادی هم‌زمان اجرا می‌شوند، بدون هیچ ترتیب‌بندی میانشان. وقتی چند هسته در همان لحظه اجرا می‌کنند، هسته‌ای دیگر می‌تواند در همان پنجره، پس از بارگذاری این هسته و پیش از ذخیره‌ی آن، 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 همیشه اتمیک است. پردازنده برای این مدت روی آن مکان قفل می‌گذارد، همان سازوکاری که پیشوند lock برای دستورهای دیگر به کار می‌برد و در ادامه توضیح داده می‌شود.

پیشوند lock

رایج‌ترین راه برای اتمیک کردن یک دستور در 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، که در ادامه توضیح داده می‌شوند.

روی هر دستور دیگری، مانند یک mov ساده، این پیشوند نامعتبر است و پردازنده یک خطای کد عملیات نامعتبر ایجاد می‌کند. یک بارگذاری تنها یا یک ذخیره‌ی تنها به هیچ پیشوندی نیاز ندارد: یک دسترسی همتراز به شکل طبیعی، خودش به‌تنهایی اتمیک است.

عملیات بیتی اتمیک

میان دستورهای قابل قفل کردن، آزمون‌های بیتی به‌طور طبیعی با قفل چرخشی که در پایان این سند می‌آید جفت می‌شوند. هر یک از bts، btr و btc یک بیت برگزیده را در پرچم نقلی کپی می‌کند و سپس آن را تنظیم، پاک یا وارونه می‌کند. با پیشوند lock، این به یک خواندن-تغییر-نوشتن یک‌بیتی تبدیل می‌شود: بیت به‌صورت اتمیک تغییر می‌کند و CF گزارش می‌دهد که پیش‌تر چه بود.

    lock bts qword [rdi], 0 ; set bit 0; CF = the bit's previous value
    setc al                 ; al = 1 when the bit was already set

تنظیمی که بیت را از پیش تنظیم‌شده بیابد یعنی نخ دیگری پیش‌تر آن را تصاحب کرده است. این نسخه‌ی تک‌بیتی همان تصاحب پرچمی است که xchg برای یک کلمه‌ی کامل انجام می‌دهد.

تعویض و جمع

یک 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.

انباره از اندازه‌ی عملوند پیروی می‌کند: al برای یک بایت، سپس ax، eax و rax برای شکل‌های پهن‌تر.

توجه کنید که dest تنها وقتی به‌روز می‌شود که با مقدار انتظارشده، که پیش‌تر در rax بارگذاری شده، برابر باشد. این برابری تضمین می‌کند که dest هنوز همان مقداری را دارد که مقدار جدید از آن محاسبه شده، پس به‌روزرسانی‌ای که بر پایه‌ی یک خواندن کهنه باشد هرگز اعمال نمی‌شود. این ویژگی cmpxchg را به بلوک سازنده‌ی یک به‌روزرسانی اتمیک تبدیل می‌کند، که به آن compare-and-swap (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 با خودداری از ذخیره‌ی مقداری که از یک خواندن کهنه محاسبه شده، آن را می‌گیرد.

یک نکته‌ی ظریف ارزش دانستن دارد. cmpxchg بررسی می‌کند که مقدار با آنچه خوانده شده برابر است، نه اینکه آن مکان هرگز دست نخورده باشد. اگر نخی دیگر در همان پنجره مقدار را از A به B و باز به A ببرد، تعویض باز هم موفق می‌شود، حتی اگر دنیای زیر آن تغییر کرده باشد.

برای یک شمارنده‌ی ساده این بی‌ضرر است، چون شمارش برابر، شمارشی به همان خوبی است. اما برای نشانی حافظه‌ای در سر یک فهرست بدون قفل چنین نیست، چون ممکن است همان نشانی اکنون به جای دیگری اشاره کند. این همان مسئله‌ی ABA است.

راه‌حل معمول این مسئله، جفت کردن مقدار با نوعی «مهر» است، برای نمونه شمارنده‌ای که تنها رشد می‌کند. چون مهر تنها جلو می‌رود، مهر منطبق ثابت می‌کند که آن مکان در این فاصله دست نخورده است، نه صرفاً اینکه تغییرنکرده به نظر می‌رسد.

اما برای اینکه این در محیطی چندنخی کار کند، باید نشانی حافظه و مهرش با هم به‌روز شوند. چون یک نشانی حافظه در x86-64 یک کلمه‌ی چهارگانه‌ی کامل است، یک cmpxchg برای به‌روزرسانی آن و هم‌زمان مقدار دیگری کافی نیست.

دستور دوبرابری به نام cmpxchg16b وجود دارد که از نظر معنایی همان cmpxchg است اما روی ۱۶ بایت به‌طور هم‌زمان کار می‌کند و در آن حالت می‌توان از آن استفاده کرد. عملوند مبدأ ندارد و به‌جایش از rcx:rbx به‌عنوان مقدار جایگزین استفاده می‌کند. تنها عملوندش یک مکان حافظه‌ی همتراز با ۱۶ بایت است. این دستور همچنین به‌جای فقط rax، از rdx:rax به‌عنوان انباره استفاده می‌کند.

ترتیب حافظه

هر عملیات تا اینجا یک مکان واحد را دست زده است. وقتی نخ‌ها از طریق بیش از یک مکان هماهنگ می‌شوند، پرسش تازه‌ای پدید می‌آید: نوشتن‌های یک نخ به چه ترتیبی برای نخ دیگر مرئی می‌شوند. قواعدی که به این پرسش پاسخ می‌دهند، ترتیب حافظهی پردازنده‌اند.

مفهوم کد بدون شاخه این ایده را معرفی کرد که یک هسته‌ی امروزی دستورها را یکی‌یکی و کُند پیش نمی‌برد. بلکه بسیاری را هم‌زمان در جریان نگه می‌دارد و هرجا بتواند جلوتر می‌رود. این یعنی ممکن است یک نوشتن دیرتر از آنچه برنامه نشان می‌دهد برای هسته‌های دیگر مرئی شود، در حالی که دستورهای پس از آن پیش‌تر رفته‌اند.

x86-64 یک ترتیب حافظه‌ی قوی میان بارگذاری‌ها و ذخیره‌های معمولی حفظ می‌کند، به این ترتیب که روی هر هسته:

1. یک بارگذاری هرگز پس از یک بارگذاری بعدی بازچینش نمی‌شود؛
2. یک ذخیره هرگز پس از یک ذخیره‌ی بعدی بازچینش نمی‌شود؛
3. یک بارگذاری هرگز پس از یک ذخیره‌ی بعدی بازچینش نمی‌شود.

تنها بازچینش ممکن این است که یک ذخیره به نظر برسد پس از یک بارگذاری بعدی از نشانی‌ای متفاوت کامل می‌شود.

یک دستور با پیشوند lock، یا یک xchg با عملوند حافظه، یک سد کامل است: هیچ‌چیز به نظر نمی‌رسد که در هیچ جهتی از آن بگذرد. به همین دلیل برای تضمین ترتیب کامل در بیشتر موقعیت‌ها کافی‌اند.

سازوکار پشت آن یک بازچینش بازمانده، بافر ذخیره است. برای اینکه بتواند جلوتر برود، هسته هر ذخیره را در آن بافر می‌گذارد و می‌گذارد دستورهای بعدی پیش از رسیدن ذخیره به حافظه‌ای که هسته‌های دیگر می‌بینند، ادامه پیدا کنند. پس یک نوشتن و سپس خواندن از مکانی متفاوت می‌تواند بی‌ترتیب به نظر برسد: نوشتن ممکن است هنوز در بافر باشد در حالی که خواندن بعدی جلو می‌رود. این مدل، یعنی همه‌چیز مرتب است جز همان شکاف نوشتن-سپس-خواندن، ترتیب کامل ذخیره نامیده می‌شود.

همان شکاف واحد برای شکستن یک دست‌دادن نوشتن-سپس-بررسی کافی است. اگر دو نخ هرکدام پرچم خودشان را بنویسند و سپس پرچم دیگری را بخوانند، هر دو خواندن می‌توانند تنظیم‌نشده برگردند، چون هیچ‌کدام از ذخیره‌ها هنوز از بافر ذخیره‌اش بیرون نرفته است. دستور mfence این شکاف را با تخلیه‌ی بافر ذخیره می‌بندد: هر نوشتنی پیش از آن، مرئی می‌شود پیش از هر خواندنی پس از آن.

    mov dword [rdi], 1    ; publish: this thread is ready
    mfence                ; the store above must land before the load below
    mov eax, dword [rsi]  ; observe whether the other thread is ready

دو سد باریک‌تر هم وجود دارد:

• sfence نوشتن‌ها را نسبت به یکدیگر مرتب می‌کند و عمدتاً با ذخیره‌های جریانی و غیرزمانی اهمیت دارد؛
• lfence خواندن‌ها را مرتب می‌کند.

برای الگوهای اتمیک معمولی بالاتر، دستورهای با پیشوند lock از پیش ترتیب کامل را با خود دارند، پس یک سد صریح تنها برای دست‌دادنی لازم است که از ذخیره‌ها و بارگذاری‌های ساده مانند نمونه‌ی بالا ساخته شده باشد.

این تضمین‌ها نام‌هایی دارند که فراتر از x86 می‌روند. یک عملیات وقتی ترتیب acquire دارد که هیچ دسترسی بعدی به نظر نرسد که پیش از آن برود، و ترتیب release دارد وقتی هیچ دسترسی پیشینی به نظر نرسد که پس از آن برود. روی x86 هر بارگذاری یک acquire است، هر ذخیره یک release است، و یک دستور با پیشوند lock، یا یک xchg با حافظه، هر دو را هم‌زمان دارد.

چرخش و pause

دستورهایی که پرچمی را تنظیم می‌کنند و هم‌زمان وضعیت پیشین آن را برمی‌گردانند، به test-and-set شناخته می‌شوند. می‌توانند پایه‌ای برای یک قفل چرخشی باشند و تضمین کنند که یک هسته دسترسی انحصاری به بخشی از کد دارد.

این الگوریتم کلی است، با استفاده از دستور 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 در حلقه‌ی انتظار تغییری در آنچه کد محاسبه می‌کند ایجاد نمی‌کند. بلکه به پردازنده اشاره می‌کند که این یک انتظار چرخشی است. پردازنده آنگاه می‌تواند مصرف انرژی نخ منتظر را کم کند و به نخ دیگری که همان هسته را به اشتراک می‌گذارد واگذار کند. یک حلقه‌ی چرخشی بدون pause همچنان درست است، فقط انرژی را هدر می‌دهد.

توجه کنید که در یک test-and-set، دستوری مانند xchg همیشه پرچم را تنظیم می‌کند، حتی وقتی از پیش تنظیم شده باشد. یعنی در هر چرخش دسترسی انحصاری به حافظه می‌گیرد، حتی وقتی احتمالاً قفل هنوز در دست دیگری است.

گونه‌ای از این الگوریتم وجود دارد، به نام test-and-test-and-set، که نخست پرچم را آزمون (می‌خواند) می‌کند تا ببیند از پیش تنظیم شده است یا نه. سپس تنها وقتی قفل آزاد به نظر برسد test-and-set (در این مورد xchg) را امتحان می‌کند:

acquire:
    mov  eax, 1
    xchg dword [rdi], eax ; try to take the lock
    test eax, eax
    jz   .taken           ; got it
.held:
    pause                 ; wait before trying again
    cmp  dword [rdi], 0   ; watch the lock without writing to it
    jne  .held            ; still held
    jmp  acquire          ; looks free: retry
.taken:
    ret

وقتی نخ کارش را تمام کرد، می‌تواند قفل را با یک ذخیره‌ی ساده‌ی 0 به کمک mov آزاد کند. چیزی بیش از یک mov لازم نیست، چون در x86-64 بارگذاری‌ها و ذخیره‌ها هرگز پس از یک ذخیره‌ی بعدی بازچینش نمی‌شوند. ذخیره‌ای که هرگز از دسترسی‌های پیش از خود جلو نمی‌افتد، ترتیب release دارد و روی x86 هر ذخیره‌ی ساده آن را با خود دارد.