Conditievariabelen, semaforen en deadlocks

Een mutex beantwoordt de vraag “Wie mag nu bij deze gegevens?” Hij beantwoordt niet de vraag “Is het werk klaar?” Om op een gebeurtenis te wachten, heeft een thread een registratie van die gebeurtenis nodig en een manier om te slapen totdat die registratie verandert.

Waarom actief wachten een slechte manier van wachten is

De lus while (done == 0) ; besteedt CPU-tijd aan het herhaaldelijk controleren van een vlag. Op één CPU vertraagt dat werk het kind dat de vlag moet instellen. In C is het zonder synchronisatie lezen van een gewone variabele terwijl een andere thread erin schrijft bovendien een datarace. De compiler hoeft de vlag niet bij elke herhaling opnieuw te laden.

Een conditievariabele geeft threads een wachtrij. POSIX biedt pthread_cond_t, geïnitialiseerd met PTHREAD_COND_INITIALIZER of pthread_cond_init(). De wachtrij staat los van de toestand die wordt gecontroleerd: done legt voltooiing vast; de conditievariabele biedt een plaats om te slapen.

Houd de controle en het wachten bij elkaar

pthread_cond_wait(&c, &m) vereist dat de aanroeper mutex m vasthoudt. De aanroep geeft die mutex atomair vrij en begint te wachten. Voordat de aanroep terugkeert, verwerft de thread de mutex opnieuw. Dit sluit de gevaarlijke tussenruimte waarin een andere thread de toestand zou kunnen veranderen en signaleren voordat de wachtende thread daadwerkelijk is begonnen met wachten.

Hier wacht een ouder op de voltooiing van een kind. De namen lock, wait, signal en unlock verkorten de bijbehorende aanroepen van de threadbibliotheek.

/* Parent */
lock(&m);
while (done == 0)
    wait(&c, &m);
unlock(&m);

/* Child */
lock(&m);
done = 1;
signal(&c);
unlock(&m);

Aanvankelijk is done 0. Als de ouder eerst wordt uitgevoerd, vergrendelt die, ziet dat het werk niet klaar is en wacht. Het wachten geeft m vrij, zodat het kind die kan vergrendelen, done kan instellen en kan signaleren. De ouder verwerft uiteindelijk m opnieuw, controleert done opnieuw en gaat verder.

Als het kind eerst wordt uitgevoerd, legt het de voltooiing vast voordat de ouder arriveert. Het signaal wekt niemand, maar de ouder ziet later done == 1 en slaat het wachten over. De oplossing moet in beide volgordes correct werken.

Signalen slaan geen gebeurtenissen op

pthread_cond_signal(&c) deblokkeert ten minste één wachtende thread als die er is; POSIX staat toe dat er meer ontwaken. Zonder wachtende threads heeft de aanroep geen effect. pthread_cond_broadcast(&c) wekt alle op dat moment wachtende threads. Geen van beide aanroepen bewaart een melding voor toekomstige threads.

Als je done weglaat, werkt het patroon voor wachten op threadbeëindiging daarom niet: een kind kan signaleren voordat zijn ouder wacht, waarna de ouder gaat slapen zonder dat er nog een signaal volgt. Dit is een verloren weksignaal. done buiten de mutex controleren schept een andere mogelijkheid voor een verloren weksignaal: de ouder controleert en ziet dat de conditie onwaar is, het kind maakt die waar en signaleert, waarna de ouder begint te wachten.

Bescherm de toestandscontrole en elke toestandsverandering met dezelfde mutex. Houd die vast vanaf de controle tot en met de wachtoproep. Een eenvoudige signaleringsroute verandert de toestand en signaleert terwijl de thread die mutex nog vasthoudt. POSIX staat signaleren zonder de mutex vast te houden toe, maar het protocol voor de gedeelde toestand moet nog steeds een verloren weksignaal voorkomen.

Terugkeren uit een wachtoproep betekent dat de thread het opnieuw mag proberen. Het betekent niet dat de conditie die de thread nodig heeft nog waar is. Dit onderscheid is van belang wanneer meerdere threads om dezelfde gegevens concurreren.

Mesa- en Hoare-semantiek

POSIX, Java, C++-conditievariabelen en Python-condities volgen het Mesa-gedrag. Hoares monitors introduceerden het sterkere overdrachtsmodel; de aanpak van Mesa is de gebruikelijke praktische keuze.

Stel dat C1 wacht totdat een buffer met één plaats niet meer leeg is. Een producent vult die en signaleert C1. C1 is nu gereed, maar C2 kan eerst de mutex verwerven en het element pakken. Wanneer C1 uiteindelijk de mutex opnieuw verwerft, is de buffer weer leeg.

lock(&m);
while (count == 0)
    wait(&filled, &m);
v = get();
unlock(&m);

De while herhaalt de controle na elke terugkeer. Een if controleert alleen vóór de eerste wachtoproep en zou C1 get() op een lege buffer laten aanroepen. Gebruik ook met één producent en één consument while: POSIX staat ook spontaan ontwaken toe, waarbij de wachtoproep terugkeert zonder bijbehorend signaal.

Eén thread wekken of allemaal?

Een signaal is geschikt als de wachtende threads dezelfde conditie nodig hebben en elk van hen de verandering kan benutten. Een broadcast is nuttig als meerdere threads verder kunnen, of als verschillende wachtende threads verschillende hoeveelheden nodig hebben en de signalerende thread niet de juiste kan selecteren.

Neem een allocator met 0 vrije bytes. Ta heeft 100 bytes nodig en Tb 10. Een andere thread geeft 50 bytes vrij. Een signaal kan Ta wekken, die nog steeds niet verder kan, terwijl Tb blijft slapen hoewel zijn verzoek past. Een broadcast wekt beide. Ze verwerven de mutex één voor één opnieuw; Tb kan geheugen toegewezen krijgen, terwijl Ta opnieuw wacht. Dit is een overkoepelende conditie: de melding bereikt elke wachtende thread die mogelijk verder kan.

Een broadcast kan extra weksignalen, contextwisselingen en concurrentie om de mutex veroorzaken. Afzonderlijke conditievariabelen voor verschillende predicaten kunnen signalering selectiever maken. In een buffer moeten producenten en consumenten niet één ongedifferentieerde signaalwachtrij delen.

Het verband met monitors

Een monitor bundelt gedeelde gegevens met bewerkingen die één thread tegelijk toelaten en met conditievariabelen om te wachten. Java-objecten bieden een vergrendeling en een wachtverzameling. Binnen synchronized kan een thread wait(), notify() of notifyAll() aanroepen; aanroepen zonder eigenaar van de monitor van dat object te zijn, werpt IllegalMonitorStateException.

Wachten geeft alleen de bijbehorende mutex of de vergrendeling van het Java-object vrij. Als een thread ook een andere vergrendeling vasthoudt, blijft die tweede vergrendeling vastgehouden. Een producent die die nodig heeft, kan de conditie dan mogelijk niet waar maken. Controleer bij een wachtoproep alle vastgehouden vergrendelingen, niet alleen de vergrendeling die in de aanroep staat.

Producenten voegen elementen toe aan een buffer met vaste grootte; consumenten halen ze eruit. Een correcte begrensde buffer voorkomt dat een volle buffer wordt overschreven, dat elementen uit een lege buffer worden gehaald en dat de administratie gelijktijdig wordt gewijzigd. De verzoekenwachtrij van een webserver en de pipe tussen grep error log.txt en wc -l passen beide in dit patroon.

