Atomi műveletek ebben a kurzusban:

A(z) Atomi műveletek fogalomról

Egyetlen utasítás úgy tűnhet, mintha egyetlen oszthatatlan művelet lenne, pedig korántsem az. Vegyük például, amikor egy memóriában lévő értékhez ötöt adunk:

add qword [rel counter], 5

A háttérben a processzornak nincs módja arra, hogy közvetlenül a memóriához adjon. Ezt az egyetlen utasítást három kisebb lépésre bontja, amelyeket mikrooperációknak nevezünk:

1. beolvassa az aktuális értéket a memóriából;
2. módosítja ezt az értéket egy regiszterben, hozzáadva ötöt;
3. visszaírja az eredményt.

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

Ez egy gyakori minta, amelyet olvasás-módosítás-írásnak (RMW) nevezünk.

Figyeld meg, hogy az olvasás (vagy betöltés) és az írás (vagy tárolás) külön események, így időablak van közöttük. Ezt általában nem vesszük észre, mert egyetlen magon minden utasítás garantáltan teljesen kifejti a hatását, mielőtt a következő sorra kerülne. Ez az ablak tehát láthatatlan, és az add úgy viselkedik, mint egyetlen egység.

A modern processzorok azonban ritkán egymagúak, és az alkalmazások gyakran egyszerre több magon futnak, amelyek között nincs semmilyen sorrendezés. Amikor több mag fut ugyanabban a pillanatban, egy másik mag beolvashatja vagy írhatja a counter értékét az ablakon belül, miután ez a mag betöltötte és mielőtt eltárolná. Két szál ugyanazt a régi értéket tölti be, mindkettő hozzáad ötöt, és mindkettő eltárolja az eredményét. Két összeadás történt, de az érték csak öttel nőtt. Az egyik frissítés csendben elveszett.

Ez egy adatverseny, és gyakori probléma a többszálú kódban.

Nem minden érték van kitéve ennek. Minden szálnak saját regiszterei és saját verme van, ezért a regiszterben tartott érték, illetve a szál vermében lévő lokális változó kizárólag ahhoz a szálhoz tartozik, és nem versenyezhet. Csak a szálak által megosztott memóriát, mint a fenti counter, kell védeni.

Az x86-64 utasításkészlete megoldást kínál erre a problémára: olyan utasításokat, amelyek oszthatatlanok. Nemcsak a feldolgozó mag számára viselkedik egyetlen egységként, hanem minden más mag számára is. Az olyan műveletet, amely egyben marad, és amelyet egyetlen más mag sem tud kettéválasztani, atomikusnak nevezzük.

Atomikus csere

Az xchg utasítás két operandust cserél fel. A céloperandus egyenlő lesz a forrásoperandus korábbi értékével, a forrásoperandus pedig a céloperandus korábbi értékével. Fogalmilag úgy képzelhető el, mintha két mov utasítás egyszerre hajtódna végre.

Ahogy megszokott, használható két regiszteroperandussal, vagy egy memóriaoperandussal és egy regiszteroperandussal:

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

Ha memóriaoperandussal használjuk, az xchg mindig atomikus. A processzor erre az időtartamra zárolja a memóriacímet, ugyanazzal a mechanizmussal, amelyet a lock előtag használ más utasításoknál, és amelyet a következőkben ismertetünk.

A lock előtag

A leggyakoribb módja annak, hogy egy utasítást atomikussá tegyünk x86-64-en, a lock előtag hozzáadása. Ez összeolvasztja az olvasást, a módosítást és az írást egyetlen oszthatatlan lépéssé. Ez azt jelenti, hogy a mag a teljes folyamat alatt kizárólagosan birtokolja a memóriát, így közben egyetlen más mag sem olvashatja vagy írhatja azt a címet.

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

A lock csak akkor működik, ha a cél memória, és csak olyan utasításokon, amelyek olvassák és módosítják azt a memóriát:

