Table of Contents

Il tempo di esecuzione peggiore (WCET) di un compito computazionale è la durata massima del tempo che l'attività potrebbe prendere per eseguire su una piattaforma hardware specifica. Nel regno dei sistemi operativi in tempo reale (RTOS), la comprensione e l'applicazione dell'analisi WCET non è solo un esercizio accademico, è un requisito fondamentale per garantire l'affidabilità del sistema, la sicurezza e la prevedibilità.

Per gli sviluppatori che lavorano su applicazioni critiche alla sicurezza come sistemi di controllo automobilistico, avionica, dispositivi medici e automazione industriale, l'analisi WCET fornisce la certezza matematica necessaria per garantire che le attività completeranno entro le loro finestre temporali assegnate. Un sistema informatico che controlla il comportamento di un motore in un veicolo potrebbe essere necessario rispondere a input entro una specifica quantità di tempo, e se il tempo di esecuzione del caso più difettoso del software può essere determinato, allora il progettista del sistema di utilizzare come altre tecniche di pianificazione.

Questa guida completa esplora i principi, le metodologie e le applicazioni pratiche dell'analisi WCET nella progettazione di attività RTOS, fornendo ingegneri di sistemi incorporati con la conoscenza necessaria per costruire sistemi robusti e prevedibili in tempo reale.

Comprendere l'analisi del tempo di esecuzione peggiore-casi

L'analisi WCET rappresenta un approccio sistematico per determinare il limite superiore assoluto del tempo di esecuzione per un pezzo di codice in qualsiasi condizione possibile. A differenza dei tempi di esecuzione medio-caso o tipico, WCET si concentra sulla durata massima possibile, tenendo conto degli scenari più esigenti che potrebbero verificarsi durante il funzionamento del sistema.

L'importanza fondamentale del WCET

Il WCET dipende sia dal flusso del programma, come le iterazioni e le chiamate di funzione del loop, sia da fattori hardware, come le cache e le tubazioni. Questa doppia dipendenza rende l'analisi WCET una disciplina complessa ma essenziale.

  • Controllo della complessità del flusso con rami condizionali e loop nidificati
  • Caratteristiche dell'architettura hardware come le pipeline di istruzioni e la previsione di branch
  • Effetti di gerarchia della memoria, inclusi i colpi di cache e le mancanze
  • Gestione interrotta e contesto di commutazione overhead
  • Contenzione delle risorse in ambienti multicore
  • Sistema operativo decisioni di programmazione e prelazione delle attività

Le stime WCET dovrebbero essere sia sicure (non è consentito sottovalutare) che strette (come minimo sovrastima possibile).Questo duplice requisito crea una tensione fondamentale nell'analisi WCET: le stime devono essere abbastanza conservatrici per garantire la sicurezza, ma abbastanza strette da essere praticamente utili per la progettazione e l'allocazione delle risorse del sistema.

WCET in Sistemi di sicurezza-critici

Mentre WCET è potenzialmente applicabile a molti sistemi in tempo reale, in pratica una garanzia di WCET è utilizzata principalmente da sistemi in tempo reale che sono legati ad alta affidabilità o sicurezza.

DO-178C stabilisce la necessità di analizzare WCET, evidenziandolo nel §6.3 (Software Recensioni e Analyses), §6.3.4 (Reviews and Analyses of Source Code), e §11.20 (Software Accomplishment Summary). Allo stesso modo, DO-178C guida per l'aerospaziale e lo standard ISO 26262 per il settore automobilistico richiedono entrambe le stime WCET della vostra applicazione e la sua subroutine critica.

L'industria automobilistica ha visto una crescita esplosiva della complessità del software, con veicoli moderni contenenti milioni di linee di codice che controllano tutto, dalla gestione del motore ai sistemi avanzati di assistenza al conducente.

Le Fondazioni e le Sfide Teoriche

Il problema di trovare WCET per analisi è equivalente al problema di arresto e quindi non è solvibile in generale, ma fortunatamente, per il tipo di sistemi che gli ingegneri in genere vogliono trovare WCET per, il software è tipicamente ben strutturato, sarà sempre terminare ed è analizzabile.