Volg de ringindices

Een ringbuffer gebruikt een array en twee indices. fill_ptr geeft de volgende schrijfplaats aan; use_ptr geeft de volgende leesplaats aan. Beide worden verhoogd modulo MAX. Een afzonderlijke count maakt onderscheid tussen leeg en vol, ook als de twee indices gelijk zijn.

void put(int v) {
    buffer[fill_ptr] = v;
    fill_ptr = (fill_ptr + 1) % MAX;
    count++;
}
int get(void) {
    int v = buffer[use_ptr];
    use_ptr = (use_ptr + 1) % MAX;
    count--;
    return v;
}

Begin met capaciteit 3 en beide indices op 0. Het plaatsen van 7, 8 en 9 vult de plaatsen 0, 1 en 2. De schrijfindex springt terug naar 0 en count bereikt 3. Ophalen geeft 7 terug en verhoogt de leesindex naar 1. Het plaatsen van 10 gebruikt plaats 0 opnieuw. De array is nu [10, 8, 9], maar verwijderen volgens FIFO volgt de leesindex: eerst komt 8, dan 9 en dan 10.

Richt elk signaal op de andere rol

Gebruik één mutex, empty voor producenten die op ruimte wachten en fill voor consumenten die op een element wachten. Initialiseer beide conditievariabelen en de mutex voordat je threads start.

/* Producer: repeat for each item v */
lock(&m);
while (count == MAX)
    wait(&empty, &m);
put(v);
signal(&fill);
unlock(&m);

/* Consumer */
lock(&m);
while (count == 0)
    wait(&fill, &m);
v = get();
signal(&empty);
unlock(&m);

De controle en de wijziging van de buffer blijven in één kritieke sectie. Anders zouden twee producenten allebei één vrije plaats kunnen zien en elkaars werk overschrijven. Wachten geeft m vrij, zodat de andere rol de buffer kan veranderen.

Waarom één wachtrij kan vastlopen

Met één conditievariabele en signalen kunnen producenten en consumenten de verkeerde rol wekken. Bij capaciteit 1 slapen C1 en C2 eerst omdat de buffer leeg is. P voegt een element in, wekt C1 en wacht daarna omdat de buffer vol is. C1 haalt het element eruit en signaleert, maar het signaal kan C2 wekken in plaats van P. C1 wacht opnieuw; C2 ziet ook dat de buffer leeg is en wacht. P blijft slapen hoewel er ruimte beschikbaar is. Twee wachtrijen leiden elk signaal naar de rol die nu verder kan. Alle wachtende threads op een gedeelde wachtrij wekken kan dat selectieprobleem voorkomen, ten koste van extra weksignalen.

Een grotere capaciteit vangt pieken op en laat productie en consumptie buiten de korte kritieke sectie van de buffer overlappen. De wijzigingen aan de buffer zelf blijven na elkaar plaatsvinden. Capaciteit 1 dwingt elke invoeging en verwijdering elkaar af te wisselen.

Voor een nette afsluiting wacht je eerst tot elke producent klaar is met zijn echte elementen. Plaats daarna per consument één gereserveerd gegevenseindelement in de wachtrij, zoals -1 als echte elementen niet-negatief zijn. Elke consument stopt nadat hij er één heeft gepakt. Als je die markeringen verstuurt terwijl producenten nog actief zijn, kunnen echte elementen zonder consument achterblijven.

Een semafoor bevat een geheel getal dat door atomaire wacht- en vrijgavebewerkingen wordt veranderd. Dijkstra introduceerde die in de jaren 1960 als P en V; POSIX noemt de bewerkingen sem_wait() en sem_post(). Atomair betekent dat twee threads dezelfde tellerbewerking niet tegelijk gedeeltelijk kunnen uitvoeren.

Beschikbare eenheden bepalen de beginwaarde

sem_init(&s, 0, X) maakt een naamloze semafoor met waarde X. Het tweede argument 0 kiest voor delen tussen threads in één proces. Voor delen tussen processen vereist een argument ongelijk aan nul dat de semafoor zich in gedeeld geheugen bevindt.

Een binaire semafoor die als vergrendeling wordt gebruikt, plaatst een wachtbewerking vóór en een vrijgavebewerking na een kritieke sectie. Als die bij 0 begint, wordt de eerste thread die naar binnen wil geblokkeerd. Als die bij 2 begint, kunnen twee threads naar binnen en is er geen wederzijdse uitsluiting.

Twee equivalente telmodellen

In Dijkstra's definitie blijft de waarde niet-negatief: de wachtbewerking slaapt tot de waarde kan worden verlaagd zonder onder nul te komen en de vrijgavebewerking voegt een eenheid toe. Linux volgt deze niet-negatieve conventie.

Gebruik voor handmatige uitvoeringsverlopen het model met een teller met teken: de wachtbewerking verlaagt de waarde en blokkeert als de nieuwe waarde negatief is; de vrijgavebewerking verhoogt de waarde en wekt een wachtende thread als die is geblokkeerd. In dit model telt de absolute waarde van een negatieve waarde de geblokkeerde wachtende threads. Het is een redeneerconventie, geen negatieve waarde die je van de Linux-semafoor-API moet verwachten.

Volg een vergrendeling die op 1 is geïnitialiseerd:

1. T0 wacht: 1 wordt 0, dus T0 gaat naar binnen.
2. T1 wacht: 0 wordt −1, dus T1 blokkeert.
3. T0 geeft vrij: −1 wordt 0, zodat T1 verder kan.
4. T1 is klaar en geeft vrij: 0 wordt 1.

Het weksignaal draagt het bestaande toegangsbewijs over aan T1; er is geen nieuwe wachtbewerking nodig voordat T1 zijn kritieke sectie binnengaat.

Een vrijgavebewerking wordt onthouden

Als niemand wacht, verhoogt een vrijgavebewerking het beschikbare aantal. Een latere wachtbewerking kan dat toegangsbewijs gebruiken. Dit is nuttig als één thread klaar is voordat de thread die erop wacht is begonnen. Een signaal van een conditievariabele heeft zo'n geheugen niet.

Semaforen hebben geen eigenaar: één thread mag wachten en een andere mag een vrijgavebewerking uitvoeren. Een mutex behoort toe aan de thread die die heeft vergrendeld; een standaard-POSIX-mutex vanuit een andere thread ontgrendelen is ongedefinieerd gedrag. De semafoor zonder eigenaar maakt signalering mogelijk, maar maakt een extra vrijgavebewerking ook lastiger te diagnosticeren.

Een semafoor kan worden opgebouwd uit een mutex, een conditievariabele en een niet-negatief geheel getal. De wachtbewerking vergrendelt, herhaalt zolang value <= 0, wacht, verlaagt de waarde en ontgrendelt. De vrijgavebewerking vergrendelt, verhoogt de waarde, signaleert en ontgrendelt. De mutex maakt de tellerbewerkingen atomair; de lus vangt weksignalen op waarna geen eenheid beschikbaar blijft. Vergrendelingen met conditievariabelen en semaforen kunnen elkaar implementeren, al is een correcte implementatie van conditievariabelen met semaforen ingewikkelder.

