Multiprocessering: Undgå Kapløb med Semaforer

De fleste moderne computere i dag er udstyret med mere end én processorenhed, ofte kaldet kerner. For en udvikler kan det være en udfordring effektivt at udnytte flere kerner samtidigt for at fremskynde et programs eksekvering gennem parallel behandling. En af de største udfordringer opstår, når man skal ændre værdien af en variabel i delt hukommelse. Denne artikel introducerer en af de mest almindelige metoder til at overvinde dette problem ved at synkronisere adgangen til delt hukommelse: brugen af fork og semaforer.

Hvad er Parallel Behandling?

Nutidens computere, fra bærbare til stationære, kommer næsten altid med en flerkerneprocessor. Det betyder dog ikke, at al software automatisk kører hurtigere. Kun en lille del af al software udnytter den enorme regnekraft, som moderne maskiner besidder. Årsagen er simpel: at skrive software, der udfører flere opgaver parallelt, er betydeligt mere komplekst end at løse det samme problem sekventielt, altså trin for trin.

Når vi taler om parallel behandling, er de to primære tekniske muligheder for en udvikler multiprocessing og multithreading. Begge tillader eksekvering af flere opgaver samtidigt ved at oprette separate processer eller tråde, der kører uafhængigt af hovedprocessen.

Det er vigtigt at forstå, at i begge metoder kører opgaverne kun reelt "samtidigt" eller parallelt, hvis der er mere end én processorenhed. Hvis du kører flere processer eller tråde på en computer med en enkelt kerne, vil alle opgaver i sidste ende stadig blive udført sekventielt, én efter én, af den samme processor, uden nogen gevinst i ydeevne. Opgavestyringen varetages af operativsystemet, ikke af applikationen, så som udvikler kan man ikke bestemme, hvilken opgave der kører på hvilken kerne.

Udfordringer ved Parallel Behandling

For effektivt at bruge flere kerner skal en udvikler først tilpasse applikationens logik. At køre den samme algoritme på en maskine med flere kerner vil ikke i sig selv give nogen forbedring. Den største udfordring opstår, når disse parallelle processer skal kommunikere eller udveksle information med hinanden, et koncept kendt som Inter-Process Communication (IPC).

En almindelig metode til IPC er at bruge delt hukommelse. I stedet for at sende beskeder frem og tilbage, kommunikerer opgaverne ved at skrive information til et hukommelsesområde, som andre opgaver kan læse fra. Denne metode er ofte hurtigere end beskedbaserede teknikker. Men den kommer med en stor faldgrube: Hvis flere opgaver skriver til den samme delte hukommelse på samme tid, kan de komme i konflikt med hinanden. Dette kaldes en kapløbstilstand (race condition), fordi opgaverne kører parallelt, som løbere i et kapløb, og man kan ikke forudsige, hvilken opgave der "vinder" og skriver sidst. For at undgå dette problem er vi nødt til at synkronisere enhver skriveadgang til den delte hukommelse.

Et Simpelt Problem: Løst med en Enkelt Proces

Lad os forestille os, at vi har en stor liste (et array) af tilfældige heltal mellem 0-9, og vi ønsker at beregne frekvensen af hvert ciffer. Hvor mange 1'ere, 2'ere, 3'ere osv. er der i listen? En simpel løsning i en enkelt proces ville være at gennemløbe hele listen og tælle hver forekomst. For at simulere en mere kompleks beregning, kan vi tilføje en lille pause i hver iteration.

Hvis vi kører denne simple beregning på en liste med 100.000 tal, vil resultatet være korrekt, og det vil tage en vis mængde tid, lad os sige 13 sekunder. Summen af alle frekvenser skal svare til længden af listen (100.000), hvilket fungerer som vores kontrolsum.

Løsning af Problemet med Multiprocessering

For at fremskynde denne beregning ved hjælp af multiprocessering skal vi ændre logikken. I stedet for at én proces gennemgår hele listen, kan vi opdele listen i segmenter og lade hver proces beregne cifferfrekvenserne for sit eget segment. Hvis vi bruger to processer, vil proces #1 arbejde på den første halvdel af listen, og proces #2 vil arbejde på den anden halvdel.

Til at oprette flere processer kan vi bruge systemkaldet fork(). fork() skaber en ny proces ved at duplikere den kaldende proces. Den nye proces kaldes barneprocessen, og den oprindelige kaldes forælderprocessen.

Første Forsøg: Multiprocessering uden Delt Hukommelse

Når vi implementerer denne logik, opdager vi hurtigt et problem. Selvom programmet kører hurtigere (f.eks. 6 sekunder), er vores kontrolsum pludselig 0. Hvorfor? Problemet er, at når man "forker" en proces, får hver barneproces sin egen separate kopi af alle variabler fra forælderprocessen. Når barneprocesserne opdaterer deres frekvenstællere, påvirker disse ændringer ikke den oprindelige variabel i forælderprocessen. Resultaterne går tabt.

Andet Forsøg: Brug af Delt Hukommelse

For at løse dette skal vi definere vores frekvenstællere i et delt hukommelsesområde, som både forælder- og barneprocesser kan tilgå. Nu kan alle barneprocesser skrive til den samme hukommelse, og deres ændringer kan læses af forælderprocessen. Men når vi kører koden igen, opstår et nyt mystisk problem. Tiden er stadig forbedret, men kontrolsummen er nu forkert, f.eks. 99.988 i stedet for 100.000. Hvad skete der?

Svaret er den førnævnte kapløbstilstand. Flere processer forsøger at skrive til den samme delte hukommelse på nøjagtig samme tid. For eksempel kan to processer begge læse værdien 5 for cifferet '7', begge lægge 1 til (resultat 6), og derefter begge skrive 6 tilbage. Den ene opdatering går tabt. Dette fører til et upålideligt og forkert resultat.