1. aritmetikai műveletek, például add, sub, inc, dec, neg;
2. bitenkénti műveletek, például and, or, xor, not;
3. a bts, btr, btc bitműveletek;
4. néhány más, erre a célra szolgáló utasítás, például az xadd és a cmpxchg, amelyeket alább ismertetünk.

Bármely más utasításon, például egy egyszerű mov esetén az előtag érvénytelen, és a processzor érvénytelen opkód kivételt vált ki. Egy önmagában álló betöltéshez vagy tároláshoz nem kell előtag: a természetesen igazított hozzáférés önmagában is atomikus.

Atomikus bitműveletek

A zárolható utasítások közül a bittesztek természetesen illeszkednek a dokumentum végén szereplő spinlockhoz. A bts, btr és btc mindegyike átmásol egy kiválasztott bitet a carry jelzőbe, majd beállítja, törli vagy átbillenti azt. A lock előtaggal ez egybites olvasás-módosítás-írássá válik: a bit atomikusan változik meg, a CF pedig azt jelzi, hogy mi volt korábban.

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

Ha egy beállítás azt tapasztalja, hogy a bit már be van állítva, az azt jelenti, hogy egy másik szál előbb igényelte. Ez a jelzőigénylés egybites változata, amelyet az xchg egy egész szóra végez.

Csere és összeadás

Egy egyszerű lock add frissíti a memóriát, de eldobja a régi értéket. Gyakran éppen a régi értékre van szükség, például hogy minden szál külön sorszámot kapjon.

Az xadd utasítás (az x a csere, exchange rövidítése) összeadás közben visszaadja a korábbi értéket. Az összeget a céloperandusba írja, a céloperandus eredeti értékét pedig a forrásregiszterben hagyja.

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

A lock előtaggal ez egy atomikus fetch-and-add. Ha sok szál futtatja ugyanazon a számlálón, minden hívás más régi értéket ad vissza.

A lock add-hoz hasonlóan a számláló pontosan a hívások számánál végződik. A lock add-tól eltérően azonban minden közbenső érték is visszaadódik, mindegyik hívónak egy.

A forrás bármely általános célú regiszter lehet, az operandus szélessége pedig egy bájttól egy quadwordig terjed. Negatív érték hozzáadásával ugyanaz az utasítás fetch-and-subtractté válik.

Összehasonlítás és csere

Az xadd összead, az xchg felülír, de egyik sem tudja az új értéket a jelenlegitől függővé tenni, és csak akkor alkalmazni, ha a háttérben semmi sem változott. Ezt a feltételes frissítést nyújtja a cmpxchg, azaz az összehasonlítás és csere, és ez a legáltalánosabb az itteni primitívek közül.

A cmpxchg dest, src implicit akkumulátorként a rax-et használja, és összehasonlítja a dest-tel:

• Ha dest == rax, akkor dest = src és ZF = 1.
• Ha dest != rax, akkor rax = dest és ZF = 0.

Az akkumulátor követi az operandus méretét: egy bájthoz al, a szélesebb formákhoz pedig ax, eax és rax.

Figyeld meg, hogy a dest csak akkor frissül, ha egyenlő a várt értékkel, amelyet korábban a rax-be töltöttünk. Ez az egyenlőség biztosítja, hogy a dest még mindig azt az értéket tartalmazza, amelyből az újat kiszámítottuk, így egy elavult olvasáson alapuló frissítés soha nem kerül alkalmazásra. Ez teszi a cmpxchg-t az atomikus frissítés építőelemévé, amelyet összehasonlítás és csere (CAS) néven is ismerünk:

    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

Ez az újrapróbálkozó ciklus a lock-free frissítések szíve. Az olvasás és az összehasonlítás-és-csere közötti ablak pontosan az, amikor egy másik szál közbeavatkozhat, és a cmpxchg ezt úgy kapja el, hogy megtagadja egy elavult olvasásból számított érték eltárolását.

