Lukustusvabad andmestruktuurid: täielik juhend C++, Java ja .NET näidetega

Mutex on lihtne. Sa lukustad selle, muudad jagatud olekut, avad selle. Iga ligipääsu sooviv lõim ootab oma korda. Probleem on selles, et see „ootab oma korda“ – suure südamike arvu ja läbilaskevõime korral saab serialiseerimisest lagi. Lukustatud lõim saab ennetada, pannes kõik teised lõimed jõude seisma. Prioriteedi inversioon võib põhjustada madala prioriteediga lõimede blokeerimise kõrge prioriteediga lõimede poolt. Süsteemides, mis töötlevad miljoneid operatsioone sekundis kümnete südamike vahel, ei aeglusta mutexi konkureerimine mitte ainult asju, vaid vähendab ka läbilaskevõimet.

Lukustusvabad andmestruktuurid asendavad vastastikuse välistamise aatomioperatsioonidega. Konflikti ennetamise asemel taluvad nad seda ja taastuvad sellest. Lõim, mis ebaõnnestub võrdlemise ja vahetamise korduskatsel, proovib uuendatud olekus. Ükski lõim ei blokeeri kunagi teist. Vähemalt üks lõim edeneb alati. Tulemuseks on oluliselt parem läbilaskevõime suure konkurentsi korral, prognoositav latentsus ilma konvoiefektideta ning ummikseisu ja prioriteedi inversiooni vältimine. Hind on rakenduse keerukus: ABA probleem, mälu taastamise ohud, vale jagamine ja peened mälu järjestamise nõuded on kõik lõksud, mida lukustuspõhises koodis ei eksisteeri. See artikkel käsitleb neid kõiki konkreetse koodi abil.

Lukustusvaba vs ootamisvaba vs Mutex: millist kasutada?

Enne rakendusmeetodi valimist on õige küsimus, millist edenemisgarantiid süsteem tegelikult vajab. Kolm mudelit erinevad selle poolest, mida nad lubavad, kui lõimed konkureerivad.

MUDEL	Edusammude garantii	Tüüpiline latentsusaeg	Keerukus	Parim
Mutex / lukupõhine	Blokeerimine, lõimed ootavad	Ettearvamatu võistluse ajal	Madal	Madala konkurentsiga jagatud olek, lihtsad korrektsusnõuded
Lukustamata	Süsteemiüleselt edeneb vähemalt üks lõim	Madal võistlusvaim	Kõrge	Suure läbilaskevõimega järjekorrad, pinud, loendurid
Ootevaba	Lõime kohta lõpeb iga lõim piiratud sammudega	Piiratud halvim juhtum	Väga kõrge	Reaalajas süsteemid, ohutuskriitilised, ranged latentsusalased SLA-d
Takistusteta	Üksikreis, ainult siis, kui seda pole vaidlustatud	Madal ilma vaidlusteta	Keskmine	Transaktsioonilise mälu prototüübid, uurimiskontekstid

Lukustamata on praktiline vaikeväärtus suure samaaegsusega tootmissüsteemide jaoks. Michael-Scotti järjekord, Treiberi pinu ja enamik MPMC rõngaspuhvreid on lukuvabad. Üksikud lõimed võivad äärmise konkurentsi korral nälga jääda, kuid süsteem tervikuna edeneb.

Ootevaba garanteerib lõime kohta piiratud edenemise, kuid nõuab oluliselt keerukamaid algoritme. Universaalsed konstruktsioonid on olemas, kuid nendega kaasneb suur üldkulu. Ootevabad algoritmid sobivad keeruliste reaalajas kontekstide jaoks, kus saba latentsus on olulisem kui keskmine läbilaskevõime.

Takistusteta kasutatakse harva otse tootmises. See esineb mõnes tehingumälu rakenduses ja toimib hüppelauana algoritmi õigsuse tõestamisel.

Enamiku suure samaaegsusega süsteemide puhul: kasutage mutexi, kui konkurents on madal ja korrektsus on lihtne; kasutage lukustusvaba režiimi, kui läbilaskevõime on konkurentsi korral oluline; kasutage ootamisvaba režiimi ainult siis, kui halvimal juhul on lõime kohta teatav latentsusaeg range nõue.

Mis on lukuvaba andmestruktuur?

