Semaforer, klassiske synkroniseringsproblemer og deadlock

Semaforen som universalverktøy

Dijkstra fant opp semafor i 1965 som en generalisering av låsen. En semafor er en heltallsteller med to atomiske operasjoner: p / wait (også kalt P, eller sem_wait) reduserer telleren hvis den er positiv, ellers blokkerer den tråden. v / signal (V, eller sem_post) øker telleren og vekker eventuelt en ventende tråd.

Formelt: ƒsemaforens vent-operasjon og ƒsemaforens signal-operasjon. To rene linjer, men kraftige nok til å løse de fleste synkroniseringsproblemer du møter.

Initial-verdien bestemmer rollen. En semafor initialisert til 1 er en lås (binær semafor / mutex). Initialisert til 0 er den et rent signal. Initialisert til N er den en ressurspool med N enheter. Samme abstraksjon, helt forskjellige bruksmønstre — det er derfor semaforer er det første generelle verktøyet vi lærer etter den rene låsen.

Bounded buffer — tre-semaforsløsningen

bounded buffer (producer-consumer) er den arketypiske semafor-oppgaven, og den dukker opp på eksamen år etter år. Du har en kø med plass til N elementer. Producers legger inn; consumers tar ut. Begge kan ha flere tråder, og koordinasjonen må holde under alle scheduler-flaks.

Initialisering: ƒinitialisering for buffer av størrelse n. Tre semaforer: - empty-semafor teller ledige plasser, starter på N - full-semafor teller okkuperte plasser, starter på 0 - mutex-semafor (binær) beskytter selve buffer-strukturen, starter på 1

Producer-koden: ƒproducer-mal (semaforer). Consumer-koden: ƒconsumer-mal (semaforer). Resten er detaljer i producer-consumer mønster, men én detalj er kritisk: rekkefølgen sem_wait(empty) før sem_wait(mutex). Bytter du om — sem_wait(mutex) først — kan du havne i deadlock fra feil låserekkefølge. La oss se hvorfor.

Buffer er fullt. Producer tar mutex først (mutex blir 0). Producer prøver sem_wait(empty) — empty er 0, så producer blokkerer mens den fortsatt holder mutex. Consumer kommer for å tømme et element, men kan ikke ta mutex — den er låst. Ingen kommer videre. Klassisk deadlock fra dårlig låserekkefølge, og det er typisk eksamensfellen for dette mønsteret.

Regelen: vent på ressurs først, så på mutex. Slipp mutex først, så signaliser motpart. Det er én av de få faste reglene i synkronisering — og en av de hyppigste tabbene.

Readers-writers

I readers-writers-problemet kan mange lesere holde låsen samtidig, men skrivere må ha eksklusiv tilgang. Tenk database: mange queries kan kjøre parallelt, men én UPDATE må ha alt for seg selv.

Naiv løsning: én skrive-lås, en teller for aktive lesere beskyttet av en separat mutex. Første leser tar skrive-låsen; siste leser slipper den. Skrivere venter på skrive-låsen direkte. Det funker — for korrekthet.

Problemet er rettferdighet. Hvis lesere kommer kontinuerlig, kan skriveren vente for alltid — klassisk starvation. Praktiske implementasjoner introduserer en writer pending-flagg som blokkerer nye lesere når en skriver er i kø. Linux sine rwsem og pthreads sin rwlock gjør dette automatisk, men variansen mellom plattformer er stor: les dokumentasjonen før du antar at biblioteket ditt er rettferdig.

Dining philosophers

Fem filosofer rundt et bord. Mellom hvert par en pinne. For å spise trenger man begge pinnene på hver side. dining philosophers er pedagogisk: hvis hver filosof tar venstre pinne først, så høyre, kan alle fem holde venstre samtidig — ingen får høyre — alle venter — deadlock.

Løsninger illustrerer fire forskjellige angrep: 1. Asymmetri: én filosof tar høyre først. Bryter sirkulær venting. 2. Ressurs-hierarki: nummerer pinnene, ta alltid lavest nummer først. Generalisering av asymmetri. 3. Begrens samtidige spisere (maks 4 om gangen) med en semafor — minst én er garantert å få begge. 4. Forsøk-og-slipp: hvis du ikke får begge, slipp den du har og prøv igjen senere.

Hver løsning angriper en av ƒcoffman-betingelsene for deadlock. Det er pedagogikken: deadlock kan forhindres på flere måter, og valget avhenger av hvilken kostnad du tåler.

Coffman-betingelsene

