• Lock-Free Programming
• Unit test i den virkelige verden
• Using Files In Unit Tests
• Why Bugs should not be Tracked

Lock-Free Programming

Af Kristian Dupont,
november 2005

Vi ved det godt. Vi udviklere kan ikke blive ved med at sende kravet om bedre performance videre til hardwarefolkene. Moores lov kan ikke blive ved med at holde, og måske er det også udemærket, for strømforbruget og varmeudviklingen i moderne processorer er vokset næsten lige så eksplosivt som hastigheden.
Hvis vi skal blive ved med at yde mere, er der kun én retning: parallelitet. Distribution over flere processorer eller endda maskiner bliver noget vi skal vænne os til at tænke i. Det er ikke let, som de fleste der har arbejdet med multitrådet programmering ved. Der er en række indlysende fordele men også nye problemstillinger af en art som serielt afviklet kode slet ikke støder ind i. Hvor man i seriel programmering er vant til at skulle overholde sin invariant ved afslutningen af en funktion, bliver man nu nødt til at være opmærksom på de indre dele af funktionen ligeså. Da man ikke kan vide hvornår en delt resource bliver tilgået udefra, kan man ikke bare arbejde hensynsløst med den. Man bliver nødt til at låse den mens man bruger den, og pænt bede andre om at vente på at få lov.

Man kunne bruge et udviklingsmiljø som analogi. Hvis man er én udvikler på et projekt kan man hele tiden rette vilkårlige steder uden fare, og man kan altid stole på at den kode man arbejder med ser ud som man selv ser den. Så snart man bliver flere der skal dele arbejdet opstår der en række problemer. Man løser disse ved at indføre et versionskontrolsystem. Systemet SourceSafe er i sit udgangspunkt låsebaseret, hvilket vil sige at man låser sine source filer og dermed forhindrer andre i at rette i dem indtil man er færdig, og låser dem op igen. Dette løser problemet - man kan frit rette i en fil som man har låst, uden at frygte at andre skulle lave rettelser i samme fil samtidigt.
Til gengæld får man en række nye problemer. Det kan være irriterende nok at skulle til at arbejde med en fil og så erfare at den er låst af en anden og derfor være tvunget til at vente på vedkommende. Hvis man selv har en opgave der er af højere prioritet kan man faktisk blive offer for det, der kaldes priority inversion, der vil sige at vigtigt arbejde forsinkes af mindre vigtigt arbejde der bruger samme resource. Værre bliver det hvis personen er taget hjem eller måske på ferie, uden at have låst den givne fil op.
Andre versionskontrolsystemer som CVS og Subversion baserer sig på et andet paradigme, der minder om lock free programming. I Subversion låser man ikke sine filer - faktisk skal man ikke informere nogen om at man arbejder med dem. Man sørger blot for at have en lokal kopi af den senest opdaterede version når man påbegynder sit arbejde, og når man er færdig, lægger man sine ændringer ind i systemet. Problemet er nu, at en anden kan have lavet ændringer det samme sted i mellemtiden. Systemet kan ikke automatisk afgøre hvorvidt vores ændringer dermed er blevet ugyldige eller ej. Derfor bliver man informeret når man forsøger at lægge sine ændringer ind, og man må så tage stilling til hvad man nu vil gøre. Oftest kan Subversion lave automatisk fletning, men i princippet kan man blive tvunget til at lave sine ændringer forfra så de passer ind i den kode der nu foreligger, hvorefter man må prøve igen osv.

Hvis man skriver lock free kode arbejder man meget efter samme princip. Man laver en algoritme der udfører sit arbejde på en "lokal" kopi af det data den skal arbejde med, hvorefter den forsøger at lægge ændringerne ind i de delte data. Hvis de delte data har ændret sig i mellemtiden, bliver algoritmen nødt til at prøve igen. For at dette kan fungere skal der eksistere en måde at lægge disse ændringer ind i form af en transaktion, således at resultatet altid er veldefineret. Hvis det går godt, er alle nye data blevet lagt ind og går det ikke godt, er intet blevet lagt ind.