Egy finomságot érdemes megismerni. A cmpxchg azt ellenőrzi, hogy az érték egyenlő-e az olvasottal, nem azt, hogy a címhez hozzá sem nyúltak. Ha egy másik szál az ablakon belül A-ból B-be és vissza A-ba viszi az értéket, a csere mégis sikerül, pedig a háttérben közben megváltozott a világ.

Egy egyszerű számláló esetében ez ártalmatlan, hiszen egy egyenlő darabszám ugyanolyan jó darabszám. Egy lock-free lista elején lévő memóriacím esetében viszont nem az, mert ugyanaz a cím most máshová vezethet. Ez az ABA-probléma.

A szokásos megoldás erre a problémára, hogy az értéket összepárosítjuk valamilyen „bélyeggel”, például egy csak növekvő számlálóval. Mivel a bélyeg csak előrehalad, egy egyező bélyeg bizonyítja, hogy a címhez közben nem nyúltak hozzá, nem csupán azt, hogy változatlannak tűnik.

Ahhoz azonban, hogy ez többszálú környezetben működjön, a memóriacímet és a bélyegét együtt kell frissíteni. Mivel x86-64-en egy memóriacím egy teljes qword, a cmpxchg nem elég ahhoz, hogy egyszerre frissítse azt és egy másik értéket is.

Létezik egy kétszeres szélességű utasítás, a cmpxchg16b, amely szemantikailag ugyanaz, mint a cmpxchg, de egyszerre 16 bájton dolgozik, és ilyen helyzetben használható. Nincs forrásoperandusa, helyette a rcx:rbx-et használja a helyettesítő értékként. Az egyetlen operandusa egy 16 bájtos határra igazított memóriabeli cím. Ez az utasítás is a rdx:rax-et használja akkumulátorként, nem csak a rax-et.

Memóriarendezés

Az eddigi műveletek mind egyetlen címhez nyúltak. Amikor a szálak egynél több címen keresztül hangolódnak össze, új kérdés merül fel: milyen sorrendben válnak láthatóvá az egyik szál írásai egy másik számára. Az erre a kérdésre választ adó szabályok alkotják a processzor memóriarendezését.

A branchless-code fogalom mutatta be azt az elképzelést, hogy egy modern mag nem egyesével, nehézkesen halad végig az utasításokon. Egyszerre sok utasítást tart folyamatban, és előreszalad, ahol tud. Ez azt jelenti, hogy egy írás később válhat láthatóvá a többi mag számára, mint ahogy a program sugallná, miközben az utána következő utasítások már előrehaladtak.

Az x86-64 erős memóriarendezést tart fenn a közönséges betöltések és tárolások között, így minden magon:

1. egy betöltés soha nem kerül egy későbbi betöltés mögé;
2. egy tárolás soha nem kerül egy későbbi tárolás mögé;
3. egy betöltés soha nem kerül egy későbbi tárolás mögé.

Az egyetlen lehetséges átrendeződés, hogy egy tárolás úgy tűnik, egy más cím későbbi betöltése után fejeződik be.

A lock előtaggal ellátott utasítás, illetve a memóriaoperandusos xchg teljes sorompó: látszólag semmi sem kerül át rajta egyik irányban sem. Ezért elegendőek ahhoz, hogy a legtöbb helyzetben teljes sorrendezést biztosítsanak.

Az egyetlen megmaradó átrendeződés mögött a tárolási puffer áll. Hogy továbbra is előreszaladhasson, a mag minden tárolást elhelyez abban a pufferben, és hagyja, hogy a későbbi utasítások továbbhaladjanak, mielőtt a tárolás eléri a többi mag számára látható memóriát. Ezért egy írás, amelyet egy másik cím olvasása követ, sorrenden kívülinek tűnhet: az írás még mindig a pufferben ülhet, miközben a későbbi olvasás már előrehalad. Ezt a modellt, amelyben minden rendezett, kivéve azt az írás-majd-olvasás rést, teljes tárolási sorrendnek nevezzük.

