Annons

Minska overhead med Preemption-Threshold-planering

Många realtidssystem kräver säkra svarstider, även vid sämsta tänkbara förutsättningar. John A. Carbone från Express Logic, Inc. beskriver här en planeringsteknik för ARM-baserade system som gör det möjligt att undvika onödiga kontextbyten och klara tidsgränserna.

ARM-baserade embeddedsystem finns nu nästan överallt – i smarttelefoner, på surfplattor, medicinska enheter och i industriell utrustning. ARM-arkitekturen har börjat dominera dessa realtidsapplikationer, främst därför att de kan ge utvecklare många olika programverktyg som stöd, och lösningar som passar bra för realtidssystem.

Programmen i dessa system består vanligtvis av en samling applikationsuppgifter eller trådar som måste svara i realtid på externa händelser och som hanteras av realtidsoperativsystem (RTOS).

Hårda realtidssystem kräver att svarstidsgränserna kan uppnås med absolut säkerhet, även vid sämsta möjliga omständigheter. Realtidsoperativsystem använder vanligtvis förebyggande planeringsregler för att garantera att de viktigaste trådarna får omedelbar uppmärksamhet så att de kan klara av tidsgränserna. Men planering av åsidosättning kan leda till betydande overhead för kontextbyten i vissa situationer.

Preemption-Threshold-planering (PTS) är en annorlunda planeringsteknik för ARM-baserade systemutvecklare, och som gör det möjligt för dem att eliminera onödiga kontextbyten och därmed minska overhead, samtidigt som man upprätthåller förmågan att klara av tidsgränser, även under sämsta möjliga omständigheter.

Koncept för realtidsoperativsystem (RTOS)
Innan vi utforskar Preemption-Threshold-planering, är det viktigt att förstå och kunna några grundläggande koncept för RTOS-teknik.
I den här artikeln använder vi ordet ”tråd”, men vissa RTOS kan använda ordet ”uppgift”. I de flesta fall är dessa synonyma. En tråd är en funktion eller ett program som verkställer tills det är klart, eller tills det blir avbrutet av någonting annat. Ibland kan trådar avbryta sig själva medan den väntar på någon slags händelse. Trådar delar ett adressutrymme och körs så gott som samtidigt på samma CPU. I flerkärniga system kan trådar köras samtidigt, några på en kärna och andra på andra kärnor. Trådar används till att strukturera ett program i modulära delar, vilket gör det enklare att hantera applikationen och så att den kan utvecklas av flera teammedlemmar.

Trådar kan ha flera körningslägen:
1. REDO – betyder att tråden är redo att köras, inte blockerad, och väntar inte på något eller behöver något, men den kör inte några instruktioner just nu.
2. KÖR – betyder att tråden kör instruktioner
3. AVBRUTEN – kallas också för ”blockerad”, eller ”väntar”, vilket betyder att tråden inte är redo att köras därför att den väntar på något – kanske ett meddelande i en kö, en semafor, en tidsgräns etc.
4. AVSLUTAD – betyder att tråden har slutfört bearbetningen och inte längre kan köras.

Trådar blir tilldelade olika prioriteter som anger deras relativa betydelse och i vilken ordning de får åtkomst till processorn om de alla är REDO att köras. I allmänhet är prioriteterna angivna som heltalen 0-till-N, antingen 0-hög eller 0-låg. I den här rapporten använder vi 0 som högsta prioritet och högre nummer för att ange lägre prioriteter. Varje tråd blir tilldelad en prioritet och prioriteten kan ändras dynamiskt. Flera trådar kan få samma prioritet, eller så kan de alla få en unik prioritet.


Fig 1. Ett kontextbyte är nödvändigt för åsidosättning, men involverar många steg och betydande bearbetning, enligt exemplet för en vanlig RTOS

När en tråd verkställs och en annan tråd med högre prioritet blir REDO att köras, avbryter eller ”åsidosätter” RTOS tråden som körs och ersätter den med tråden som har högre prioritet. Den här processen kallas för ett ”kontextbyte”. I ett kontextbyte sparar RTOS kontextet för den tråd som verkställs i dess stack (stapel) och hämtar kontext för den nya tråden, från dess stack (stapel), samt laddar den i processorns register och programräknare. Därmed byts kontextet för den tråd som verkställs från det ena till det andra.

