Basic personligt

Daniel Brahneborgs blogg

Multitrådad statemaskin

Statemaskiner (ja, det heter säkert “tillståndsmaskiner” på svenska, men datorer ska prata engelska och det där ordet blir alldeles för svenskt) har länge varit ett av mina favoritverktyg för att implementera komplexa beteenden. En sådan består av ett antal tillstånd varav ett är det man startar i. Varje indata gör att man flyttar till ett annat tillstånd. Indatat kan vara ett tecken, en händelse som en nytt inkommande data, eller något annat. I varje tillstånd vet man exakt vilket indata som är giltigt, och när indatat tar slut är det enkelt att veta om sekvensen var ok genom att kolla om tillståndet man är i är godkänt som sluttillstånd.

I en multitrådad värld blir det lite mer komplicerat. Till att börja med krävs en mutex, så att man inte får flera trådar som pillar på statemaskinens fält samtidigt. Lämpligen har man då en handle_event(), som kollar vilket tillstånd man är i och uppdaterar maskinen till dess nya tillstånd, allt inom en låst mutex.

I vissa övergångar ska det hända någonting. Socketar ska öppnas eller stängas, data ska hämtas eller skickas iväg, eller vad det nu är. Inga problem, det är ju bara att lägga in det i handle_event? Nej, för vissa saker kan ta lång tid att utföra. Om det görs av handle_event, kommer det ske i den tråd som triggade eventet, och låsa den tråden så att den inte kan göra någonting annat.

Istället kan man då ha en loop i en separat tråd, som bara anropar statemaskinens run() tills den har nått ett sluttillstånd. Eventet “connect” flyttar maskinen till tillståndet “do_connect”, och när run() körs nästa gång, kommer den utföra uppkopplingen. När den är klar, går den vidare till tillståndet “connected”. På det sättet görs uppkopplingen bara en gång, och av rätt tråd. Å andra sidan gör det att andra trådar som vill skicka något event till den här statemaskinen kommer stanna tills uppkopplingen är klar, och så är vi tillbaka ungefär där vi började. Fast bara nästan.

Här kan man använda asynkrona funktioner istället, som antingen kan polla med jämna mellanrum eller få en callback från när de är klara. När anropet är gjort, stannar man i ett väntetillstånd tills dess att callbacken kommer. Frågan är vad man gör i den tråden under tiden. Den kan ju inte anropa run() hela tiden, för då har vi en busywait som stjäl cpu i onödan.

Den enklaste lösningen på detta är en “condition variable”. Statemaskinens tråd (den som anropar run-funktionen) hänger då på en sådan när den inte har något bättre för sig. När det kommer ett nytt event, avslutas handle_event med att väcka den som väntar på variabeln (dvs run-tråden). Det listiga är att anropet som gör att run-tråden börjar vänta, samtidigt släpper maskinens mutex, för annars skulle ju de andra trådarna inte komma in i handle_event. Efteråt är mutexen låst i run-tråden igen. I handle_event får man då: lock, update state, signal cond, unlock.

I run är det lockande att göra ungefär likadant: lock, check state, do stuff, kanske wait on cond, unlock. Symmetriskt och bra. Tyvärr fungerar det inte, eftersom det där “do stuff” kan resultera i ett man postar något event tillbaka till sig själv. Det går inte, eftersom maskinens lås redan är taget. Alltså flyttar man allt “do stuff” till efter “unlock”. Låset är då taget bara under den tid det tar att tilldela en variabel eller två, och sannolikheten blir exakt noll att låset är inblandat i någon form av deadlock.

En annan lösning, om huvuddelen av ens event kommer via sockets, är att använda något som libevent. Istället för att hänga på en cond, hänger man då i epoll eller liknande. Tyvärr går det inte att hänga i epoll och på en cond samtidigt, så för att handle_event ska kunna väcka huvudtråden använder man en intern pipe. Huvudtråden väntar på sina vanliga sockets och den här pipen, och om andra trådar vill att maskinen ska vakna så skriver de en byte på pipen efter att ha uppdaterat maskinens tillstånd. Maskinen vaknar då, läser det nya datat, gör det som behövs för dess nya tillstånd, och så hänger den igen.

June 5th, 2016 Posted by Daniel Brahneborg | blogg | no comments

|