Andmestruktuur on lukuvaba kui see garanteerib, et vähemalt üks lõim kõigist sellel töötavatest lõimedest viib oma operatsiooni lõpule lõpliku arvu sammude jooksul, olenemata sellest, mida teised lõimed teevad või kuidas need on ajastatud. Sellel formaalsel definitsioonil on täpne tagajärg: ükski lukuvaba algoritm ei saa ummikseisu sattuda. Kui üks lõim peatatakse, suspendeeritakse või töötab aeglaselt, jätkavad teised lõimed edenemist.

Mehhanism on aatomioperatsioonid, protsessori käsud, mis täidetakse ühe jagamatu üksusena. Universaalne primitiiv on Võrdle ja vaheta (CAS):

CAS(location, expected, new_value):
  if *location == expected:
    *location = new_value
    return true
  else:
    return false  // someone else changed it first

CAS on riistvaralisel tasandil atomaarne. X86-l on see CMPXCHG käsk. ARM-is rakendatakse seda LDXR/STXR (laadimise-ainulaadne/salvestuse-ainulaadne), mis on LL/SC (laadimisega lingitud/tingimuslik) variant. Lõim loeb väärtust, arvutab uue väärtuse ja kasutab CAS-i selle installimiseks ainult siis, kui keegi teine ​​pole seda vahepeal muutnud. Kui CAS ebaõnnestub, proovib lõim uuesti värske väärtusega.

C++11-s ja hilisemates versioonides on see nähtav läbi std::atomic:

cpp

#include <atomic>

// Atomic increment using CAS loop
void atomic_add(std::atomic<int>& counter, int delta) {
    int expected = counter.load(std::memory_order_relaxed);
    while (!counter.compare_exchange_weak(
        expected,
        expected + delta,
        std::memory_order_release,
        std::memory_order_relaxed))
    {
        // expected is updated on failure -- retry with fresh value
    }
}

compare_exchange_weak on CAS-primitiiv. Rikke korral see uuendatakse. expected automaatselt praegusele väärtusele, muutes uuesti proovimise tsükli idioomaatiliseks.

ABA probleem: lukustamata süsteemi kõige ohtlikum lõks

ABA probleem on lukuvaba programmeerimise puhul kõige ebaloogilisem õigsuse oht. CAS kontrollib enne uue mälupesa installimist, kas see sisaldab endiselt oodatud väärtust. See ei suuda tuvastada, kas seda väärtust on lugemise ja CAS-i vahel muudetud ja tagasi muudetud. Asukoht näeb endiselt välja nagu algne väärtus, kuid süsteemi aluseks olev olek on muutunud viisil, mida CAS ei näe.

Stsenaarium samm-sammult

Mõelge lukuvabale pinule, mis kasutab ühte pointerit top:

1. Lõim A loeb top = Node1Sõlme 1 järgmine pointer on Sõlme 2.
2. Lõim A enne hüpikakna lõpetamist eelnev aktiveerimine.
3. Lõim B lisab Node1 (ülemisest saab Node2), seejärel Node2 (ülemisest saab null).
4. Lõim B lisab uue sõlme, mis on eraldatud samale mäluaadressile kui sõlm1 (tavaline vabade nimekirjade eraldajate puhul). Ülemine = sõlm1 (sama pointer, erinev sisu).
5. Lõng A jätkub. Selle CAS näeb top == Node1 (eeldatav väärtus), õnnestub ja seab top = Node2, aga Node2 oli juba vabastatud. Katastroof.

ABA probleem avaldub igas andmestruktuuris erinevalt:

• StackCAS õnnestub, aga paigaldab aegunud järgmise pointeri, mis põhjustab use-after-free'i.
• JärjekordPea või saba osuti näib muutumatuna, kuid struktuur on muutunud
• Lingitud loendSõlm näib olevat endiselt oma kohal, kuid see on eemaldatud ja ümber paigutatud.

Kas LL/SC väldib ABA probleemi?

Jah, LL/SC (koormuspõhine/tingimuslik salvestamine) pakub tugevam semantikat kui CAS ja loomulikult väldib ABA-d. LL tähistab laaditud mäluaadressi "lingituks". SC samal aadressil ebaõnnestub, kui pärast LL-i on sellele aadressile salvestatud, isegi kui väärtus taastati algsesse olekusse. Muudatuste ajalugu jälgitakse riistvara tasandil, mitte ainult praegust väärtust.