Hetzelfde paar van een wacht- en een vrijgavebewerking kan een gebeurtenis of een beperkte voorraad voorstellen. Bepaal wat een toegangsbewijs betekent voordat je het beginaantal kiest en bepaalt waar elke bewerking hoort.

Laat voltooiing aan gebruik voorafgaan

Initialiseer finished op 0 voor een ouder die op een kind wacht. Het kind voert een vrijgavebewerking uit nadat het zijn werk heeft voltooid. De ouder wacht voordat die het resultaat gebruikt.

/* Child */
produce_result();
sem_post(&finished);

/* Parent */
sem_wait(&finished);
use_result();

Als de ouder eerst arriveert, verandert de waarde met teken van 0 naar −1 en gaat de ouder slapen. De vrijgavebewerking van het kind brengt de waarde terug naar 0 en wekt de ouder. Als het kind eerst arriveert, verandert zijn vrijgavebewerking 0 in 1; de latere wachtbewerking verandert 1 in 0 zonder te blokkeren. Eén voltooide gebeurtenis maakt één succesvolle wachtbewerking mogelijk.

Tel een verzameling bronnen

Een verzameling van vier databaseverbindingen gebruikt een semafoor die op 4 is geïnitialiseerd. Elke client wacht voordat die een verbinding leent en voert een vrijgavebewerking uit nadat die de verbinding heeft teruggegeven. Een vijfde gelijktijdige gebruiker gaat slapen. De semafoor telt de toelatingen; een afzonderlijke mutex beschermt nog steeds de gedeelde lijst die aangeeft welke verbinding vrij is. Twee toegelaten threads mogen niet dezelfde lijstvermelding verwijderen.

Begrenzing van gelijktijdige toegang past hetzelfde idee toe op een kostbare fase. Stel dat 100 threads tijdens de verwerking elk 500 MB nodig hebben. Samen zouden ze 50.000 MB nodig kunnen hebben. Een machine met 8 GB heeft volgens decimale SI-eenheden 8.000 MB. Als je hoogstens 12 werkthreads toelaat, beperk je deze fase tot 6.000 MB en blijft 2.000 MB over voor ander gebruik.

sem_wait(&processing_slots);
run_memory_heavy_phase();
sem_post(&processing_slots);

Elk pad na een succesvolle wachtbewerking moet het toegangsbewijs teruggeven, ook een foutpad. Een vrijgavebewerking vergeten vermindert geleidelijk de capaciteit. Twee keer een vrijgavebewerking uitvoeren creëert een extra toegangsbewijs en laat meer gelijktijdige gebruikers toe dan bedoeld.

Ontmoet elkaar bij een rendez-vous

Een rendez-vous vereist dat twee threads arriveren voordat een van beide verdergaat. Initialiseer a_arrived en b_arrived op 0.

/* A */
sem_post(&a_arrived);
sem_wait(&b_arrived);

/* B */
sem_post(&b_arrived);
sem_wait(&a_arrived);

Als A eerst arriveert, legt die zijn aankomst vast en blokkeert voor B. B legt zijn aankomst vast en kan het bewaarde toegangsbewijs van A gebruiken. A kan daarna het toegangsbewijs van B gebruiken. Als je beide reeksen omdraait zodat ze vóór de vrijgavebewerking wachten, gaat elke thread slapen voordat die iets heeft aangekondigd.

Deze twee semaforen implementeren één ontmoeting. Om de synchronisatie in herhaalde rondes opnieuw te gebruiken, moet je voorkomen dat rondes elkaars aankomsten gebruiken; één succesvol verloop is geen herbruikbaar barrièreontwerp.

Een semafoor past goed bij een aantal of een eenvoudige gebeurtenis. Een conditievariabele past bij een rijker predicaat, zoals wachten tot een wachtrij meerdere elementen van een vereist type bevat. In dat geval beschermt de mutex de toestand waaruit de conditie wordt berekend.

Een buffer met semaforen onderscheidt twee vragen: “Is er een element of plaats beschikbaar?” en “Wie mag de array nu wijzigen?” Twee telsemaforen beantwoorden de eerste vraag en een mutex beantwoordt de tweede.

Stel drie afzonderlijke besturingselementen in

Initialiseer bij capaciteit MAX de semafoor empty op MAX, full op 0 en de mutex als ontgrendeld. Hier zijn empty en full semaforen, geen conditievariabelen. Een toegangsbewijs van empty reserveert één plaats; een toegangsbewijs van full reserveert één element.

/* Producer */
sem_wait(&empty);
lock(&mutex);
put(v);
unlock(&mutex);
sem_post(&full);

/* Consumer */
sem_wait(&full);
lock(&mutex);
v = get();
unlock(&mutex);
sem_post(&empty);

De producent verwerft ruimte voordat hij de ring aanspreekt en maakt daarna het voltooide element beschikbaar met een vrijgavebewerking op full. De consument verwerft een element, verwijdert het onder de mutex en geeft ruimte terug met een vrijgavebewerking op empty. Een succesvolle wachtbewerking op een semafoor reserveert de bron al, dus deze aanroepen hebben geen predicaatlus nodig zoals bij een conditievariabele.

Volg één plaats

Aanvankelijk is empty 1 en full 0. Een consument wacht op full, waardoor die in het model met een teller met teken −1 wordt, en gaat slapen. De producent wacht op empty, waardoor die van 1 naar 0 gaat. De producent vergrendelt, voegt een element in, ontgrendelt en voert een vrijgavebewerking op full uit, waardoor −1 in 0 verandert en de consument verder kan.

De volgende wachtbewerking van de producent op empty verandert 0 in −1 en blokkeert. De consument neemt het element onder de mutex en voert een vrijgavebewerking op empty uit, waardoor −1 in 0 verandert en de producent verder kan. De semafoorwaarden regelen de overdracht; voor de synchronisatie is geen afzonderlijke count nodig.

Bij een grotere buffer kunnen meerdere producenten de ruimtesemafoor passeren. Zonder de mutex zouden ze dezelfde fill_ptr kunnen lezen en naar dezelfde plaats kunnen schrijven. Een reservering is geen exclusieve toegang tot de indices van de array.

Waarom eerst vergrendelen een deadlock kan veroorzaken

Stel dat de consument mutex vergrendelt voordat hij op full wacht. Bij een lege buffer slaapt hij terwijl hij de mutex nog vasthoudt. De producent heeft die mutex nodig om het element in te voegen waarvan de vrijgavebewerking de consument zou laten doorgaan. Geen van beide kan zijn werk afmaken.

Een wachtbewerking op een semafoor geeft geen mutex vrij. Een wachtbewerking op een conditievariabele geeft bewust de bijbehorende mutex vrij. De volgorde is bij deze buffer dus van belang: eerst reserveren, dan vergrendelen, de buffer veranderen, ontgrendelen en vervolgens het toegangsbewijs voor de andere rol beschikbaar maken.

De bredere regel is dat je niet moet blokkeren terwijl je een vergrendeling vasthoudt die nodig is voor de bewerking die je kan deblokkeren. Die regel verklaart waarom het lezers-schrijversalgoritme een andere veilige inrichting kan hebben: de schrijver heeft de vergrendeling van de lezersteller niet nodig om zijn bron vrij te geven.