CompareExchange er .NET implementationen af det der normalt kendes under navnet compare and swap (forkortet CAS). Denne funktion er speciel idét den udgør et af de primitiver man kan bruge til at programmere lock free med. Der findes andre, men CAS er ret udbredt og det er CAS jeg vil fokusere på i denne artikel. CAS er en atomisk operation, dvs. den kan ikke afbrydes af andre tråde - selv hvis disse afvikles på andre cpu'er.
Det, den gør er meget simpelt, og sikkert lettest illustreret med kode:

 int CompareExchange(ref int Current, int Fresh, int Expected)
 {
     if(Current == Expected)
     {
         Current = Fresh;
         return Expected;
     }
     return Current;
 }

Denne illustration viser en implementation der ikke vil fungere da den ikke er atomisk, men derudover er semantikken den samme. Faktisk kan man ikke programmere en sådan rutine - den skal implementeres i hardwaren (dog kan man simulere den med låse, men så vil man miste den performance gevinst der ellers er). Det er heldigvis sket på alle større platforme, så man kan roligt benytte sig af funktionen. Som det ses, skifter den blot en reference (i dette tilfælde en int) ud med en ny, Fresh, men kun hvis den aktuelle reference, Current svarer til det, man tror den gør (hvilket man indikerer med Expected).
I JDK 5.0 er der tilføjet en package ved navn java.util.concurrent.atomic, der indeholder klasser for atomiske variable, så som AtomicInteger og lignende, der hver har en .compareAndSet() metode.
I C++ er man lidt dårligere stillet da der ikke findes nogen standard implementation af CAS (lige som der ikke findes nogen standard implementation af nogen synkroniseringsmekanisme). Der findes dog platformsspecifikke implementationer - i Windows har man eksempelvis funktionen InterlockedCompareExchangePointer().

Lad os kigge på et simpelt eksempel i C#[1]:

 public class Sensor
 {
     private Sampler sampler;
     private ProbeTemperature probe;
     public Sensor(Sampler sampler, ProbeTemperature probe)
     {
         this.sampler = sampler;
         this.probe = probe;
     }
 
     public void run()
     {
         for(int i = 0; i != 1000; ++i)
         {
             int temperature = probe.GetTemperature();
             NewSample(temperature);
         }
     }
     
     private void NewSample(int temperature)
     {
         RunningAvg initialAvg = sampler.runningAvg;
         RunningAvg newAvg = new RunningAvg(initialAvg, temperature);
 
         System.Threading.Interlocked.CompareExchange<RunningAvg>(ref sampler.runningAvg, 
         	newAvg, initialAvg);
     }
 }

Koden her viser en klasse Sensor, der repræsenterer eksempelvis et termometer. Scenariet er, at man har et antal af disse termometre der hver bidrager med en måling til et fælles gennemsnit. Idéen her er, at en enkelt temperaturmåling ikke er vigtig i sig selv da der hele tiden kommer nye. Derfor vælger vi at smide målingen ud hvis vores "commit" (indlæsning af de nye data) fejler. I eksemplet her laver en sensor 1000 målinger som den forsøger at registrere hos en "sampler", der deles af alle de eksisterende sensorer. Metoden NewSample kaldes når man har foretaget en måling. Denne beregner et nye gennemsnit og forsøger at skifte samplerens gennemsnit ud med det nye beregnede via funktionen CompareExchange. Denne funktion returnerer en reference til den RunningAvg instans der er aktiv i sampleren, efter CompareExchange kaldet er blevet udført.Når vi kalder CompareExchange uden at kigge på resultatet er det fordi vi ikke bekymrer os om hvorvidt det gik godt eller skidt, for vi ved at systemet er i en stabil tilstand. Enten er den nye måling blevet tilføjet og gennemsnittet er blevet tilsvarende justeret, eller også er det ikke, og begge situationer er acceptable. Hvad der ikke havde været acceptabelt var hvis vi havde tilføjet en ny måling men ikke fået justeret gennemsnittet før der var blevet tilføjet en ny måling fra en anden tråd. Det kan imidlertid ikke forekomme da CompareExchange netop sørger for dette ved at sikre sig at det data vi arbejdede med er det samme når vi forsøger at registrere vores nye måling.