Siiski on LL/SC implementatsioonidel reaalsel riistvaral praktilised piirangud. ARM-i ja POWERi puhul võivad esineda näilised LL/SC tõrked isegi ilma konkurentsita (kontekstivahetused, vahemälu eemaldamised). Kood peab arvestama uuesti proovimise tsüklitega isegi ilma reaalsete konfliktideta. X86-l puudub natiivne LL/SC; CAS on riistvaraline primitiiv. X86-koodi puhul tuleb tarkvaras ABA-d vältida.

ABA parandamine: kolm lähenemisviisi

1. Versiooniloendurid (sildistatud pointerid)

Pakkige versiooniloendur samasse aatomsõnasse kui pointer. Iga edukas versiooniloendur suurendab loendurit. Isegi kui pointer naaseb oma algsele väärtusele, erineb loendur:

cpp

#include <atomic>
#include <cstdint>

struct TaggedPtr {
    uintptr_t ptr : 48;  // pointer (48-bit virtual address space)
    uintptr_t tag : 16;  // version counter
};

std::atomic<TaggedPtr> top;

bool cas_with_tag(std::atomic<TaggedPtr>& loc,
                  TaggedPtr expected,
                  void* new_ptr) {
    TaggedPtr desired = { (uintptr_t)new_ptr, expected.tag + 1 };
    return loc.compare_exchange_strong(expected, desired);
}

See on praktikas standardne lähenemisviis. 16-bitine silt rakendub pärast 65 536 operatsiooni, mis on teoreetiliselt ohtlik, kuid praktiliselt enamiku süsteemide jaoks piisav, seega on äärmiselt ebatõenäoline, et lõime ennetatakse täpselt 65 536 CAS-tsükli jooksul samas asukohas.

2. Ohumärgid

Igal lõimel on väike komplekt "ohuvihjeid", mis viitavad sõlmedele, millele see hetkel juurde pääseb. Enne mis tahes sõlme vabastamist kontrollib lõim kõiki ohuvihjete registreid, et veenduda, et ükski teine ​​lõim sellele juurde ei pääse. Ohuvihjes kuvatav sõlm lükatakse edasi, kuni see osuti tühjendatakse:

cpp

// Simplified hazard pointer pattern
thread_local void* hazard_ptr = nullptr;

void* safe_load(std::atomic<void*>& head) {
    void* ptr;
    do {
        ptr = head.load(std::memory_order_acquire);
        hazard_ptr = ptr;                          // announce we are using this
        // memory fence ensures announcement is visible before validation
        std::atomic_thread_fence(std::memory_order_seq_cst);
    } while (ptr != head.load(std::memory_order_acquire)); // validate still valid
    return ptr;
}

void safe_release() {
    hazard_ptr = nullptr;
}

Ohuvihjed takistavad ABA-d mälu taastamise tasandil: sõlme ei saa uuesti kasutada, kui mõni lõim hoiab sellele suunatud ohuvihjet. See nõuab kõigi lõimede ohuvihjete skannimist enne vabastamist, mis lisab lõimede arvuga proportsionaalset lisakoormust.

3. Epohipõhine taastamine (EBR)

Lõimed toimivad globaalselt jälgitavates "ajastutes". Erandiks olevad sõlmed puhverdatakse ajastu kohta ja vabastatakse alles siis, kui kõik lõimed on jõudnud kaugemale ajastust, mil sõlm aeglustati. EBR on lihtsam kasutada kui ohuindikaatorid ja sellel on madalam operatsioonipõhine üldkulu, kuid vaiksete perioodide ajal on mälumahu kasv piiratud, kuid ettearvamatu.

Java keeles AtomicStampedReference lahendab ABA probleemi otse, sidudes viite täisarvutempliga:

Java

import java.util.concurrent.atomic.AtomicStampedReference;

AtomicStampedReference<Node> top =
    new AtomicStampedReference<>(null, 0);

void push(Node newNode) {
    int[] stamp = new int[1];
    Node current;
    do {
        current = top.get(stamp);
        newNode.next = current;
    } while (!top.compareAndSet(current, newNode, stamp[0], stamp[0] + 1));
}

Lukustusvabade järjekordade rakendamine