De mutex kan zelf een binaire semafoor zijn die op 1 is geïnitialiseerd. Zijn rol blijft wederzijdse uitsluiting; de andere twee semaforen tellen bronnen.

Structuren die vaak worden gelezen, kunnen meerdere lezers tegelijk toelaten omdat lezen de gegevens niet verandert. Een lezers-schrijversvergrendeling laat een groep lezers of één schrijver toe. Elke wijziging van de beschermde gegevens vereist schrijftoegang.

Bouw de groep lezers op

Gebruik readers = 0, een semafoor lock die op 1 is geïnitialiseerd om die teller te beschermen, en writelock die op 1 is geïnitialiseerd om de gedeelde bron te beschermen.

/* Acquire read access */
sem_wait(&lock);
readers++;
if (readers == 1)
    sem_wait(&writelock);
sem_post(&lock);

/* Release read access */
sem_wait(&lock);
readers--;
if (readers == 0)
    sem_post(&writelock);
sem_post(&lock);

Een schrijver wacht op writelock, verandert de gegevens en voert daarna een vrijgavebewerking op writelock uit. Hij verwerft de vergrendeling van de teller niet. De eerste lezer verwerft writelock voor de groep en de laatste lezer geeft die terug. Een semafoor is geschikt voor die overdracht, omdat de thread die de vrijgavebewerking uitvoert niet de thread hoeft te zijn die oorspronkelijk heeft gewacht.

Volg hoe R1 naar binnen gaat: R1 verhoogt readers naar 1 en verwerft writelock. R2 verhoogt de teller naar 2 zonder nog een toegangsbewijs te verwerven. Schrijver W blokkeert nu op writelock. R1 vertrekt en verlaagt de teller naar 1. R2 vertrekt, verlaagt de teller naar 0 en voert een vrijgavebewerking uit, zodat W als enige kan schrijven.

De eerste lezer kan op writelock wachten terwijl hij lock vasthoudt. Dit veroorzaakt niet de deadlock uit de begrensde buffer: de huidige schrijver heeft de vergrendeling van de teller niet nodig om zijn werk af te maken en een vrijgavebewerking op writelock uit te voeren.

Eerlijkheid is een afzonderlijke eigenschap

Dit ontwerp geeft lezers voorrang. Zolang de lezersteller positief blijft, kan een andere lezer zich bij de groep voegen vóór een wachtende schrijver. Een voortdurende stroom overlappende lezers kan de schrijver onbeperkt laten wachten: uithongering van schrijvers.

Het basisontwerp biedt veiligheid, maar geen grens aan hoe lang een schrijver wacht. Een hogere doorvoer van lezers is niet hetzelfde als een eerlijke bediening.

Gebruik de juiste modus

Een leesvergrendeling kan een schrijfbewerking niet tegen andere lezers beschermen. Zelfs het wijzigen van een cacheteller onder leestoegang kan een race met een andere lezer veroorzaken. Om in dit basisontwerp over te stappen op schrijftoegang, geef je de leestoegang vrij, verwerf je schrijftoegang en controleer je de conditie opnieuw. Als een thread op schrijftoegang wacht terwijl hij nog als lezer meetelt, kan hij voor altijd op zichzelf wachten.

POSIX biedt pthread_rwlock_t, pthread_rwlock_rdlock(), pthread_rwlock_wrlock() en pthread_rwlock_unlock(). Java biedt ReentrantReadWriteLock; C++17 biedt std::shared_mutex. Deze vergrendelingen vergen meer administratie dan een gewone mutex. Meet de werklast: bij korte secties of veel schrijfbewerkingen kan een eenvoudige mutex even snel of sneller zijn.

Een schending van atomiciteit ontstaat wanneer code erop vertrouwt dat een groep toegangen ondeelbaar is, maar een andere thread ertussen kan handelen. Elke afzonderlijke toegang kan redelijk lijken terwijl de gecombineerde bewerking faalt.

Zoek de tussenruimte na de controle

Bekijk een gedeelde logbuffer:

/* T1 */
if (log->buf != NULL)
    write_out(log->buf);

/* T2 */
log->buf = NULL;

T1 kan een niet-nulle pointer controleren, pauzeren en verdergaan nadat T2 die op null heeft gezet. T1 geeft dan null door aan write_out(). De bedoelde garantie was niet alleen een geldige controle, maar ook dat de gecontroleerde waarde tijdens de aanroep bruikbaar bleef.

Bescherm de controle en het gebruik samen en bescherm de concurrerende toekenning met dezelfde mutex:

/* T1 */
lock(&m);
if (log->buf != NULL)
    write_out(log->buf);
unlock(&m);

/* T2 */
lock(&m);
log->buf = NULL;
unlock(&m);

T2 wordt nu vóór of na de volledige bewerking van T1 uitgevoerd. Elke thread een eigen vergrendeling geven helpt niet: beide kunnen hun afzonderlijke vergrendeling tegelijk vasthouden. Als je alleen T1 vergrendelt, kan T2 nog steeds in de tussenruimte handelen.

Een geldige controle kan toch tot een ongeldig saldo leiden

Begin met saldo 50. Twee threads willen elk 30 opnemen, maar alleen als er genoeg overblijft. Beide kunnen 50 lezen en balance >= 30 passeren voordat een van beide handelt. Als de opnames daarna worden toegepast, kan het saldo −10 worden. Als je de controle en aftrekking samen beschermt, laat de eerste opname 20 over; de volgende thread ziet 20 en weigert.

Zelfs atomaire laad- en aftrekbewerkingen maken van dat paar nog geen transactie. Een andere thread kan tussen de atomaire controle en de atomaire verandering handelen. Eén vergrendeling rond de volledige beslissing en verandering dwingt de vereiste afbakening af.

Hetzelfde probleem zie je bij count++: laden, optellen en opslaan zijn afzonderlijke stappen. Twee threads kunnen dezelfde oude waarde laden en dezelfde verhoogde waarde opslaan, waardoor een wijziging verloren gaat. Een vergrendeling rond de verhoging of een atomaire fetch-and-add voert de vereiste wijziging veilig uit.

Gebruik onderzoeksresultaten zonder te veralgemeniseren

Lu en collega's onderzochten in een onderzoek uit 2008 105 verholpen gelijktijdigheidsfouten in MySQL, Apache, Mozilla en OpenOffice. Daarvan waren er 74 fouten zonder deadlock en 31 deadlocks. Schendingen van atomiciteit en volgordeschendingen vormden 97% van de steekproef zonder deadlock. Dit zijn bevindingen over die onderzochte steekproef, geen percentage dat voor elke codebasis gegarandeerd is.

Ongeveer 92% van de onderzochte fouten kon worden uitgelokt door de volgorde van hoogstens vier geheugentoegangen te beheersen. Een kleine tabel met een vervlechting kan daardoor meer inzicht geven dan duizenden succesvolle gewone uitvoeringen. ThreadSanitizer helpt uitgevoerde dataraces te vinden, maar een logische atomiciteitsfout kan blijven bestaan ook als elke afzonderlijke toegang is gesynchroniseerd. Test de invariant van de hele bewerking, zoals “een succesvolle opname maakt het saldo nooit negatief”.

Een volgordeschending betekent dat bewerking A vóór bewerking B moet plaatsvinden, maar dat het programma geen synchronisatie biedt die dit garandeert. Wederzijdse uitsluiting alleen kan niet bepalen welke bewerking eerst gaat.