Ez az egyetlen rés elég ahhoz, hogy megtörjön egy tárolás-majd-ellenőrzés kézfogást. Ha két szál mindegyike kiírja a saját jelzőjét, majd beolvassa a másikét, mindkét olvasás beállítatlanul térhet vissza, mert egyik tárolás sem hagyta még el a tárolási pufferét. Az mfence utasítás úgy zárja be a rést, hogy kiüríti a tárolási puffert: minden előtte lévő írás láthatóvá válik minden utána következő olvasás előtt.

    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

Két szűkebb sorompó is létezik:

• az sfence egymáshoz rendezi az írásokat, és főleg a streamelő, nem temporális tárolásoknál számít;
• az lfence az olvasásokat rendezi.

A fenti közönséges atomikus mintákhoz a lock előtaggal ellátott utasítások már teljes sorrendezést hordoznak, így explicit sorompóra csak egy olyan kézfogásnál van szükség, amelyet egyszerű tárolásokból és betöltésekből építünk, mint a fenti.

Ezeknek a garanciáknak olyan elnevezéseik vannak, amelyek túlmutatnak az x86-on. Egy művelet acquire sorrendezésű, ha egyetlen későbbi hozzáférés sem tűnik úgy, hogy eléje kerül, és release sorrendezésű, ha egyetlen korábbi hozzáférés sem tűnik úgy, hogy utána kerül. Az x86-on minden betöltés acquire, minden tárolás release, a lock előtaggal ellátott utasítás pedig, illetve a memóriaoperandusos xchg, egyszerre mindkettő.

Pörgés és pause

Azokat az utasításokat, amelyek beállítanak egy jelzőt, miközben vissza is adják annak korábbi állapotát, test-and-set néven ismerjük. Ezek alapját képezhetik egy spinlocknak, amely biztosítja, hogy egy mag kizárólagos hozzáféréssel rendelkezzen a kód egy részéhez.

Ez a teljes algoritmus, amely az xchg utasítást használja egy bináris jelzővel:

1. A jelző kezdetben 0.
2. A zár megszerzéséhez a mag kicseréli a jelző értékét 1-re.
3. Ha a visszaadott érték 1, az azt jelenti, hogy a zárat egy másik mag birtokolja. Az aktuális mag ekkor vár, és újra megpróbálja megszerezni a zárat.
4. Ha a visszaadott érték 0, az azt jelenti, hogy a zár szabad volt. Az xchg most 1-re állította, és a többi mag addig vár, amíg ez a mag el nem engedi.
5. Amint az aktuális mag befejezi a munkát, a jelző 0-ra frissítése elengedi a zárat.

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

A várakozó ciklusban lévő pause utasítás nem változtatja meg azt, amit a kód kiszámít. Csak jelzi a processzornak, hogy ez egy pörgő várakozás. A processzor ekkor csökkentheti a várakozó szál energiafogyasztását, és átadhatja a helyet egy ugyanazon a magon osztozó testvérszálnak. Egy pause nélküli pörgő ciklus is helyes, csak pazarló.

Figyeld meg, hogy egy test-and-set során egy olyan utasítás, mint az xchg, mindig beállítja a jelzőt, még akkor is, ha már be volt állítva. Ez azt jelenti, hogy minden pörgésnél kizárólagos hozzáférést szerez a memóriához, még akkor is, ha valószínűleg a zárat még mindig birtokolják.

Létezik ennek az algoritmusnak egy változata, a test-and-test-and-set, amely először megvizsgálja (beolvassa) a jelzőt, hogy ellenőrizze, be van-e már állítva. Csak akkor kísérli meg a test-and-set műveletet (ebben az esetben az xchg-t), amikor a zár szabadnak tűnik:

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

Amint a szál befejezi a munkáját, egy egyszerű 0 tárolással elengedheti a zárat a mov segítségével. Nem kell több egy mov-nál, mert x86-64-en a betöltések és tárolások soha nem kerülnek egy későbbi tárolás mögé. Egy tárolás, amely soha nem előzi meg az előtte lévő hozzáféréseket, release sorrendezésű, és az x86-on minden egyszerű tárolás rendelkezik ezzel.