Järjekorrad on kõige sagedamini vajalik lukuvaba struktuur. Kanooniline lukuvaba järjekord on Michael-Scotti järjekord, mis kasutab kahte pointerit (pea ja saba) ja valvursõlme, et võimaldada samaaegseid järjekorda lisamise ja järjekorrast eemaldamise toiminguid.

SPSC järjekord: maksimaalne jõudlus minimaalse sünkroniseerimisega

Ühe tootja ja ühe tarbija järjekord välistab igasuguse kirjutamis-kirjutamis- ja lugemis-lugemisvõistluse. Üks lõim kirjutab sabasse; teine ​​lõim loeb päisest. Tootja ja tarbija jagavad ainult päise pointerit:

cpp

#include <atomic>
#include <array>

template<typename T, size_t Capacity>
class SPSCQueue {
    std::array<T, Capacity> buffer;
    alignas(64) std::atomic<size_t> head{0}; // consumer reads head
    alignas(64) std::atomic<size_t> tail{0}; // producer writes tail
    // alignas(64) puts each on a separate cache line -- prevents false sharing

public:
    bool push(const T& item) {
        size_t t = tail.load(std::memory_order_relaxed);
        size_t next = (t + 1) % Capacity;
        if (next == head.load(std::memory_order_acquire))
            return false; // full
        buffer[t] = item;
        tail.store(next, std::memory_order_release);
        return true;
    }

    bool pop(T& item) {
        size_t h = head.load(std::memory_order_relaxed);
        if (h == tail.load(std::memory_order_acquire))
            return false; // empty
        item = buffer[h];
        head.store((h + 1) % Capacity, std::memory_order_release);
        return true;
    }
};

. alignas(64) Pea ja saba puhul on oluline eristada neid. Ilma selleta mahuvad mõlemad samale vahemälu reale. Iga saba kirjutamine käivitab vahemälu rea kehtetuks tunnistamise, mis on nähtav lugemispea jaoks, ja vastupidi, vale jagamise, mis serialiseerib toiminguid, mis peaksid olema sõltumatud.

MPMC järjekord: mitme tootjaga mitu tarbijat

Täielikult samaaegne MPMC järjekord on oluliselt keerulisem. Tootmisrakendustes kasutatakse tootjate ja tarbijate lukustamata koordineerimiseks järjekorranumbrit pesa kohta:

cpp

#include <atomic>
#include <array>

template<typename T, size_t Capacity>
class MPMCQueue {
    struct Slot {
        std::atomic<size_t> sequence;
        T data;
    };

    alignas(64) std::array<Slot, Capacity> slots;
    alignas(64) std::atomic<size_t> enqueue_pos{0};
    alignas(64) std::atomic<size_t> dequeue_pos{0};

public:
    MPMCQueue() {
        for (size_t i = 0; i < Capacity; ++i)
            slots[i].sequence.store(i, std::memory_order_relaxed);
    }

    bool push(const T& item) {
        size_t pos = enqueue_pos.fetch_add(1, std::memory_order_relaxed);
        Slot& slot = slots[pos % Capacity];
        size_t seq = slot.sequence.load(std::memory_order_acquire);
        // wait for the slot to be ready for writing
        while (seq != pos) {
            seq = slot.sequence.load(std::memory_order_acquire);
        }
        slot.data = item;
        slot.sequence.store(pos + 1, std::memory_order_release);
        return true;
    }

    bool pop(T& item) {
        size_t pos = dequeue_pos.fetch_add(1, std::memory_order_relaxed);
        Slot& slot = slots[pos % Capacity];
        size_t seq = slot.sequence.load(std::memory_order_acquire);
        while (seq != pos + 1) {
            seq = slot.sequence.load(std::memory_order_acquire);
        }
        item = slot.data;
        slot.sequence.store(pos + Capacity, std::memory_order_release);
        return true;
    }
};

.NET ConcurrentQueue: kuidas see sisemiselt töötab

.NET-id ConcurrentQueue<T> .NET 5+ kasutab segmenteeritud massiivistruktuuri. Iga segment on fikseeritud suurusega massiiv, mille pea- ja sabaindekseid hallatakse Interlocked toimingud (mis on seotud alusriistvara CAS-iga). Segmendid on omavahel ühendatud volatiilse _nextSegment pointer. Järjekorda lisamine lisab praegusele saba segmendile, suurendades segmendi ahelat, kui see on täis. Järjekorrast eemaldamine loeb peasegmendilt ja suurendab peaindeksit aatomiliselt.

