Threads, racecondities en vergrendelingen

Een thread is één uitvoeringsreeks binnen een proces. Meerdere threads kunnen aan dezelfde programmagegevens werken, maar elke thread heeft een eigen positie in de code en eigen onafgemaakte functieaanroepen nodig.

Wat wordt gedeeld en wat hoort bij een thread?

Threads in één proces delen code, globale en statische variabelen, heapobjecten, open bestandsdescriptoren en de proces-ID. Elke thread heeft een eigen programmateller, registers, stack en thread-ID. Een globale int total duidt één gedeeld object aan. Een gewone lokale int i in de werkthreadfunctie duidt bij elke aanroep een ander object aan.

Een proces met drie threads heeft drie stacks op verschillende adressen in dezelfde adresruimte. Een stack is geen beschermde afgeschermde ruimte: een andere thread kan een lokale variabele bereiken als die het adres ervan krijgt. Dat delen is alleen geldig zolang de variabele bestaat. Een pointer naar het beëindigde stackframe van een functie kan de variabele niet in leven houden. Grote lokale arrays en diepe recursie kunnen de stack van een thread ook uitputten.

Wisselen tussen threads

Het besturingssysteem slaat de uitvoeringstoestand van elke thread op in een threadbesturingsblok, of TCB. Wanneer het van T1 naar T2 wisselt, slaat het de registers van T1 op en herstelt het de registers van T2. De onafgemaakte berekening van T1 blijft in de opgeslagen registers staan totdat T1 weer draait.

Bij threads in hetzelfde proces blijft de adresruimte tijdens de wisseling gelijk. De paginatabellen hoeven niet te veranderen, wat deze wisseling meestal goedkoper maakt dan wisselen tussen processen. Gedeeld geheugen betekent ook gedeelde fouten: een schrijfbewerking via een ongeldige pointer kan de gegevens van een andere thread beschadigen en een fout die het proces beëindigt, beëindigt elke thread.

Waarom meerdere threads gebruiken?

Parallellisme betekent uitvoering op hetzelfde moment op verschillende processorkernen. Vier onafhankelijke delen van een berekening kunnen op vier kernen een bijna viervoudige versnelling bereiken, als gedeeld werk en coördinatie geen knelpunten worden. Met threads kan een programma ook wachten met werk laten overlappen: terwijl één thread wacht op een schijfleesbewerking of netwerkantwoord, kan een andere de CPU gebruiken.

Gelijktijdigheid betekent dat uitvoeringen gedurende overlappende perioden voortgang maken. Op één kern wisselt de scheduler tussen threads, zodat ze gelijktijdig actief zijn zonder parallel te draaien. Ook op één kern kunnen fouten door gelijktijdige uitvoering optreden: een wisseling kan een wijziging van gedeelde gegevens tussen de machine-instructies onderbreken.

Wie plant de threads in?

Linux en Windows gebruiken een een-op-een-model: elke gewone toepassingsthread komt overeen met een thread die door de kernel wordt ingepland. Verschillende threads kunnen op verschillende kernen draaien en een blokkerende aanroep blokkeert de aanroepende thread. Een veel-op-een-bibliotheek plant meerdere gebruikersthreads op één kernelthread in. De wisselingen kunnen goedkoop zijn, maar de bibliotheek kan die threads niet op meerdere kernen laten draaien en een blokkerende systeemaanroep kan de hele groep stoppen.

Als je A vóór B aanmaakt, is dat geen garantie dat A als eerste draait. Als A “A” print en B “B” print, kan zowel “AB” als “BA” verschijnen. De aanmaakvolgorde bepaalt wanneer een thread beschikbaar komt om te draaien; de scheduler kiest wanneer die wordt uitgevoerd.

De interface voor POSIX-threads, of pthreads, start een C-functie in een andere thread. Neem <pthread.h> op en bouw met een commando zoals gcc -pthread -o sum sum.c. De optie -pthread levert de compiler- en linkerinstellingen voor code met threads.

Maak een thread met stabiele argumenten

De aanroep pthread_create(&t, NULL, worker, arg) slaat een thread-ID op in t en start worker(arg). De attribuutpointer NULL vraagt om standaardwaarden. Een werkthreadfunctie heeft de signatuur void *worker(void *arg): het argument en de retourwaarde zijn pointers. Met een struct kan die ene pointer meerdere velden doorgeven.

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

struct range { int lo, hi; long result; };

void *sum_range(void *arg) {
    struct range *r = arg;
    long sum = 0;
    for (int n = r->lo; n <= r->hi; n++)
        sum += n;
    r->result = sum;
    return NULL;
}

De aanmakende thread bereidt twee structs voor, {1, 50, 0} en {51, 100, 0}, en geeft aan elke werkthread een ander adres door. Houd beide structs in leven totdat de werkthreads klaar zijn. Elke werkthread telt op in zijn eigen lokale sum en schrijft alleen naar zijn eigen veld result.

pthread_create geeft bij succes 0 terug en bij een fout een foutnummer. Controleer dat teruggegeven nummer rechtstreeks; de functie stelt errno niet in om de fout te melden. Alleen een geslaagde aanmaak levert een thread op waarop je met join kunt wachten.

Wacht met join voordat je resultaten leest

Nadat beide werkthreads met succes zijn aangemaakt, roept de hoofdthread pthread_join(t[0], NULL) en pthread_join(t[1], NULL) aan. Een join blokkeert totdat de opgegeven thread eindigt. Een geslaagde join maakt de schrijfbewerkingen van die werkthread ook zichtbaar voor de wachtende thread. De hoofdthread kan dan 1.275 en 3.775 lezen en optellen tot 5.050 zonder mutex: de werkthreads schreven naar afzonderlijke objecten en de hoofdthread wachtte voordat die ze las.

Als je beide threads start voordat je met join wacht, kan hun werk overlappen. Als je één werkthread aanmaakt en direct met join wacht voordat je de volgende aanmaakt, draaien de werkthreads na elkaar.

Hier is het hoofdprogramma. Het stopt bij een pthread-fout en gebruikt daardoor nooit een ID van een mislukte aanmaak:

static void require_success(int rc) {
    if (rc != 0) {
        fprintf(stderr, "pthread error: %d\n", rc);
        exit(EXIT_FAILURE);
    }
}

int main(void) {
    struct range jobs[2] = {{1, 50, 0}, {51, 100, 0}};
    pthread_t threads[2];
    for (int i = 0; i < 2; i++)
        require_success(pthread_create(&threads[i], NULL,
                                      sum_range, &jobs[i]));
    for (int i = 0; i < 2; i++)
        require_success(pthread_join(threads[i], NULL));
    printf("%ld\n", jobs[0].result + jobs[1].result);
    return 0;
}

Om een teruggegeven pointer te verzamelen, geef je het adres door waarop die moet worden opgeslagen: void *answer; pthread_join(t, &answer);. De pointer moet verwijzen naar opslag die langer bestaat dan de werkthread, zoals toegewezen heapgeheugen of een struct van de aanmakende thread. &local_result teruggeven vanuit de werkthread is ongeldig, omdat de lokale variabele ophoudt te bestaan wanneer de functie terugkeert.