La maggior parte dei metodi per trovare un WCET comporta approssimazioni (solitamente un arrotondamento verso l'alto quando ci sono incertezze) e quindi in pratica l'esatto WCET stesso è spesso considerato inosservabile. Invece, diverse tecniche per trovare il WCET producono stime per il WCET. Tali stime sono tipicamente pessimistiche, il che significa che il WCET stimato è noto per essere superiore al vero WCET (che è di solito quello che è quello che è desiderato).

Questo pessimismo intrinseco serve come margine di sicurezza, ma molto lavoro sull'analisi WCET è quello di ridurre il pessimismo in analisi in modo che il valore stimato è abbastanza basso da essere prezioso per il progettista di sistema. Pessimismo eccessivo può portare a sovra-provisione delle risorse hardware, aumento dei costi e riduzione dell'efficienza del sistema.

Metodologie di analisi WCET

Nel corso dei decenni, i ricercatori e i professionisti hanno sviluppato diversi approcci distinti all'analisi WCET, ciascuno con i propri punti di forza, limitazioni e casi di utilizzo appropriati.

Tecniche di analisi statica

Uno strumento WCET statico tenta di stimare WCET esaminando il software del computer senza eseguirlo direttamente sull'hardware. Gli strumenti di analisi statiche lavorano ad un livello elevato per determinare la struttura del compito di un programma, lavorando sia su un pezzo di codice sorgente o smontato binario eseguibile.

La stima WCET è stata sviluppata come alternativa alla stima basata sulla misurazione. Il principale vantaggio dell'analisi statica è che non è necessario prendere misure da un vero obiettivo, minimizzare i costi e lo sforzo. Questo approccio costruisce modelli dettagliati sia del flusso di controllo software che del comportamento di tempistica hardware, quindi combina questi modelli per derivare limiti di temporizzazione.

La stima statica dell'analisi richiede un modello preciso delle caratteristiche di tempistica del processore, che include il comportamento di tubazioni, cache, memoria, autobus e qualsiasi altra caratteristica dell'hardware sotto esame che può influenzare il tempo di esecuzione delle istruzioni della macchina.

Il processo di analisi statica comporta in genere diversi componenti chiave:

  • Control Flow Analysis:[] Costruire un grafo di flusso di controllo che rappresenta tutti i possibili percorsi di esecuzione attraverso il programma
  • Valuta analisi:[] Determinare i possibili valori delle variabili per risolvere i rami e i limiti dei loop dipendenti dai dati
  • Analisi del suono:[] Identificare il massimo conteggio di iterazione per tutti i loop del programma
  • Analisi di temporizzazione a basso livello:[] Modellazione del comportamento del processore pipeline, effetti della cache e modelli di accesso alla memoria
  • Analisi dei grafici:[] Identificare il percorso di esecuzione più lungo attraverso il programma utilizzando tecniche come la programmazione lineare interi

Tuttavia, l'analisi statica soffre di due punti chiave: è pessimista in quanto identifica il patologico – peggio teoricamente possibile - WCET.

Analisi basata su misura

Fin dai primi giorni di elaborazione incorporata, gli sviluppatori di software incorporati hanno o utilizzato: misurazioni end-to-end del codice, per esempio eseguito impostando un pin I/O sul dispositivo ad alta all'inizio del compito, e a bassa alla fine del compito e utilizzando un analizzatore di logica per misurare la larghezza di impulso più lunga, o misurando all'interno del software stesso utilizzando l'orologio del processore o il conteggio istruzioni.

L'analisi WCET basata su misurazioni comporta l'esecuzione del programma sull'hardware effettivo di destinazione con vari scenari di input e la registrazione dei tempi di esecuzione osservati. L'approccio è pragmatico e riflette il comportamento hardware reale, ma viene fornito con limitazioni significative.

L'analisi basata sulla misurazione non può identificare con certezza WCET, poiché in generale vengono esercitate solo un sottoinsieme delle esecuzioni, che non può contenere lo scenario peggiore. Per una serie di ragioni, l'uso di analisi basate sulla misura tende ad essere l'approccio più pratico, e di conseguenza l'approccio utilizzato per molti sistemi passati e presenti. A causa del vasto numero di possibili percorsi attraverso il codice, che potrebbe essere preso, c'è ancora la preoccupazione che si potrebbe perdere un lungo tempo.

Pertanto, in pratica, l'ottimismo di un approccio basato sulla misurazione viene ridotto aggiungendo un "margine di sicurezza", ad esempio, aggiungendo il 20% al tempo di esecuzione più lungo osservato.

Approcci di analisi ibride

L'analisi ibrida WCET combina i punti di forza di due metodologie comunemente utilizzate. Gli approcci ibridi sono emersi come un potente terreno centrale, cercando di sfruttare i vantaggi delle tecniche sia statiche che basate sulla misurazione, mitigando le rispettive debolezze.

Gli strumenti ibridi WCET mirano a combinare le migliori caratteristiche degli strumenti WCET basati sulla misurazione e dell'analisi statica evitando le loro insidie utilizzando test on-target per misurare il tempo di esecuzione di brevi sotto-pericoli tra punti di decisione nel codice e combinando misurazioni e informazioni dall'analisi del percorso per calcolare i tempi di esecuzione peggiori in un modo che cattura la variazione di tempo di esecuzione su singoli percorsi a causa di effetti hardware.

L'analisi ibrida mira a fornire un valore tra il WCET eccessivamente pessimistico dell'analisi statica e i valori ottimistici della misura pura.

  • Codice di strumentazione per misurare i tempi di esecuzione dei blocchi di base o piccoli segmenti di codice
  • Eseguire il codice strumentale sull'hardware di destinazione con input di test rappresentativi
  • Eseguire analisi del flusso di controllo statico per identificare tutti i possibili percorsi di esecuzione
  • Combinando i dati di temporizzazione misurati con informazioni sul percorso per calcolare le stime WCET globali
  • Contabilità per percorsi non osservati attraverso l'estrapolazione conservatrice

I tempi di esecuzione sono determinati da misurazioni reali, affrontando il primo problema con gli strumenti WCET statici: nessuna dipendenza dai modelli del processore. Ciò è particolarmente prezioso per i processori moderni complessi in cui i modelli di tempistica accurati sono difficili o impossibili da creare.

Applicare l'analisi WCET a RTOS Task Design

L'integrazione dell'analisi WCET nella progettazione di attività RTOS è dove la teoria incontra la pratica. Capire come applicare efficacemente i principi WCET può significare la differenza tra un sistema affidabile e certificabile e quello che sperimenta inesorabili guasti di tempo nel campo.

RTOS Fondamenti e requisiti di temporizzazione

Un compito è un pezzo di codice che deve essere eseguito all'interno di un unico thread di esecuzione. Un compito emette una sequenza di lavori al processore che sono in coda ed eseguito. Il tempo trascorso dal lavoro attivamente utilizzando risorse del processore è il suo tempo di esecuzione.

I requisiti di sistema di alto livello specificano i tempi di risposta massimi per un'attività, nota come scadenza. Il tempo di esecuzione dei casi è la durata massima di tempo che un'attività richiede per eseguire su una specifica piattaforma hardware.

Nella progettazione di alcuni sistemi, WCET è spesso utilizzato come input per l'analisi della pianificazione, anche se un uso molto più comune di WCET nei sistemi critici è quello di garantire che i budget pre-allocated di temporizzazione in un sistema divisorio-scheduled come ARINC 653 non sono violati.

Attività di studio e WCET

Recenti progressi nell'ambito dell'interpretazione astratta hanno portato allo sviluppo di strumenti di analisi statica del programma che determinano in modo efficiente i limiti superiori per il Worst-Case Execution Time (WCET) di frammenti di codice per eseguire un'analisi di pianificazione generale al fine di garantire che tutti i vincoli di temporizzazione saranno soddisfatti.

Il rapporto tra WCET e pianificazione è bidirezionale. I valori WCET informano le decisioni di programmazione, mentre le politiche di pianificazione influiscono sul tempo effettivo di esecuzione dei compiti attraverso fattori come:

  • Presenzione in testa:[ Context switching aggiunge tempo all'esecuzione delle attività
  • Cache inquinamento:[] La prevenzione può causare errori nella cache quando un'attività riprende
  • Inversione di priorità:[ Le attività di priorità inferiore possono bloccare quelle di maggiore priorità
  • Contenzione delle risorse:[ Compiti multipli per risorse condivise
  • Latenza interrotta: Tempo necessario per rispondere e gestire interrotti

Tuttavia, su hardware moderno, in particolare multi-core, altre attività nel sistema influenzeranno il WCET di una determinata attività se condividono cache, linee di memoria e altre caratteristiche hardware. Inoltre, eventi di programmazione delle attività come il blocco o per essere interruzioni dovrebbero essere considerati nell'analisi WCET se possono verificarsi in un particolare sistema.

Analisi WCET di RTOS Kernels

L'analisi dei tempi di esecuzione dei casi (WCET) è uno dei compiti principali nella convalida dei tempi dei sistemi in tempo reale. Nei sistemi complessi con sistemi operativi in tempo reale (RTOS), le proprietà di temporizzazione del sistema sono decise sia dalle applicazioni che da RTOS. Tradizionalmente, l'analisi WCET riguarda principalmente i programmi di applicazione, mentre è fondamentale sapere se RTOS si comporta anche in modo tempestivo prevedibile.

Il kernel RTOS stesso contribuisce alla tempistica complessiva del sistema attraverso vari servizi e operazioni:

  • Creazione e cancellazione delle attività
  • Interruttore di contesto tra le attività
  • Operazioni di Semaphore e Mutex
  • Gestione della coda dei messaggi
  • Servizi di timer
  • Movimentazione interrotta
  • Attribuzione della memoria e negoziazione

Ciascuno di questi servizi del kernel ha un proprio WCET, che deve essere considerato quando si analizzano le attività di livello di applicazione. Capire il comportamento di tempismo dei primitivi di RTOS è essenziale per l'analisi accurata del livello di sistema.

Priorizzazione delle attività e allocazione delle risorse

L'analisi WCET influenza direttamente il modo in cui le attività sono prioritarie e come le risorse di sistema sono allocate.

  • Assegna priorità adeguate alle attività basate sulle loro scadenze e tempi di esecuzione
  • Allocare le fette di tempo della CPU sufficienti in sistemi partizionati tempo
  • Determinare i set di attività fattibili che possono essere programmati senza violazioni di scadenza
  • Ottimizzare l'utilizzo delle risorse mantenendo le garanzie di tempistica
  • Identificare potenziali colli di bottiglia e problemi di prestazioni all'inizio della fase di progettazione

Gli algoritmi di programmazione (RMA) e prima (EDF) si affidano entrambi ai valori WCET per determinare la pianificazione. Senza valutazioni accurate, queste analisi non possono fornire garanzie significative sul comportamento del sistema.

Analisi WCET di applicazione nella pratica

Trasferirsi dalla comprensione teorica all'implementazione pratica richiede un'attenta pianificazione, una selezione appropriata degli strumenti e una metodologia sistematica, che fornisce una guida pratica per integrare l'analisi WCET in progetti di sviluppo di RTOS nel mondo reale.

Identificare le attività critiche per l'analisi

Non tutte le attività in un RTOS richiedono lo stesso livello di analisi dei tempi. Il primo passo nell'implementazione pratica WCET è identificare quali compiti sono veramente critici e richiedono analisi dettagliate.

  • Funzioni critiche alla sicurezza:[ Compiti il cui fallimento potrebbe causare danni alle persone o alle proprietà
  • I compiti in tempo reale:[ Compiti con scadenze non negoziabili in cui qualsiasi violazione costituisce un fallimento del sistema
  • Attività ad alta frequenza:[] Compiti che eseguono frequentemente e consumano risorse significative della CPU
  • Scelta sul percorso critico:[ Compiti che influiscono direttamente sul tempo di risposta del sistema agli eventi esterni
  • I rischi con margini di tempismo stretti:[ Compiti dove la differenza tra WCET e la scadenza è piccola

Per ogni compito critico identificato, documentare i suoi requisiti di tempistica, compreso il periodo, la scadenza e qualsiasi dipendenze su altri compiti o risorse, che costituiscono la base per l'analisi successiva.

Selezione di strumenti di analisi WCET

La scelta degli strumenti di analisi WCET dipende da molteplici fattori, tra cui hardware di destinazione, linguaggio di programmazione, requisiti di certificazione e vincoli di bilancio.

I dati richiesti per la stima WCET come obiettivi di ramo e limiti di loop calcolati sono determinati da analisi statiche. Lo strumento aiT di AbsInt è ampiamente utilizzato nelle industrie aerospaziale e automobilistica per l'analisi statica WCET.

Lo strumento di analisi ibride di Rapita viene chiamato RapiTime ed è identificato dalla FAA come "un esempio di uno strumento maturo" per l'analisi dinamica dei tempi. RapiTime rappresenta l'approccio di analisi ibrida ed è particolarmente utile per piattaforme hardware complesse.

Altri strumenti di rilievo includono:

  • Bound-T:[] Strumento di analisi statico WCET che supporta vari processori incorporati
  • Crono:[] Strumento di analisi WCET accademico con supporto per architetture multiple
  • OTAWA:[] Quadro open source per l'analisi WCET
  • SymTA/S:[ Strumento per l'analisi e l'ottimizzazione dei tempi di livello di sistema

Quando si valutano strumenti, si considerano fattori come processori supportati, precisione di analisi, facilità d'uso, integrazione con flussi di lavoro di sviluppo esistenti e disponibilità di kit di qualificazione per scopi di certificazione.

Codice di preparazione per l'analisi WCET

La struttura del codice influisce in modo significativo sulla fattibilità e l'accuratezza dell'analisi WCET.

  • Avoid loop non legati:[ Tutti i loop dovrebbero avere conteggi di iterazione massima statically determinabili
  • Minimizzare il comportamento dinamico: Ridurre o eliminare l'allocazione dinamica della memoria, i puntatori di funzione e la ricorsione
  • Semplificare il flusso di controllo:[ Complesso ramificazione e condizionali nidi aumentano difficoltà di analisi
  • I vincoli di temporizzazione del documento:[ Fornire annotazioni per i limiti del loop e i vincoli del percorso di esecuzione
  • Modularizzare il codice:[ Interrompere grandi funzioni in unità più piccole e analizzabili
  • Ottimazioni di compilatore avoide che oscurano il tempismo:[ Alcune ottimizzazioni rendono l'analisi dei tempi più difficile

L'analisi WCET richiede che i limiti superiori per il numero di iterazione di tutti i loop siano noti. aiT determina il numero di iterazioni a ciclo mediante analisi a catena. Questo è possibile per molti loop che si verificano nelle applicazioni tipiche.

Analisi WCET statica

Il flusso di lavoro di analisi statica segue tipicamente questi passaggi:

Step 1: Build and Ready Executable[[[
]]Compili il codice con le impostazioni del compilatore appropriate, tipicamente disabilitando le ottimizzazioni aggressive che complicano l'analisi dei tempi. Genera le informazioni di debug e le tabelle dei simboli necessarie per mezzo di strumenti di analisi.

Step 2: Fornisci informazioni di flusso[[
]] Annota il codice con fatti di flusso come limiti di loop, percorsi infettivi e frequenze di esecuzione.

Step 3: Configurare il modello hardware[[[
]]Scegli il modello di tempismo per il processore di destinazione, inclusa la configurazione della cache, le caratteristiche della pipeline e la tempistica della memoria.

Step 4: Run Analysis[[][
]]Esegui lo strumento di analisi WCET sull'eseguibile preparato. Lo strumento eseguirà analisi del flusso di controllo, analisi dei tempi e analisi del percorso per calcolare le stime WCET.

Step 5: Risultati della recensione[[
]Esaminare i risultati dell'analisi, compreso il valore WCET calcolato, il percorso critico attraverso il codice, e qualsiasi avvertimento o errore. Verificare che i risultati sono ragionevoli e indagare eventuali risultati inaspettati.

Step 6: Iterate and Refine[[[
]] Basato sui risultati dell'analisi, affinare la struttura del codice, aggiungere annotazioni mancanti, o regolare i modelli hardware secondo le necessità.

Analisi basata su misura

Per l'analisi WCET basata sulla misurazione, il processo differisce in modo significativo:

Step 1: Codice strumento[[[][
]Aggiungi la strumentazione per catturare le informazioni di tempistica durante l'esecuzione. Ciò può comportare l'inserimento di timestamp di letture nei punti chiave del codice o utilizzando le funzionalità di tracciamento hardware.

Step 2: Sviluppare i casi di prova[[][
]]Crea una suite di test completa progettata per esercitare i percorsi di esecuzione peggiori. Ciò richiede una profonda comprensione del codice e una attenta considerazione delle combinazioni di input che portano al massimo tempo di esecuzione.

Step 3: Eseguite su Target Hardware[[[
]]Riprimo il codice strumentale sull'hardware effettivo di destinazione con i casi di test sviluppati.

Step 4: Analizzare le misurazioni[[[[
]]Procedere i dati di temporizzazione raccolti per identificare il tempo di esecuzione più lungo osservato.

Step 5: Applicare il margine di sicurezza[[[
]Aggiungi un margine di sicurezza appropriato al tempo più lungo osservato per tenere conto di scenari peggiori non osservati. Il margine dovrebbe essere giustificato in base alla copertura di prova e alla criticità del sistema.

Step 6: Convalida copertura[[[
]]Verificare che i casi di test hanno raggiunto una copertura adeguata dei percorsi di esecuzione e degli stati hardware.

Implementazione di analisi ibrida

Gli approcci ibridi utilizzano test online per misurare il tempo di esecuzione di brevi sotto-percorsi tra punti di decisione nel codice, supportano l'analisi offline con le informazioni ottenute durante i test, come numeri di iterazioni a ciclo, e le frequenze di esecuzione per costruire un modello della struttura generale del codice e determinare quali combinazioni di sotto-pericoli formano percorsi completi e fattibili attraverso il codice, e le informazioni di analisi dei percorsi vengono combinate per calcolare i tempi di esecuzione peggiori.

Il flusso di lavoro di approccio ibrido combina elementi di analisi statica e basata sulla misurazione:

  • Codice strumento a una granularità fine (blocchi di base o piccoli segmenti di codice)
  • Eseguire codice strumentale con input di test rappresentativi
  • Raccogliere le misurazioni di temporizzazione per singoli segmenti di codice
  • Eseguire l'analisi del flusso di controllo statico per identificare tutti i possibili percorsi
  • Combina i tempi di segmento misurati in base al flusso di controllo per calcolare i tempi di percorso
  • Identificare il percorso più lungo possibile attraverso il programma

Questo approccio è particolarmente efficace per l'hardware complesso in cui la modellazione statica è difficile, ma solo gli approcci basati sulla misurazione sono insufficienti per la certificazione di sicurezza.

Argomenti avanzati nell'analisi WCET

Poiché i sistemi incorporati crescono più complessi, l'analisi WCET deve evolversi per affrontare nuove sfide poste dalle moderne architetture hardware e paradigmi software.

Sfide multicore e multiprocessore

Quando si esegue l'analisi WCET sui sistemi multicore, l'approccio ibrido è l'unico metodo efficace per generare metriche di tempistica utili. Ciò detto, l'approccio ibrido convenzionale all'analisi single-core non risponde a una stima multicore WCET da solo, in quanto non rappresenta interferenza dovuta alla contention per risorse condivise e altre idiosincrasie hardware.

Le tecniche di stima WCET statiche non possono spiegare tutte le possibili fonti di interferenza; e anche se potrebbero, sarebbero estremamente complesse e computazionalmente costose da eseguire.

I processori multicore presentano diverse fonti di interferenza dei tempi:

  • Contenzione della cache del raccolto:[ Nuclei multipli che competono per i livelli di cache condivisi
  • Contenzione bus di memoria:[ Connettivi di memoria simultanei da diversi core
  • Protocollo di coerenza:[ Traffico di coerenza tra core
  • Arbitazione delle risorse del capitale:[ Accesso alle periferiche condivise e I/O
  • Comunicazione Inter-core:[ Messaggio di passaggio e sincronizzazione overhead

L'indirizzo di queste sfide richiede tecniche di analisi specializzate che possono limitare le interferenze da attività di co-running. Gli approcci includono il multisala di divisione temporale delle risorse condivise, la partizione delle risorse statiche e i metodi di analisi WCET di interferenza-consapevole.

Complessità di analisi della cache

L'analisi Cache classifica gli accessi alla memoria principale. L'analisi nel nostro strumento si basa su tecniche che gestiscono l'analisi delle cache con la strategia di sostituzione LRU (Più recente Usato).

Il comportamento di Cache rappresenta una delle fonti più significative di variabilità dei tempi nei processori moderni. Un colpo di cache potrebbe prendere alcuni cicli, mentre una carenza di cache potrebbe prendere centinaia di cicli.

  • Classificare ogni accesso alla memoria come sempre, sempre-miss, o incerto
  • Modelli di politiche di sostituzione della cache (LRU, FIFO, pseudo-LRU, ecc.)
  • Analizzare i conflitti di cache tra diversi accessi di memoria
  • Contabilità per l'inquinamento della cache da interrotti e preenni
  • Gestione di gerarchie di cache multilivello

Per i sistemi critici della sicurezza, possono essere impiegati approcci conservatori come la partizione della cache o il blocco della cache per rendere il tempo più prevedibile, anche al costo delle prestazioni medie.

Effetti di predizione della tubatura e del ramo

L'analisi statica WCET a basso livello è complicata dalla presenza di caratteristiche architettoniche che migliorano le prestazioni medie del processore: cache di istruzioni/dati, predizione di branch e oleodotti di istruzione, ad esempio. È possibile, ma sempre più difficile, determinare limiti WCET stretti se queste caratteristiche architettoniche moderne sono prese in considerazione nel modello di tempo utilizzato dall'analisi.

I processori moderni impiegano tecniche sofisticate per migliorare le prestazioni medie, ma queste caratteristiche complicano l'analisi dei tempi:

  • Istruzione condutture: Istruzioni multiple in varie fasi di esecuzione simultaneamente
  • Previsione del tronco:[ Esecuzione speculativa basata sui risultati previsti del ramo
  • Esecuzione di ordine:[ Istruzioni eseguite in ordine diverso rispetto all'ordine del programma
  • Esecuzione speculativa: Esegui istruzioni prima di sapere se sono necessari
  • Esecuzione superscalare: Istruzioni multiple emesse per ciclo

L'analisi di queste caratteristiche richiede modelli di processori dettagliati e algoritmi di analisi sofisticati. In alcuni casi, la complessità diventa così grande che processori più semplici e prevedibili sono scelti per applicazioni di sicurezza-critical.

Gestione di interrotti e preclusione

In ambienti RTOS, le attività possono essere interrotte da attività di maggiore priorità o interrompere le routine di servizio (ISR).

  • Prova di prelazione diretta:[ Tempo speso per salvare e ripristinare il contesto
  • Ritardo di prelazione relativo al cache (CRPD): Ulteriori errori di cache dopo la ripresa a causa dell'inquinamento della cache
  • Pipeline gettare la testa:[ Cancellare il canale di istruzioni durante l'interruttore di contesto
  • LB e ramificare inquinamento predittore:[ Perdita di traduzione aspetto buffer e ramificazione stato previsione

La contabilità per la prelazione nell'analisi WCET richiede la comprensione del numero massimo di predegni che possono verificarsi durante l'esecuzione delle attività e la copertura associata a ogni prelazione.

Analisi probabilistica del WCET

Per i sistemi in cui i limiti deterministici WCET sono troppo pessimistici o impossibili da ottenere, l'analisi probabile WCET (pWCET) offre un approccio alternativo, invece di fornire un unico limite peggiore, l'analisi pWCET produce una distribuzione di probabilità dei tempi di esecuzione.

Questo approccio è particolarmente rilevante per i sistemi con caratteristiche hardware randomizzate o quando si tratta di architetture estremamente complesse. La distribuzione pWCET consente ai progettisti di sistema di prendere decisioni basate sul rischio sui margini di temporizzazione e sull'allocazione delle risorse.

Tuttavia, gli approcci probabilistici richiedono un'attenta considerazione delle probabilità di fallimento accettabili e possono affrontare le sfide nella certificazione per le applicazioni di sicurezza più critiche.

Integrazione con i flussi di lavoro di sviluppo

Per l'analisi WCET, è necessario integrare il ciclo di vita globale dello sviluppo del software piuttosto che essere trattato come un'attività di una volta alla fine dello sviluppo.

Integrazione della fase di progettazione iniziale

Le considerazioni WCET dovrebbero influenzare le decisioni di architettura del sistema dalle prime fasi di progettazione:

  • Stabilire i bilanci di tempistica per le principali funzioni di sistema durante l'analisi dei requisiti
  • Seleziona piattaforme hardware con la predisposizione dei tempi in mente
  • Progettazione di software per facilitare l'analisi WCET
  • Allocare i margini di temporizzazione per ogni compito in base alle stime preliminari
  • Identificare potenziali tempistiche strozzature prima di una dettagliata implementazione

L'integrazione precoce consente di affrontare problemi di tempismo quando sono meno costosi da risolvere, piuttosto che scoprire problemi di sviluppo tardi quando le opzioni sono limitate.

Integrazione continua e analisi automatizzata

Le pratiche di sviluppo moderne sottolineano l'integrazione continua e i test automatizzati. L'analisi WCET può e dovrebbe essere parte di questo flusso di lavoro automatizzato:

  • Integrare gli strumenti di analisi WCET nel sistema di costruzione
  • Eseguire automaticamente l'analisi dei tempi su ogni codice commit o costruire di notte
  • Monitorare le tendenze WCET nel tempo per rilevare le regressioni dei tempi
  • Generare avvisi quando le stime WCET superano i bilanci assegnati
  • Mantenere un database di risultati WCET per analisi storiche

L'automazione assicura che l'analisi dei tempi rimanga corrente, mentre il codice si evolve e aiuta a catturare i problemi di tempismo prima che diventino problemi critici.

Documentazione e Tracciabilità

Per i sistemi critici di sicurezza soggetti alla certificazione, è essenziale una documentazione completa dell'analisi WCET:

  • Metodologia e strumenti di analisi dei documenti utilizzati
  • Registra tutte le ipotesi e le annotazioni effettuate durante l'analisi
  • Mantenere la tracciabilità tra i risultati delle analisi dei requisiti, del codice e dei tempi
  • Validazione e verifica dei documenti delle stime WCET
  • Fornire giustificazione per i margini di sicurezza e le ipotesi conservatrici

Questa documentazione serve a molteplici scopi: sostenere argomenti di certificazione, consentire la manutenzione futura, e fornire prove di due diligence nello sviluppo del sistema.

Validazione e verifica delle stime WCET

Ottenere una stima WCET è solo parte della sfida, vale a dire che la stima è corretta e sufficiente è altrettanto importante.

Strategie di prova e simulazione

La convalida delle stime WCET comporta in genere molteplici approcci complementari:

  • Prova di prova:[ Eseguire il sistema in condizioni di carico massimo per osservare il comportamento attuale dei tempi
  • Test di boundary:[] Test con valori di input agli estremi di intervalli validi
  • Iniezione di errore:[] Introdurre i guasti a verificare il comportamento del sistema in condizioni di errore
  • Simulazione Hardware-in-the-loop:[ Test con stimoli esterni realistici e tempistiche
  • Analisi statistica:[] Analizzare le misurazioni dei tempi per verificare che cadano entro limiti predetti

L'obiettivo è di ottenere fiducia che le stime WCET siano sia sicure (non sottovalutate) che ragionevolmente strette (non eccessivamente pessimistiche).

Metodi di analisi comparati

In futuro, è probabile che un requisito per i sistemi critici di sicurezza sia che vengano analizzati utilizzando approcci statici e basati sulla misurazione.

Quando diversi metodi producono stime WCET significativamente diverse, l'indagine è giustificata per capire la fonte della discrepanza.

  • Errori nei modelli di tempistica hardware utilizzati dall'analisi statica
  • Copertura di test insufficiente nell'analisi basata sulla misurazione
  • Presupposti eccessivamente conservativi nell'analisi statica
  • Strade dei casi peggiori non osservate nell'analisi basata sulla misurazione

Monitoraggio e verifica dei tempi di esecuzione

Per i sistemi implementati, il monitoraggio dei tempi di esecuzione può fornire una verifica continua che le ipotesi di temporizzazione rimangono valide:

  • Implement time monitor che tracciano i tempi di esecuzione delle attività effettivi
  • Trasmissioni di tempistiche per post-analisi
  • Utilizzare timer watchdog per rilevare le attività che superano il tempo assegnato
  • Raccogliere statistiche di tempistica per analisi di tendenza a lungo termine
  • Attuazione strategie di degrado graziose quando si verificano violazioni dei tempi

Il monitoraggio Runtime serve come rete di sicurezza finale, catturando problemi di tempistica che evadono l'analisi e il test.

Strategie di ottimizzazione per la riduzione WCET

Quando l'analisi WCET rivela che le attività superano i loro budget di tempistica, l'ottimizzazione diventa necessaria, ma l'ottimizzazione delle prestazioni dei casi peggiori differisce dall'ottimizzazione delle prestazioni dei casi medi.

Ottimizzazione del codice-Level

Diversi metodi di livello di codice possono ridurre WCET:

  • Loop srolling:[ Ridurre il loop overhead eseguendo più iterazioni per ciclo di ciclo
  • Inlineazione di frequenza:[ Eliminare la funzione chiamata overhead per le piccole funzioni, spesso chiamate
  • Ridurre la ramificazione:[] Minimizzare i rami condizionali che causano bancarelle di tubazione
  • Ottimizzazione della struttura dei dati:[ Abilitare i dati per migliorare la localizzazione della cache
  • Miglioramenti algoritmici:[ Sostituisci algoritmi con una migliore complessità dei casi peggiori

Quando si applicano le ottimizzazioni, è fondamentale eseguire l'analisi WCET per verificare che i cambiamenti effettivamente migliorare tempistiche peggiori. Alcune ottimizzazioni che migliorano le prestazioni medie possono effettivamente peggiorare il comportamento dei casi peggiori.

Considerazioni di ottimizzazione dei clienti

Le ottimizzazioni dei Compiler presentano una spada a doppio taglio per l'analisi WCET, mentre possono migliorare le prestazioni, possono anche rendere l'analisi dei tempi più difficile e introdurre la variabilità dei tempi.

Per i sistemi critici di sicurezza, prendere in considerazione:

  • Utilizzo di livelli di ottimizzazione moderati che bilanciano le prestazioni e l'analisi
  • Disabilitare le ottimizzazioni che introducono una notevole variabilità dei tempi
  • Utilizzo di compilatori qualificati con comportamento di ottimizzazione documentato
  • Verificare che le ottimizzazioni non violinino le ipotesi di tempistica

Ottimizzazione hardware-Level

La configurazione hardware può avere un impatto significativo su WCET:

  • Cache locking:[] Bloccare codice critico e dati nella cache per eliminare le mancanze della cache
  • Memoria di Grattacielo:[] Utilizzare la memoria gestita esplicitamente invece di cache
  • Disabling caratteristiche speculative:[ Disattivare la previsione e l'esecuzione speculativa del ramo
  • Modi di accesso comuni:[] Disposizione della disposizione della memoria per minimizzare i conflitti di accesso
  • Selezione del processore:[] Scegliere i processori con caratteristiche di tempismo più prevedibili

Questi approcci a livello hardware scambiano prestazioni medie per migliorare la predisposizione dei tempi e i limiti WCET più stretti.

Studi sui casi e applicazioni reali

Capire come l'analisi WCET viene applicata nei sistemi reali fornisce preziose informazioni sulle sfide e sulle soluzioni pratiche.

Controllo motore automobilistico

Le moderne unità di controllo del motore automobilistico (ECU) devono eseguire algoritmi di controllo complessi all'interno di rigidi vincoli di tempismo.

  • Controllo tempistiche di iniezione del carburante (durata in tempo reale, scadenze submilliseconde)
  • Controllo tempistiche di accensione (durata in tempo reale, scadenze submilliseconde)
  • Acquisizione e filtraggio dei dati del sensore (periodico, su scala milliseconda)
  • Monitoraggio diagnostico (dei termini in tempo reale e rilassati)

L'analisi WCET per tali sistemi deve tener conto degli input dei sensori a interrompi, degli algoritmi di controllo complessi e della necessità di certificazione ai sensi della norma ISO 26262.

Avionics Controllo volo

I sistemi di controllo aereo rappresentano alcune delle applicazioni più esigenti per l'analisi WCET, che devono soddisfare i requisiti di certificazione DO-178C e operare con un'affidabilità estremamente elevata.

Le sfide includono:

  • Canali ridondanti multipli che richiedono tempi sincronizzati
  • Algoritmi di fusione complessi dei sensori
  • Meccanismi di rilevamento e ripristino dei guasti
  • Schedulazione parziale con isolamento temporale rigoroso

Gli strumenti di analisi statici WCET come iT sono comunemente utilizzati in avionica, fornendo i limiti deterministici necessari per la certificazione. L'analisi deve tenere conto di tutte le possibili modalità di fallimento e le loro implicazioni di tempismo.

Controllo dispositivi medici

I dispositivi medici come le pompe di insulina, i pacemaker e i ventilatori hanno requisiti di tempismo critico per la vita. Un ventilatore, ad esempio, deve controllare con precisione i cicli di respirazione con precisione di tempismo misurati in millisecondi.

L'analisi WCET per i dispositivi medici deve considerare:

  • Sicurezza dei pazienti come preoccupazione fondamentale
  • Requisiti di regolazione (FDA, IEC 62304)
  • Funzionamento a batteria con vincoli energetici
  • Comportamento sicuro in tutte le condizioni

L'analisi deve dimostrare che tutte le funzioni di sicurezza-criticale possono completare entro le loro scadenze anche in condizioni peggiori, comprese le variazioni di tensione della batteria e i guasti dei sensori.

Tendenze e direzioni di ricerca

L'analisi WCET continua ad evolversi in risposta a nuove architetture hardware, paradigmi software e requisiti applicativi.

Imparare la macchina e l'intelligenza artificiale nell'analisi WCET

Si propone un'estensione della metodologia ibrida che implementa un modello predittore utilizzando Machine Learning (ML). Questo nuovo approccio stima il WCET su entità più piccole del codice, cosiddetti blocchi ibridi, basati su funzionalità software e hardware.

Gli approcci di apprendimento automatico mostrano la promessa per migliorare la precisione di stima WCET e ridurre lo sforzo di analisi. Le reti neurali addestrate sui dati del tempo di esecuzione potrebbero potenzialmente prevedere WCET per un nuovo codice basato su modelli appresi.

Tuttavia, l'applicazione di ML ai sistemi critici per la sicurezza solleva domande sulla spiegabilità, la certificazione e la fiducia nelle previsioni.

Architettura prevedibile

Piuttosto che analizzare l'hardware imprevedibile complesso, un approccio alternativo sta progettando hardware specificamente per la predisposizione dei tempi.

  • Criteri di sostituzione della cache prestabiliti
  • Risorse condivise multiplexate di divisione temporale
  • Comportamento di pipeline
  • Eliminazione dell'esecuzione speculativa

I progetti come l'architettura PRET (Precision Timed) e il processore T-CREST dimostrano questo approccio, mentre questi processori possono sacrificare prestazioni medie, offrono limiti WCET molto più stretti e analisi più semplici.

Analisi di Timing Composizione

Poiché i sistemi crescono più grandi e complessi, analizzandoli monoliticamente diventa impraticabile; l'analisi dei tempi compositivi rompe il sistema in componenti, analizza ogni componente in modo indipendente, e poi compone i risultati.

Questo approccio consente:

  • Riutilizzo dei risultati dell'analisi dei tempi in tutti i progetti
  • Sviluppo indipendente e certificazione dei componenti
  • Scalabilità dei sistemi molto grandi
  • Analisi incredibile quando i componenti cambiano

La ricerca continua a sviluppare dei sistemi di analisi compositive che forniscono garanzie di tempistica a livello di sistema da analisi a livello di componenti.

Migliori Pratiche e Raccomandazioni

Basato su decenni di ricerca e di esperienza industriale, sono emersi diverse migliori pratiche per un'analisi efficace del WCET nello sviluppo di RTOS.

Design per l'analisi

Il modo più efficace per raggiungere i limiti WCET stretti è quello di progettare software con analizability in mente fin dall'inizio:

  • Utilizzare flusso di controllo semplice e strutturato
  • Evitare o minimizzare il comportamento dinamico
  • Documento decisioni di progettazione rilevanti
  • Scegliere algoritmi con una buona complessità peggiore dei casi
  • Design per la verifica e l'osservanza

Il codice che è difficile da analizzare spesso ha caratteristiche di tempismo peggiori e anche. La progettazione per l'analisi migliora tipicamente entrambi.

Mantenere i bilanci di Timing

Stabilire e mantenere i budget di temporizzazione durante lo sviluppo:

  • Allocare i bilanci di temporizzazione alle principali funzioni di sistema presto
  • Monitorare la WCET reale contro i budget continuamente
  • Escalate quando i bilanci rischiano di essere superati
  • margine di riserva per le modifiche del palco e correzioni di bug
  • Bilanci di revisione e aggiornamento come i requisiti si evolvono

I bilanci di temporizzazione forniscono un avviso precoce dei problemi e aiutano a prevenire le crisi dell'ultimo minuto.

Investire nella formazione e nella competenza

L'analisi WCET richiede conoscenze e competenze specialistiche. Le organizzazioni che sviluppano sistemi in tempo reale critici per la sicurezza dovrebbero:

  • Sviluppatori di treni in tempo reale di programmazione
  • Sviluppare competenze interne in strumenti e metodi di analisi dei tempi
  • Impegnarsi con esperti di analisi dei tempi per progetti complessi
  • Partecipazione allo sviluppo della ricerca e degli standard
  • Condividere conoscenze e lezioni apprese in progetti

L'investimento in competenze paga dividendi attraverso uno sviluppo più efficiente e sistemi di qualità superiore.

Sicurezza e praticità dell'equilibrio

Mentre la sicurezza è fondamentale, l'analisi eccessivamente conservatrice dei tempi può portare a sistemi troppo provvisti e costosi.

  • Utilizzare metodi di analisi appropriati per il livello di criticità
  • Applicare analisi più rigorose alle funzioni più critiche
  • Accettare margini ragionevoli piuttosto che limiti di caso peggiori assoluti
  • Considera gli approcci probabilistici in cui i limiti deterministici sono impraticabili
  • Utilizzare la difesa-in profondità con più strati di protezione dei tempi

L'obiettivo è sistemi che sono sia sicuri che economicamente fattibili.

Conclusioni

L'analisi dei tempi di esecuzione dei casi più gravi rappresenta una disciplina critica nello sviluppo di sistemi operativi in tempo reale e applicazioni integrate in sicurezza-criticale.

L'applicazione di un'analisi di WCET alla progettazione di attività RTOS richiede la comprensione delle basi teoriche, la selezione di metodologie di analisi appropriate, l'utilizzo di strumenti adeguati e l'integrazione dell'analisi dei tempi durante il ciclo di vita di sviluppo.

Per le organizzazioni che sviluppano sistemi in tempo reale, investire nelle capacità di analisi WCET non è facoltativo – è essenziale per fornire sistemi affidabili e certificabili che soddisfino i loro requisiti di tempismo in tutte le condizioni.

Il campo continua ad evolversi con nuove tecniche di analisi, strumenti più sofisticati e hardware progettati per la predisposizione dei tempi. Rimanendo aggiornati con questi sviluppi e applicandoli in modo appropriato permetterà alla prossima generazione di sistemi in tempo reale sicuri e affidabili.

Risorse aggiuntive

Per coloro che cercano di approfondire la loro comprensione dell'analisi WCET e della sua applicazione allo sviluppo di RTOS, sono disponibili numerose risorse:

  • Ricerca accademica:[] Il Workshop internazionale sull'analisi del tempo di esecuzione del peggiore-caso (officina WCET) pubblica ogni anno una ricerca all'avanguardia
  • Norme di industria:[ DO-178C per avionica e ISO 26262 per il settore automobilistico forniscono una guida sui requisiti di analisi dei tempi
  • I fornitori di utensili:[ Le aziende come AbsInt, Rapita Systems e LDRA offrono una documentazione e una formazione completa per i loro strumenti di analisi WCET
  • Comunità online:[] Forum e mailing list dedicati ai sistemi in tempo reale offrono opportunità di imparare dai praticanti
  • Organizzazione Professionali:[ I gruppi di interesse speciali IEEE e ACM si concentrano su sistemi in tempo reale e calcolo incorporato

Per ulteriori informazioni sullo sviluppo dei sistemi in tempo reale e sull'ingegneria del software incorporato, visitate la comunità [Embedded Systems Design[]. Ulteriori informazioni sullo sviluppo del software critico della sicurezza possono essere trovate nella Safety Critical Systems Club]].

Combinando conoscenze teoriche con esperienza pratica e sfruttando il crescente ecosistema di strumenti e risorse, gli sviluppatori possono masterizzare l'analisi WCET e applicarla efficacemente per creare sistemi in tempo reale robusti e affidabili che soddisfino le esigenze più esigenti delle applicazioni in sicurezza-criticale di oggi.