Fig 1 visar en analys av de åtgärder som vanligtvis krävs för att en RTOS ska utföra ett kontextbyte. Kontextbytet är relativt komplext och kan ta mellan 50–500 cykler, beroende på RTOS och processor. Därför är det viktigt att optimera kontextbytet i en RTOS och minimera behovet av sådana åtgärder. Det är det som är målet med Preemption-Threshold-planering.

I allmänhet är RTOS-planerare förebyggande. Det betyder att de ser till att den tråd som har högsta prioritet och som är REDO att köras är den enda som får köras och de andra får vänta. RTOS-planerare kan också utföra resursallokering för flera trådar som har samma prioritet. I sådana fall verkställs varje tråd tills den är klar och sedan körs nästa tråd. Det är också möjligt att ge varje tråd en viss procent av processortiden, i stället för att låta den köra klart eller avbrytas frivilligt. RTOS-planeraren utför kontextbyten vid behov och gör det möjligt för trådar att inaktiveras, att frivilligt avstå från CPU-användning till en tråd med lägre prioritet, eller att avsluta och lämna trådpoolen som väntar på CPU.

Åsidosättning för också med sig potentiella problem som utvecklaren måste undvika eller kunna hantera på rätt sätt. Det första är trådstrypning, när en tråd aldrig får verkställas därför att en tråd med högre prioritet aldrig avslutas. Utvecklare bör undvika alla tillstånd där en tråd med hög prioritet kan hamna i en oändlig loop (slinga), eller en situation där tråden tar upp oönskat mycket processortid som förhindrar att andra trådar får tillräckligt med åtkomst till processorn.

Prioritetsomkastning är den situation då trådar med hög prioritet väntar på en delad resurs, men resursen är upptagen av en tråd med låg prioritet och tråden med låg prioritet kan inte få tid att avsluta användningen av resursen på grund av att den åsidosätts av en tråd med medelhög prioritet.

Slutligen är den vanligaste nackdelen med åsidosättningsplanering kanske själva overhead. I situationer med många kontextbyten kan overhead bli stor. Även om alla RTOS försöker optimera sina kontextbyten tar dessa åtgärder som regel 50–500 cykler, enligt illustrationen ovan. Det är ofta möjligt att undvika kontextbyten helt och hållet, vilket visas med PTS. I ett kommande exempel undersöker vi precis ett sådant system med några verktyg som gör det möjligt för oss att se och mäta overhead och visa skillnaden som PTS kan åstadkomma.

Preemption-Threshold-planering (PTS)
I Preemption-Threshold-planering definierar vi en prioritet som måste överskridas för att kunna åsidosätta en tråd. PTS förhindrar vissa åsidosättningar och eliminerar därmed vissa kontextbyten, vilket minskar overhead.

Vanligtvis kan vilket tråd som helst som har en högre prioritet än den tråd som körs åsidosätta den. Men med PTS kan en tråd som körs bara åsidosättas om den tråd som åsidosätter den har en högre prioritet än åsidosättningströskeln för den tråd som körs. I ett system som helt kan åsidosättas skulle åsidosättningströskeln vara lika med trådens prioritet. Genom att ställa åsidosättningströskeln högre än trådens prioritet kommer åsidosättning av trådar som har prioriteter mellan dessa två värden inte att tillåtas.


Fig 2. Om man tilldelar en åsidosättningströskel som är högre än en tråds prioritet förhindrar det att den åsidosätts av trådar som har prioriteter mellan dessa värden

I fig 2 ser vi att en tråd med prioritet 20 normalt skulle gå att åsidosättas av en tråd som har prioriteten 19, 18, 17, 16 o s v (alla prioriteter högre än 20). Men om dess åsidosättningsströskel ställs in på 15 kan bara trådar som har en högre prioritet än 15 (lägre siffra) åsidosätta tråden. Trådar däremellan – med prioriteterna 19, 18, 17, 16 och 16 – kan inte åsidosätta, men trådar som har prioritet 14 och högre (lägre siffra) kan det. Åsidosättningströskeln är valfri och kan anges för en enstaka tråd, alla trådar eller inga trådar. Om den inte anges är åsidosättningströskeln för en tråd alla värden som är högre än dess prioritet. Men med en åsidosättningströskel kan en tråd förhindra åsidosättning av trådar med högre prioritet, upp till en viss gräns, över vilken åsidosättning tillåts.