Een thread kan direct worden uitgevoerd

Stel dat een aanmakende thread een nieuw aangemaakt werkthreadrecord in een gedeelde pointer opslaat, terwijl de werkthread begint met het gebruiken van die pointer:

/* Creator */
worker = thread_create(worker_main);

/* New worker */
use(worker->state);

De werkthread kan worden uitgevoerd voordat thread_create() terugkeert en voordat de toekenning is voltooid. De volgorde in de broncode van de aanmakende thread zegt niets over wanneer de nieuwe thread CPU-tijd krijgt. Een succesvolle uitvoering betekent alleen dat de aanmakende thread die race toevallig heeft gewonnen.

Maak gereedheid na initialisatie bekend

Voeg ready = 0, mutex m en conditievariabele c toe. De aanmakende thread houdt de mutex vast terwijl die de pointer toekent en gereedheid bekendmaakt:

/* Creator */
lock(&m);
worker = thread_create(worker_main);
ready = 1;
signal(&c);
unlock(&m);

/* Worker, before using worker */
lock(&m);
while (ready == 0)
    wait(&c, &m);
unlock(&m);
use(worker->state);

Als de werkthread de mutex eerst bereikt, kan die de gereedheidscontrole niet passeren voordat de aanmakende thread het record beschikbaar heeft gemaakt. Als de werkthread later arriveert, onthoudt ready dat de initialisatie klaar is. Houd het record in leven zolang de werkthread het gebruikt en synchroniseer eventuele latere wijzigingen.

Een semafoor die op 0 is geïnitialiseerd, biedt een kortere overdracht: de aanmakende thread voert na de toekenning van de pointer een vrijgavebewerking uit en de werkthread wacht voordat die de pointer gebruikt. Voor een resultaat dat pas bestaat nadat een thread klaar is, legt wachten op de beëindiging van die thread vóór het lezen van het resultaat de vereiste volgorde vast. Het vrijgeven van een object moet eveneens wachten tot de gebruikers klaar zijn, bijvoorbeeld door op threadbeëindiging te wachten of met een correct gesynchroniseerde referentieteller.

Waarom veranderingen in timing het probleem niet oplossen

Het toevoegen van sleep(1) of sched_yield() verandert alleen de kans op de gewenste uitvoeringsvolgorde. Een trager of belast systeem kan de consument nog steeds te vroeg laten doorgaan. Een mutex rond elke bewerking voorkomt overlap, maar laat nog steeds toe dat het gebruik de mutex vóór de initialisatie verwerft.

In het onderzoek van Lu en collega's was ongeveer een derde van de fouten zonder deadlock een volgordeschending en werd ongeveer 73% van de fouten zonder deadlock niet opgelost door alleen vergrendelingen toe te voegen of te veranderen. Benoem voordat je een primitieve bouwsteen kiest de bewerking die klaar moet zijn en de bewerking die moet wachten. Die afhankelijkheid bepaalt waar de vrijgavebewerking, het signaal of het wachten op threadbeëindiging hoort.

Een verzameling threads zit in een deadlock wanneer elke thread wacht op iets wat alleen een andere thread in de verzameling kan bieden. Geen van de threads kan verdergaan en de handeling uitvoeren die de andere laat doorgaan. Het programma kan bij veel uitvoeringsvolgordes werken voordat één ongelukkige volgorde de cyclus blootlegt.

Bouw de fout met twee vergrendelingen op

T1 verwerft L1 en vraagt daarna L2 aan. T2 verwerft L2 en vraagt daarna L1 aan. Als T1 L1 verwerft en daarna T2 L2 verwerft, blokkeren beide tweede verwervingen. Elke thread houdt precies de bron vast die de andere nodig heeft.

Dit kan in gewone functies verborgen zitten. Als transfer(a, b) eerst a en daarna b vergrendelt, kunnen gelijktijdige aanroepen transfer(x, y) en transfer(y, x) de rekeningvergrendelingen in omgekeerde volgorde verwerven. Inkapseling maakt een aanroep gemakkelijk, maar kan de vergrendelingen die de aanroep verwerft verbergen.

Herken alle vier de voorwaarden

Alle vier de voorwaarden zijn noodzakelijk. Als je één ervan in het ontwerp uitsluit, voorkom je een deadlock om bronnen. De aanwezigheid van exclusieve vergrendelingen en geneste verwerving alleen bewijst niet dat een bepaalde uitvoering een cyclus heeft bereikt.

Lees een wachtafhankelijkheidsgraaf

Teken per thread een knoop. Teken T → U wanneer T wacht op een bron die U vasthoudt. Bij bronnen met één exemplaar, zoals exclusieve vergrendelingen, wijst een cyclus op een deadlock.

Als T1 A vasthoudt en op B wacht, T2 B vasthoudt en op C wacht, en T3 C vasthoudt en op A wacht, is de graaf T1 → T2 → T3 → T1. Alle drie zitten vast. Als T3 in plaats daarvan een vrije vergrendeling D aanvraagt, kan T3 zijn werk afmaken en C vrijgeven, zodat T2 en daarna T1 verder kunnen. Een keten is geen cyclus.

Als brontypen meerdere uitwisselbare exemplaren hebben, is een cyclus alleen onvoldoende: een extra exemplaar kan beschikbaar komen. Gebruik aantallen bronnen en openstaande verzoeken om dat geval te beoordelen.

Dinerende filosofen en verwante fouten

Vijf filosofen delen vijf vorken die in een cirkel zijn geplaatst. Ieder heeft beide aangrenzende vorken nodig. Als ze allemaal eerst hun linkervork oppakken, kunnen ze allemaal voor altijd op hun rechtervork wachten. Als één filosoof de verwervingsvolgorde omdraait, wordt de cyclus doorbroken. Toelating beperken tot vier filosofen voorkomt ook dat alle vijf een vork vasthouden; ten minste één toegelaten filosoof kan beide vorken verkrijgen.

Uithongering betekent dat één thread onbeperkt wacht terwijl andere voortgang maken. Livelock betekent dat threads draaien en reageren, maar er herhaaldelijk niet in slagen voortgang te maken. Een verzameling threads in een deadlock is geblokkeerd. Eén thread kan zelfs zichzelf in een deadlock brengen door een gewone, niet-recursieve mutex te vergrendelen die hij al vasthoudt. Ook semaforen en conditievariabelen kunnen afhankelijkheden scheppen: een wachtende thread die een vergrendeling vasthoudt die zijn signalerende thread nodig heeft, kan een cyclus sluiten zonder een tweede expliciete verwerving van een vergrendeling.

Preventie verandert het ontwerp zodat een noodzakelijke voorwaarde voor deadlock niet kan ontstaan. Een vaste vergrendelingsvolgorde is vaak de duidelijkste aanpak, omdat die de circulaire afhankelijkheid rechtstreeks aanpakt.

Geef elke vergrendeling een plaats in de volgorde

Ken unieke sleutels aan vergrendelingen toe en verwerf lagere sleutels altijd vóór hogere. Sorteer bij overboekingen de rekeningidentificaties voordat je vergrendelt. Zowel transfer(x, y) als transfer(y, x) verwerft dan eerst dezelfde rekening. Als de identificaties dezelfde rekening aanduiden, verwerf je de vergrendeling daarvan één keer.

