I värsta fall exekveringstid - Worst-case execution time

Den värsta utförandetiden ( WCET ) för en beräkningsuppgift är den maximala tid som uppgiften kan ta att utföra på en specifik hårdvaruplattform .

Vad den används till

Exekveringstid i värsta fall används vanligtvis i tillförlitliga realtidssystem , där förståelse av programvaran för värsta fall är viktigt för tillförlitlighet eller korrekt funktionellt beteende.

Som ett exempel kan ett datorsystem som styr beteendet hos en motor i ett fordon behöva svara på insignaler inom en viss tid. En komponent som utgör svarstiden är den tid det tar att köra programvaran - därför om programvarans värsta fall kan utföras, kan systemets konstruktör använda detta med andra tekniker som schemaläggningsanalys för att säkerställa att systemet svarar snabb nog.

Medan WCET potentiellt är tillämpligt på många realtidssystem, används i praktiken en säkerhet för WCET huvudsakligen av realtidssystem som är relaterade till hög tillförlitlighet eller säkerhet. Till exempel, i luftburen programvara krävs viss uppmärksamhet på programvara enligt DO178B avsnitt 6.3.4. Den ökande användningen av programvara i bilsystem driver också behovet av att använda WCET -analys av programvara.

Vid utformningen av vissa system används WCET ofta som en ingång till schemaläggningsanalys , även om en mycket vanligare användning av WCET i kritiska system är att säkerställa att de förtilldelade tidsbudgetarna i ett partitionsplanerat system som ARINC 653 är inte kränkt.

Beräkning

Sedan de inledande dagarna med inbäddad dator har inbyggda mjukvaruutvecklare antingen använt:

  • end-to-end-mätningar av kod, till exempel utförda genom att ställa in en I/O-stift på enheten till hög i början av uppgiften och till låg i slutet av uppgiften och använda en logisk analysator för att mäta den längsta pulsen bredd, eller genom att mäta i själva programvaran med processorklockan eller antalet instruktioner.
  • manuell statisk analysteknik som att räkna monteringsinstruktioner för varje funktion, slinga etc. och sedan kombinera dem.

Båda dessa tekniker har begränsningar. Mått från ände till ände lägger en stor börda på mjukvarutestning för att uppnå den längsta vägen; räkningsinstruktioner gäller endast enkel programvara och hårdvara. I båda fallen används ofta en felmarginal för att redogöra för otestad kod, approximationer av hårdvaruprestanda eller misstag. En marginal på 20% används ofta, även om det är mycket lite motivering som används för denna siffra, med undantag för historiskt förtroende ("det fungerade förra gången").

Eftersom mjukvara och hårdvara har ökat i komplexitet har de drivit behovet av verktygsstöd. Komplexitet blir alltmer ett problem i både statisk analys och mätningar. Det är svårt att bedöma hur bred felmarginalen ska vara och hur väl testad mjukvarusystemet är. Systemsäkerhetsargument baserade på ett högvattenmärke som uppnås vid testning används ofta, men blir svårare att motivera eftersom mjukvaran och hårdvaran blir mindre förutsägbara.

I framtiden är det troligt att ett krav för säkerhetskritiska system är att de analyseras med både statiska och mätbaserade metoder.

Överväganden

Problemet med att hitta WCET genom analys motsvarar stoppproblemet och är därför inte lösbart i allmänhet. Lyckligtvis, för den typ av system som ingenjörer vanligtvis vill hitta WCET för, är programvaran vanligtvis välstrukturerad, kommer alltid att avslutas och är analyserbar.

De flesta metoder för att hitta ett WCET innefattar approximationer (vanligtvis en avrundning uppåt när det finns osäkerheter) och därför anses i själva verket det exakta WCET ofta vara ouppnåeligt. Istället ger olika tekniker för att hitta WCET uppskattningar för WCET. Dessa uppskattningar är vanligtvis pessimistiska, vilket innebär att det uppskattade WCET är känt för att vara högre än det verkliga WCET (vilket vanligtvis är vad man önskar). Mycket arbete med WCET -analys går ut på att minska pessimismen i analysen så att det uppskattade värdet är tillräckligt lågt för att vara värdefullt för systemdesignern.

WCET -analys avser vanligtvis utförandetiden för en enda tråd, uppgift eller process. På modern hårdvara, särskilt flerkärnig, påverkar dock andra uppgifter i systemet WCET för en given uppgift om de delar cache, minneslinjer och andra maskinvarufunktioner. Vidare bör uppgiftsplaneringshändelser som blockering eller avbrott övervägas i WCET -analys om de kan inträffa i ett visst system. Därför är det viktigt att överväga i vilket sammanhang WCET -analys tillämpas.

Automatiserade metoder

Det finns många automatiska metoder för att beräkna WCET utöver de manuella teknikerna ovan. Dessa inkluderar:

  • analytiska tekniker för att förbättra testfall för att öka förtroendet för änd -till -slut -mätningar
  • statisk analys av programvaran ("statisk" mening utan att köra programvaran).
  • kombinerade tillvägagångssätt, ofta kallad "hybrid" -analys, en kombination av mätningar och strukturanalys

Statisk analysteknik

Ett statiskt WCET -verktyg försöker uppskatta WCET genom att undersöka datorprogramvaran utan att köra den direkt på hårdvaran. Statiska analystekniker har dominerat forskningen i området sedan slutet av 1980-talet, men i en industriell miljö var änd-till-slut-mätmetoder standardpraxis.