Voorkom dat je een veranderende lusvariabele deelt

Als je in een aanmaaklus &i aan elke werkthread doorgeeft, geef je steeds hetzelfde adres door. Werkthreads kunnen dat lezen nadat de lus de waarde heeft gewijzigd, zodat meerdere threads ogenschijnlijk dezelfde ID krijgen. Gebruik in plaats daarvan een array: wijs ids[i] = i toe, geef &ids[i] door en houd de array in leven en ongewijzigd totdat alle join-aanroepen zijn voltooid.

Beëindig threads en processen bewust

Terugkeren uit main of exit() aanroepen in een willekeurige thread beëindigt het hele proces en kan werkthreads afbreken. De hoofdthread wacht normaal met join op werkthreads voordat die terugkeert. pthread_exit() aanroepen beëindigt alleen de aanroepende thread; andere threads kunnen doorgaan.

Een losgekoppelde thread geeft zijn threadbronnen automatisch vrij wanneer die eindigt en kan niet met join worden afgewacht. Zorg dat op elke thread waarop met join kan worden gewacht één keer met join wordt gewacht of dat die wordt losgekoppeld. Join wacht op voltooiing; het beschermt geen twee werkthreads die hetzelfde object wijzigen terwijl ze allebei draaien.

De instructie counter++ lijkt klein, maar een gewone verhoging van een gedeeld geheel getal is geen ondeelbare bewerking. Meestal wordt een waarde geladen, in een register verhoogd en wordt het resultaat opgeslagen. Tussen die stappen kan een andere thread draaien.

Een uitvoeringsverloop waarbij een verhoging verloren gaat

Begin met counter gelijk aan 50. Beschouw laden, optellen en opslaan als afzonderlijke machinestappen:

Twee verhogingen hadden 52 moeten opleveren. T1 overschrijft in plaats daarvan het resultaat van T2 met een waarde die is berekend uit de eerdere waarde 50. Dit is een verloren wijziging.

Een contextwisseling bewaart de registers van T1 in zijn TCB. Wanneer T1 verdergaat, bevat zijn register nog steeds 51; de thread laadt de gedeelde teller niet opnieuw alleen omdat T2 heeft gedraaid. De fout zit in de onbeschermde reeks, niet in het herstellen van een verkeerd register door de scheduler.

Vergelijk met een sequentiële uitvoering

Als T1 alle drie de stappen voltooit voordat T2 laadt, slaat T1 51 op en slaat T2 daarna 52 op. Als de volledige threads in omgekeerde volgorde draaien, geeft dat ook 52. Het resultaat 51 van de vervlochten uitvoering kan bij geen van beide sequentiële volgordes ontstaan. Om dit soort fouten te vinden, markeer je een leesbewerking, plaats je daarna een schrijfbewerking van een andere thread en hervat je de berekening van de eerste thread met de verouderde waarde.

Dit verloop is een model van de fout op machineniveau. In daadwerkelijke C-code vormen niet-gesynchroniseerde conflicterende toegangen tot een gewoon gedeeld geheel getal een datarace, die tot ongedefinieerd gedrag leidt. C beperkt dat programma niet tot de resultaten van een eenvoudig model van vervlochten instructies.

Waarom geslaagde tests weinig bewijzen

Twee threads die elk 10.000.000 verhogingen uitvoeren, moeten 20.000.000 opleveren. Experimentele uitvoeringen zonder bescherming kunnen verschillende kleinere totalen printen, zoals 19.345.221 en 19.221.041 in gepubliceerde voorbeelden. Een goed ogende uitvoering betekent alleen dat het waargenomen resultaat toevallig aanvaardbaar was.

De kwetsbare periode kan maar enkele instructies breed zijn. Een ander aantal kernen, andere compilerkeuzes of een andere systeembelasting kunnen een uitvoeringsvolgorde blootleggen die duizenden eerdere uitvoeringen misten. Als twee threads in het model elk één verhoging vanaf nul uitvoeren, staat het model 1 of 2 toe. Bij minstens twee verhogingen per thread kunnen zeldzame uitvoeringsvolgordes een totaal van slechts 2 opleveren, ook als het aantal bedoelde verhogingen groeit.

Herstel de bewerking, niet het uiterlijk ervan

Het gehele getal als volatile declareren maakt het laden, optellen en opslaan niet ondeelbaar en synchroniseert threads niet. Al het werk op één regel schrijven verandert niets. Zelfs een x86-instructie die rechtstreeks bij geheugen optelt, heeft de juiste atomaire vorm nodig om tussen kernen te coördineren.

Bescherm de volledige reeks lezen-wijzigen-schrijven met een gedeelde mutex of gebruik een atomaire C11-bewerking voor lezen-wijzigen-schrijven, zoals atomic_fetch_add. Op één kern is dat ook nodig: een timer kan een wisseling veroorzaken tussen het laden en opslaan, ook zonder parallelle uitvoering.

Een fout door gelijktijdige uitvoering kan één geheugentoegang of een hele bedrijfsregel betreffen. Bepaal zowel welke objecten worden gedeeld als welke bewerking voor andere threads ondeelbaar moet lijken.

Raceconditie of datarace?

Een raceconditie ontstaat wanneer de juistheid afhangt van de relatieve timing. Een datarace ontstaat wanneer verschillende threads zonder synchronisatie dezelfde geheugenlocatie benaderen, minstens één thread erin schrijft en minstens één toegang niet-atomair is. C11 en C++11 kennen aan een datarace ongedefinieerd gedrag toe.

Atomaire toegang kan een datarace voorkomen terwijl een grotere bewerking nog steeds een raceconditie heeft. Afzonderlijk beschermde lees- en schrijfbewerkingen houden bijvoorbeeld een beslissing tussen die bewerkingen niet geldig. Twee threads kunnen elk een toereikend saldo lezen, de vergrendeling vrijgeven en later op basis van die verouderde beslissing geld opnemen.

Werk een opname uit

Een saldo begint op 100. Twee threads vragen elk om 80. De regel is dat een opname alleen wordt toegestaan als het saldo toereikend is.

1. T1 controleert 100 en besluit dat de opname kan slagen.
2. T2 controleert ook 100 en neemt dezelfde beslissing.
3. T1 trekt 80 af, zodat 20 overblijft.
4. T2 handelt op basis van de eerdere beslissing en trekt 80 van 20 af, zodat −60 overblijft.

Alleen de aftrekking beschermen herstelt die reeks niet. Bescherm de controle en de aftrekking met dezelfde vergrendeling, die je onafgebroken vasthoudt. Dan laat één thread 20 over en controleert de volgende thread 20 en weigert de opname. Bij een andere onbeschermde uitvoeringsvolgorde kan een aftrekking verloren gaan en 20 overblijven nadat beide opnames zijn uitbetaald, wat ook onjuist is.

Zoek de kritieke sectie