Peamine disainiotsus on globaalse lukustuse vältimine. Tootjad konkureerivad ainult praeguse segmendi tagaindeksi pärast. Tarbijad konkureerivad ainult peaindeksi pärast. Ükski tootja ei konkureeri kunagi tarbijaga. See teeb... ConcurrentQueue<T> väga tõhus tootja-tarbija torujuhtmete jaoks:

csharp

using System.Collections.Concurrent;
using System.Threading;

// .NET ConcurrentQueue -- lock-free, thread-safe, FIFO
var queue = new ConcurrentQueue<int>();

// Producer thread
var producer = Task.Run(() => {
    for (int i = 0; i < 1_000_000; i++)
        queue.Enqueue(i);
});

// Consumer thread
var consumer = Task.Run(() => {
    long sum = 0;
    while (!queue.IsEmpty || !producer.IsCompleted) {
        if (queue.TryDequeue(out int item))
            sum += item;
        else
            Thread.SpinWait(1);  // brief spin before retry
    }
    return sum;
});

await Task.WhenAll(producer, consumer);

Vahemälu sidusus ja vale jagamine lukuvabas koodis

Vahemälu sidusus on nähtamatu jõudlusmuutuja lukustusvabades rakendustes. Kui tuum kirjutab mälupesasse, siis kogu seda asukohta sisaldav 64-baidine vahemälu rida kehtetuks tunnistatakse kõigi teiste tuumade vahemäludes. Enne lugemist peavad nad uuendatud rea hankima. Lukustusvabas koodis, kus toimuvad sagedased aatomivärskendused, võib see vahemälu rea kehtetuks tunnistamine muutuda domineerivaks kuluks.

Vale jagamine tekib siis, kui kaks lõime muudavad erinevaid muutujaid, mis juhtumisi jagavad vahemälu rida. Kumbki lõim ei pääse juurde samadele andmetele, kuid vahemälu koherentsusprotokoll käsitleb kogu vahemälu rida vastavalt vajadusele:

cpp

// BAD: head and tail on the same cache line
struct BadQueue {
    std::atomic<size_t> head;   // bytes 0-7
    std::atomic<size_t> tail;   // bytes 8-15
    // both fit in the same 64-byte cache line
    // producer writing tail invalidates head in consumer's cache
};

// GOOD: head and tail on separate cache lines
struct GoodQueue {
    alignas(64) std::atomic<size_t> head;
    alignas(64) std::atomic<size_t> tail;
    // each on its own cache line -- no false sharing
};

MESI protokoll (Modified, Exclusive, Shared, Invalid) kirjeldab, kuidas x86 protsessorid koordineerivad vahemälu rea omandiõigust. Kui tuum soovib kirjutada asukohta, mida ta jagab teiste tuumadega (jagatud olek), peab see saatma kirjutamistaotluse, ootama kõigi jagajate kinnitust ja lülituma muudetud olekusse. See edasi-tagasi teekond koherentsusprotokollini võtab mitme sokliga süsteemis 50–300+ tsüklit. Valejagamine muudab sõltumatud lõimekohalikud toimingud vahemälukoherentsusliikluseks, mis vähendab jõudlust, mis peaks tuumadega lineaarselt skaleeruma.

Vale jagamise tuvastamine: kasutage perf stat -e cache-misses,L1-dcache-load-misses Linuxis või Visual Studio protsessori jõudluse profiilija Windowsis. Suur L1-vahemälu möödalaskmiste määr mitmekeermelises programmis, mis vahemällu mahub, on tugev näitaja valest jagamisest.

Mälu järjestamine: miks memory_order_relaxed Ei ole alati piisav

C + + std::atomic operatsioonid paljastavad C++11 mälumudeli mälujärjestuse täieliku ulatuse. Vale järjestuse valimine on lukustamata koodis ABA probleemi järel teine ​​​​kõige levinum viga.

cpp

// The five memory orderings and when each applies:

// relaxed: no synchronization, only atomicity
// Use for: counters where only the final value matters
counter.fetch_add(1, std::memory_order_relaxed);

