Worst-case execution time
Il tempo di esecuzione nel caso peggiore, molto più comunemente chiamato con il termine inglese Worst-Case Execution Time (WCET), è il tempo che un programma informatico necessita per completare la sua esecuzione su una data piattaforma hardware. Il suo valore è fondamentale nelle analisi dei sistemi real-time, specialmente per i sistemi critici.
Definizione
[modifica | modifica wikitesto]Il Worst-Case Execution Time di un dato programma informatico è un valore costante e calcolato a in fase di progettazione, che dipende dal programma stesso e dalla configurazione hardware del sistema. Questo lo differenzia dalla complessità computazionale, che invece non dipende dallo specifico hardware né dalla particolare implementazione dell'algoritmo. Esso è definito come il tempo massimo che intercorre tra l'inizio dell'esecuzione del task e la sua fine, senza conteggiare eventuali preemption, considerando tutti i possibili input ammessi dal programma[1]. In questo tempo devono, invece, essere considerati anche tutte le interference causate da altri processi attivi nel sistema, ad esempio collissioni nell'accesso della cache. La conoscenza dell'esatto WCET o di almeno una sua approssimazione pessimistica è fondamentale per dimostrare la correttezza temporale di un sistema real-time.
Il WCET può essere espresso come unità di misura continua (come il secondo o un suo sotto-multiplo) oppure discreta (come numero di cicli di clock).
Altri tempi di esecuzione correlati
[modifica | modifica wikitesto]Altri sigle comunemente utilizzate nella letteratura scientifica per identificare tempi di esecuzioni particolari sono[2][3]:
- BCET - Best-Case Execution Time: il tempo di esecuzione nel caso migliore
- ACET - Average-Case Execution Time: il tempo di esecuzione nel caso medio
Modalità di stima
[modifica | modifica wikitesto]È possibile classificare le modalità di stima del WCET in quattro categorie[4][5]:
- SDTA: Deterministico, statico
- MBDTA: Deterministico, basato su misure
- SPTA: Probabilistico, statico
- MBPTA: Probabilistico, basato su misure
Dei quattro, solo le prime due categorie sono effettivamente utilizzate in sistemi critici e certificabili, mentre le seconde due sono attualmente utilizzate solo in mondo accademico. L'MBDTA è utilizzabile ai fini pratici solo su architetture hardware molto semplici e software poco complessi.
SDTA
[modifica | modifica wikitesto]L'analisi temporale statica deterministica (Static Deterministic Timing Analysis, SPTA) si basa sulla dettagliata conoscenza di software e hardware, in particolare delle loro caratteristiche temporali. Il control-flow graph del programma di cui si vuole calcolare il WCET viene analizzato al fine di trovare il path peggiore i termini di tempo.
La complessità computazionale degli algoritmi utilizzati per questa analisi è il maggiore limite nell'uso di approcci statici su architetture di processori complesse. Per ovviare al problema, si introducono nell'analisi alcune semplificazioni hardware. Per esempio, se è presenta una memoria cache, si assume sempre miss. Queste semplificazioni riducono il tempo necessario all'analisi ma peggiora la stima del WCET che diventa in questo modo pessimistica.
MBDTA
[modifica | modifica wikitesto]La tecnica Measurement-Based Deterministic Timing Analysis (MBDTA) consiste nel misurare direttamente il tempo di esecuzione del sistema stesso e utilizzare il massimo osservato come WCET. Questo approccio non richiede complesse analisi dell'hardware e software, perché il tempo odi esecuzione viene misurato direttamente.
Tuttavia, per fare in modo che questa tecnica sia sicura e che non sottostimi il WCET, è necessario assicurarsi di aver visitato tutti gli stati dell'hardware e aver visitato tutti i path (o quantomeno i peggiori) del control-flow graph. Ottenere questa certezza è il maggior problema della tecnica MBDTA e le tecniche attuali richiedono un effort parti alle analisi di SDTA.
SPTA
[modifica | modifica wikitesto]
MBPTA
[modifica | modifica wikitesto]Note
[modifica | modifica wikitesto]- ^ Björn Franke, Lecture 11: Worst-Case Execution Time (PDF), su inf.ed.ac.uk, University of Edinburgh. URL consultato il 5 gennaio 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 Worst-Case Execution Time Problem — Overview of Methods and Survey of Tools, in Transactions on Embedded Computing Systems, vol. 7, n. 3, ACM, maggio 2008, p. 53, DOI:10.1145/1347375.1347389.
- ^ X. Guo, M. Boubekeur, J. McEnery, and D. Hickey, ACET Based Scheduling of Soft Real-Time Systems: An Approach to Optimise Resource Budgeting, in International Journal of Computers and Communications, vol. 1, n. 3, 2007.
- ^ J. Abella, D. Hardy, I. Puaut, E. Quiñones, F. J. 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.