I mange situationer ville det dog ikke være acceptabelt at skulle springe en måling eller iteration helt over. Løsningen vil i så fald være at prøve igen, hvilket giver sig til udtryk i en løkke. Den generiske løsning for lock free algoritmik ser således ud:

 Data Expected;
 Data Fresh;
 
 do
 {
     Expected = Current;
     Fresh = Current.Clone();
     
     // Udfør modificering af "Fresh"...
         
 } while(CompareExchange<Data>(ref Current, Fresh, Expected) != Expected);

Denne løkke bliver ved med at forsøge ind til udskiftningen går godt, og den illustrerer faktisk hvordan man kan løse mange problemer uden at bruge låse.

Dog skal man være opmærksom på granulariteten. Hvis klassen Data fra eksemplet er stor og tung, er det måske ikke hensigtsmæssigt at instansiere og klone den gentagne gange for at udføre operationen. Den bedste performance opnåes ved at have en fin granularitet, og det kan derfor være en bedre løsning at dele Data op i mindre dele og kun holde de dele der rent faktisk er delte synkroniserede med denne mekanisme.
Og netop hér bliver det besværligt. For så snart en ændring ikke kan udføres i én transaktion bliver man tvunget til at lave et større regnskab for at sørge for at man ikke efterlader sine data i en ustabil tilstand på noget tidspunkt. Har man for eksempel en dobbelthægtet liste, skal man opdatere to pointere der begge er afgørende for listens tilstand. At implementere sådanne datastrukturer er ikke trivielt og det er noget der forskes meget i. Dog findes der efterhånden pålidelige implementationer af mange generiske datastrukturer som netop lister og lignende.
Sammenlignet med låsebaseret programmering har lock free programmering den fordel at processoren udnyttes bedre hvilket vil sige at man kan opnå en bedre performance. Denne gevindst har dog desuden den omkostning at cpu'en rent faktisk arbejder mere, hvilket efterlader mindre overskud til andre processer der måtte være aktive. Desuden betyder det at cpu'ens strømforbrug forøges, hvilket kan have en betydning hvis man for eksempel laver en server applikation der skal køre i døgndrift (eller blot på en almindelig pc, hvor det vil betyde mere støj fra blæseren!)

Af og til står vi som udviklere over for et nyt paradigme. Af og til kan det være af eget valg. Mange har valgt at lære objekt orienteret programmering fordi de fornemmede at det kunne være en effektiv måde at betragte tingene på. Andre ting bliver man tvunget til at lære. Hvis man skal skrive en client/server applikation kan man være fristet til at lave et framework der abstraherer denne skelnen væk, så man oven på det kan skrive sin kode som man plejer. Hvis man har forsøgt dette vil man vide at det ikke er så let. Man bliver simpelthen nødt til at tænke på en anden måde.
Ligeledes gælder det for kode der skal kunne afvikles parallelt. Sådan et krav kan ændre på strukturen af et program helt op til højeste abstraktionslag, så man skal passe på med ikke at forvente at man blot kan skrive et parallelt fundament og derefter bygge sit program op efter de mønstre som man altid har gjort.
Analogien med versionskontrol er efter min mening et meget godt udgangspunkt. Når flere udviklere arbejder med samme kode skal de passe på ikke at ødelægge den fælles kodebase men kun at lægge ændringer ind der virker med det eksisterende. Dette opnår man ved at tænke i transaktioner - man laver små ændringer der påvirker en isoleret del af systemet. Man kan ikke bare ændre arbitrære data rundt omkring, man samler sine ændringer i blokke. Jo større ændringer man laver og jo længere man er om at indføre sine ændringer i den fælles kodebase, jo større er risikoen for at man får problemer med andres ændringer.
Disse arbejdsmetoder illustrerer faktisk gode tommelfingerregler for kode. Hvis koden overfører data i små isolerede transaktioner forøger man sin exception safety og sandsynligheden for at programmet befinder sig i en veldefineret tilstand. Så selv om det er lettere at skrive kode der benytter låse til at synkronisere med, er det sundt at kende til principperne og eventuelt holde sig til dem så langt som man kan se fornuften i.

[1]Fungerende kildekode til eksemplet her kan hentes fra vores website (temperature-sensor.zip). Koden er skrevet i C# 2.0 og kan bygges og testes med Visual Studio .NET 2005.