15.5 Konkurens élettartam és nehéz hibák

Egy pointer atomikus beolvasása még nem biztosítja, hogy a megcímzett objektum él, mire dereferáljuk. A konkurens program helyességéhez ezért két külön kérdésre kell válaszolni: hogyan egyeztetjük a hozzáféréseket, és mikor szüntethetjük meg biztonságosan az objektum élettartamát?

A C atomics és memory order részben megismert publikálási kapcsolat láthatóvá teheti az inicializált adatokat, de önmagában nem akadályozza meg későbbi felszabadításukat. Most ezt az élettartamproblémát kapcsoljuk össze az előrehaladási garanciákkal és a diagnosztika korlátaival. A cél nem egy általános lock-free könyvtár megvalósítása, hanem annak felismerése, hogy egy megoldás pontosan mit garantál — és mit nem.

15.5.1 Biztonságos hozzáférés és biztonságos felszabadítás

A memória-visszanyerés, angolul memory reclamation, annak eldöntése, hogy egy megosztott adatszerkezetből eltávolított objektum tárolója mikor szabadítható fel vagy használható újra.

Az eltávolítás és a felszabadítás nem ugyanaz:

1. Az objektumot elérhetetlenné tesszük az új olvasók számára.
2. Megvárjuk vagy bizonyítjuk, hogy a korábbi olvasók sem használhatják többé.
3. Megszüntetjük az élettartamát, és felszabadítjuk a tárolóját.

ISO C17: ha egy szál dereferál egy már felszabadított objektumra mutató pointert, a viselkedés nem definiált. Az, hogy a címen még látszólag ugyanazok a bitek találhatók, nem élettartam-garancia.

Tegyük fel, hogy egy olvasó atomikusan beolvassa a megosztott pointert. Ezután egy másik szál atomikusan nullára cseréli azt, és felszabadítja az objektumot. Az olvasó következő dereferálása már hibás lehet. Mindez memory_order_seq_cst mellett is megtörténhet: az atomikus pointerműveletek rendezése nem hosszabbítja meg a megcímzett objektum élettartamát.

15.5.1.1 ABA: ugyanaz az érték, megváltozott történet

Az ABA-probléma akkor jelentkezik, amikor egy állapot értéke $A \rightarrow B \rightarrow A$ módon változik, és egy későbbi összehasonlítás az eredeti $A$ értéket látva nem észleli a közbülső változásokat.

Nézzünk egy veremfejet. A fogalmi példában a head és a next mezők atomikusak, és egyetlen csomópontot sem szabadítunk fel. Így az ABA-hibát külön vizsgálhatjuk az adatversenytől és a dangling pointerektől.

A compare-and-exchange sikeres, pedig T1 elavult kapcsolat alapján dolgozik. B visszakerül a verembe, noha T2 már kivette, és akár saját tulajdonának tekinti.

A felszabadítás utáni cím-újrafelhasználás hasonló azonossági problémát okozhat: ugyanaz a numerikus cím később más objektumhoz tartozhat. C-ben azonban a régi pointert nem kezelhetjük automatikusan ártalmatlan címazonosítóként a megcímzett objektum élettartamának vége után.

Egy generációszámmal kiegészített fej csökkentheti az ABA veszélyét, de feltételei vannak:

• a pointert és a generációt együtt kell atomikusan összehasonlítani;
• a számláló körbefordulását kezelni vagy kizárni kell;
• az összetett atomikus művelet nem feltétlenül lock-free;
• a verziózás önmagában nem teszi biztonságossá a dereferálást.

15.5.2 Reclamation-megoldások fogalmi térképe

15.5.2.1 Referenciaszámlálás

A reference count az objektum élettartamáért felelős referenciákat számolja. Az utolsó referencia elengedése engedélyezheti a felszabadítást.

A kényes pont a referencia megszerzése. Ez a gondolatmenet hibás:

Beolvasom a megosztott pointert, majd atomikusan növelem a benne található referenciaszámlálót.

A két művelet között az utolsó tulajdonos felszabadíthatja az objektumot. A számláló növelése ekkor már megszűnt élettartamú objektumot érint.