Een kritieke sectie is het gebied met gedeelde gegevens dat concurrerende toegang moet uitsluiten. Een reeks lezen-wijzigen-schrijven leest eerst gegevens, berekent een nieuwe waarde en schrijft die terug. Een reeks controleren en vervolgens handelen beslist of een handeling is toegestaan en voert die daarna uit. Lijstbewerkingen, uitgestelde initialisatie en het aanmaken van bestanden kunnen deze patronen ook bevatten.

Een vergrendeling biedt wederzijdse uitsluiting: hoogstens één deelnemende thread bevindt zich tegelijk in het beschermde gebied. Een atomaire bewerking lijkt voor andere deelnemende threads één volledige bewerking; ze kunnen geen half voltooide toestand waarnemen. Een mutex biedt dat beeld alleen voor code die dezelfde vergrendelingsafspraak volgt.

Niet elk object heeft een vergrendeling nodig. Gegevens die door één thread worden benaderd, blijven privé tenzij hun adres wordt gedeeld. Gegevens die volledig zijn geïnitialiseerd voordat werkthreads starten en daarna alleen worden gelezen, kunnen zonder vergrendeling worden gedeeld. Beoordeel wie een object kan bereiken en of schrijfbewerkingen met het gebruik ervan overlappen, niet alleen waar het is gedeclareerd.

Wat een correcte oplossing belooft

• Wederzijdse uitsluiting: concurrerende threads kunnen niet samen naar binnen.
• Voortgang: wanneer de sectie vrij is en threads naar binnen willen, kunnen threads die niet naar binnen proberen te gaan de keuze van een thread die naar binnen mag niet voor onbepaalde tijd uitstellen.
• Begrensd wachten: na een verzoek bestaat er een grens aan het aantal keren dat concurrerende threads eerder naar binnen kunnen.

De C11-bewerking atomic_fetch_add(&count, 1) voert één atomaire wijziging uit op een atomic_int. Atomiciteit is gegarandeerd, ook op een platform dat de bewerking met een interne bibliotheekvergrendeling implementeert. Twee rekeningvelden afzonderlijk atomair maken verandert een overboeking ertussen nog steeds niet in één atomaire transactie; ook de samenhang tussen de velden heeft bescherming nodig.

Een mutex is een vergrendeling waarmee één thread tegelijk eigenaar van een beschermd gebied kan zijn. Een thread verkrijgt de mutex voordat die beschermde gegevens benadert en geeft die daarna vrij. Als een andere thread de mutex houdt, wacht een blokkerende vergrendelingsaanroep.

Initialiseer de gedeelde mutex

Gebruik pthread_mutex_t uit <pthread.h>. Een statische mutex kan beginnen met pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;. Een dynamisch aangemaakt object kan zijn veld initialiseren met pthread_mutex_init(&obj->lock, NULL). De initialisatie moet voltooid zijn voordat een thread de mutex gebruikt.

Hier is een tellerbewerking met een statisch geïnitialiseerde gedeelde mutex. De hulpfunctie controleert de pthread-retourwaarden, die rechtstreeks foutnummers zijn:

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

static pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
static long counter = 0;  // guarded by m

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

void increment(void) {
    check(pthread_mutex_lock(&m));
    counter = counter + 1;
    check(pthread_mutex_unlock(&m));
}

Elke gelijktijdige leesbewerking of wijziging van counter moet dezelfde regel volgen. Een afzonderlijke functie die een andere mutex gebruikt, zou niet met increment coördineren.

Wat gebeurt er terwijl de mutex wordt vastgehouden?

T1 vergrendelt m, laadt de teller, rekent en slaat op. Als T2 in die periode pthread_mutex_lock(&m) aanroept, kan die pas voorbij de aanroep zodra T2 het eigenaarschap verkrijgt nadat T1 de mutex heeft vrijgegeven. T1 kan nog steeds worden onderbroken: een mutex voorkomt dat concurrerende threads naar binnen gaan, geen contextwisselingen.

Houd voor de saldoregel de mutex vast voordat je balance >= amount beoordeelt. Trek alleen af als de controle slaagt, leg succes of mislukking vast en ontgrendel dan. Bij een saldo van 100 en twee verzoeken om 80 slaagt er precies één en blijft 20 over.

Kies hoe je wacht

pthread_mutex_trylock(&m) keert direct terug: 0 betekent dat de aanroepende thread de mutex heeft verkregen; EBUSY betekent dat dit niet is gelukt omdat de mutex bezet was. Bij een bezette mutex kan de thread ander werk doen en mag die de beschermde gegevens niet benaderen. pthread_mutex_timedlock wacht tot een absolute deadline. Ook bij deze interfaces moet je retourcodes controleren en een vergrendeling alleen vrijgeven nadat die met succes is verkregen.

Respecteer eigenaarschap en levensduur

De thread die eigenaar is, geeft een mutex vrij. Een normale niet-recursieve mutex blokkeert als de eigenaar die opnieuw probeert te vergrendelen. Een mutex met foutcontrole meldt fouten zoals opnieuw vergrendelen met EDEADLK of ontgrendelen door een andere thread dan de eigenaar met EPERM. Een recursieve mutex telt herhaalde verkrijgingen door de eigenaar en vereist evenveel vrijgaven. Vertrouw er niet op dat een standaardmutex verkeerd gebruik meldt: het gedrag hangt af van het type waaraan de implementatie die koppelt en van de bewerking.

Wanneer alle threads de mutex niet meer gebruiken en die ontgrendeld is, roep je pthread_mutex_destroy aan. Een object vernietigen of vrijgeven terwijl een andere thread het nog kan vergrendelen, schendt de levensduur van de mutex. Door de mutex via een pointer door te geven blijft de identiteit behouden; kopiëren maakt geen andere geldige verwijzing naar dezelfde vergrendeling.

Vergrendelingsgranulariteit is de hoeveelheid gedeelde toestand die door één vergrendeling wordt beschermd. Die bepaalt welke bewerkingen op elkaar moeten wachten, ook wanneer ze op verschillende kernen draaien.

Eén grote vergrendeling of meerdere kleinere?

Een grofmazig ontwerp gebruikt één mutex voor een hele structuur of een heel subsysteem. Het heeft een eenvoudige beschermingsregel, maar niet-gerelateerde bewerkingen worden na elkaar uitgevoerd. Een fijnmazig ontwerp wijst afzonderlijke mutexen toe aan afzonderlijke rekeningen, buckets of gebieden. Threads kunnen dan tegelijk in verschillende gebieden werken, ten koste van meer vergrendelingsbewerkingen en ingewikkeldere regels.

Plaats de vergrendeling naast de toestand die die beschermt:

struct account {
    pthread_mutex_t lock;
    long balance;
    unsigned id;
};

Een bewerking op één rekening verkrijgt de bijbehorende mutex. Een overboeking tussen twee verschillende rekeningen heeft beide mutexen nodig, omdat die de relatie tussen de rekeningen verandert. Kies een vaste volgorde, bijvoorbeeld op oplopende rekening-ID, en gebruik die op elk pad. Anders kan één thread A vasthouden en op B wachten terwijl een andere B vasthoudt en op A wacht.

Een vergrendeling stelt een bovengrens aan de doorvoer