Voor een cyclus zouden de sleutels rond de cirkel steeds moeten toenemen en toch naar de beginsleutel moeten terugkeren. Dat is onmogelijk. Elk verwervingspad moet de regel volgen. Eén hulpfunctie die de volgorde omkeert, brengt het risico terug. De Linux-tool lockdep houdt waargenomen vergrendelingsafhankelijkheden bij en meldt mogelijk onveilige volgordes.

Verwerf alles of niets

Een strikte manier om vasthouden en wachten uit te sluiten, is een thread zijn volledige verzameling bronnen in één stap toe te kennen, of niets toe te kennen. De thread houdt dan nooit een gedeeltelijke verzameling vast terwijl hij op de rest wacht. Hiervoor moet vooraf bekend zijn welke bronnen nodig zijn en de gelijktijdigheid kan erdoor afnemen.

Een verwant protocol laat verwervingsreeksen na elkaar verlopen met een globale preventievergrendeling:

lock(&prevention);
lock(&L1);
lock(&L2);
unlock(&prevention);
/* use L1 and L2, then release them */

Alle threads moeten hun volledige verzameling onder die globale vergrendeling verwerven, en het vrijgeven van bronnen mag niet vereisen dat ze die verwerven. Eén thread kan nog steeds L1 vasthouden terwijl hij op L2 wacht, dus dit sluit vasthouden en wachten niet letterlijk uit. Het voorkomt dat andere threads een concurrerende gedeeltelijke verwerving beginnen. Geen thread die bronnen vasthoudt, kan halverwege een tweede concurrerende verwervingsreeks zijn. De kosten zijn dat vergrendelingen eerder worden vastgehouden en dat verwervingen na elkaar verlopen.

Geef op en probeer opnieuw

pthread_mutex_trylock() keert direct terug met EBUSY als een vergrendeling niet beschikbaar is. Een thread kan L1 verwerven, L2 proberen en L1 vrijgeven als de poging mislukt. Ook andere gedeeltelijk verworven bronnen moet hij vrijgeven voordat hij het opnieuw probeert.

Twee threads kunnen herhaaldelijk botsen, opgeven en het tegelijk opnieuw proberen. Dat is livelock: beide worden uitgevoerd, maar geen van beide wordt voltooid. Een willekeurige wachttijd vóór een nieuwe poging vermindert herhaalde botsingen; die maakt van de herhalingslus geen garantie op eerlijkheid.

Vervang een vergrendeling door een atomaire bewerking

Compare-and-swap (CAS) verandert een locatie alleen als die nog overeenkomt met een verwachte waarde. Conceptueel leest een herhalingslus voor atomair optellen de oude waarde, probeert die te vervangen door de oude waarde plus de verhoging en probeert het opnieuw als een andere thread de waarde eerst heeft veranderd. Werkelijke C-implementaties gebruiken atomaire typen en atomaire bewerkingen voor zowel het lezen als het wijzigen.

Als de bewerking geen vergrendeling meer verwerft, kan ze niet meer door die vergrendeling in een deadlock raken. Een vergrendelingsvrij algoritme garandeert voortgang voor het systeem als geheel, maar één thread kan bij nieuwe pogingen steeds blijven verliezen. Algemene vergrendelingsvrije structuren vereisen ook een zorgvuldig ontwerp van de geheugenlevensduur.

Vermijding controleert of een voorgesteld verzoek een mogelijkheid openlaat voor elke thread om zijn werk af te maken. De gebruikelijke patronen voor brongebruik zijn toegestaan, maar verzoeken die de resterende veilige voltooiingsvolgordes wegnemen, worden uitgesteld.

Veilig betekent dat een volgorde mogelijk is

Een veilige volgorde ordent threads zo dat elke thread zijn resterende maximale behoefte kan verkrijgen uit de bronnen die nu vrij zijn plus de bronnen die eerdere threads vrijgeven. In een onveilige toestand ontbreekt zo'n gegarandeerde volgorde. Er hoeft nog geen deadlock te zijn: threads kunnen minder dan hun maximum aanvragen of bronnen vroeg vrijgeven.

Planning kan gevaarlijke overlap ook vermijden door ervoor te zorgen dat twee conflicterende taken niet samen hun fasen van brongebruik ingaan. Beide op één CPU plaatsen is op zichzelf onvoldoende, omdat ze nog steeds kunnen worden onderbroken en vervlochten terwijl ze bronnen vasthouden. De vereiste garantie is dat de conflicterende fasen niet overlappen.

Stel de tabellen voor het bankiersalgoritme op

Houd voor elk brontype Available bij. Houd voor elke thread Max, Allocation en Need = Max - Allocation bij. Vergelijk vectoren component voor component, nooit op basis van hun opgetelde totalen.

Gebruik brontotalen (7, 5, 6):

De toewijzingen bedragen samen (4, 3, 4), zodat Available = (3, 2, 2) overblijft.

Doorloop de veiligheidscontrole

Stel Work gelijk aan de beschikbaarheidsvector. Kies een onvoltooide thread waarvan de resterende behoefte binnen de gesimuleerde beschikbaarheid past, doe alsof die wordt voltooid en tel zijn toewijzing weer bij de gesimuleerde beschikbaarheid op.

1. T1 past binnen (3, 2, 2). Teruggeven van (2, 0, 1) levert gesimuleerd beschikbaar (5, 2, 3) op.
2. T0 past. Teruggeven van (1, 1, 0) levert (6, 3, 3) op.
3. T2 past. Teruggeven van (1, 1, 2) levert (7, 4, 5) op.
4. T3 past. Teruggeven van (0, 1, 1) levert (7, 5, 6) op.

Elke thread wordt in deze simulatie voltooid, dus de toestand is veilig. De gesimuleerde beschikbaarheid neemt toe met de toewijzing, niet met het maximum: de extra bronnen die tijdelijk voor voltooiing zijn toegekend, worden ook teruggegeven. De nettotoename is dus gelijk aan wat de thread oorspronkelijk vasthield.

Doe alsof je toekent en controleer opnieuw

Een verzoek moet zowel binnen de resterende behoefte van de thread als binnen de beschikbare hoeveelheid passen. Trek het vervolgens af van de beschikbare hoeveelheid, tel het op bij de toewijzing, trek het af van de resterende behoefte en voer de veiligheidscontrole uit op die voorlopige toestand.

Als T2 vanuit de oorspronkelijke tabel (1, 0, 1) aanvraagt, blijft beschikbaar (2, 2, 1) over. T1 kan nog steeds eerst gaan, gevolgd door T0, T2 en T3, dus dit is veilig.

Als T3 daarentegen (2, 1, 1) aanvraagt, blijft beschikbaar (1, 1, 1) over. De resterende behoefte van T3 is (2, 0, 1). Geen enkele thread past: T0 heeft 4 van A nodig, T1 heeft 2 van B nodig, T2 heeft 2 van C nodig en T3 heeft 2 van A nodig. Stel dit verzoek uit ondanks de bronnen die nu vrij zijn.

Elk later verzoek heeft dezelfde controle nodig. Vermijding vereist opgegeven maximale behoeften en een bekend bronmodel en is daardoor geschikter voor voorspelbare gespecialiseerde systemen dan voor algemene toepassingswerklasten.