// acquire: reads see all writes by threads that released this location
// Use for: reading shared state protected by a flag
if (ready.load(std::memory_order_acquire)) {
    use(data); // guaranteed to see all writes made before ready was set
}

// release: writes are visible to threads that acquire this location
// Use for: publishing shared state
data = compute();
ready.store(true, std::memory_order_release);

// acq_rel: acquire + release in one operation
// Use for: read-modify-write operations like CAS in the middle of a chain
node.compare_exchange_strong(expected, desired,
    std::memory_order_acq_rel,   // success
    std::memory_order_acquire);  // failure

// seq_cst: total order across all seq_cst operations, all cores
// Use for: when you need a global consistent view (but slowest)
flag.store(true, std::memory_order_seq_cst);

Levinud viga: kasutamine relaxed väljalaskelipu jaoks. Lõim, mis määrab ready = true koos relaxed järjestamine ei garanteeri eelnevate kirjutuste toimumist data on nähtavad teistele teemadele, mis loevad readyOmandamise/väljaandmise paar loob kirjutaja ja lugeja ühendava enne-juhtumi suhte.

Treiber Stack: lukuvaba pinu C++-s

Treiberi pinu puhul on tegemist lihtsaima mittetriviaalse lukuvaba andmestruktuuriga. See kasutab CAS-tsüklit ühel top kursor:

cpp

#include <atomic>

template<typename T>
class TreiberStack {
    struct Node {
        T data;
        Node* next;
        explicit Node(T d) : data(std::move(d)), next(nullptr) {}
    };

    std::atomic<Node*> top{nullptr};

public:
    void push(T data) {
        Node* node = new Node(std::move(data));
        node->next = top.load(std::memory_order_relaxed);
        while (!top.compare_exchange_weak(
            node->next,          // expected -- updated on failure
            node,                // desired
            std::memory_order_release,
            std::memory_order_relaxed))
        { /* retry */ }
    }

    bool pop(T& result) {
        Node* node = top.load(std::memory_order_acquire);
        while (node) {
            if (top.compare_exchange_weak(
                node,
                node->next,      // new top
                std::memory_order_acquire,
                std::memory_order_relaxed))
            {
                result = std::move(node->data);
                // WARNING: cannot free node here safely without hazard pointers or EBR
                // delete node; -- ABA hazard if another thread reads node->next
                return true;
            }
        }
        return false; // empty
    }
};

