MultiTasking

Uit RoboWiki
Ga naar: navigatie, zoeken

Inleiding

Bij de besturing van een robot is het vaak nodig om meerdere dingen tegelijk te doen. Bijvoorbeeld tijdens het rijden in de gaten houden of er op de stopknop wordt gedrukt. Of terwijl we wachten op de reactie van de ultrasoon ping, de wand blijven volgen en de encoders uitlezen.

Een deel van deze taken, zoals het uitlezen van de encoders, zijn wellicht zo tijdkritisch dat we een interrupt of hardware gebruiken om deze goed uit te voeren. Voor een enkele specifieke taak is het prima om de normale programma-uitvoering even te onderbreken. Maar we kunnen niet iedere taak een eigen interrupt geven. Maar wat hebben we wel voor opties?

Opties

Preëmptieve multitasking

De meest voor de hand liggende optie is het gebruik van een echt operating system, zoals Linux. Door oplossingen als de Raspberry Pi en Beaglebone is dit een reële, betaalbare optie. Multi-tasking in operating systemen is gebaseerd op zogenaamd 'preëmptieve multitasking'. Dit houdt in dat een interrupt wordt gebruikt om de uitvoering van een taak te onderbreken en de 'task scheduler' te starten. Het eerste wat de scheduler doet, is de 'toestand' van de onderbroken taak opslaan. Vervolgens kijkt de scheduler in zijn lijst met lopende taken en kiest, op basis van o.a. de prioriteit, welke taak aan de beurt is. De 'toestand' van deze taak wordt teruggezet en de scheduler geeft de controle aan de gekozen taak.

De toepassing van preëmptieve multitasking is niet beperkt tot operating systemen, zoals Linux. Er zijn speciale 'Real Time Operating Systems' (RTOS) die - meer dan het voor algemeen gebruik ontworpen Linux - geoptimaliseerd zijn om snel en voorspelbaar ('real time') te reageren, bijvoorbeeld op signalen uit de omgeving. Ook binnen het RTOS domein vind je veel verschillen, van aangepaste Linux systemen tot library die meegelinkt worden met je programma. Een voorbeeld van deze laatste is freertos.

Door het meelinken van een RTOS worden multitasking functies als het ware ingebouwd in je programma. De taken wordt geprogrammeerd als gewone functies en de met de RTOS functies kun je taken starten, prioriteiten en nog veel meer. In de rest van dit artikel nemen we dit type RTOS als uitgangspunt.

State machines

Een andere aanpak is om 'multitasking' in te bouwen in de taken zelf, door ze zo op te zetten dat ze snel de benodigde actie uitvoeren en daarna de taak weer wordt verlaten. De volgende keer dat de taak wordt aangeroepen gaat deze verder waar hij gebleven was.

Een hulpmiddel om 'multitasking' te ontwerpen en te bouwen zijn 'State machines'. Hierbij verdeel je de taak op in 'States', de toestand waarin een taak zich kan bevinden. Of, anders gezegd, waar we mee bezig zijn. Een toestand kan bijvoorbeeld zijn 'wand volgen' of 'een bocht naar links maken'. Aan iedere toestand worden acties gekoppeld, bijvoorbeeld 'motoren bijsturen op basis van afstand tot de wand' bij wandvolgen. Daarnaast kent een toestand 1 of meer condities, waaraan de overgang naar een andere toestand is gekoppeld. Bijvoorbeeld 'als er er een obstakel voor de robot staat' dan 'ga naar toestand STOP'.

Het inbouwen van multitasking in je programma vraagt vooraf enig denkwerk (technisch ontwerp). Een alternatief in C is de library ProtoThreads, die het grootste deel van dit werk uit handen neemt en waardoor de taak nauwelijks anders opgezet wordt dan een 'normale, blokkerende' taak.

Processors met uitgebreide periferie

Moderne µ-processors zijn uiterst veelzijdig en hebben in hun hardware dikwijls een uitgebreide periferie die allerlei taken kunnen afhandelen met minimale belasting van de CPU. Bijvoorbeeld de bekende STM32 ARM Cortex reeks, die erg populair zijn geworden door de goedkope "Discovery" bordjes :

