Tråder, locks og condition variables

Tråder deler — derfor er de farlige

En prosess kan ha mange tråd-er. De har hver sin egen stack og hvert sitt sett med registre, men deler heap, kodesegmentet, globale variabler og åpne filer. Det er hele poenget: tråder kan utveksle data ved å peke på det samme objektet, uten dyre IPC-kall.

Men delingen er også problemet. Scheduleren kan avbryte en tråd hvor som helst — midt i en addisjon, midt i en linkedlist-oppdatering, midt i et printf. Hvis to tråder mekker på samme variabel og rekkefølgen ikke er styrt, snakker vi om en race condition. Det er den slags feil som krasjer i produksjon én gang i måneden og aldri reproduserer på laptopen din.

Den klassiske telleren

Tenk deg en delt teller counter = 0 og to tråder som hver kjører for i in 0..1_000_000: counter++. Forventet sluttverdi: ƒkorrekt tellerverdi = 2 000 000. Faktisk sluttverdi i en C-versjon uten beskyttelse: gjerne ~1 200 000, og forskjellig hver kjøring.

Grunnen er at counter++ ikke er én instruksjon. Den kompilerer typisk til load → inc → store. Hvis tråd A leser 7, blir avbrutt, tråd B leser 7, B øker til 8 og lagrer, A øker sin 7 til 8 og lagrer — vi har tapt en inkrementering. Det er en race condition i mikro-skala, og den skalerer med scheduler-flaks: jo flere tråder og lengre kjøringer, desto verre.

Kodebiten som leser eller skriver delt tilstand kalles en kritisk seksjon. Målet er mutual exclusion: at høyst én tråd er inne i kritisk seksjon om gangen. Alle synkroniseringsprimitiver vi diskuterer i resten av kapittelet, handler om å bygge mutual exclusion på en eller annen måte.

Atomiske primitiver

Synkronisering kan ikke bygges av vanlige load/store-instruksjoner alene. Hvis to kjerner gjør counter++ samtidig, gir hardwaren ingen garantier om hvem som «vant». Vi trenger spesielle instruksjoner som garanterer udelelighet — atomicity — på tvers av kjerner.

De vanlige primitivene er test-and-set (skriv 1, returner gammel verdi), compare-and-swap (skriv ny verdi bare hvis nåværende er X, returner suksess) og fetch-and-add (legg til, returner gammel sum). Alle er én instruksjon på moderne CPU-er (x86: xchg, cmpxchg, lock add; ARM: ldrex/strex). Disse er fundamentet som alt høyere-nivå synkronisering hviler på.

I tillegg trenger vi memory barriers for å hindre at CPU-en omorganiserer load/store-rekkefølgen. På sterke modeller (x86) er dette stort sett implisitt; på svakere modeller (ARM, RISC-V) må programmereren plassere barrierer manuelt. Bibliotekene skjuler dette, men når du skriver lock-free kode er det din jobb.

Spinlocks og blocking locks

Den enkleste låsen er en spin lock. En tråd som vil inn, spinner i en stram løkke til låsen er ledig. Den implementeres typisk med en atomisk maskininstruksjon — test-and-set eller compare-and-swap — som hardwaren garanterer er udelelig på tvers av kjerner.

Spinlocks er bra på korte kritiske seksjoner: ingen scheduler-rundtur, ingen kontekstbytte. Men de er forferdelige hvis ventetiden blir lang: du brenner CPU på ingenting, og hvis tråden som holder låsen ikke får CPU (uniprosessor uten preemption!) kan spinneren spinne for evig. Aldri spinn på uniprosessor uten preemption — du har designet en deadlock.

blocking lock er motsetningen. Tråden som ikke får låsen, settes til å sove på en venteliste. Når den som holder slipper, vekker OS-et neste i køen. Mer overhead per lock-operasjon, men null bortkasta CPU. Realistiske systemer kombinerer — adaptive locks spinner et lite vindu før de blokkerer. Linux sin futex og Java sin synchronized er begge varianter av dette: spinn et øyeblikk, gi opp og legg deg til å sove hvis det ikke åpner seg fort.

Condition variables — vent på en tilstand

Lås gir gjensidig utelukkelse, men ikke koordinering. Hva hvis en tråd må vente på at en annen produserer noe — for eksempel en consumer som venter på et element i køen?

