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

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

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

È 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

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

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

MBPTA