* Een uitgebreide reeks 16-bit timers die zeer flexibel gebruikt kunnen worden : 
* PWM voor motorregeling, maar evengoed voor Servo-aansturing.
* 10-bit ADC, die via DMA automatisch werkt zonder CPU tussenkomst.
* Communicatie via verschillende USART, I2C, SPI die ook via DMA kunnen lopen.
* Kwadratuurencoder uitlezing via een 16-bit timer, zonder tussenkomst van de CPU.
* Input capture via een Timer, bijvoorbeeld voor het uitlezen van een SRF04 US sensor.

Dankzij deze periferie is het relatief eenvoudig om simultane taken op een perfect voorspelbare manier af te handelen.

De afweging

Op basis van het bovenstaande is de keuze simpel: het is natuurlijk een stuk eenvoudiger om wat routines mee te linken om taken te laten uitvoeren, dan dat je iedere taak zo ontwerpt dat deze multitasking is. De keuze lijkt nog duidelijker als je je realiseert dat bij state machines iedere taak het hele systeem kan blokkeren.

Helaas is het toch niet zo simpel...

Efficient

Veel argumenten in het voordeel van state machines hebben betrekking op efficiency van de oplossing:

  • De methode gebruikt geen extra (RAM) geheugen
  • Het programma wordt niet groter
  • Het 'schakelen' tussen taken gaat zeer snel

Kortom, het resultaat is een compact en snel programma. Maar hoe belangrijk is dat voor ons? Processoren worden steeds sneller, krijgen meer geheugen en tegelijk lijkt de prijs eerder te dalen dan te stijgen. Kortom, bovenstaande argumenten zijn alleen van belang als we een bestaande (krappe) processor hebben. Of als je 100.000 robots laat maken en die euro verschil in kostprijs zelf moet betalen...

Voorspelbaar

Een belangrijk afweging is of het systeem voorspelbaarheid (deterministisch) is. Simpel gezegd: reageert het systeem altijd hetzelfde?

Zoals we gezien hebben wordt met state machines de multitasking ingebouwd in iedere taak. Dit maakt de taken voorspelbaar, het systeem zal onder dezelfde omstandigheden steeds hetzelfde reageren. Natuurlijk kunnen er bugs in het systeem zitten waardoor dit niet het gedrag is wat je wilt. En soms zal het systeem onder (schijnbaar) dezelfde omstandigheden anders reageren. Maar... dit wordt niet veroorzaakt door het 'taak-systeem'.

Preëmptieve multitasking heeft mogelijk wel invloed op de voorspelbaarheid. Dit komt omdat de uitvoering van de taak op ieder willekeurig punt kan worden onderbroken en vervolgens een andere taak - ook op een willekeurig punt onderbroken - weer verder gaat. Een paar voorbeelden.

  • Een taak zet iedere seconde twee leds direct na elkaar aan en, na een seconde, weer uit. Je zou dus denken dat beide leds tegelijk aan en uit gaan. Het kan echter zijn dat de taak wordt onderbroken, nadat de eerste led is ingeschakeld, maar voor de tweede led wordt ingeschakeld. Er worden nu eerst andere taken uitgevoerd en pas als onze taak weer aan de beurt is, bijvoorbeeld 100ms later, wordt de tweede led ingeschakeld.
  • Taak 1 leest iedere 50ms de sensor uit, werkt het gemiddelde bij en slaat deze op. Taak 2 berekent iedere 100ms de gewenste motorsnelheid op basis van de sensor waarde. Natuurlijk is het zo geconfigureerd dat taak 2 na taak 1 wordt gestart. Echter, als taak 1 door omstandigheden iets meer tijd nodig heeft, wordt deze onderbroken voordat de sensorwaarde is opgeslagen. Taak 1 gebruikt nu een oude sensor-waarde voor haar berekening.

Of, nog erger:

  • De oude sensor-waarde is 500, wat opgeslagen wordt in 2 bytes met de waarden 1 (*256) en 244. De nieuwe sensor-waarde is 550 ( 2 (*256) en 38). Nadat de waarde 1 veranderd is in 2 wordt de taak onderbroken. Taak 2 ziet nu de waarde 2 (*256) en 244 en rekent dus met 756!

