Tillståndsmaskiner 20/11/2016

I samband med arbete på masterdelen av SerialNet behövde jag åter igen ta fram mjukvara som hanterar sitt tillstånd utifrån serier av inkommande event. En klassisk lösning för detta är tillstådsmaskiner. De har varit en stapelvara inom elektronik och programmering i många år. De har välkända för och nackdelar.

Några exempel är:

  • Välkänd modell för att koppla isär programflödet från lagrade state. (icke blockerande)
  • Bra på att hantera kod som har många naturliga flöden istället för ett huvudflöde.
  • Events är och lätta att serialisera för att passa mellan processer och trådar. Lätt att dela upp programmet.

Några välkända nackdelar:

  • Saknas naturligt stöd i C/C++. Snuttifiering av kod. Man hoppar runt väldigt mycket.
  • De ökar i kompexitet snabbt med storlek. Antalet kopplingar ökar O(events * tillstånd)
  • Ofta kan modellen upplevas som 'trång'. Det blir många tillstånd för lite funktionalitet.

De fungerar ofta bra för maskingenererad kod. I det läget ser utvecklaren de grafiska diagrammen och koden automatgenereras. Tyvärr är den typen av verktyg sällan billiga/lämpade för mindre prototypprojekt där koden ändras ofta. Jag har själv använt dom rätt så flitigt då de ofta kan hjälpa till att undvika andra problem. Har tidigare tagit fram ett ramverk för dessa för handskriven kod baserat på idén "ett state är en funktion". Ursprungliga idén kommer från Miro Samek.

Trådar vs Events.
Några inledande idéer kring vad de är bra för. En av de grundläggande frågorna som delar upp utvecklare i grupper är 'trådar' vs 'events'. Ofta finns det flera parallella aktiviteter som pågår i ett program. Problemdomänen brukar vanligtvis ha rätt mycket oberoende uppgifter som man vill lösa. Samtidigt så är språken C/C++ i grunden sekvensiella till sin natur, då de modellerar en exekveringsenhet som utför det instruktionsflöde som programmet har. De primitiver språket har i form av loopar och funktioner är ett sätt att gruppera funktionalitet. Men språket är i grunden fortfarande seriellt.
Trådar är den primitiv som tillåter modellering av samtidig exekvering. Varje tråd får var sin uppsättning med register, programräknare och en egen stack. Sedan ser det ut som om varje tråd oberoende utför sina uppgifter. Så förespråkare av trådar för modellering av domänspecifik parallelism tycker ofta att en tråd ska utföra varje domänspecifik oberoende uppgift.

Sedan finns det andra lägret som även tittar på den extra komplexitet som trådar innebär. Med trådar behövs synkronisering med t.ex. mutexes, atomic etc. Dessa är dyra för hårdvaran att utföra samt har en del designproblem som gör det svårt att garantera att inte 'deadlocks' inträffar.
I grund och botten är en tråd en abstraktion över en exekveringsenhet, inte en abstraktion uppe i problemdomänen. Används de för finmaskigt, resulterar detta i rätt kraftiga prestandaproblem med ökat tryck på cachar och nödvändingheten att dela kod/data mellan olika exekveringsenheter.

Själv lutar jag åt eventhållet på lägre nivåer i programmet. Trådning tar man till när man har lite större mängd kod som behöver isoleras från annan kod, eller har latencykrav.

Så för en modul eller del av ett program brukar jag grovt dela in koden i 'lågnivådelar' som enbart  är rak kod utan blockerande anrop och utan större vägval i koden. Väldigt 'imperativt' eller 'peka med hela handen' typ av kod.
Nästa nivå upp där sker mycket av den tidsbaserade logiken. Här passar tillståndsmaskiner bra. Genom att de inte blockerar tråden, kan flera ligga parallelt och sköta den delen av problemdomänen se är skapade för. De är eventbaserade. Det ger möjligheten att lättare flytta runt dom utan att det får följdverkningar på övriga koden. Överst ligger main eller en tråd-main och driver en scheduler som distribuerar körtiden för tråden. Detta är enda stället som man sover i någon större utsträckning.