Stel dat elke bewerking één globale vergrendeling 2 µs vasthoudt. Het beschermde werk kan hoogstens één bewerking per 2 µs voltooien:

Door kernen toe te voegen kunnen geen twee bewerkingen dezelfde mutex tegelijk vasthouden. Overhead van de vergrendeling en ander werk kunnen de werkelijk behaalde snelheid verder verlagen. De duur van het beschermde werk is daarom een nuttige grens om te berekenen voordat je versnelling verwacht.

Verkort de sectie zonder de bewerking te verstoren

Bereid privéwerk voor voordat je de mutex verkrijgt. Wijs bij het invoegen in een lijst eerst de nieuwe knoop toe en vul de sleutel ervan in. Verkrijg de lijstmutex pas om de huidige kop te lezen en de knoop te koppelen. Als de toewijzing mislukt, gebeurt dat dan zonder dat een vergrendeling wordt vastgehouden.

Trage I/O, printen of een onbekende callback kan alle wachtende threads laten vastlopen. Verplaats zulk werk naar buiten als de gegevens daar geldig kunnen blijven. Houd een beslissing en de wijziging die ervan afhangt bij elkaar: als je een opname verkort door tussen de saldocontrole en de aftrekking te ontgrendelen, is de uitkomst niet meer correct.

Beoordeel drie verschillende eigenschappen

Bij wederzijdse uitsluiting vraag je of het ontwerp conflicterende toegang echt voorkomt. Bij eerlijkheid vraag je of een wachtende thread uiteindelijk aan de beurt komt of kan uithongeren. Bij prestaties vraag je wat de vergrendeling kost met één thread, meerdere threads op één CPU en threads op meerdere CPU's. Een vergrendeling kan correct zijn en toch oneerlijk of traag.

Concurrentie om een vergrendeling ontstaat wanneer threads wedijveren om een vergrendeling die al wordt vastgehouden. Bij zware concurrentie verplaatsen ze ook gedeelde cachelijnen met de vergrendeling en gegevens tussen kernen. In een gepubliceerd tellerexperiment duurde een miljoen wijzigingen door één thread ongeveer 0,03 s, maar een miljoen wijzigingen per thread door twee threads meer dan 5 s; dit zijn metingen van die opstelling, geen universele tijden.

Houd voor een schaalbaarheidsexperiment het werk per thread gelijk. Bij ideale schaalbaarheid doen N threads op N kernen N keer zoveel werk in de oorspronkelijke tijd. Begin met een eenvoudige correcte structuur, meet de wachttijd en totale tijd en splits een vergrendeling alleen op waar de extra gelijktijdigheid de extra overhead goedmaakt.

Een mutex kan perfect zijn geïmplementeerd terwijl een programma die toch verkeerd gebruikt. Controleer het hele pad door een functie, inclusief leesbewerkingen, fouten, callbacks en de vernietiging van objecten.

Geef eigenaarschap vrij op elk afsluitpad

Deze functie laat de vergrendeling op het foutpad vastgehouden:

pthread_mutex_lock(&m);
if (failed) return -1;
update_shared_state();
pthread_mutex_unlock(&m);

De terugkerende thread kan eindigen, maar de mutex blijft vergrendeld. Een latere aanroepende thread wacht dan op een vrijgave die nooit zal plaatsvinden. Gebruik één opruimpad of plaats vóór elke terugkeer een ontgrendeling. Met gecontroleerde pthread-aanroepen kan de structuur zo zijn:

int rc = -1;
check(pthread_mutex_lock(&m));
if (!failed) {
    update_shared_state();
    rc = 0;
}
check(pthread_mutex_unlock(&m));
return rc;

Eén vrijgavepunt controleren is eenvoudiger dan veel verspreide punten controleren. Het gaat erom dat elke met succes verkregen vergrendeling op elk normaal afsluitpad wordt vrijgegeven.

Volg de beschermingsregel ook bij lezen

Een statusfunctie die “alleen leest” kan een raceconditie met een wijzigende thread hebben. Die kan ook samenhangende velden in verschillende stadia van één wijziging waarnemen. Als een lijstbewerking een knoop publiceert voordat de velden ervan volledig zijn ingevuld, kan een onbeschermde lezer een pointer naar onvoltooide gegevens volgen. Verkrijg de vastgelegde vergrendeling voor elke toegang waarvan de juistheid daarvan afhangt.

Verschillende mutexen voor hetzelfde object gebruiken helpt niet. Als T1 lockA verkrijgt en T2 lockB, kunnen beide verkrijgingen slagen. Een mutex die in elke werkthread als nieuwe lokale variabele wordt gedeclareerd, maakt deze fout gemakkelijk te missen: elke thread vergrendelt zijn eigen object, dus er is geen gezamenlijke uitsluiting.

Behoud zowel de identiteit als de grenzen van de bewerking

Je kunt een pthread_mutex_t niet door toewijzing of door het kopiëren van de struct waarin die staat kopiëren en vervolgens als tweede handle voor de mutex gebruiken. Gebruik van de kopie leidt tot ongedefinieerd gedrag. Geef een pointer naar de oorspronkelijke gedeelde mutex door.

Controleer ook waar vrijgaven plaatsvinden. Een functie die vergrendelt om een saldo te controleren, ontgrendelt en later opnieuw vergrendelt om af te trekken, heeft afzonderlijke toegangen beschermd maar de beslissing laten verouderen. Houd de volledige reeks controleren en vervolgens handelen onder onafgebroken eigenaarschap.

Voorkom dat je op jezelf wacht

Onbekende code aanroepen terwijl je een mutex vasthoudt, kan onverwacht opnieuw toegang tot hetzelfde beschermde object proberen te krijgen. Bij een normale mutex blokkeert een tweede vergrendelingsaanroep door de eigenaar die eigenaar. Een mutex met foutcontrole meldt deze fout, terwijl een recursieve mutex genest eigenaarschap toestaat en bijpassende ontgrendelingen nodig heeft. Kies bewust een type; gebruik recursie niet om een onduidelijk beschermingsontwerp te verbergen.

Houd trage I/O en slapen waar mogelijk buiten een gedeelde kritieke sectie. Controleer voordat je de mutex vernietigt of het object met de mutex vrijgeeft dat geen thread eigenaar is of de mutex opnieuw kan benaderen. Initialisatie, gebruik en vernietiging moeten een duidelijke volgorde hebben.

Gebruik runtimehulpmiddelen om waargenomen fouten bloot te leggen

ThreadSanitizer, ingeschakeld met -fsanitize=thread, en Helgrind van Valgrind kunnen dataraces en verkeerd gebruik van vergrendelingen melden in uitvoeringen die ze waarnemen. Combineer hun meldingen met een controle van gedeelde toegangen en mogelijke vervlechtingen. Een uitvoering zonder meldingen stelt vast dat het hulpmiddel in die uitvoeringen geen probleem vond; over een ongetest pad moet je nog steeds redeneren.

Een vergrendeling heeft een betrouwbare manier nodig om één eigenaar te kiezen. Een gewone leesbewerking gevolgd door een gewone schrijfbewerking laat een tussenruimte in die beslissing, ook als het beschermde werk zelf heel kort is.