Een systeem kan een deadlock laten ontstaan, detecteren en ervan herstellen. Het accepteert daarbij dat af en toe werk verloren gaat in ruil voor minder beperkingen op gewone bronverzoeken. Detectie is alleen nuttig als er een uitvoerbare herstelactie is.

Zoek geblokkeerde cycli

Houd bij bronnen met één exemplaar een wachtafhankelijkheidsgraaf bij en zoek naar een cyclus, bijvoorbeeld met een diepte-eerstzoekopdracht. Stel dat de verbindingen T1 → T2, T2 → T3, T3 → T1 en T4 → T2 zijn. T1, T2 en T3 vormen de cyclus. T4 is daarachter geblokkeerd; de uitvoering van T4 zelf kan geen bron vrijgeven die de cyclus doorbreekt.

Bij meerdere exemplaren is een cyclus onvoldoende. Gebruik de beschikbare hoeveelheid, de toewijzing en het huidige openstaande verzoek van elke thread. Stel de gesimuleerde beschikbaarheid aanvankelijk gelijk aan de beschikbare hoeveelheid. Zoek herhaaldelijk een verzoek dat past, simuleer voltooiing en tel de toewijzing van die thread op bij de gesimuleerde beschikbaarheid. Anders dan bij vermijding gebruikt deze controle waar threads nu op wachten, niet hun mogelijke toekomstige maximale behoefte.

De standaarddetector voor bronnen zet aanvankelijk threads opzij die geen bronnen vasthouden: zij kunnen geen vastgehouden bronnen aan een broncyclus bijdragen. Van de threads die bronnen vasthouden, zitten de threads die na de controle onvoltooid blijven volgens het model in een deadlock. Andere threads kunnen nog steeds geen voortgang kunnen maken doordat ze van die verzameling afhankelijk zijn. Door de cyclus en de daarachter geblokkeerde afhankelijke threads apart te houden, kun je een geschikte taak voor herstel kiezen.

Herstel zonder gedeelde toestand te beschadigen

Een systeem kan één of meer processen beëindigen, bronnen terugwinnen door terug te draaien naar een checkpoint, of opnieuw opstarten. Kies welke taken je afbreekt op basis van herstelkosten, prioriteit, al verricht werk en vastgehouden bronnen. Controleer opnieuw nadat je één taak hebt verwijderd: meerdere onafhankelijke cycli kunnen meer dan één herstelactie vereisen.

Een willekeurige thread beëindigen is niet genoeg als daardoor een mutex vergrendeld blijft of een gedeelde structuur half gewijzigd achterblijft. Herstel moet bronnen vrijgeven of reconstrueren en een geldige toestand herstellen. Transactiesystemen kunnen een transactie in een deadlock afbreken omdat terugdraaien deel uitmaakt van hun ontwerp. Een gewone toepassing heeft vaak een gecontroleerde herstart van het proces nodig.

Interpreteer time-outs zorgvuldig

pthread_mutex_timedlock() kan na een uiterste tijd ETIMEDOUT teruggeven. Een waakhond kan een apparaat resetten dat geen voortgang meer meldt. Beide detecteren buitensporig lang wachten; lang wachten kan ook door trage I/O of planning komen. Een time-out is een aanwijzing om onderzoek te doen of te herstellen, geen eenduidige diagnose van een cyclus.

Linux en Windows vinden en herstellen doorgaans geen cycli tussen de eigen vergrendelingen van een toepassing. Het programma moet de gekozen strategie implementeren. Als herstel herhaaldelijk hetzelfde werk kiest om af te breken, kan dat werk worden uitgehongerd, ook al wordt elke afzonderlijke deadlock doorbroken.

Een gebeurtenislus wacht op gebeurtenissen en laat korte afhandelaars op één thread uitvoeren. Het programma kiest expliciet welke gereedstaande gebeurtenis het als volgende afhandelt. Node.js en nginx gebruiken gebeurtenisgestuurde ontwerpen om veel verbindingen te bedienen zonder aan elke verbinding een eigen thread toe te wijzen.

while (1) {
    events = get_events();
    /* handle each ready event, then return to the loop */
}

Synchrone afhandelaars op dezelfde lus worden één voor één uitgevoerd. De gewone instructies van een afhandelaar worden niet door een andere afhandelaar op die lus onderbroken. De lus blijft ervan afhankelijk dat afhandelaars snel terugkeren.

Bouw select-verzamelingen op en controleer ze

select() accepteert verzamelingen descriptoren om te volgen voor lezen, schrijven en uitzonderlijke condities, plus een time-out. Het argument nfds is één groter dan de hoogste gevolgde descriptor. Voor het volgen van descriptoren 3, 5 en 9 is daarom nfds = 10 nodig, niet 3.

FD_ZERO(&readset);
FD_SET(3, &readset);
FD_SET(5, &readset);
FD_SET(9, &readset);
int n = select(10, &readset, NULL, NULL, NULL);
/* If n > 0, test each watched descriptor with FD_ISSET. */

Een null-time-out wacht op gereedheid; een time-out van nul controleert en keert direct terug. select() overschrijft de verzamelingen met de gereedstaande descriptoren, dus bouw ze vóór elke aanroep opnieuw op. Een positieve retourwaarde telt de ingestelde bits in de teruggegeven verzamelingen; een descriptor die in twee verzamelingen gereed is, telt twee keer. Nul betekent dat de time-out is verstreken; −1 betekent een fout.

Gereedheid is geen gegevensoverdracht. Het programma roept nog steeds read() of recv() aan. Het einde van de invoer kan als leesbaarheid verschijnen; een leesbewerking die 0 teruggeeft, betekent dat de andere partij haar zendzijde heeft gesloten. Handel dat resultaat af in plaats van dezelfde beëindigde invoer telkens opnieuw te laten afhandelen.

Houd afhandelaars kort en niet-blokkerend

Stel sockets in op O_NONBLOCK. Wanneer een bewerking niet verder kan, geeft die −1 terug met errno ingesteld op EAGAIN of EWOULDBLOCK, zodat de afhandelaar naar de lus kan terugkeren. De gereedheid kan vóór de bewerking veranderen, dus de niet-blokkerende modus beschermt ook tegen onverwacht wachten na een gereedheidsmelding.

Een blokkerende leesbewerking binnen een afhandelaar vertraagt elke gebeurtenis in de wachtrij. Bij 100 verzoeken in de wachtrij en een blokkerende schijfleesbewerking van 10 ms per afhandelaar wacht het laatste verzoek ongeveer 990 ms voordat zijn eigen leesbewerking begint; de reeks duurt ongeveer 1.000 ms. De thread besteedde het grootste deel van die tijd aan wachten terwijl gereed werk in de wachtrij stond.

Kies een gereedheidsinterface

select() en poll() onderzoeken bij elke aanroep de opgegeven gevolgde verzameling, dus hun werk groeit met de grootte daarvan. Linux biedt epoll; FreeBSD en macOS bieden kqueue. Slechts enkele descriptoren volgen maakt een hoge descriptorwaarde niet veilig voor een fd_set met vaste grootte.

Netwerkgereedheid vertelt een lus wanneer die I/O kan proberen. Gewone schijfbestanden zijn anders: select() en poll() melden ze als gereed, ook als toegang tot hun gegevens nog op de opslag wacht. Dien werk asynchroon in en handel het resultaat later af om andere gebeurtenissen te kunnen blijven bedienen.