Ovanstående visar en uppdelning utifrån 'callstack' perspektiv med main överst och anrop nedåt. Rent lagermässigt och med logiska beroenden i koden, ser det annorlunda ut. Schedulern är en lågnivåkomponent och interfaceklasser bildar botten i denna uppdelning.

Åter till tillståndsmaskinerna. Klassiska platta tillståndsmaskiner blir snabbt för krångliga. Det finns ett antal förbättringar som ökar deras användbarhet:

  • Entry/exit events. Vid varje tillståndsbyte genereras dessa. De tillåter enklare resurshantering inom states via RAII.
  • Interna eventköer. Har man dessa tillåts man att posta events till sin egen maskin. Då kan man lättare samla kod under extra event handlers. Köer undviker också 'reentrancyproblem' när de skickar event till varandra. Ser man sedan till att postfunktionen är trådsäker är det en utmärkt trådgräns.
  • Hierarkiska tillståndsmaskiner. Tillåter att states kan existera i varandra och att olika states kan bevaka olika events.

Med dessa förbättringar kan man lösa meningsfulla problem och ha en översiktlig kodbas. Hierarkiska tillståndsmaskiner beskrevs först av Harel på 80 talet och han kallade dem 'StateCharts'. Senare i UML så kallas de tillståndsmaskiner men är definerade som hierarkiska med entry/exit events.

Idén med Statecharts är att ett tillstånd (kallat bastillstånd) kan ha ett antal undertillstånd. När ett undertillstånd är aktivt och ett event kommer in, så kollar man först efter en eventhanterare i undertillståndet. Finns inte det, så får bastillståndet försöka hantera det. Det kan finnas flera undertillstånd till ett bastillstånd och man kan hoppa runt bland dessa. Detta fungerar äver rekursivt vidare med godtyckligt djup.
Stora fördelen är att event som alltid kan komma och som ska behandlas lika kan hanteras i ett bastillstånd och då kan undertillstånden begränsas till de event som rör dem.

Nog om teorin bakom StateCharts. Med dessa funktioner är de rätt användbara. Så frågan är,  hur beskriver vi dom i C++ kod? Vilka primitiver i C++ passar här och på vilket sätt?

Tillstånd är i grunden data. De ligger över tid och fungerar som en behållare av funktionalitet som vi vill använda när tillståndet är aktivt. Till det kommer extra data som håller koll på vilket tillstånd är aktivt.
Event är egentligen en händelse, men tillsammans med själva händelsen följer ofta med en del data. Själva hanteringen av Events (event handlers) är dock mer funktionslikt. Så när ett event skickas in behövs kod för att utvärdera vad ska hända för varje tillstånd.
Tittar vi på en klass i C++ är detta en samling data samt funktioner. Den har också en kontruktor/destruktor.
Det är klart lockande att låta konstruktor/destruktor modellera entry / exit funktioner.

Eventhanterare är naturliga funktioner. Hur vill vi göra detta? Jag använder en klass för Events. Sedan behöver denna innehålla något sätt att skilja på olika typer av events. Jag kommer använda en 'enum' för att enumerera olika typer. Naturlig kan tyckas att göra subklasser av en basklass Event. Detta har dock provats förr. Det introducerar prestandaproblem då det tvingar fram dynamisk allokering av Events samt dynamic casts. Med intern eventkö är heapallokering svår att undvika.
Grundproblemet är att man får 'double dispatch' på både state och eventtyp. C++ har bara 'single dispach' med
virtuella funktioner. Det de brukar landa i är en 'if / else' kratta med 'dynamic_cast<>' på eventtyperna. Detta är uruselt i C++ ur ett prestandaperspektiv. Planen är att detta ska fungera i embedded så väljer enum istället.

Så med eventtyper i form av enums vi skulle behöva koppla denna enum till olika medlemsfunktioner. Inte helt lätt
att få till automatiskt. Jag väljer istället att varje state får en 'event' funktion, sedan får användaren frihet att titta på eventobjektet och välja metod för dispatch till olika eventhanterare. En enkel 'switch' fungerar ofta bra. I eventet kan man låta en smart_ptr följa med om man absolut vill ha olika klasser för olika eventtyper.

