Timp de execuție în cel mai rău caz
Timpul de funcționare, în cel mai rău caz, denumit în mod obișnuit Timpul de execuție al celui mai rău caz în engleză (WCET), este timpul de care are nevoie un program de computer pentru a-și finaliza execuția pe o anumită platformă hardware . Valoarea sa este fundamentală în analiza sistemelor în timp real , în special pentru sistemele critice .
Definiție
Timpul de execuție al celui mai rău caz al unui anumit program de computer este o valoare constantă calculată în etapa de proiectare, care depinde de programul însuși și de configurația hardware a sistemului. Acest lucru îl diferențiază de complexitatea de calcul , care nu depinde de hardware-ul specific sau de implementarea algoritmului particular. Este definit ca timpul maxim care trece între începutul execuției sarcinii și sfârșitul acesteia, fără a lua în considerare orice prevenire , luând în considerare toate intrările posibile permise de program [1] . În acest timp, totuși, trebuie luate în considerare toate interferențele cauzate de alte procese active în sistem, de exemplu coliziuni în accesul la cache . Cunoașterea exactă a WCET sau cel puțin una dintre aproximările sale pesimiste este fundamentală pentru a demonstra corectitudinea temporală a unui sistem în timp real .
WCET poate fi exprimat ca o unitate de măsură continuă (cum ar fi a doua sau un multiplu al acesteia) sau discret (cum ar fi numărul de cicluri de ceas ).
Alte perioade de execuție aferente
Alte acronime utilizate în mod obișnuit în literatura științifică pentru a identifica anumite perioade de execuție sunt [2] [3] :
- BCET - Best-Case Execution Time: timpul de executare în cel mai bun caz
- ACET - Timp mediu de executare a cazului: timpul de execuție în cazul mediu
Metoda de estimare
Metodele de estimare WCET pot fi clasificate în patru categorii [4] [5] :
- SDTA: Determinist, static
- MBDTA: Determinist, bazat pe măsuri
- SPTA: Probabilistic, static
- MBPTA: Probabilistic, bazat pe măsuri
Dintre cele patru, doar primele două categorii sunt de fapt folosite în sisteme critice și certificabile , în timp ce a doua două sunt utilizate în prezent doar în mediul academic . MBDTA poate fi utilizat în scopuri practice numai pe arhitecturi hardware foarte simple și software-uri nu foarte complexe.
SDTA
Analiza Static Deterministic Timing (SPTA) se bazează pe cunoștințe detaliate despre software și hardware, în special despre caracteristicile lor temporale. Graficul control-flux al programului a cărui WCET urmează să fie calculat este analizat pentru a găsi cea mai proastă cale în termeni de timp.
Complexitatea de calcul a algoritmilor utilizați pentru această analiză este limita majoră în utilizarea abordărilor statice pe arhitecturi complexe de procesor. Pentru a depăși această problemă, unele simplificări hardware sunt introduse în analiză. De exemplu, dacă există o memorie cache , miss este întotdeauna presupusă. Aceste simplificări reduc timpul necesar analizei, dar înrăutățesc estimarea WCET, care devine astfel pesimistă.
MBDTA
Tehnica Analizei determinării bazate pe măsurare (MBDTA) constă în măsurarea directă a timpului de execuție al sistemului în sine și utilizarea maximului observat ca WCET. Această abordare nu necesită analize hardware și software complexe, deoarece timpul de execuție este măsurat direct.
Cu toate acestea, pentru a vă asigura că această tehnică este sigură și nu subestimează WCET, este necesar să vă asigurați că ați vizitat toate stările hardware și că ați vizitat toate căile (sau cel puțin cele mai rele) ale graficului de control al fluxului . Obținerea acestei certitudini este problema majoră a tehnicii MBDTA, iar tehnicile actuale necesită un efort de a împărtăși analizele SDTA.
SPTA
MBPTA
Notă
- ^ Björn Franke, Lecture 11: Worst-Case Execution Time ( PDF ), la inf.ed.ac.uk , Universitatea din Edinburgh. Adus pe 5 ianuarie 2020 .
- ^ (EN) Reinhard Wilhelm, Jakob Engblom, Andreas Ermedahl, Niklas Holsti, Stephan Thesing, David Whalley, Guillem Bernat, Christian Ferdinand, Reinhold Heckmann, Tulika Mitra, Frank Mueller, Isabelle Puaut, Peter Puschner, Jan Staschulat, Per Stenstrom, The Problema timpului de execuție al celui mai rău caz - Prezentare generală a metodelor și studiului instrumentelor , în Tranzacții pe sisteme de calcul încorporate , vol. 7, nr. 3, ACM, mai 2008, p. 53, DOI : 10.1145 / 1347375.1347389 .
- ^ X. Guo, M. Boubekeur, J. McEnery și D. Hickey, ACET Based Scheduling of Soft Real-Time Systems: An Approach to Optimize Resource Budgeting , în International Journal of Computers and Communications , vol. 1, nr. 3, 2007.
- ^ J. Abella, D. Hardy, I. Puaut, E. Quiñones, FJ Cazorla, On the Comparison of Deterministic and Probabilistic WCET Estimation Techniques , in 26th Euromicro Conference on Real-Time Systems , IEEE, 2014, DOI : 10.1109 / ECRTS .2014.16 .
- ^ Augusto Vega, Pradip Bose, Alper Buyuktosunoglu, Rugged Embedded Systems: Computing in Harsh Environments , Morgan Kaufmann, 2016, ISBN 9780128026328 .