Svaret er en condition variable. En condition variable er bundet til en lås. Tre operasjoner: wait(cv, lock) slipper låsen og setter tråden til å sove, signal(cv) vekker én ventende tråd, broadcast(cv) vekker alle. Når en tråd våkner fra wait, holder den låsen igjen automatisk.

Bruksmønster: ƒventemønster med condition variable. Først tas låsen. Deretter sjekkes betingelsen. Hvis ikke oppfylt: wait. Når wakeup kommer, sjekkes betingelsen på nytt. Først når den er oppfylt, gjøres jobben — og deretter slippes låsen. Det er fem linjer som ser banale ut, men hver linje er der av en grunn.

Hvorfor while, ikke if?

Den evige fellen. Hvorfor må vi sjekke betingelsen igjen etter wakeup?

Tre grunner. (1) Spurious wakeups: enkelte plattformer kan vekke deg uten at noen signaliserte. (2) Mesa-semantikk: signal markerer bare at noen kan kjøre, ikke at de må kjøre umiddelbart — i mellomtiden kan en annen tråd ha kommet til og spist opp ressursen du ventet på. (3) Robusthet mot fremtidige endringer: hvis koden senere får flere consumers, fungerer while fortsatt; if brekker subtilt.

while (!cond) wait(...) er trygt under alle disse. if (!cond) wait(...) har feil som krasjer i produksjon når en venter ble dyttet inn ekstra. Lær det som en refleks — det er én av de få faste reglene i synkronisering.

Tilsvarende: lost wakeup skjer hvis signalet sendes før mottakeren rakk å kalle wait. Mottakeren sover for alltid. Riktig lock-disciplin — signal sendes mens du holder låsen, mottaker sjekker betingelsen mens den holder låsen — forhindrer dette. Hold låsen rundt hele beslutningen, og rekkefølgen er trygg.

Producers, consumers og signaling

Den enkleste praktiske bruken av condition variables er en bounded queue mellom producer- og consumer-tråder. Producer låser køen, legger inn et element, signaliserer at det er noe der, slipper låsen. Consumer låser, sjekker om køen er tom — hvis ja, wait — ellers ta element, slipp låsen og prosesser.

Når du har én producer og én consumer er det rett frem. Når du har mange av hver, må du tenke nøye gjennom: signal vekker én tilfeldig venter, broadcast vekker alle. Broadcast er trygt men kan gi thundering herd: alle tråder våkner, kjemper om låsen, og bare én får jobben — resten må sove igjen. Signal er mer effektivt men krever at du vet at presis én tråd kan gjøre nyttig arbeid med wakeupen.

Praktisk regel: når én ressurs ble lagt til, bruk signal. Når en delt tilstand endret seg slik at flere ting nå er mulige (typisk: lukkingstilstand for hele systemet), bruk broadcast. Det er ikke alltid åpenbart, men feilvalg gir enten ytelsesproblemer eller deadlock.

Hva gjør en lås god?

ƒkrav til en god lås. Correctness: mutual exclusion er garantert under alle interleavings. Fairness: ingen tråd må vente urimelig lenge mens andre kjører forbi. Low overhead: lock-operasjonen i seg selv må være rask sammenlignet med kritisk seksjon.

De tre dras mot hverandre. Streng FIFO-fairness (ticket lock) gir god rettferdighet, men er treigere enn en MCS-lås på en travel server med mange kjerner. Adaptive locks ofrer litt fairness for ytelse. Linux sine kernel-locks er fine-tunet for hver use case — futex for userspace, spinlock for korte kritiske seksjoner i kernel, rwlock for lese-tunge mønstre, RCU når lesningen må være fullstendig lock-free.

Et siste poeng: synkronisering er et lagdelt verktøy. Atomiske instruksjoner ligger nederst (hardware). På toppen bygger vi spinlocks og blocking locks. På toppen av disse igjen bygger vi condition variables, semaforer og høyere-nivå abstraksjoner som monitors og channels. Hvert lag skjuler kompleksitet, men gir også mer rom for å skyte seg selv i foten — derfor er det å forstå underbygget viktig selv når du bare bruker en mutex.lock() i Rust eller synchronized i Java.