Nyitóest

Atomikus műveletek

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

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 mikroműveleteknek nevezünk:

1. olvasás: az aktuális érték kiolvasása a memóriából;
2. módosítás: az érték megnövelése egy regiszterben, öttel;
3. visszaírás: az eredmény visszaírása.

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ás (RMW) néven ismerü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 az utasítások garantáltan teljesen kifejtik a hatásukat, mielőtt a következő sorra kerülne. Ez az ablak tehát láthatatlan, és az add úgy viselkedik, mintha egyetlen egység lenne.

A modern processzoroknak azonban ritkán van csak egyetlen magjuk, és az alkalmazások gyakran egyszerre több magon futnak, amelyek között nincs semmilyen sorrendiség. Mivel 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, de még 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, az érték mégis 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 azonban így kitéve ennek. Minden szálnak saját regiszterei és saját verme van, így a regiszterben tartott érték, illetve a szál vermén lévő lokális változó kizárólag az adott szálhoz tartozik, és nem kerülhet versenyhelyzetbe. Csak a szálak által megosztott memóriát, például a fenti counter értékét kell védeni.

Az x86-64 egy sor utasítást kínál erre a problémára, amelyek oszthatatlanná teszik az utasítást. Az ilyen művelet 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ásik mag sem tud kettéválasztani, atomikusnak nevezzük.

Atomikus csere

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

A szokásos módon 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 lock előtag

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

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 a memória, és csak azokon az utasításokon, amelyek olvasás-módosítás-írás műveletet végeznek ezen a memórián:

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

Csere és összeadás

Az egyszerű lock add frissíti a memóriát, de a régi értéket eldobja. Gyakran épp 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 (x az exchange, azaz a csere rövidítése) visszaadja a korábbi értéket, miközben összead. Az összeget a céloperandusba írja, az eredeti célértéket 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öztes érték is visszaadódik, mindegyik hívónak egy.

Összehasonlítás és csere

Az xadd összead, az xchg felülír, de egyik sem tudja elérni, hogy az új érték a jelenlegitől függjön, és csak akkor kerüljön alkalmazásra, ha a háttérben semmi sem változott. Ezt a feltételes frissítést biztosítja a cmpxchg (compare-and-exchange, azaz összehasonlítás és csere), és ez a legáltalánosabb ezek közül a primitívek közül.

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

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

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 új értéket szá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 compare-and-swap (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 lelke. Az olvasás és az összehasonlítá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.

Memóriasorrend

Az eddigi műveletek mind egyetlen helyet érintettek. Amikor a szálak egynél több helyen keresztül hangolják össze a működésüket, új kérdés merül fel: milyen sorrendben válnak láthatóvá az egyik szál írásai a másik számára. Az erre a kérdésre választ adó szabályok alkotják a processzor memóriasorrendjét.

Az elágazás nélküli kód fogalma mutatta be azt a gondolatot, hogy a modern mag nem egyesével araszol végig az utasításokon. Egyszerre többet is úton tart, és ahol lehet, előre szalad. Ez azt jelenti, hogy egy írás később válhat láthatóvá a többi mag számára, mint amit a program sugall, miközben a mögötte lévő utasítások már előrehaladtak.

Az x86-64 erős memóriasorrendet tart fenn a hétköznapi betöltések és tárolások között, így minden magon:

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

Az egyetlen lehetséges átrendezés az, hogy egy tárolás úgy tűnik, egy másik 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óriaoperandusú xchg teljes korlát: semmi sem tűnik úgy, hogy átlép rajta bármelyik irányban. Ezért elegendőek ahhoz, hogy a legtöbb helyzetben biztosítsák a teljes sorrendet.

Pörgés és a pause

Azokat az utasításokat, amelyek beállítanak egy jelzőt, miközben visszaadják annak korábbi állapotát, test-and-set néven ismerjük. Ezek használhatók egy spinlock alapjaként, biztosítva, hogy egy mag kizárólagos hozzáféréssel bírjon a kód egy részéhez.

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

1. A jelző kezdetben 0.
2. A zár megszerzéséhez a mag 1-re cseréli a jelző értékét.
3. Ha a visszaadott érték 1, az azt jelenti, hogy a zárat egy másik mag birtokolja. Az aktuális mag ilyenkor 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. Amikor az aktuális mag végzett a munkával, 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 spin-wait. A processzor így csökkentheti a várakozó szál energiafogyasztását, és átadhatja a helyét egy ugyanazon a magon osztozó testvérszálnak. A pause nélküli pörgő ciklus is helyes, csak pazarló.

Amint a szál befejezi a munkáját, elengedheti a zárat egy egyszerű mov-mal elvégzett 0-tárolással. Nem kell több egy mov-nál, mert az x86-64-en a betöltések és a tárolások soha nem rendeződnek át egy későbbi tárolás mögé. Egy tárolásról, amely soha nem előzi meg a korábbi hozzáféréseket, azt mondjuk, hogy release ordering jellemzi, és az x86-on minden egyszerű tárolás rendelkezik ezzel.