Synkronisering af Hukommelsesadgang med Semaforer

For at undgå kapløbstilstande skal vi sikre, at kun én proces kan skrive til en delt ressource ad gangen. Dette kaldes gensidig udelukkelse (mutual exclusion). En af de mest almindelige teknikker til at opnå dette er ved hjælp af semaforer. Man kan tænke på en semafor som en lås. Før en proces skriver til den delte hukommelse, skal den først "låse" semaforen. Dette blokerer andre processer, der forsøger at gøre det samme. De må vente, indtil den første proces er færdig med at skrive og "låser op" for semaforen igen.

Brugen af semaforer involverer typisk følgende trin:

1. Definer: Opret et nyt semaforsæt.
2. Initialiser: Sæt semaforens startværdi (typisk 1 for ulåst).
3. Lås: Før en kritisk sektion (som at skrive til delt hukommelse), skal processen vente på og låse semaforen.
4. Lås op: Efter den kritiske sektion er afsluttet, frigives eller låses semaforen op.
5. Fjern: Når semaforsættet ikke længere er nødvendigt, skal det fjernes korrekt for at frigive systemressourcer.

Tredje Forsøg: Multiprocessering med Synkronisering

Når vi tilføjer en enkelt semafor til at beskytte vores delte frekvenstællere, ser vi, at resultatet nu er korrekt! Kontrolsummen er 100.000. Men en ny skuffelse melder sig: Ydeevnen er faldet tilbage til de oprindelige 13 sekunder. Hele fordelen ved multiprocessering er forsvundet.

Omkostningerne ved Synkronisering

Denne negative påvirkning på ydeevnen skyldes, at synkronisering har en omkostning. Hver gang en lås sættes eller fjernes, foretages et systemkald, hvilket er en langsom operation. Med vores nuværende logik låser alle processer den samme ene semafor, hver gang de skal skrive. Det betyder, at sandsynligheden for, at en proces skal vente, er ekstremt høj. I praksis har vi tvunget processerne til at skrive én ad gangen, hvilket fjerner fordelen ved parallelisme.

Hvordan kan vi forbedre dette? Løsningen er at bruge flere låse. I stedet for én lås til alle ti ciffertællere, kan vi oprette en lås for hver tæller. Vi definerer et semaforsæt med ti semaforer. Når en proces skal opdatere tælleren for cifferet '7', låser den kun semaforen for '7'. En anden proces kan samtidigt opdatere tælleren for cifferet '3' ved at låse semaforen for '3'. Sandsynligheden for at støde på en låst ressource falder drastisk.

Fjerde og Sidste Forsøg: Optimeret Synkronisering

Ved at implementere et semaforsæt med ti semaforer (én for hvert ciffer) og køre koden igen, opnår vi endelig det ønskede resultat. Kontrolsummen er korrekt (100.000), og eksekveringstiden er markant forbedret, f.eks. 7 sekunder. Vi har opnået både korrekthed og en betydelig ydeevneforbedring.

Sammenligning af Resultater

Konklusion

Multiprocessering kræver en fuldstændig ny overvejelse og ofte et redesign af applikationens logik. Processer skal kunne kommunikere med hinanden for at dele resultaterne af deres arbejde. Når delt hukommelse bruges til dette, skal hukommelsesadgang synkroniseres for at undgå uforudsigelige resultater forårsaget af kapløbstilstande. Synkronisering, uanset om det er via semaforer eller andre mekanismer som mutexes, har en omkostning, der ofte kan opveje ydeevnegevinsten fra multiprocessering. For at reducere denne omkostning må en udvikler omhyggeligt overveje forskellige muligheder for designet af synkroniseringsmekanismerne for at minimere flaskehalse og maksimere parallel eksekvering.

Ofte Stillede Spørgsmål

Hvad sker der, hvis jeg kører flere processer på en computer med én kerne?

På en computer med en enkelt kerne vil operativsystemet skifte hurtigt mellem de forskellige processer (kontekstskift). Dette giver en illusion af, at de kører samtidigt, men i virkeligheden udføres de sekventielt. Der vil ikke være nogen ydeevneforbedring; tværtimod kan det gøre programmet langsommere på grund af den overhead, der er forbundet med at administrere flere processer.

Hvad er den primære forskel på en proces og en tråd?

En proces er et uafhængigt program med sit eget hukommelsesrum. En tråd er en mindre eksekveringsenhed inden for en proces. Flere tråde inden for den samme proces deler det samme hukommelsesrum, hvilket gør kommunikation lettere, men også øger risikoen for kapløbstilstande, hvis ikke adgangen synkroniseres korrekt. At oprette en ny tråd er generelt hurtigere end at oprette en ny proces.

Hvorfor er "kapløbstilstande" et alvorligt problem?

Kapløbstilstande er alvorlige, fordi de fører til uforudsigelig og ofte forkert opførsel. Fejlen kan være sporadisk og svær at reproducere, hvilket gør debugging ekstremt vanskelig. I kritiske systemer, som f.eks. i finansielle transaktioner eller medicinsk udstyr, kan en kapløbstilstand have katastrofale konsekvenser.

Er semaforer den eneste måde at synkronisere hukommelsesadgang på?

Nej, der findes flere andre synkroniseringsmekanismer. En anden meget almindelig mekanisme er en mutex (mutual exclusion lock), som fungerer som en simpel binær lås (låst/ulåst). Mens semaforer kan tælle og tillade et bestemt antal samtidige adgange, tillader en mutex kun én ad gangen. Valget af mekanisme afhænger af det specifikke problem, der skal løses.