Interrupts regelen heeft een beperkte rol

Op één CPU kan een kernel interrupts kort uitschakelen rond een niet-blokkerende kritieke sectie om te voorkomen dat die daar door een interrupt wordt onderbroken. Dit berust erop dat de thread op de CPU blijft zonder vrijwillig te blokkeren of te wisselen. De kernel gebruikt deze techniek voor korte interne bewerkingen.

Het is geen algemene toepassingsmutex. Instructies om interrupts te regelen zijn geprivilegieerd; als een toepassing ze onbeperkt mocht gebruiken, zou die de CPU kunnen monopoliseren. Interrupts op één kern uitschakelen houdt andere kernen niet tegen om dezelfde gegevens te benaderen. Lang uitschakelen vertraagt ook de afhandeling van interrupts en kan op sommige apparaten tot verloren gebeurtenissen leiden.

Volg de ondeugdelijke vergrendeling met een vlag

Bekijk deze C-achtige pseudocode:

while (flag == 1) { }
flag = 1;
// critical section
flag = 0;

Begin met flag op 0. T1 test de vlag en verlaat de lus, maar pauzeert vóór de toewijzing. T2 test dezelfde 0, stelt de vlag in op 1 en gaat naar binnen. T1 gaat verder, stelt de vlag in op 1 en gaat ook naar binnen. Beide kwamen door de test voordat een van beide eigenaarschap opeiste.

Als je het lezen en schrijven afzonderlijk atomair maakt, verdwijnt een datarace op de vlag, maar blijven er in dit protocol nog steeds twee afzonderlijke bewerkingen over. Het opeisen van eigenaarschap vereist een atomaire bewerking voor lezen-wijzigen-schrijven of een vollediger synchronisatiealgoritme.

De lege lus is actief wachten: herhaaldelijk controleren terwijl CPU-tijd wordt verbruikt. Op één CPU kan een wachtende thread die actief wacht nadat die de eigenaar heeft onderbroken, de eigenaar niet sneller laten vrijgeven. De wachtende thread moet de eigenaar uiteindelijk laten draaien.

De oplossing van Peterson voor twee threads

Het algoritme van Peterson coördineert twee threads met een belangstellingsvlag per thread en een gedeelde beurt. Thread i voert uit:

flag[i] = 1;
turn = 1 - i;
while (flag[1 - i] == 1 && turn == 1 - i) { }
// critical section
flag[i] = 0;

De thread meldt belangstelling, geeft de andere thread bij gelijke aanspraak voorrang en wacht alleen zolang de andere belangstelling heeft en voorrang heeft. Onder sequentiële consistentie behouden de bewerkingen van elke thread hun programmavolgorde en zien alle threads één gemeenschappelijke volgorde. In dat model biedt het algoritme van Peterson wederzijdse uitsluiting, voortgang en begrensd wachten voor twee threads.

Ook de geheugenvolgorde is belangrijk

Moderne processors en compilers kunnen geheugenbewerkingen zichtbaar laten worden in een andere volgorde dan in de broncode. Een opslagbewerking kan in een buffer blijven staan terwijl een latere laadbewerking geheugen leest. Beide threads kunnen dan de belangstellingsvlag van de andere als 0 zien en allebei naar binnen gaan. Gewone gedeelde gehele getallen in C veroorzaken bovendien dataraces volgens C.

Een geldige implementatie heeft geschikte atomaire bewerkingen en ordening nodig, zoals sequentieel consistente atomaire C11-bewerkingen voor de vlaggen en de beurt. volatile biedt die synchronisatie niet. Praktische vergrendelingen combineren een ondeelbare eigendomsbewerking met garanties voor geheugenordening, zodat beschermde toegangen aan de juiste kant van verkrijgen en vrijgeven blijven.

Een atomaire bewerking voor lezen-wijzigen-schrijven combineert het lezen en bijwerken van een locatie tot één ondeelbare handeling. Daarmee wordt de tussenruimte gesloten waardoor twee threads samen door een gewone vlagtest kunnen komen.

Wissel de vlag uit en bekijk de oude waarde

Test-and-set, of atomaire uitwisseling, schrijft een nieuwe waarde en geeft de oude terug. Als een vlag op 0 begint, wisselt T1 die uit voor 1 en ontvangt 0, zodat T1 naar binnen gaat. T2 wisselt de vlag uit voor 1 en ontvangt 1, zodat T2 wacht. Totdat de vrijgave 0 schrijft, kan geen andere uitwisseling 0 teruggeven.

Hier is een C11-spinlock met de standaard sequentieel consistente atomaire bewerkingen:

#include <stdatomic.h>

static atomic_flag held = ATOMIC_FLAG_INIT;

void lock(void) {
    while (atomic_flag_test_and_set(&held)) { }
}

void unlock(void) {
    atomic_flag_clear(&held);
}

De ordening is net zo belangrijk als de vlag. Verkrijging moet ervoor zorgen dat latere toegangen binnen de kritieke sectie na de geslaagde verkrijging blijven; vrijgave moet ervoor zorgen dat eerdere toegangen binnen de kritieke sectie vóór de vrijgave blijven. Ook het wissen van de vlag moet atomair zijn; gewone opslagbewerkingen mengen met atomaire toegang implementeert deze overdracht niet.

Vergelijk vóór je vervangt

Compare-and-swap, of CAS, verandert een waarde alleen als die gelijk is aan een verwachte waarde. Stel dat twee threads een teller op 7 lezen en elk 1 willen optellen. T2 verandert 7 met succes in 8. De poging van T1 om 7 in 8 te veranderen mislukt nu, dus probeert T1 het opnieuw vanaf 8 en verandert die waarde in 9. Door opnieuw te proberen blijven beide verhogingen behouden.

atomic_compare_exchange_strong van C11 geeft succes of mislukking terug en werkt bij mislukking het argument met de verwachte waarde bij. Sommige hardwareachtige pseudocode geeft in plaats daarvan de oude opgeslagen waarde terug. Controleer welke afspraak een uitgewerkt verloop gebruikt. Op x86 implementeert xchg met een geheugenoperand uitwisseling, terwijl lock cmpxchg atomaire vergelijking en uitwisseling biedt.

Andere hardwarebouwstenen

Load-linked/store-conditional, of LL/SC, leest terwijl een reservering wordt vastgelegd en probeert daarna te schrijven. De voorwaardelijke schrijfbewerking mislukt als een andere schrijfbewerking de reservering ongeldig heeft gemaakt; die kan ook om andere redenen mislukken en hoort daarom in een lus die het opnieuw probeert. LDXR/STXR van ARM en lr/sc van RISC-V ondersteunen dit patroon.

Fetch-and-add telt atomair op en geeft de oude waarde terug. C11 biedt dit als atomic_fetch_add; x86 biedt lock xadd. Doordat de oude waarde wordt teruggegeven, is de bewerking bruikbaar om unieke ticketnummers uit te delen.