Dien in, werk elders verder en haal het resultaat op

POSIX slaat een verzoek voor asynchrone I/O op in struct aiocb. Belangrijke velden zijn aio_fildes voor de bestandsdescriptor, aio_offset voor de bestandspositie, aio_buf voor de bestemming en aio_nbytes voor de aangevraagde lengte.

/* cb describes a read request */
aio_read(&cb);
/* Return to other work. Later: */
int status = aio_error(&cb);
/* EINPROGRESS: still running; 0: succeeded; otherwise an error. */
/* After completion, aio_return(&cb) collects its result. */

aio_read() plaatst het verzoek in de wachtrij en keert terug. Voltooiing is een afzonderlijke gebeurtenis. Wanneer aio_error() voltooiing aangeeft, levert aio_return() het resultaat, zoals het aantal gelezen bytes na een succesvolle bewerking. Een verzoek kan mislukken en een succesvolle leesbewerking kan minder bytes teruggeven dan aangevraagd. Het verzoekrecord en de buffer moeten geldig blijven zolang de bewerking openstaat.

Elk verzoek steeds opnieuw in een korte lus doorzoeken verspilt CPU-tijd. aio_sigevent kan een voltooiingssignaal of callback instellen. Linux io_uring gebruikt indienings- en voltooiingswachtrijen; Windows-I/O-voltooiingspoorten bieden afhandeling op basis van voltooiing. Met deze interfaces kan het programma op voltooid werk reageren zonder voortdurend elk onvoltooid verzoek opnieuw te proberen.

Bewaar de toestand gedurende de tussenliggende tijd

Een geblokkeerde thread bewaart de lokale variabelen van zijn functie op zijn stack. Een gebeurtenisafhandelaar die I/O indient en terugkeert, moet opslaan wat de latere afhandelaar nodig heeft. Deze expliciete administratie is handmatig stackbeheer; de opgeslagen toestand is een voortzetting.

Stel dat een server bestandsdescriptor 12 leest voor een client op socket 7. Bij indiening slaat de server een record op dat het leesverzoek aan socket 7 en de toestand van het antwoord koppelt. Wanneer de voltooiing binnenkomt, vindt de lus het record, controleert het leesresultaat en gaat verder met het sturen van het antwoord naar de juiste client. Afzonderlijke records voorkomen dat de bestemmingen van meerdere openstaande verzoeken door elkaar raken.

De voortzetting moet aan de specifieke bewerking zijn gekoppeld, niet alleen aan een identificatie die later opnieuw kan worden gebruikt. Houd de clientverwijzing geldig totdat de voltooiing is afgehandeld en verwijder het record wanneer de taak klaar is. Deze details over de levensduur vervangen aannames die een rechtlijnige blokkerende functie op zijn stack kan bewaren.

Leesbare syntaxis kan een opschorting verbergen

Callbacks, beloften en async/await automatiseren een groot deel van dit opslaan van toestand. In JavaScript schort const data = await readFile(path); die functie op zolang de I/O openstaat. Ander werk in de lus kan worden uitgevoerd en de functie gaat later verder met haar lokale toestand hersteld.

Asynchroon betekent dat de aanroeper kan doorgaan voordat de bewerking is voltooid. Het betekent niet dat de afhandelaars ervan tegelijk op meerdere processorkernen draaien. Ook geeft CPU-intensieve code na een await daardoor niet automatisch de beurt af: die code bezet de uitvoerende thread totdat ze terugkeert of opnieuw wordt opgeschort.

Een gebeurtenislus past goed bij veel verbindingen die meestal niets doen en af en toe kort werk opleveren. Een threadgebaseerd ontwerp houdt de besturingsstroom en stack van een taak bij elkaar. De beste keuze hangt af van wachttijd, CPU-werk, geheugen en hoe de code zich zal ontwikkelen.

Vergelijk wat elk ontwerp met zich meebrengt

Een chatserver met 50.000 verbindingen die meestal niets doen, kan baat hebben bij gebeurtenisrecords in plaats van een eigen threadstack per verbinding. Een afbeeldingsverwerker die veel rekenwerk per verzoek doet, heeft genoeg werkthreads nodig om de beschikbare kernen te gebruiken; één bezige lus kan die berekeningen niet parallel maken.

Verborgen wachttijden blijven van belang

Een afhandelaar kan vastlopen zonder een duidelijke blokkerende API-aanroep. Toegang tot een pagina die naar schijf is gewisseld, kan een schijfleesbewerking veroorzaken. Tijdens die paginafout wacht de thread van de lus. mlock() kan benodigde pagina's in het geheugen houden als het systeem de gevraagde hoeveelheid vastgezet geheugen toestaat. Alleen expliciete blokkerende aanroepen verwijderen neemt niet elke oorzaak van vertraging weg.

Codewijzigingen kunnen een ander verborgen wachtmoment introduceren. Als een hulpfunctie die voorheen direct terugkeerde gegevens gaat ophalen, moet een gebeurtenisgestuurde aanroeper zijn werk rond een voortzetting splitsen of de aanroep uitbesteden. De stack van een blokkerende thread bewaart al waar de uitvoering moet worden hervat en welke lokale toestand daarvoor nodig is.

Combineer de sterke punten

Een hybride ontwerp houdt de I/O-gereedheid van het netwerk bij in de gebeurtenislus en stuurt blokkerende of CPU-intensieve taken naar een pool van werkthreads. Voltooiingen keren terug naar de lus voor het afhandelen van het antwoord. Node.js gebruikt de threadpool van libuv voor bestandssysteembewerkingen, zodat een asynchrone interface door achtergrondthreads kan worden geïmplementeerd.

Om meerdere kernen te gebruiken, kan een server één gebeurtenislus per kern uitvoeren in afzonderlijke threads of processen. Als die lussen veranderlijke gegevens delen, hebben ze de gebruikelijke vergrendelingen of een ander synchronisatieprotocol nodig. Het voordeel dat geen vergrendeling nodig is, geldt voor synchrone afhandelaars op één lus, niet voor elk deel van een gebeurtenisgestuurde server.

Een taak kan over await heen worden vervlochten

Stel dat er nog één exemplaar op voorraad is. Een afhandelaar controleert de beschikbaarheid, wacht op de betaling en vermindert daarna de voorraad. Terwijl die is opgeschort, kan een andere afhandelaar dezelfde voorraad controleren en ook een betaling starten. Beide controles kunnen slagen voordat een van beide de voorraad vermindert. Er worden geen twee synchrone afhandelaars tegelijk uitgevoerd, maar de volledige controle en wijziging vormen toch geen atomaire bewerking.

Reserveer de voorraad als één gesynchroniseerde toestandsverandering voordat de thread de beurt afgeeft, met een manier om de reservering vrij te geven als de betaling mislukt, of controleer opnieuw onder een protocol dat een tweede verkoop voorkomt. Een mutex vasthouden tijdens lang wachten kan andere voortgangsproblemen veroorzaken, dus ontwerp de toestandsovergang en het herstel daarvan expliciet. Ook bij gebeurtenisgestuurde code moet je beredeneren welke feiten tijdens elke opschorting waar blijven.