شب افتتاح

عملیات اتمیک

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

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

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

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