C garandeert het atomaire gedrag van zijn atomaire bibliotheekbewerkingen. De taal vereist niet dat elk atomair type vergrendelingsvrij is; sommige bewerkingen gebruiken een interne bibliotheekvergrendeling. Voor atomic_flag is vergrendelingsvrijheid gegarandeerd en atomic_is_lock_free controleert andere objecten.

Correct betekent niet eerlijk of snel

Een vergrendeling met test-and-set biedt wederzijdse uitsluiting, maar geen volgorde van binnenkomst: een thread kan na vrijgave herhaaldelijk de race verliezen en uithongeren. Op één CPU kunnen vier threads met round-robintijdschijven van 10 ms in drie wachtende threads 30 ms verspillen aan actief wachten voordat de onderbroken eigenaar weer draait. Op meerdere kernen, met een draaiende eigenaar en korte secties, kan kort actief wachten de overhead van slapen en wekken voorkomen.

Een vergrendeling met test-and-set onthoudt of die bezet is, maar niet wie heeft gewacht. Een ticketvergrendeling voegt een volgorde van binnenkomst toe met een atomaire ticketuitgever en een beurtteller.

Neem een nummer en wacht erop

Beide tellers beginnen op 0. Elke aanroepende thread verhoogt ticket atomair en bewaart de oude waarde als mine. De thread gaat pas naar binnen wanneer turn gelijk is aan mine. De eigenaar geeft de vergrendeling vrij door turn één keer te verhogen.

#include <stdatomic.h>

static atomic_uint ticket = 0;
static atomic_uint turn = 0;

void lock(void) {
    unsigned mine = atomic_fetch_add(&ticket, 1);
    while (atomic_load(&turn) != mine) { }
}

void unlock(void) {
    atomic_fetch_add(&turn, 1);
}

Deze standaard atomaire C11-bewerkingen bieden zowel atomiciteit als sequentieel consistente ordening. Elke aanroepende thread bewaart mine in zijn eigen lokale variabele. De gedeelde ticketteller geeft unieke nog geldige nummers uit.

Volg drie aankomsten

A neemt ticket 0 en gaat naar binnen omdat turn 0 is. B neemt ticket 1 en wacht. C neemt ticket 2 en wacht. Het volgende ongebruikte ticket is nu 3, terwijl de huidige beurt nog steeds 0 is.

Wanneer A vrijgeeft, wordt turn 1, dus gaat B naar binnen. C wacht nog steeds op 2. Door de vrijgave van B gaat turn naar 2 en gaat C naar binnen. Een nieuw aankomende thread krijgt ticket 3 en kan C niet voorbijgaan.

Dit onderscheid is belangrijk bij het volgen van het verloop: ticket houdt het volgende uit te delen nummer bij; turn houdt bij welk nummer aan de beurt is. Een ticket nemen verandert alleen het uit te delen nummer. Vrijgave laat de beurt opschuiven.

Wat eerlijkheid garandeert

Een aanroepende thread wacht achter de threads met eerdere tickets. Als elke houder uiteindelijk vrijgeeft en de threads ervoor kunnen draaien, kunnen latere aankomsten de thread niet inhalen. Het aantal concurrerende kritieke secties ervoor is begrensd door de eerdere nog geldige tickets. Dit biedt begrensd wachten en voorkomt uithongering onder die voorwaarden voor voortgang.

De garantie betreft de volgorde van binnenkomst, niet de verstreken tijd. Een houder die lang vastloopt, kan ook alle latere aanroepende threads lang laten wachten. Een ticketnummer kan de scheduler niet dwingen de eigenaar ervan te laten draaien.

Kosten die door de ticketvolgorde blijven bestaan

Elke wachtende thread wacht nog steeds actief. Als de thread die als volgende aan de beurt is tijdelijk niet draait, wachten latere uitvoerbare threads ook al bevindt zich momenteel geen thread in de kritieke sectie. Dit zijn planningskosten van de strikte volgorde.

Wachtende threads lezen ook één gedeelde locatie turn. Elke vrijgave verandert de cachelijn die ze allemaal volgen en veroorzaakt verkeer tussen kernen. Spinlocks met een wachtrij verminderen dat verkeer door elke wachtende thread een afzonderlijke lokale locatie te laten volgen; Linux stapte over van ticketspinlocks op ontwerpen met een wachtrij.

Werkelijke tickettellers gebruiken rekenkundige bewerkingen zonder teken. Gelijkheidscontroles kunnen bij telleromslag werken wanneer het aantal nog geldige tickets kleiner blijft dan het bereik van de teller. Een nummer opnieuw gebruiken terwijl een eerder gelijk ticket nog geldig is, zou uniciteit en uitsluiting tenietdoen.

Een correcte vergrendeling kan het grootste deel van een CPU aan wachten verspillen. De juiste wachtstrategie hangt ervan af of de eigenaar kan draaien en hoe lang die de vergrendeling vasthoudt.

De CPU-beurt afstaan

Een wachtende thread kan yield() aanroepen na een mislukte poging om eigenaarschap te verkrijgen. Door de CPU-beurt af te staan gaat de thread van de toestand in uitvoering naar de gereedtoestand, zodat de scheduler een andere thread kan kiezen. De thread blijft uitvoerbaar en kan dus snel opnieuw worden gekozen en weer falen. Met 100 threads op één CPU kunnen maximaal 99 wachtende threads elk draaien en de CPU-beurt afstaan voordat een onderbroken eigenaar weer aan de beurt komt. Dit vermindert actief wachten, maar biedt geen eerlijke volgorde van binnenkomst.

Blokkeren haalt de wachtende thread uit het uitvoerbare werk

Een vergrendeling met slapen plaatst een aanroepende thread die de vergrendeling niet krijgt in een wachtrij. De thread gebruikt geen CPU terwijl die geblokkeerd is. Ontgrendelen wekt een wachtende thread zodat die weer kan draaien. Een kleine interne spinlock kan de vlag en wachtrij beschermen; die wordt alleen kort vastgehouden voor de administratie.

Het scheiden van “besluiten te gaan slapen” en “daadwerkelijk gaan slapen” brengt het risico van een verloren weksignaal mee:

1. Een wachtende thread plaatst zichzelf in de wachtrij en geeft de interne vergrendeling vrij.
2. De thread wordt gepauzeerd voordat die park() aanroept.
3. De eigenaar geeft vrij en roept voor die thread unpark() aan.
4. Als dat weksignaal wordt weggegooid, gaat de wachtende thread later slapen terwijl er niemand meer is om die te wekken.

setpark() van Solaris kondigt het voornemen aan om te gaan slapen. Een tussentijdse aanroep van unpark laat de latere aanroep van park dan direct terugkeren. Het protocol verbindt de beslissing met de daadwerkelijke blokkering.

Linux gebruikt atomair vergelijken en blokkeren

Een futex combineert een woord in gebruikersgeheugen met kernelondersteuning voor wachten. futex_wait(addr, expected) blokkeert alleen als het woord nog gelijk is aan de verwachte waarde; de controle en de beslissing om te blokkeren zijn atomair ten opzichte van bewerkingen op dat futexwoord. Als een ontgrendeling het al heeft gewijzigd, gaat de aanroepende thread niet slapen op basis van de verouderde verwachting.