Biztonságos kiindulás például, ha a megosztott pointer beolvasása és a referencia megszerzése ugyanazon mutex alatt történik, mint az eltávolítás. Már birtokolt referenciából további referencia létrehozásakor viszont az eredeti referencia biztosítja az élettartamot. A ciklusok, a számláló túlcsordulása és az utolsó elengedés szinkronizációja külön kezelendő.

15.5.2.2 Epoch és hazard pointer

Epoch-alapú kezelésnél az olvasó védett szakaszba lép. Az eltávolított objektum először retired, vagyis visszavonásra jelölt állapotba kerül. Csak akkor szabadítható fel, amikor egyetlen olyan korábbi olvasói szakasz sem aktív, amely még elérhette.

Hazard pointernél az olvasó fogalmilag:

1. beolvassa a megosztott pointert;
2. közzéteszi saját védelmi bejegyzésében;
3. újraellenőrzi a megosztott pointert;
4. csak sikeres ellenőrzés után dereferál;
5. a használat végén megszünteti a védelmet.

Ez nem kész implementációs recept. A publikálás, az újraellenőrzés és a felszabadító szál vizsgálata közötti memory-order kapcsolat bizonyítandó; néhány release/acquire művelet önmagában nem bizonyítás.

A hazard pointer megakadályozhatja a védett objektum felszabadítását, de nem old meg minden ABA-helyzetet: egy még élő csomópont eltávolítása és visszahelyezése továbbra is algoritmikus problémát okozhat.

15.5.3 Kidolgozott példa: másolat a zár alatt, felszabadítás utána

Konfigurációs állapot olvasásakor gyakran nincs szükség tartós borrowed pointerre. Elég a szükséges értéket a zár alatt kimásolni.

Laborprofil: ISO C17 és POSIX pthreads; Linux x86-64 System V, LP64, CHAR_BIT=8; választott fordítók GCC 14.2.0 és Clang 19.1.7, libc glibc 2.40. Az alábbi példa nem közölt fordítási vagy mérési eredmény.

/* lifetime.c */
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

struct record {
    unsigned value;
};

static struct {
    pthread_mutex_t mutex;
    struct record *current;
} state = { PTHREAD_MUTEX_INITIALIZER, NULL };

static void check(int error)
{
    if (error != 0) {
        fprintf(stderr, "pthread hibakod: %d\n", error);
        abort();
    }
}

static void *reader(void *unused)
{
    (void)unused;

    for (unsigned i = 0; i < 10000; ++i) {
        unsigned snapshot = 0;

        check(pthread_mutex_lock(&state.mutex));
        if (state.current != NULL)
            snapshot = state.current->value;
        check(pthread_mutex_unlock(&state.mutex));

        /* Itt mar csak a sajat masolatot hasznaljuk. */
        if (snapshot != 0 && snapshot != 42)
            abort();
    }

    return NULL;
}

int main(void)
{
    state.current = malloc(sizeof *state.current);
    if (state.current == NULL)
        return EXIT_FAILURE;
    state.current->value = 42;

    pthread_t thread;
    check(pthread_create(&thread, NULL, reader, NULL));

    check(pthread_mutex_lock(&state.mutex));
    struct record *retired = state.current;
    state.current = NULL;
    check(pthread_mutex_unlock(&state.mutex));

    free(retired);

    check(pthread_join(thread, NULL));
    check(pthread_mutex_destroy(&state.mutex));
    return EXIT_SUCCESS;
}

A tanuló külön laborjában használható fordítási parancsok:

gcc -std=c17 -Wall -Wextra -Wpedantic -O1 -g -pthread \
    lifetime.c -o lifetime

clang -std=c17 -Wall -Wextra -Wpedantic -O1 -g -pthread \
    -fsanitize=thread lifetime.c -o lifetime-tsan

A -pthread és a sanitizer kapcsoló fordítóeszköz-szintű beállítás, nem ISO C nyelvi elem. A ThreadSanitizer futtatási támogatását a tényleges környezetben külön ellenőrizni kell.