Statiska analysverktyg arbetar på hög nivå för att bestämma strukturen för ett programs uppgift, antingen på en bit källkod eller demonterad binär körbar . De arbetar också på en låg nivå, med hjälp av tidsinformation om den verkliga hårdvaran som uppgiften kommer att köra på, med alla dess specifika funktioner. Genom att kombinera dessa två typer av analyser försöker verktyget ge en övre gräns för den tid som krävs för att utföra en given uppgift på en given hårdvaruplattform.

På den låga nivån kompliceras statisk WCET-analys av närvaron av arkitektoniska funktioner som förbättrar processorns genomsnittliga prestanda : instruktion/ datacacher , grenprediktion och instruktionsrörledningar , till exempel. Det är möjligt, men allt svårare, att fastställa snäva WCET -gränser om dessa moderna arkitektoniska särdrag beaktas i den tidsmodell som analysen använde.

Certifieringsmyndigheter som European Aviation Safety Agency förlitar sig därför på modellvalideringssviter.

Statisk analys har resulterat i bra resultat för enklare hårdvara, men en möjlig begränsning av statisk analys är att hårdvaran (i synnerhet CPU: n) har nått en komplexitet som är extremt svår att modellera. I synnerhet kan modelleringsprocessen introducera fel från flera källor: fel i chipdesign, brist på dokumentation, fel i dokumentation, fel i modellskapande; allt leder till fall där modellen förutsäger ett annat beteende än det som observeras på verklig hårdvara. Vanligtvis, där det inte är möjligt att exakt förutsäga ett beteende, används ett pessimistiskt resultat, vilket kan leda till att WCET-uppskattningen är mycket större än vad som uppnås vid körning.

Att få en noggrann statisk WCET-uppskattning är särskilt svår för flerkärniga processorer.

Det finns ett antal kommersiella och akademiska verktyg som implementerar olika former av statisk analys.

Mätning och hybridtekniker

Mätbaserade och hybridmetoder försöker vanligtvis mäta körtiden för korta kodsegment på den verkliga hårdvaran, som sedan kombineras i en högre nivåanalys. Verktyg tar hänsyn till programvarans struktur (t.ex. slingor, grenar) för att skapa en uppskattning av WCET för det större programmet. Motiveringen är att det är svårt att testa den längsta vägen i komplex programvara, men det är lättare att testa den längsta vägen i många mindre komponenter i den. En värsta fallseffekt behöver bara ses en gång under testet för att analysen ska kunna kombinera den med andra värsta fall i analysen.

Vanligtvis kan de små delarna av mjukvaran mätas automatiskt med hjälp av tekniker som instrumentering (lägga till markörer till programvaran) eller med hårdvarustöd som felsökare och CPU -hårdvaruspårningsmoduler. Dessa markörer resulterar i ett spår av körning, som inkluderar både sökvägen som togs genom programmet och den tidpunkt då olika punkter utfördes. Spåret analyseras sedan för att bestämma den maximala tid som varje del av programmet någonsin har tagit att utföra, vad den maximala observerade iterationstiden för varje slinga är och om det finns några delar av programvaran som är otestade ( kodtäckning ).

Mätbaserad WCET-analys har resulterat i bra resultat för både enkel och komplex hårdvara, även om den i likhet med statisk analys kan drabbas av överdriven pessimism i flerkärniga situationer, där effekterna av en kärna på en annan är svåra att definiera. En begränsning av mätningen är att den är beroende av att observera de värsta effekterna under testning (även om det inte nödvändigtvis är samtidigt). Det kan vara svårt att avgöra om de värsta effekterna nödvändigtvis har testats.

Det finns ett antal kommersiella och akademiska verktyg som implementerar olika former av mätbaserad analys.

Forskning

De mest aktiva forskargrupperna finns i Sverige (Mälardalen, Linköping), Tyskland (Saarbrücken, Dortmund, Braunschweig), Frankrike (Toulouse, Saclay, Rennes), Österrike (Wien), Storbritannien (University of York och Rapita Systems Ltd), Italien ( Bologna), Spanien (Cantabria, Valencia) och Schweiz (Zürich). Nyligen har temat tidsanalys på kodnivå fått mer uppmärksamhet utanför Europa av forskargrupper i USA (North Carolina, Florida), Kanada, Australien, Bangladesh (MBI LAB och RDS), Saudiarabien-UQU (HISE) LAB) och Singapore.

WCET Tool Challenge

Den första internationella WCET Tool Challenge ägde rum under hösten 2006. Den organiserades av Mälardalens universitet och sponsrades av ARTIST2 Network of Excellence on Embedded Systems Design. Målet med utmaningen var att inspektera och jämföra olika tillvägagångssätt vid analys av den värsta utförandetiden. Alla tillgängliga verktyg och prototyper som kan bestämma säkra övre gränser för WCET: s uppgifter har deltagit. De slutliga resultaten presenterades i november 2006 vid ISoLA 2006 International Symposium i Paphos , Cypern.

En andra utmaning ägde rum 2008.

Se även

Referenser

  1. ^ " Det värsta utförandetidsproblemet-översikt över metoder och undersökning av verktyg ", Wilhelm, Reinhard, et al., ACM Transactions on Embedded Computing Systems (TECS), Vol. 7, nr 3, 2008.
  2. ^ "Arkiverad kopia" (PDF) . Arkiverad från originalet (PDF) 2011-10-01 . Hämtad 2010-08-15 .CS1 maint: arkiverad kopia som titel ( länk )
  3. ^ "Arkiverad kopia" . Arkiverad från originalet 2012-02-16 . Hämtad 2008-08-16 .CS1 maint: arkiverad kopia som titel ( länk )

Artiklar och vitböcker

externa länkar