Worst-case execution timeIl 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. DefinizioneIl 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 correlatiAltri sigle comunemente utilizzate nella letteratura scientifica per identificare tempi di esecuzioni particolari sono[2][3]:
Modalità di stimaÈ possibile classificare le modalità di stima del WCET in quattro categorie[4][5]:
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. SDTAL'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. MBDTALa 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. SPTAMBPTANote
Voci correlate |
Portal di Ensiklopedia Dunia