Bizonyításvázlat. Ha az olvasó előbb szerzi meg a mutexet, befejezi a másolást, mielőtt az eltávolító beléphet. Ha az eltávolító lép be előbb, nullára állítja a pointert, ezért a későbbi olvasó nem dereferálja. Mivel pointer nem szökik ki a kritikus szakaszból, az eltávolítás utáni free biztonságos. A join nem a record, hanem a még használt szinkronizációs objektum lezárását teszi biztonságossá.

Ez POSIX mutex- és szál-életciklus-szerződésre épül. Allokációs hibakor a program hibakóddal kilép; pthread-hibakor szándékosan azonnal leáll. Ez egyszerűsített hibapolitika, nem szolgáltatásüzemeltetési helyreállítás.

15.5.4 Előrehaladás: mit jelent a „nem blokkoló”?

Az előrehaladási garancia azt írja le, hogy milyen feltételekkel fejeződnek be a műveletek. Nem azonos az alacsony késleltetéssel.

A szokásos modellben:

$$\text{wait-free} \Rightarrow \text{lock-free} \Rightarrow \text{obstruction-free}.$$

A wait-free korlát függhet például a bemenet méretétől és a résztvevők rögzített számától. Ezek lépésszámra vonatkozó állítások: egyáltalán nem ütemezett szálnak nem adnak faliórás határidőt.

ISO C17: az atomic_is_lock_free az adott atomikus objektum műveleteinek tulajdonságáról tájékoztat, nem a teljes algoritmusról. Lock-free atomikus műveletekből felépített spinlock továbbra is várhat egy megállt zártulajdonosra.

A teljes hívási lánc számít. Egy lock-free mutatómódosítás köré helyezett blokkoló allocator, naplózás vagy reclamation-várakozás megváltoztathatja a teljes API garanciáját. Az epoch-alapú visszanyerésnél külön vizsgálandó, hogy az elakadt olvasó csak a memória felszabadítását akadályozza-e, vagy a műveleteket is.

15.5.4.1 Deadlock, livelock, starvation és fairness

Deadlock, vagyis holtpont esetén a résztvevők egymástól függően várnak. Két mutex ellentétes sorrendű megszerzése klasszikus ellenpélda. Következetes globális zársorrend megszüntetheti az ilyen körkörös várakozást.

Livelock esetén a szálak aktívak, de nem történik hasznos előrehaladás: például mindig egyszerre hátrálnak ki, majd egyszerre próbálkoznak újra.

Starvation, vagyis éhezés esetén mások haladnak, de egy résztvevő tartósan nem jut sorra. Ez lock-free algoritmusban is megengedett.

A fairness a kiszolgálás méltányosságára vonatkozik. Sem a helyes mutexhasználatból, sem a lock-free tulajdonságból nem következik automatikusan FIFO-sorrend vagy korlátos várakozás. A backoff javíthatja a gyakorlatot, de önmagában nem bizonyít fairness-t.

15.5.5 False sharing atomikus számlálókon

A Cache, locality, alignment és false sharing alapján külön objektumok is osztozhatnak egy cache line-on. Két szál saját atomikus számlálóját módosíthatja adatverseny nélkül, mégis ugyanannak a koherenciaegységnek a tulajdonjogáért versenyezhetnek.

Az alábbi szemléltető layout a fenti x86-64 laborprofilban is külön ellenőrzendő: 64 C bájtos cache line-t, 8 C bájtos számlálót és 64-re igazított kezdőcímet feltételez.

Ezek nem az ABI-ból automatikusan következő layoutadatok. A tényleges sizeof, offset, igazítás és hardverjellemző ellenőrzendő; dinamikus tárolónál az allokáció igazítása is számít.

A memory_order_relaxed nem szünteti meg a false sharinget: az írás továbbra is koherenciaforgalmat okozhat. Megoldás lehet a külön elhelyezés vagy a szálankénti helyi számlálás ritkább összesítéssel. Utóbbi viszont módosítja a megfigyelhető számláló frissességi szerződését. Az eredményt mérni kell; a padding nagyobb memóriaigénnyel és rosszabb összesítési localityval járhat.

15.5.6 Diagnosztika: bizonyíték, de nem bizonyítás

A ThreadSanitizer dinamikus adatverseny-detektor. Egy jelzés konkrét végrehajtás problémájára adhat bizonyítékot; egy jelzés nélküli stresszteszt nem bizonyítja minden végrehajtás helyességét.