Prestandafördelar med PTS
För att illustrera de prestandafördelar som kan uppnås med Preemption-Threshold-planering, jämför vi en metod med fullständig åsidosättningsplanering med en som använder PTS och vi mäter konsekvenserna av varje vad gäller kontextbyte och dataflöde. För den här utredningen beaktar vi en enkel producent-konsument-applikation, med en tråd som skickar meddelanden och tre trådar som hämtar dem från meddelandeköer. Vi loggar alla händelser (händelseloggning är en RTOS-kapacitet som gör det möjligt att analysera loggade händelser efteråt, och göra en tidsrelevant upptäckt av omkostnader och dataflöde under en viss realtidsperiod) så att vi kan se vad som pågår. Sedan visar vi de loggade händelserna, räknar antalet kontextbyten, mäter prestanda och drar slutsatser från detta.

För att jämföra metoder beaktar vi två fall:
1. Fall 1 använder metoden där allt kan åsidosättas, med prioriteterna 1, 2, 3 och 4 tilldelade.
2. Fall 2 använder Preemption-Threshold-planering för att se hur den kan användas för att minska antalet kontextbyten. För att göra detta tilldelar vi tråd_D åsidosättningströskel 1, vilket betyder att den bara kan åsidosättas av en tråd som har en prioritet som är högre än 1. I det här systemet har ingen tråd en prioritet som är högre än 1 (= 0) och därför åsidosätts inte tråd_D av tråd A, B eller C.

Vi har kört den här exempelapplikationen på ett ARM Cortex-M3-baserat system från STMicroelectronics, med realtidsspårningsverktyget ThreadX RTOS and TraceX från Express Logic. Resultaten visas nedan och här är vad de illustrerar.

I Fall-1 börjar tråd_D skicka sina meddelanden till varje kö, men så snart den skickar det första meddelandet hoppar tråd_A in för att hämta det (se fig 3). Varför? Därför att tråd_A har högre prioritet än tråd_D, och tråd_A är nu redo att köras eftersom kön den väntade på nu är tom. När tråd_A läser dess meddelande, väntar det återigen på en tom kö, och tråd_D återupptas. Tråd_D skickar nu ett meddelande till tråd_B, som omedelbart åsidosätter tråd_D o s v genom alla nio meddelandena. Detta slutför en cykel. I den här cykeln skickades nio meddelanden, nio hämtades, och 18 kontextbyten registrerades.

I fall 2 avbryts inte tråd_D medan den skickar sitt meddelande (se återigen fig 3). Tråd_D fortsätter att skicka meddelanden tills det stöter på en kö som är full och väntar tills kön är tom igen. Observera att när tråd_D väntar återupptar den inte förrän tråd A, B och C har blockerats, eftersom tråd_D har prioritet = 4 och inte kan åsidosätta någon annan tråd. Resultatet skiljer sig avsevärt från fall 1. I stället för 18 kontextbyten ser vi bara fyra kontextbyten. När vi jämför kontextbyten ser vi fall 1 med 18 och fall 2 med fyra.


Fig 3. Fall 1 visar kontextbyten med fullt åsidosättningsbar planering. Fall 2 visar samma trådar, men Preemption-Threshold-planering används

Genom att välja en komplett cykel, som består av sändning och mottagning av nio meddelanden (tre för varje konsumenttråd, A, B och C) kan vi räkna antalet timertick i den cykeln (se fig 4). Vi ser att fall 1 tar 7 531 tick, medan cykeln för fall 2 är 4 420 tick.


Fig 4. Genom att välja en komplett cykel kan vi mäta antalet timertick och tillhörande realtid som förflöt medan cykeln verkställdes

Fig 5 visar en sammanfattning av kontextbyten och resulterande flöde.


Fig 5. En sammanfattning av flöde och omkostnader för fall 1 kontra fall 2 visar tydligt fördelarna med PTS i det här exemplet

Om applikationen var ett system som skickade meddelanden skulle vi se en betydande förbättring i prestanda och flöde med Preemption-Threshold-planering, jämfört med fall 1 som helt kunde åsidosättas.

Sammanfattning
Vi har sett hur olika typer av RTOS-planerare fungerar och hur en planerare som helt kan åsidosättas ger maximal responsivitet. Men en planerare som helt kan åsidosätta kan introducera betydande overhead som minskar systemets effektivitet. Å andra sidan kan Preemption-Threshold-planering minska antalet kontextbyten och öka de ARM-baserade systemens prestanda.
John A. Carbone, Express Logic, Inc.

Comments are closed.