Så, hur ska understate och basstate modelleras?
Flera har försökt med arv. Detta är dock fel. Räcker med att titta på livstid för objektet. Ett basstate har en strikt större livstid än alla sina understates. I arv är livstiden samma för basklass som för subklass.

En variant är också att substate instansieras som medlemmar i basstate. I detta läget kommer livstiden för substate i alla fall rymmas inom basstate. Men vi behöver forfarande kunna hoppa runt mellan substates inom ett basstate. Det innebär construction/destruction. Så rena medlemmar funkar inte, ev. någon form av pekare med new/delete. Kan tänka oss en union av substates inom basstate och sedan explicita anrop till placement new/delete. Detta kan fungera. union ser till att utrymmet blir rätt till största objektet. Sedan placement new / delete. Nu är unions lite röriga. Det är nog en framkomlig väg, men jag har valt en annan.

Lagring av aktiva states kan bättre liknas vid en programstack. För varje funktionsanrop läggs en ny stacknivå till ovanpå. Alla överliggande stacknivåer måste bort innan en viss stacknivå kan tas bort. Så en stack med de för stunden aktiva tillstånden fungerar bra. Med detta blir eventhantering rättfram. Anropa event() på varje state från toppen till botten tills en signallerar att eventet har hanterats.

Konsekvenser:
Så vi har följande:

  • Event : Små objekt av en gemensam typ med en enum som anger eventtyp. Propageras genom kopiering genom eventköer.
  • States: Skapas från klasser, konstruktor/destruktor ger entry/exit events. event levereras till en event() funktion.
  • Vi har en stack med de för stunden aktiva states.
  • En huvudklass 'StateChart' där vi postar events och som äger alla states.

Här kan man notera att för en viss nivå, är enbart ett enda state aktivt vid varje tillfälle. Det destrureras innan det nya statet konstrueras. Det öppnar en optimeringsmöjlighet. Vi vill undvika dynamisk minnesallokering varje gång
vi byter state. Det jag gör är att reservera ett minnesblock för varje nivå av samma storlek som det största statet på den nivån (ung. som union gör). Sedan vid övergångar andvänds 'placement new / delete' för att skapa objekt. Det har ett par fördelar:

  • Prestanda : en enkel övergång innebär ett anrop till en destruktor och en konstruktor. Vi rör inte heapen.
  • Säkerhet : Ingen risk för 'out of memory'. I miljöer som inte tål heapallokering efter startup är detta fortfarande möjligt.

Med denna optimering borde jag kunna få prestanda som liknar den jag hade i min tidigare funktionspekarbaserade approach. Tittar man på C++ metod för att bygga objekt så är minnesallokering och sedan konstruktörer. Med allokeringen är det bara ett funktionsanrop kvar. En fördel med att använda en klass för states är livstidshantering. Vi kan lägga till egna data och objekt som medlemmar till klassen. De konstrueras och destrueras tillsammans med klassen. Så C++:s idiom med RAII fungerar väldigt bra här.

Ett basstate är ansvarigt för en operation och har understate som utför den. Supportdata kan då skapas i t.ex.
basstate och så städas de upp automatiskt när det är klart. Med stöd att underklasser kan få tillgång till basstate via pekare/referens så kan de operera på data där. Det kan liknas med att passa en pekare/referens till en funktion vid funktionsanrop.
En skillnad mot min tidigare implementation med funktionspekare så behöver inte ramverket generera events för entry/exit. Så ramverket behöver aldrig röra själva eventen. Så det är valfritt om användaren vill ha en enum i sin eventklass.

Rent praktiskt har jag implementerat detta i SerialNet koden och ligger på github. Så vill man titta närmare finns koden där. Funderar på att ta ut den till ett eget repository då den är allmänt användbar. Är idag skrivet i C++14. Tror däremot de flesta koncept skulle fungera bra i C++98. Behöver då byta ut en del 'using' mot 'typedef' och 'auto' mot kontreta typer. Det som kan ställa till det är att jag kapslar in 'new' i funktionsobjekt för att få type-erasure. Använder lamdas och std::function där, men det borde gå att bygga explicita klasser som gör samma sak.