Különösen:

• a tisztán atomikus ABA-hiba nem feltétlenül adatverseny;
• az el nem ért use-after-free rejtve marad;
• a deadlock, az éhezés és a fairness nem vezethető le a TSan csendjéből;
• az instrumentálás módosítja az időzítést.

A stresszteszt változtassa a szálszámot, a szüneteket, az eltávolítás gyakoriságát és a tároló újrafelhasználását. A hibainjektálási módszerekkel együtt vizsgálja a részleges inicializálást és a leállítást is. A helyességi érvelés alapja azonban továbbra is az invariáns, az élettartamhatár és a szinkronizációs kapcsolat.

15.5.7 Feladatok

1. Magyarázó: Az ABA-táblázat minden műveletét seq_cst műveletté tesszük. Megszűnik a hiba? Segítene önmagában egy hazard pointer?

2. Kódolási: Írj a példához copy_value(unsigned *out) függvényt. Null pointer paraméternél adjon -1-et, hiányzó rekordnál 0-t, sikeres másoláskor 1-et. Ne adjon vissza borrowed pointert.

3. Diagnosztikai: Egy atomikus számlálókat használó szolgáltatás TSan alatt nem jelez hibát, négy szállal mégis lassabb, és egy worker hosszú ideig nem végez műveletet. Adj külön hipotézist a teljesítményromlásra és az éhezésre, valamint ellenőrzési tervet.

15.5.8 Megoldások

15.5.8.1 Az ABA értelmezése

Nem szűnik meg. A seq_cst rendezés mellett is létrejöhet a táblázat szerinti sorrend. A CAS az aktuális értéket vizsgálja, nem annak történetét. A hazard pointer az élettartamot védheti, de itt minden csomópont él: az eltávolítás–visszahelyezés okozta logikai ABA megmarad.

Ellenőrzési feltétel: az érvelés külön kezelje az értékegyezést, az objektum élettartamát és az adatszerkezeti tagságot.

15.5.8.2 Másoló API

Az előző fájlba illeszthető C17/POSIX-részlet; ugyanazokkal a parancsokkal fordítható:

static int copy_value(unsigned *out)
{
    if (out == NULL)
        return -1;

    int result = 0;
    check(pthread_mutex_lock(&state.mutex));
    if (state.current != NULL) {
        *out = state.current->value;
        result = 1;
    }
    check(pthread_mutex_unlock(&state.mutex));
    return result;
}

Az out a hívó tulajdonában lévő, élő, írható unsigned objektumra mutasson, amelyhez nincs szinkronizálatlan konkurens hozzáférés. A függvény csak a hívás idejére kölcsönzi; 0 és -1 eredménynél nem módosítja.

Ellenőrzési feltétel: minden rekorddereferálás a mutex alatt történik, és semmilyen rekordpointer nem hagyja el a függvényt.

15.5.8.3 Teljesítmény és éhezés szétválasztása

A lassulás egyik hipotézise false sharing. Ezt igazoltan elkülönített számlálókkal, azonos munkamennyiséggel és reprodukálható szálelrendezéssel kell összehasonlítani.

Az éhezés oka lehet egy CAS-ciklus tartós vesztese vagy kedvezőtlen ütemezés. Mérj worker-enként befejezett műveletszámot és újrapróbálkozást, ne csak összesített throughputot.

Ellenőrzési feltétel: a jobb összteljesítmény önmagában nem igazol fairness-t; a TSan csendje egyik hipotézist sem dönti el.

15.5.9 Összefoglaló

Az atomikus hozzáférés, az objektum élettartama és az előrehaladás három külön szerződés. Az ABA az értékazonosság korlátját mutatja meg; a reclamation azt szabályozza, mikor tűnhet el végleg az objektum. Kiindulásként a mutex alatt készített másolat gyakran egyszerűbb és jobban bizonyítható, mint egy tartós borrowed pointer. Lock-free vagy wait-free állítást csak a teljes műveletre, világos feltételekkel szabad tenni; a mérés és a stresszteszt ezt kiegészíti, nem helyettesíti.