For at deadlock skal kunne oppstå, må fire ting være sanne samtidig: mutual exclusion (ressursen er ikke delelig), hold and wait (en tråd kan vente mens den holder noe), no preemption (man kan ikke tvinge en tråd til å slippe), circular wait (T1 venter på T2 som venter på Tn som venter på T1).

Bryt én av dem, og deadlock er umulig. I praksis er circular wait enklest å angripe: gi alle ressurser en global rekkefølge og krev at de tas i rekkefølge. Det er hva ressurs-hierarki-løsningen for filosofene gjør. Java-konvensjonen for å nestlede synchronized-blokker — alltid i konsistent rekkefølge på objekt-identitet — er det samme prinsippet i kåpe.

Hold and wait er nest enklest: krev at en tråd ber om alle ressurser den trenger på én gang. Funker, men gir dårlig utnyttelse hvis tråden bare trenger noen av dem til en hver tid.

Deadlock-deteksjon kontra -forebygging

Det er to skoler. Forebygging designer systemet slik at deadlock er strukturelt umulig — bryt en av Coffmans betingelser, og vær ferdig med det. Dette er regelen i sikkerhetskritiske systemer (medisinsk, avionikk, jernbane) der pris på en hang er katastrofal.

Deteksjon lar deadlock oppstå, men sjekker periodisk om grafen over «hvem venter på hvem» har en sirkel. Hvis ja: abort en eller flere tråder, rull tilbake, prøv igjen. Databaser gjør dette rutinemessig — Postgres lar transaksjoner deadlocke og dreper én tilfeldig hvert sekund hvis det skjer. Det er ofte mer praktisk enn å påtvinge global rekkefølge på tusenvis av tabeller.

Det finnes også avoidance (Bankers algorithm), men det krever at du vet maks-behov for alle tråder på forhånd, og er sjelden praktisk utenfor lærebøker.

ticket dispenser-problemet

En variant på producer-consumer som dukker opp i øvinger og eksamener. Kunder kommer inn i banken, trekker et nummer, setter seg ned. Bank-medarbeidere kaller neste nummer. Modellér med fire semaforer: - empty (ledige stoler), starter på N - full (kunder som venter), starter på 0 - mutex for kø-strukturen, starter på 1 - service (signal om at en kunde er klar til betjening), starter på 0

Hver kunde-tråd venter på empty, tar mutex, legger seg i køen, slipper mutex, signaliserer full, og venter så på service. Hver bank-medarbeider venter på full, tar mutex, plukker kunde, slipper mutex, signaliserer empty og deretter service. Symmetri og asymmetri på samme tid — det er den slags problem semaforer er gode til, og som er nesten umulige å løse riktig uten å bruke dem.

Monitors — semaforen pakket inn

I språk med høyere abstraksjonsnivå støter du sjelden på P/V direkte. Java sin synchronized, Python sin with lock:, C# sin lock { ... } er alle monitors: en låst seksjon kombinert med en eller flere condition variables. Hoare og Brinch Hansen designet konstruksjonen for å gjøre semaforbruk vanskeligere å misbruke.

En monitor består av: (1) tilstand som er innkapslet i objektet, (2) prosedyrer som automatisk holder objektets lås mens de kjører, (3) condition variables for å vente på interne predikater. Du kan ikke glemme å unlocke; språket setter inn try/finally for deg. Du kan ikke gjøre kritisk operasjon utenfor låsen; tilstanden er ikke synlig.

Men under hetten: en binær semafor (mutex) og en eller flere venteliste-semaforer (condition variables). Forskjellen er sikkerhetsnett, ikke kapasitet — alt en monitor kan, kan en semafor også, og omvendt.

Når semaforer ikke er nok

Semaforer er kraftige, men feilbarlige. Glemmer du én sem_post, henger systemet for alltid. Bytter du om to operasjoner, får du deadlock. Eksamen-rettelse bygger på dette: 90 % av feilene ligger i feil rekkefølge eller manglende post — alt annet er flaks.

Høyere-nivå abstraksjoner som monitors (Hoare, Brinch Hansen), channels (Go, CSP), async/await (Rust, JS) og software transactional memory skjuler semafor-mekanikken bak typesikre konstruksjoner. Men under hetten er det fortsatt P og V — så å forstå semaforen er å forstå koordinasjon i det hele tatt. Og når kompilatoren eller runtime-en ikke kan hjelpe deg lenger — som når du jobber i C eller skriver din egen kernel — er det semaforer du må stole på.