Als programmeur sta je er normaal normaal niet bij stil dat een 16-bit variabele op een 8 bit systeem in twee keer wordt bewerkt, maar dat is in dit geval wel relevant. Daarbij komt dat een dergelijk probleem maar heel af en toe zichtbaar is. Immers, de kans dat een taak juist op dit punt wordt onderbroken is klein - 1 op 1.000 tot 1 op 1.000.000 en als het al optreedt, is het niet eenvoudig om het symptoom - een afwijkende sensorwaarde - te herleiden tot deze oorzaak.

Opmerkingen:

  • Ook bij gebruik van interrupt service routines moet je rekening houden met dit soort issues.
  • Een kans van, zeg, 1 op 10.000 lijkt misschien te verwaarlozen, maar als een taak iedere milliseconde wordt uitgevoerd, gaat het gemiddeld eens per 10 seconden fout. Of dat een probleem is hangt van van de gevolgen van de fout...

Prestaties

Bij prestaties spelen de volgende factoren een rol:

  • hoe snel (en voorspelbaar) reageer je op een gebeurtenis
  • welk percentage van je tijd ben je met 'het echte werk' dingen bezig.

Een RTOS is over het algemeen goed uitgerust om snel en voorspelbaar te reageren op gebeurtenissen. En het zorgt ervoor dat belangrijke taken automatisch voldoende tijd krijgen. De resterende tijd staat ter beschikking van minder belangrijke taken.

Als je gebruik maakt van state machines moet je dit zelf regelen. Als je snel wilt reageren, moet je zorgen dat je de betreffende taak vaak aanroept en dat andere taken niet te lang duren. En... vaak aanroepen van een taak terwijl er geen werk is, kost tijd die je niet aan 'het echte werk' kunt besteden.

Conclusie

Het gebruik van state machines lijkt in eerste instantie ingewikkeld en vraagt meer tijd bij de ontwikkeling. Maar uiteindelijk geeft het een deterministisch (voorspelbaar, te begrijpen) systeem.

Een RTOS geeft, in ruil voor wat extra resources, een eenvoudig ogende oplossing. Maar, met name op de grensvlakken met andere processen, is het goed opletten. Uiteraard kun je voorkomen dat bovenstaande problemen krijgt met een RTOS. Maar je moet dit wel goed doen, anders gaat het zo af en toe eens fout. En zoek dan maar eens uit hoe dat komt...

De conclusie is dan ook dat beide hun toepassingen hebben.

Stel je een eenvoudige robot voor met de volgende taken:

  • iedere 100ms uitlezen van een ultrasoon sensor
  • iedere 5ms uitlezen van de bumper sensor
  • iedere 50ms de motoren aansturen
  • het 'high-level-plan' is de roborama opgave T-tijd
  • binnen 100ms reageren als er op een knopje wordt gedruk

Deze functies zijn ieder op zich relatief eenvoudig. Ze kunnen daardoor ook relatief eenvoudig in een state machine worden omgezet en - los van elkaar - worden getest. De aansturing van de taken is standaard (lezen senosren, verwerken, aansturen motoren) en dus prima te overzien en zelf te doen.

Een meer complexe robot kan de volgende taken hebben:

  • de camera wordt uitgelezen en het plaatje verwerkt; afhankelijk van het beeld duurt de verwerking tussen 50 en 200ms
  • iedere 5ms uitlezen van de bumper sensor
  • iedere 50ms de motoren aansturen
  • het 'high-level-plan' is naar een heldere lamp te rijden en daarbij obstakels te omzeilen
  • binnen 100ms reageren als er op een knopje wordt gedruk

De camera taak zou wel eens complex kunnen zijn en daardoor niet zo eenvoudig in een statemachine te stoppen. Daarnaast bestaat de kans dat, naast de camera taak, ook de high-level-planner sterk varieert in looptijd. Kortom, een of twee complexe taken en een beperkt aantal interfaces tussen taken, dus een RTOS lijkt een goede keuze.