Kommentaar teemal delete node on kriitiline: naiivne kustutamine on varem kirjeldatud ABA oht. Tootmiskeskkonnas olevas Treiberi pinus nõuab sõlme taastamine ohuviitasid, epohhipõhist taastamist või prügikoristust (Java/C# tegeleb sellega automaatselt).

Java lukuvabad andmestruktuurid

Java standardteek pakub tootmiskvaliteediga lukuvabasid implementatsioone java.util.concurrent:

klass	struktuur	Edu	märkused
AtomicReference<T>	Üksikväärtus	Lukustamata	CAS objektiviitel
AtomicStampedReference<T>	Väärtus + tempel	Lukustamata	ABA ennetamine versiooniloenduri abil
ConcurrentLinkedQueue<T>	Michael-Scotti järjekord	Lukustamata	FIFO, piiramatu
ConcurrentLinkedDeque<T>	Lukustamata deque	Lukustamata	Mõlemad otsad
LongAdder	Võidelda	Lukustamata	Triibuline, suure läbilaskevõimega loendamine

LongAdder väärib eraldi märkimist. Selle asemel, et üks aatomloendur konkureeriks kõigi lõimede vahel, haldab see triibulist loendurite massiivi, millele igaühele pääseb juurde lõimede alamhulk. Konkurents on jaotatud triipude vahel, mitte koondunud ühte kohta. Kogusumma summeeritakse laiskalt sum()Paljude lõimede vaheliste suure sagedusega juurdekasvutoimingute jaoks LongAdder dramaatiliselt edestab AtomicLong.incrementAndGet():

Java

import java.util.concurrent.atomic.LongAdder;

// BAD for high-concurrency counting: all threads contend on one location
AtomicLong counter = new AtomicLong(0);
counter.incrementAndGet(); // single CAS -- all threads collide

// GOOD for high-concurrency counting: contention distributed across stripes
LongAdder adder = new LongAdder();
adder.increment();  // updates thread-local stripe -- minimal contention
long total = adder.sum(); // sum all stripes lazily

Kuidas SMART TS XL Toetab lukuvaba süsteemi arendamist

Lukustusvaba kood on üks raskemini õigesti kirjutatavaid koode. Vead on mittedeterministlikud, esinevad ainult teatud vahelduste all ja sageli ainult suuremahulises tootmises. Staatiline analüüs lahendab selle probleemi, uurides koodi struktuurilisi omadusi enne käivitamist, selle asemel et oodata võidujooksu tingimuste ilmnemist.

SMART TS XL analüüsib samaaegse koodi täielikke teostusradasid, jälgides, kuidas aatomioperatsioonid on seotud nende valvatavate mälukohtadega. Süsteemide puhul, mis segavad lukuvaba koodi pärandkomponentide või mitmekeelsete arhitektuuridega, pakub see piiriülest nähtavust, mida ühekeelsed tööriistad ei suuda: kuidas lukuvaba C++ komponendi poolt ligipääsetav jagatud mälupiirkond on seotud Java teenusega, mis seda loeb, või kuidas samaaegne järjekord suunab andmeid COBOL-põhisesse töötlustorustikku.

. staatilise koodi analüüs võimekus tuvastab samaaegsuse ohtudega seotud mustreid: aatomkoormused ilma vastava hankimise semantikata, CAS-tsüklid, mis ei värskenda eeldatavat väärtust rikke korral, jagatud andmestruktuurid, kus erinevate lõimede poolt ligipääsetavad väljad asuvad koos ilma joonduspadjata. mõju analüüs Võimalus jälgib, millised allavoolu komponendid sõltuvad jagatud samaaegsest andmestruktuurist, nii et struktuuri liidese või taastamisstrateegia muudatusi saab enne muudatuse tegemist õigesti ulatusse seada.

Ettevõtte süsteemide puhul, kus lukuvabad komponendid peavad eksisteerima koos pärandpaketttöötluse, sõnumijärjekorra vahetarkvara ja kaasaegsete teeninduskihtidega, SMART TS XL'S sõltuvuse kaardistamine annab arhitektuurilise ülevaate sellest, kuidas samaaegsed andmeteed ühendavad erinevates keeltes kirjutatud komponente kogu süsteemipinus.

Kui lukuvaba süsteem on vale valik

Lukustusvaba struktuur ei ole alati parem kui mutex. Lukustusvaba struktuuri kasuks otsustamine sõltub töökoormuse tegelikust konkurentsiprofiilist. Madala lõimede arvu või konkurentsi korral on hästi rakendatud mutex kiirem, kuna see väldib aatomite uuesti proovimise tsüklite ja vahemälu rea kehtetuks tunnistamise üldkulu erinevatel tuumadel.

Kasutage mutexi, kui:

• Lõimede arv on madal (alla 4–8) või tüli on haruldane
• Kriitiline lõik on pikk ja keeruline (lukuvabad silmused muutuvad sektsiooniga võrreldes kallimaks)
• Õigsus on olulisem kui läbilaskevõime ja lukuga on algoritm lihtsam.
• Platvormil on tõhus futex-põhine lukustus (Linux pthread_mutex, Windowsi SRWLOCK)

Kasutage lukuvaba süsteemi järgmistel juhtudel:

• Lõimede arv on suur ja konkurents püsib
• Toimingud on lühikesed (CAS-tsükli üldkulu on toiminguga võrreldes väike)
• Blokeerimine on vastuvõetamatu (reaalajas lõimed, katkestuste käitlejad, signaalikäitlejad)
• Koostamine teiste lukuvabade struktuuridega, kus lukk tooks kaasa lukustusjärjekorra sõltuvusi

Kasutage ootamisvaba teenust, kui:

• Iga lõim peab lõpule jõudma piiratud aja jooksul, olenemata teistest lõimedest
• Reaalajas või ohutuskriitilised nõuded, mille puhul nälgimine on vastuvõetamatu
• Algoritmi saab struktureerida nii, et see toetaks piiratud sammuga lõpuleviimist iga lõime kohta

Lukustusvaba programmeerimise distsipliin ei seisne luku valimises kõikjal, vaid täpses valikus seal, kus selle omadused, blokeerimata edenemine, ummikseisu kõrvaldamine ja eelistuste taluvus vastavad süsteemi tegelikele nõuetele.