futex_wake(addr, n) wekt maximaal n wachtende threads. Een vergrendeling zonder concurrentie kan worden verkregen en vrijgegeven met atomaire instructies in de gebruikersruimte, zonder systeemaanroep. De pthread-mutexen van glibc in Linux gebruiken futexen om bij concurrentie te wachten. Een weksignaal maakt een thread uitvoerbaar; het vergrendelingsprotocol moet nog steeds eigenaarschap vaststellen voordat de thread de beschermde gegevens benadert.

Wacht kort actief en ga dan slapen

Een tweefasenvergrendeling wacht eerst kort actief en blokkeert daarna als het wachten voortduurt. Actief wachten kan de moeite waard zijn als de eigenaar op een andere kern draait en de verwachte wachttijd korter is dan slapen en wekken. Blokkeren heeft de voorkeur bij lange wachttijden of wanneer er meer uitvoerbare threads dan kernen zijn. Op één CPU kan een actief wachtende thread een tijdelijk niet draaiende eigenaar niet helpen om klaar te komen.

Planningsprioriteit kan voortgang verhinderen

Bij prioriteitsinversie wacht een thread met hoge prioriteit op een mutex die wordt vastgehouden door een thread met lage prioriteit, terwijl werk met middelhoge prioriteit de eigenaar van de CPU houdt. De wachtende thread met hoge prioriteit laten slapen voorkomt actief wachten, maar neemt die planningsvertraging niet weg.

Prioriteitsovererving verhoogt de prioriteit van de eigenaar tijdelijk tot die van de wachtende thread met de hoogste prioriteit, zodat de eigenaar kan afronden en vrijgeven. NASA's Mars Pathfinder kreeg in 1997 te maken met herstarts door prioriteitsinversie; het inschakelen van prioriteitsovererving voor de mutex verhielp het probleem. Een actief wachtende thread met hoge prioriteit op één CPU met strikte prioriteitsplanning kan nog erger zijn: die kan volledig verhinderen dat de eigenaar met lage prioriteit draait.

Een gedeelde teller is eenvoudig met één mutex te beschermen. De bewerkingen increment, decrement en get verkrijgen elk dezelfde vergrendeling, voeren hun taak uit en geven die vrij. De teller is exact, maar alle wijzigingen gaan via één gedeelde plek.

Waarom de exacte teller een knelpunt wordt

Op meerdere kernen laat een mutex de tellerbewerkingen na elkaar uitvoeren. De kernen dragen ook het eigenaarschap van de cachelijnen met de vergrendeling en teller over. Werkthreads toevoegen kan de wachttijd sneller laten toenemen dan het nuttige werk. De mutex vervangen door atomic_fetch_add neemt op gangbare processors de expliciete vergrendelingsoverhead weg, maar elke wijziging schrijft nog steeds naar dezelfde gedeelde locatie.

Een benaderende teller, ook wel slordige teller genoemd, verdeelt wijzigingen over lokale tellers en brengt ze in groepen over naar een globale teller. De gerapporteerde globale waarde laat recente lokale verhogingen bewust weg.

Bouw de wijziging van lokaal naar globaal op

Houd per kern één teller en mutex bij, daarnaast een globale teller met een eigen mutex en een drempel S. Voor elke verhoging:

1. Kies de lokale plek voor deze wijziging en verkrijg de bijbehorende mutex.
2. Tel 1 bij de lokale telling op.
3. Als die S bereikt, verkrijg dan de globale mutex terwijl je de lokale nog vasthoudt.
4. Tel die lokale telling bij de globale telling op, zet de lokale telling terug op 0 en geef de globale mutex vrij.
5. Geef de lokale mutex vrij.

Houd de gekozen plek tijdens de hele wijziging gelijk. Threads die verschillende plekken gebruiken, raken meestal verschillende vergrendelingen aan en verkrijgen de globale mutex alleen bij een overdracht. Ook het lezen van de globale telling volgt de bijbehorende vergrendelingsregel.

Volg een groepsgewijze overdracht

Stel dat bij vier kernen en S gelijk aan 5 hun aantallen wijzigingen 7, 3, 4 en 0 zijn. Kern 1 draagt bij de vijfde verhoging 5 over en houdt daarna 2 lokale verhogingen over. De uiteindelijke lokale tellingen zijn 2, 3, 4 en 0. De globale telling is 5 en het werkelijke totaal is 14: negen verhogingen blijven lokaal.

Na voltooide verhogingen met één eenheid ligt elke lokale telling tussen 0 en S − 1, inclusief de grenzen. Bij P kernen kan het globale totaal hoogstens achterlopen met:

Voor vier kernen en S gelijk aan 5 is de bovengrens 16. Deze grens betreft voltooide wijzigingen en hun resterende lokale tellingen; pas die niet halverwege een overdracht toe.

Kies de drempel voor de taak

Een kleinere drempel maakt de globale waarde actueler, maar vereist meer globale verkrijgingen. Bij S gelijk aan 1 wordt elke verhoging globaal overgedragen. Dat voegt overhead van de lokale vergrendeling toe zonder het globale knelpunt te vermijden. Een grotere drempel verbetert de schaalbaarheid van wijzigingen, maar vergroot de mogelijke achterstand. In een gepubliceerd experiment konden vier threads met S gelijk aan 1.024 vier miljoen wijzigingen uitvoeren in bijna de tijd die één thread voor één miljoen nodig had.

Voor een exacte momentopname moeten alle lokale mutexen in een vaste volgorde en daarna de globale mutex worden vastgehouden voordat de tellingen worden opgeteld. Die volgorde komt overeen met wijzigingen die eerst een lokale en daarna de globale vergrendeling verkrijgen. De momentopname houdt gelijktijdige overdrachten tegen tijdens het lezen; elk veld afzonderlijk lezen zou een overdracht dubbel kunnen tellen of missen.

Benaderende tellers zijn geschikt voor statistieken waarbij vertraagde zichtbaarheid aanvaardbaar is. Een referentieteller die bepaalt wanneer geheugen kan worden vrijgegeven, heeft een exacte methode nodig: een te lage telling zou een object kunnen vrijgeven dat nog in gebruik is.

Een gedeelde gekoppelde lijst moet zowel de koppelingen als de levensduur van de knopen behouden. Eén mutex rond elke bewerking is een nuttig eerste ontwerp, omdat elke gedeelde doorloop en wijziging één regel volgt.

Hoe twee invoegingen een knoop verliezen

Stel dat de lijst bij A begint. T1 bereidt knoop X voor en T2 bereidt knoop Y voor. Zonder gedeelde vergrendeling kunnen beide head == A lezen, next van hun nieuwe knoop op A instellen en vervolgens hun eigen knoop in head opslaan. De latere toewijzing aan de kop verbergt de eerst ingevoegde knoop. Die knoop wordt onbereikbaar, waardoor een invoeging verloren gaat en het geheugen ervan lekt.

De beschermde reeks moet het lezen van de huidige kop, het instellen van de nieuwe koppeling en het publiceren van de nieuwe kop omvatten. Een vergrendeling alleen rond de laatste toewijzing zou beide threads toestaan koppelingen te maken vanuit dezelfde verouderde kop.

Bereid privégegevens voor voordat je de vergrendeling verkrijgt

Een nieuwe knoop blijft privé totdat die in de gedeelde lijst wordt gekoppeld. Toewijzing en initialisatie van de sleutel kunnen vóór het verkrijgen van de vergrendeling plaatsvinden. Met de eerdere pthread-hulpfunctie die fouten controleert, kan invoegen zo worden geschreven:

int insert(list_t *list, int key) {
    node_t *node = malloc(sizeof(*node));
    if (node == NULL) return -1;
    node->key = key;

    check(pthread_mutex_lock(&list->lock));
    node->next = list->head;
    list->head = node;
    check(pthread_mutex_unlock(&list->lock));
    return 0;
}

Als de toewijzing mislukt, keert de functie terug voordat een mutex wordt vastgehouden. De gedeelde sectie blijft klein terwijl de controle van head en het bijwerken van de koppeling bij elkaar blijven. Threadveilige toewijzing maakt de lijst zelf niet threadveilig; de koppelingen hebben nog steeds hun eigen bescherming nodig.

Lezers volgen dezelfde regel

Een zoekopdracht verkrijgt de lijstmutex voordat die head leest en houdt de mutex vast tijdens het doorlopen. Dit coördineert met invoegen en verwijderen. Stel vóór de lus een resultaatvariabele in, werk die bij een overeenkomst bij en verlaat de lus naar één ontgrendelpunt voordat je terugkeert. Een vroegtijdige terugkeer bij succes binnen de vergrendelde lus zou anders een eigen vrijgave nodig hebben.

In dit ontwerp houdt verwijderen dezelfde mutex vast terwijl een knoop wordt ontkoppeld. Andere threads kunnen die knoop niet aan het doorlopen zijn, omdat ze ook de mutex nodig hebben. Geef de knoop pas vrij wanneer geen andere bewerking die nog kan bereiken. Als een API een aanroepende thread na het ontgrendelen een knooppointer laat behouden, heeft dat extra gebruik een eigen afspraak over de levensduur nodig; de lijstvergrendeling dekt dit niet langer.

Bepaal of vergrendelingen per knoop lonen

Doorgeefvergrendeling verkrijgt de vergrendeling van de volgende knoop voordat die van de huidige knoop wordt vrijgegeven. Die overlap behoudt een beschermd pad terwijl het doorlopen vordert. Meerdere bewerkingen kunnen zich dan in verschillende gebieden van de lijst bevinden.

De extra gelijktijdigheid heeft een prijs: elke bezochte knoop voegt vergrendelings- en ontgrendelingsbewerkingen toe, ook als geen andere thread in de buurt is. Een werklast met veel doorlopen kan trager worden dan de versie met één mutex. Groepen knopen vergrendelen is een middenweg. Vergelijk het ingewikkeldere ontwerp onder de werkelijke werklast met het eenvoudige ontwerp, inclusief mislukte zoekopdrachten en verwijderpaden.

Eén mutex per structuur is een verstandig uitgangspunt, maar kan bewerkingen die verschillende gebieden benaderen na elkaar laten uitvoeren. Twee nuttige verfijningen zijn een vergrendeling per uiteinde van een wachtrij en een vergrendeling per hashbucket.

Houd een dummy aan de kop van de wachtrij

Een wachtrij met twee vergrendelingen begint met één dummyknoop D en head == tail == D. D bevat geen huidig wachtrijelement. Het eerste echte element staat, als dat bestaat, op head->next. Een kopmutex laat verwijderingen na elkaar uitvoeren; een staartmutex doet hetzelfde voor toevoegingen. Daardoor kunnen één toevoeging en één verwijdering samen doorgaan.

Toevoegen bereidt de waarde van een nieuwe knoop en een lege volgende koppeling privé voor. Onder de staartmutex publiceert de bewerking die knoop via het veld next van de oude staart en verplaatst tail naar de nieuwe knoop. Verwijderen gebruikt de kopmutex om de volgende koppeling van de oude dummy te lezen. Als die leeg is, ontgrendelt de bewerking en meldt dat de wachtrij leeg is. Anders kopieert de bewerking de eerste echte waarde, verplaatst head naar die knoop, ontgrendelt en geeft de oude dummy vrij.

De knoop die de teruggegeven waarde bevatte, wordt de volgende dummy. Als je die knoop direct zou vrijgeven, zou head naar vrijgegeven geheugen blijven wijzen.

Volg de verschuivende dummy

Begin met D. De toevoeging van 5 maakt N5 en koppelt D -> N5, met tail == N5. De toevoeging van 8 voegt N8 toe en levert D -> N5 -> N8 op. Een verwijdering geeft 5 terug, verplaatst head naar N5 en geeft D vrij. N5 is nu de dummy; alleen 8 blijft als waarde in de wachtrij. Na nog een verwijdering wordt N8 de dummy en is de wachtrij leeg.

De twee uiteinden delen nog steeds een koppeling

Wanneer de wachtrij leeg is, kan toevoegen naar next van de huidige dummy schrijven terwijl verwijderen die onder een andere mutex leest. De twee mutexen alleen synchroniseren die toegangen niet. Declareer next in C11 als een atomaire pointer en publiceer en lees die met de juiste ordening; standaard sequentieel consistente atomaire opslag- en laadbewerkingen volstaan. Publicatie moet de voorbereide knoopwaarde zichtbaar maken voordat verwijderen die leest.

Wachten op een element vereist naast vergrendeling een signaleringsmechanisme.

Bepaal de hash op basis van de sleutel en vergrendel dan de bucket

Een hashtabel met een vaste grootte kan in elke bucket een threadveilige lijst gebruiken, elk met een eigen mutex. Met 101 buckets en bucket = key % 101 gebruiken sleutels 7 en 50 verschillende vergrendelingen. Sleutels 7 en 108 worden allebei aan bucket 7 gekoppeld en moeten daar na elkaar worden verwerkt. Botsingen beïnvloeden zowel de concurrentie als de lengte van zoekopdrachten.

Alle toegang tot de lijst van een bucket volgt de vergrendelingsregel van die bucket, inclusief lezen. Het wijzigen van de tabelgrootte verandert de koppeling aan buckets en verplaatst vermeldingen, dus dit eenvoudige ontwerp heeft tijdens die wijziging exclusieve toegang tot de hele tabel nodig. Eén bucketmutex kan een wijziging die elke bucket treft niet beschermen.

Verfijn pas nadat je het knelpunt hebt gevonden

Begin met een overzicht van de gedeelde toestand: welke velden worden gedeeld, welke mutex of atomaire bewerking beschermt elk veld en wanneer worden knopen bereikbaar of kunnen ze worden vrijgegeven? Controleer elk terugkeerpad en elk pad waarop toewijzing mislukt. Redeneer over vervlechtingen, test onder belasting met een raceconditiedetector en meet concurrentie voordat je fijnmazigere vergrendelingen toevoegt.