UNIVERSITA’ DEGLI STUDI DI GENOVA
FACOLTA’ DI INGEGNERIA
Corso di Laurea in Ingegneria
Elettronica
TESI DI LAUREA
Tools di supporto alla configurazione e alla manutenzione degli apparati fail safe. Sviluppo di moduli di software residenti su piattaforme standard (es. Personal Computer) in grado di: interfacciarsi direttamente con schede microprocessore per la loro configurazione, generare la configurazione per le stesse ed aiutare l'utente nella manutenzione dell'impianto
Relatore accademico : Chiar.mo Prof. Ing. Rodolfo Zunino
Relatore aziendale: Ing. Giacomo Donati
Ansaldo Segnalamento Ferroviario
Allievo: Lorenzo Banderali
8 Novembre 2005
A.A. 2004-2005
Indice
Indice delle tabelle e delle figure
Capitolo 1 : Concetti e tecniche
Capitolo 2 : Struttura (framework) descrittiva per situazioni in tempo reale
Capitolo 3 :Modello di sistemi in tempo reale: un approccio di base
3 .1.1 Eventi periodici nel tempo
3 .1.2 Eventi ambientali periodici
3 .2.1 Eventi periodici nel tempo
3 .2.2 Eventi ambientali periodici
3 .3 Gestione di eventi periodici con dati condivisi
3 .3.1 Uso del protocollo di Masking-Interrupt (IMP)
3 .3.2 uso del protocollo Highest Locker (HLP)
3 .4 Gestione di eventi aperiodici: Arrivi limitati con hard deadline
3 .4.1 Gestione di eventi aperiodici: Arrivi limitati con hard deadline -Polling
3 .4.2 Gestione di eventi aperiodici: Arrivi limitati con hard deadline - Sporadic Server
Capitolo 4 :Trovare un metodo di schedulabilità
4 .1 Uso di un limite di utilizzo per l’intera situazione in tempo reale.
Capitolo 5 :Ottenere una valutazione precisa di schedulabilità con deadline e bloccaggio arbitrari
Capitolo 6 :Analisi di schedulabilità: alcuni esempi
6 .1 Analisi di schedulabilità: eventi a tempo periodico con deadline minori o uguali al periodo.
6 .2 Analisi di schedulabilità: eventi a tempo periodico con deadline maggiore o uguale al periodo
Capitolo 7 :Realizzazione del tool software
7 .1 Tipico scenario di utilizzo del tool realizzato
7 .2.1 Importazione ed esportazione dei dati
7 .2.3 Creazione di un nuovo progetto
7 .2.5 Analizzatore / ottimizzatore di schedulabilità
7 .2.6 Visualizzatore degli eventi di schedulazione
7 .2.7 Generazione del report HTML.
7 .2.6 Pannello dei settaggi dell’applicazione
7 .2.7 Altre features presenti nel tool realizzato.
Appendice. Sintassi per descrivere situazioni in tempo reale.
Indice delle tabelle e delle figure
Figura 1‑1: Scenario di stimolo-lavoro.
Figura 1‑2: Esempio di eventi e della rispettiva sequenza di eventi.
Figura 1‑3: Esempio di un lavoro.
Figura 1‑4: Esempio di job costituito da due azioni.
Figura 1‑5: Esempio di punti di schedulazione.
Tabella 2‑1:Esempio di tabella di eventi.
Tabella 2‑2: Esempio di tabella di risposte.
Tabella 2‑3: Esempio di tabella di azioni.
Tabella 2‑4: Esempio di tabella di tecniche.
Tabella 2‑5: Tabella degli eventi.
Tabella 2‑6: Tabella delle risposte.
Tabella 2‑7: Tabella delle azioni.
Tabella 2‑8: Tabella delle risorse.
Tabella 2‑9: Tabella delle tecniche.
Figura 3‑1: Eventi periodici nel tempo con deadline minori o uguali al periodo – Pseudocodice.
Figura 3‑2: Eventi ambientali periodici con deadline minore o uguale al periodo – Pseudocodice.
Tabella 3‑11: Eventi periodici con deadline dopo il periodo – Tabella degli eventi.
Tabella 3‑12: Eventi periodici con deadline dopo il periodo – Tabella delle risposte.
Tabella 3‑13: Eventi periodici con deadline dopo il periodo – Tabella delle azioni.
Tabella 3‑14: Eventi periodici con deadline dopo il periodo – Tabella delle risorse.
Figura 3‑3: Eventi periodici con deadline dopo il periodo – Pseudocodice.
Tabella 3‑15: Eventi periodici con deadline dopo il periodo – Tabella delle tecniche.
Tabella 3‑16: Eventi ambientali periodici con deadline dopo il periodo – Tabella degli eventi.
Tabella 3‑17: Eventi ambientali periodici con deadline dopo il periodo – Tabella delle risposte.
Tabella 3‑18: Eventi ambientali periodici con deadline dopo il periodo – Tabella delle azioni.
Tabella 3‑19: Eventi ambientali periodici con deadline dopo il periodo – Tabella delle risorse.
Figura 3‑4: Eventi ambientali periodici con deadline dopo il periodo – Pseudocodice.
Tabella 3‑20: Eventi ambientali periodici con deadline dopo il periodo – Tabella delle tecniche.
Tabella 3‑21: Uso dell’ IMP – Tabella degli eventi.
Tabella 3‑22: Uso dell’ IMP – Tabella delle risposte.
Tabella 3‑23: Uso dell’ IMP – Tabella delle azioni.
Tabella 3‑24: Uso dell’ IMP – Tabella delle risorse.
Figura 3‑5: Uso dell’ IMP – Pseudocodice.
Tabella 3‑25: Uso dell’ IMP – Tabella delle tecniche.
Tabella 3‑26: Uso dell’ HLP – Tabella degli eventi.
Tabella 3‑27: Uso dell’ HLP – Tabella delle risposte.
Tabella 3‑28: Uso dell’ HLP – Tabella delle azioni.
Tabella 3‑29: Uso dell’ HLP – Tabella delle risorse.
Figura 3‑6: Uso dell’ HLP – Pseudocodice.
Tabella 3‑30: Uso dell’ HLP – Tabella delle tecniche.
Tabella 3‑31: Arrivi limitati con hard deadline – Tabella degli eventi.
Tabella 3‑32: Arrivi limitati con hard deadline – Tabella delle risposte.
Tabella 3‑33: Arrivi limitati con hard deadline – Tabella delle azioni.
Tabella 3‑34: Arrivi limitati con hard deadline – Tabella delle risorse.
Tabella 3‑35: Arrivi limitati con hard deadline – Tabella degli eventi - Polling.
Tabella 3‑36: Arrivi limitati con hard deadline – Tabella delle risposte - Polling.
Tabella 3‑37: Arrivi limitati con hard deadline – Tabella delle azioni - Polling.
Tabella 3‑38: Arrivi limitati con hard deadline – Tabella delle risorse - Polling.
Figura 3‑7: Task di polling - Pseudocodice.
Tabella 3‑39: Arrivi limitati con hard deadline – Tabella degli eventi – Sporadic Server.
Tabella 3‑40: Arrivi limitati con hard deadline – Tabella delle risposte – Sporadic Server.
Tabella 3‑41: Arrivi limitati con hard deadline – Tabella delle azioni – Sporadic Server.
Tabella 3‑42: Arrivi limitati con hard deadline – Tabella delle risorse – Sporadic Server.
Figura 3‑8: Sporadic Server – Pseudocodice.
Tabella 4‑1: Esempio di schedulabilità – Tabella delle tecniche.
Tabella 4‑2: Esempio di schedulabilità – Tabella delle tecniche.
Tabella 5‑1: Esempio di schedulabilità – Tabella delle tecniche.
Tabella 6‑1: Esempio di schedulabilità – Tabella delle tecniche.
Tabella 6‑2: Esempio di schedulabilità – Tabella delle tecniche.
Tabella 6‑3: Esempio di schedulabilità – Tabella delle tecniche.
Tabella 6‑4: Esempio di schedulabilità – Tabella delle tecniche.
Figura 7‑1: Scenario tipico di utilizzo del tool.
Figura 7‑3:Target CPU (visione frontale).
Figura 7‑4: Importazione / Esportazione in formato “vtd”.
Figura 7‑5: Interoperabilità diretta non supportata.
Figura 7‑7: Importazione / Esportazione in formato “xml”.
Figura 7‑8: Esempio di file in formato xml.
Figura 7‑9: Finestra di dialogo durante le operazioni di lettura/scrittura su file.
Figura 7‑10: Creazione di un nuovo progetto.
Figura 7‑11: Editazione dei dati.
Figura 7‑12:Finestra di editazione dei dati.
Tabella 7‑1: Regole di immissione dei dati.
Figura 7‑13: Individuazione degli errori.
Figura 7‑14: Inserimento di un nuovo task.
Figura 7‑15: Ordinamento delle colonne della tabella.
Figura 7‑16: Inserimento di un commento ed una breve descrizione.
Figura 7‑17: Analisi di schedulabilità ed ottimizzazione.
Figura 7‑18: Finestra vuota dell’analizzatore.
Figura 7‑19: Avvio dell’analisi di schedulabilità.
Figura 7‑20: Visualizzazione dell’analisi.
Figura 7‑21: Riepilogo complessivo dell’analisi.
Figura 7‑22: Finestra di analisi di schedulabilità.
Figura 7‑23: Dettaglio di analisi.
Figura 7‑24: Esempio di task non schedulabile.
Figura 7‑25: Esempio di sistema non schedulabile.
Tabella 7‑2: Tabella di crescita del fattoriale di un numero.
Figura 7‑26: Grafico di crescita del fattoriale di un numero.
Figura 7‑27: Ottimizzazione con metodo delle permutazioni.
Figura 7‑28: Finestra di dialogo durante il processo di l’ottimizzazione.
Figura 7‑29: Esempio di ottimizzazione.
Tabella 7‑3: Esempio di priorità ordinate secondo la regola “rate monotonic”.
Figura 7‑30: Avvio dell’ottimizzazione secondo il criterio di “rate monotonic”.
Figura 7‑31: Esempio di ottimizzazione secondo il criterio di “rate monotonic”.
Figura 7‑32: Selezione dei tasks da ottimizzare.
Figura 7‑33: Finestra di selezione dei tasks da ottimizzare.
Figura 7‑34: Screenshot del contenuto della finestra dell’analizzatore di schedulabilità (toolbar).
Figura 7‑35: Screenshot del contenuto della finestra dell’analizzatore di schedulabilità.
Figura 7‑36: Esempio di salvataggio delle informazioni degli eventi di schedulazione.
Figura 7‑37: Avvio del visualizzatore degli eventi.
Figura 7‑38: Finestra di visualizzazione degli eventi.
Figura 7‑39: Interpretazione delle tracce del visualizzatore.
Figura 7‑40: Esempio di task visibilmente regolare.
Figura 7‑41: Esempio di task visibilmente non regolare.
Figura 7‑42: Visualizzazione con ingrandimento minimo.
Figura 7‑43: Visualizzazione con ingrandimento massimo.
Figura 7‑44: Formati possibile del righello.
Tabella 7‑4: Corrispondenza dello zoom.
Figura 7‑45: Attivazione della visualizzazione della deadline.
Figura 7‑46: Visualizzazione della deadline.
Figura 7‑47: Dettaglio di visualizzazione della deadline.
Figura 7‑48: Attivazione della barra di scorrimento orizzontale per la griglia della deadline.
Figura 7‑49: Attivazione della griglia dei tic.
Figura 7‑50: Visualizzazione dei tic nella finestra degli eventi di schedulazione.
Figura 7‑51: Barra verticale di indicazione.
Figura 7‑53: Ordinamento delle tracce.
Figura 7‑54: Avvio del generatore di report.
Figura 7‑55: Generazione del report HTML (toolbar).
Figura 7‑56: Salvataggio del report HTML.
Figura 7‑57: Caricamento del report HTML.
Figura 7‑58: Pannello dei settaggi: General
Tabella 7‑5: Significato delle impostazioni nel pannello General.
Figura 7‑59: Pannello dei settaggi: Edit.
Tabella 7‑6: Significato delle impostazioni nel pannello Edit.
Figura 7‑60: Pannello dei settaggi: Analyzer.
Tabella 7‑7: Significato delle impostazioni nel pannello Analyzer.
Figura 7‑61: Pannello dei settaggi: Optimyzer.
Tabella 7‑8: Significato delle impostazioni nel pannello Optimyzer.
Figura 7‑62: Pannello dei settaggi: Viewer.
Tabella 7‑9: Significato delle impostazioni nel pannello Viewer.
Figura 7‑63: Pannello dei settaggi: Import/Export.
Tabella 7‑10: Significato delle impostazioni nel pannello Import/Export.
Figura 7‑64: Pannello dei settaggi: Load/Save.
Figura 7‑65: Chiave di registro inserita.
Figura 7‑67:Esempio di riepilogo informativo per un progetto.
Figura 7‑69: Visualizzazione Tooltip.
Tabella 8‑1: Tabella delle tecniche (test 1).
Figura 8‑1: Analisi di schedulabiltà (test 1).
Figura 8‑2: Analisi di schedulabiltà (test 2).
Tabella 8‑2: Risultati dell’ottimizzazione.
Figura 8‑3 Analisi di schedulabiltà (test 3).
Figura 8‑4: Analisi di schedulabiltà (test 4).
Un ringraziamento particolare al Prof. Ing. Rodolfo Zunino per avermi dato la possibilità
di realizzare questa tesi e per il sostegno e l’aiuto fornitomi fin dai primi giorni.
Vorrei ringraziare tutto il personale dell’Ansaldo Segnalamento Ferroviario per la cordiale
ospitalità riservatami.
All’Ing. Giacomo Donati, e a tutto il personale collaboratore un grazie sincero per avermi coinvolto ed appassionato nel loro lavoro.
Ringrazio tutta la mia famiglia senza la quale oggi non sarei giunto a questo traguardo, per
avermi seguito e motivato; per non avermi mai
fatto mancare niente, grazie.
Ringrazio anche tutti coloro che contribuiscono alla diffusione
dell’informazione gratuita tramite internet.
Grazie.
Abstract
The goal of this work is to analyze and check the timing correctness of real time systems. In a real-time system all the tasks must respect precise timing constraits.
We created a tool software called “Schedanalyzer” to collect the real-time system characterizations and data from the hardware device and analyze them to check the system schedulability. After this temporal analysis the tool reports if the real-time system is schedulable or not, and how large is the temporal margin.
The chosen methodology is based on a well-known algorithm.
The realized tool
can also automatically optimize the system through the interchange of the
priority values of the tasks to maximize margins.
The software can also help the users to improve or verify the timing system
correctness through a viewer that shows how the system has been really scheduled
by the hardware device.
It’s possible to simulate a real-time system editing the data relative to the tasks that composes it and then verifies its schedulability.
Several tests were performed to check the system schedulability analysis and automatic optimization of schedulability margin. The results show that the analysis is correct and in most of the cases the automatic optimization brings to better margin of schedulability.
The tool is currently used by ASF (Ansaldo Segnalamento Ferroviario).
Prefazione
Il lavoro di tesi si è svolto prevalentemente nei mesi di Giugno e Luglio 2005 presso la sede genovese di ASF (Ansaldo Segnalamento Ferroviario).
I sistemi real-time, per la cui
correttezza non è richiesto unicamente che le risposte siano conformi alle
specifiche, ma che queste siano presentate entro precise scadenze temporali, hanno
trovato moltissime applicazioni, che nella maggior parte dei casi coinvolgono
la sicurezza di cose e persone.
Per questo motivo si è reso necessario effettuare test di controllo, sia a
priori, sia a posteriori, sul sistema per verificare che la schedulazione avvenga
nei tempi corretti in modo da evitare situazioni potenzialmente pericolose sul
campo.
Al fine di controllare la schedulabilità di un sistema in tempo reale, in
ambito ferroviario, è stato sviluppato un tool tramite il quale è possibile
effettuare analisi su un sistema reale o simulato, sia a priori, sia a
posteriori.
Lo scopo principale del programma,
residente su piattaforma standard, è quello di effettuare l’analisi della
schedulabilità del sistema real-time; per avere una migliore interazione con
l’utente e facilitare l’utilizzo del software è stata sviluppata anche una
interfaccia grafica e sono state aggiunte interessanti funzionalità.
La maggior parte del materiale di studio, compresi gli algoritmi per l’analisi
della schedulabilità, sono stati forniti dal relatore aziendale, mentre la
documentazione del linguaggio utilizzato (C#) è stato reperito in rete o su
MSDN.
Il compilatore utilizzato è Visual Studio .net 2003.
Capitolo 1 : Concetti e tecniche
Includendo un comportamento di tipo temporale nella specifica di un sistema, di conseguenza, secondo la definizione di sistema corretto, si devono distinguere sistemi in tempo reale da sistemi non in tempo reale.
I sistemi in tempo reale sono sistemi per i quali la correttezza del sistema non dipende solamente dal dominio logico, ma anche da quello temporale. Un sistema in tempo reale, solitamente, è in attesa di stimoli. Quando si presenta uno stimolo può avere inizio la schedulazione di un processo che solitamente richiede la raccolta di uno specifico aspetto ambientale.
Spesso il processo deve essere completato entro un termine di tempo massimo che ha inizio da quando il processo comincia ad essere schedulato; questo tempo limite è detto deadline. Tale scenario di stimolo-lavoro può ripetersi più volte durante l’intero tempo di vita del sistema (figura 1-1).
Figura 1‑1: Scenario di stimolo-lavoro.
Nel caso in cui
uno stimolo sia associato con uno specifico aspetto ambientale viene detto
evento. Da quando uno stimolo può potenzialmente verificarsi ripetutamente, la
ricorrenza degli eventi è detta sequenza di evento. L’arrivo di telegrammi
(figura 1-2) è un esempio di ripetizione di eventi.
La ricorrenza di tali eventi (ad esempio l’arrivo di più telegrammi) è la
sequenza di
evento associata.
Figura 1‑2: Esempio di eventi e della rispettiva sequenza di eventi.
Una computazione che è avviene come conseguenza di un evento è definibile genericamente come risposta (response). Quando la risposta si riferisce ad un evento specifico, è detta lavoro (job), vedi
figura 1-3.
Figura 1‑3: Esempio di un lavoro.
Una risposta (response)
è una sequenza di istruzioni che utilizza con continuità la CPU fino a al suo completamento. La CPU viene utilizzata in modo esclusivo dalla risposta.
Ovvero si assume che la risposta non venga sospesa durante la computazione. Ad
esempio per l’I/O si potrebbe considerare una situazione costituita da due o
più job. Se la computazione è portata a termine tramite una risposta che
necessita un cambiamento nell’allocazione delle risorse del sistema, tale
risposta deve essere ulteriormente scomposta in parti di lavoro più piccole.
La parte di lavoro più piccola di una risposta è detta azione. Una risposta può
quindi essere costituita da usa serie ordinata di azioni aventi la medesima
priorità, oppure differenti priorità. Ad esempio, con riferimento allo scenario
mostrato in figura 1-1, la risposta può essere modellata attraverso due azioni
aventi una differente priorità: una azione viene eseguita ,tramite l’handler
dell’interrupt che avviene livello di interrupt HW, e l’altra dal task
,associato con l’handler interrupt ed attivato dall’handler di interrupt,
eseguito a livello di priorità SW (vedi figura 1-4).
Figura 1‑4: Esempio di job costituito da due azioni.
Per semplificare l’analisi di schedulabilità, quando una risposta è costituita
da più azioni con priorità differente, deve essere trasformata in forma
canonica (convertendo una risposta in forma canonica non ne viene modificato il
tempo di completamento).
Una risposta è detta in forma canonica se è costituita da azioni le cui
priorità non decrescono.
Le azioni hanno inizio e terminano in punti di schedulazione (scheduling points).
I punti di schedulazione sono istanti di tempo in cui viene eseguita una
assegnazione (allocazione) delle risorse del sistema. Ad esempio si hanno
punti di schedulazione quando cambia la priorità di un task, quando un I/O ha
inizio o termina, oppure quando un task chiama un rendezvous, vedi figura 1-5.
Figura 1‑5: Esempio di punti di schedulazione.
Una sequenza di evento può essere classificata secondo le seguenti proprietà:
- Tipo (dipendente dalla sua
origine)
- Gli eventi della sequenza di evento sono detti eventi ambientali (environmental events) se sono generati dall’ambiente; questo tipo di evento indica un cambiamento
nello stato dell’ambiente.
- Gli eventi
sono detti eventi interni (internal events) quando sono generati
dal sistema stesso; questo tipo di evento indica un cambiamento nello
stato interno del sistema.
- Gli eventi sono detti eventi
temporali (timed events) se sono causati dal trascorrere del tempo:
ad esempio se si verifica un timeout.
- Pattern di arrivo della sequenza
di evento
- Il pattern di arrivo identifica quando l’evento sarà terminato per le risorse. L’evento di arrivo dei pattern può essere uno dei seguenti:
- I pattern di
arrivo dell’evento sono periodici se per ogni evento verificatosi ad un
tempo t , il successivo evento si verificherà ad un tempo
dove T
è una costante nota, e rappresenta il periodo; 
rappresenta una
piccola deviazione casuale dal tempo di arrivo periodico. Un periodico
pattern di arrivo dell’evento può anche essere caratterizzato da un
offset di tempo, detto valore di fase (phase value), relativo ad
un altro evento o ad uno specifico istante d tempo.
- Se per ogni
evento verificatosi ad un tempo t, il prossimo evento si verifica
al tempo dove
T non è costante, ma è in qualche modo conosciuto in anticipo, il
pattern di arrivo dell’evento è irregolare. Perciò un pattern irregolare
di arrivo di un evento è caratterizzato da una sequenza di intervalli.
- Quando il
pattern irregolare di arrivo di un evento permette di porre un tempo
minimo di intervallo tra due eventi successivi, il pattern è limitato.
Un pattern è limitato anche quando c’è un intervallo di tempo massimo tra due
eventi successivi.
Un minimo pattern limitato di arrivo può essere il risultato della fisica dello
stato del sistema, dei requisiti del sistema e/o dei vincoli HW/SW.
- Se il
prossimo evento può avvenire arbitrariamente poco dopo l’evento
precedente, ma il numero di eventi, in un periodo di tempo specificato, è
ristretto, allora il pattern di arrivo è detto bursty. Un bursty è
caratterizzato dalla densità bursty che consiste in:
ü
Un intervallo di burst (burst interval): la lunghezza del periodo
di tempo durante il quale il burst applica una restrizione.
ü
Una dimensione di burst (burst size): il numero di eventi che
possono verificarsi durante un intervallo di burst.
o Ogni qualvolta gli arrivi successivi dell’evento sono arbitrariamente vicini temporalmente e non sono né limitati né burst, allora sono detti illimitati. I pattern illimitati di arrivo di un evento possono essere descritti solo in modo statistico; la funzione di distribuzione è associata a ciascun pattern illimitato di arrivo di un evento.
Una sequenza aperiodica di evento è una sequenza di evento il cui pattern di
arrivo non è periodico. Una sequenza aperiodica include anche eventi con tempo
di arrivo irregolare, limitato, bursty ed illimitato.
I requisiti di tempo sono associati ad una risposta. Un requisito di tempo richiede che la risposta avvenga in una certa finestra temporale. Tale finestra temporale è sempre relativa all’evento che ha
attivato la risposta.
Una finestra di tempo ha un inizio ed una fine espressi come un offset temporale, relativi allo
stesso istante di tempo in cui si è verificato l’evento.
La notazione “finestra tra [0,t]” significa che la finestra temporale inizia nello stesso tempo in cui si verifica l’evento e si estende per t unità di tempo. Quando una finestra inizia a tempo 0 (come nell’esempio), la fine della finestra indica la deadline.
I requisiti di tempo possono essere classificati come:
- Hard: una risposta deve avvenire
entro una finestra di tempo; in caso contrario il sistema andrà in
fallimento.
- Soft: una risposta deve essere
soddisfatta entro determinato tempo medio. Il sistema è in grado di
tollerare lo sforamento della deadline
- Firm: tale requisito è formato da due componenti: una soft ed una hard. Per esempio: una risposta deve concludersi in un determinato periodo di tempo medio, ma può non rispettare fino a quattro deadline. Perciò ha un tempo medio di risposta di un periodo e una finestra di
tempo hard da 0 a quattro periodi di tempo.
Ciascuna azione
è caratterizzata dalle seguenti caratteristiche:
·
Priority: deve essere usata dalla politica di accesso alle
risorse condivise.
·
Usage: l’ammontare di tempo che utilizza ciascuna risorsa.
·
Allocation policy: dipende dal tipo di risorsa (ad esempio: CPU,
data object, backplane bus, device). Esempi di politiche sono: FIFO, LIFO,
Fixed priority based.
·
Atomic action: richiede che la risorsa sia usata dall’inizio alla
fine in modo esclusivo.
·
Jitter: è una misura della deviazione tra il tempo desiderato per
terminare l’azione e quello effettivamente trascorso per portarla a termine.
La caratteristica di jitter può essere specificata come:
o
n/a (non applicabile)
o assoluta (absolute): fissa il valore di deviazione relativo alla prima occorrenza dell’evento. Ad esempio: il tempo dell’ occorrenza (i+1)dell’evento deve essere:
Dove T rappresenta il periodo ed 
il valore del jitter assoluto.
Poiché il jitter assoluto è misurato dalla prima occorrenza dell’evento, questo
pone un limite assoluto all’errore tra computer time ed il wall clock time.
o Relativa (relative): fissa il valore della deviazione relativa solamente alla prima occorrenza dell’evento precedente. Ad esempio, al tempo (i+1) deve essere che:
Dove T rappresenta il periodo ed il valore del jitter relativo.
Siccome il jitter relativo viene misurato solo da quando si verifica l’evento
precedente, può esserci un continuo drift temporale sull’occorrenza dell’evento
che può interessare la sequenza dell’evento.
La caratteristica del jitter è associata all’inizio e/o alla fine di una
azione.
Il tempo di risposta di un job è pari al tempo intercorso tra la verifica dell’evento e il
completamento della risposta. Job differenti in una sequenza di evento hanno di solito tempi di risposta diversi; il tempo di risposta relativo al caso peggiore è il massimo valore di tempo tra tutti i job.
Se i job sono periodici ed indipendenti tra loro e le deadline non sono oltre la fine dei rispettivi periodi, un job di un evento periodico sarà nel caso peggiore se è iniziato nello stesso istante in cui
sono iniziati tutti gli atri job
con priorità più alta.
Questo istante di tempo è detto istante critico (critical instant).
D’altra parte,
se i job possono essere eseguiti anche oltre ai loro periodi, il caso peggiore
del tempo di esecuzione dell’evento 
avviene durante un periodo di
occupazione di livello 
(level busy period) iniziato
allo stesso istante di tutti gli altri job con priorità maggiore, oppure
durante un instante critico. Un periodo di occupazione di livello è un intervallo
di tempo durante il quale il processore è impegnato a ad eseguire i job aventi
la medesima o maggiore priorità rispetto al job .
La conoscenza di
un istante critico relativo ad un periodo di occupazione di livello che determina il
caso peggiore del tempo di risposta, consente ai progettisti di non
considerare tutte le fasi del lavoro eccetto quella che causa un instante
critico nel periodo di occupazione di livello , e di ignorare tutti i job eccetto
quelli iniziati all’istante critico relativo ad un periodo di occupazione di
livello .
L’utilizzazione 
associata ad una
periodica sequenza di evento 
è il rapporto tra il tempo di
esecuzione 
nel
caso peggiore ed il periodo 
(Quindi 
).
D’altra parte l’effettiva utilizzazione della sequenza di evento è una misura
che include anche gli effetti di un interruzione (pre-emption) e del bloccaggio
(blocking). La somma di tutte le singole utilizzazioni è chiamata utilizzazione
totale (total utilization) per l’insieme della sequenza di evento.
Gli effetti
causati dalla medesima o più alta priorità delle risposte, oppure dalle
risposte che iniziano con azioni aventi la medesima o maggiore priorità sono
conosciute come effetti di interruzione.
Gli effetti non cagionati da un interruzione, che causano un’attesa nella
risposta, sono detti effetti i bloccaggio (blocking effects).
Capitolo 2 : Struttura (framework) descrittiva per situazioni in tempo reale
Una situazione in tempo reale è un’astrazione che implica la conoscenza del comportamento temporale di un sistema in tempo reale o almeno parte di esso. Ciascuna situazione in tempo reale è un insieme di definizioni di sequenze di evento.
Supponiamo di avere un sistema in tempo reale caratterizzato dalle
seguenti caratteristiche:
- Il sistema deve affrontare tre
eventi:
,
ed
.
Tutti e tre gli eventi sono di tipo timed o environmental. - è una sequenza di evento
periodica con un periodo di 100 msec, con un requisito di tempo Hard ed
una finestra temporale [0,100].
- è una sequenza di evento
periodica con un periodo di 150 msec, con un requisito di tempo Hard ed
una finestra temporale [0,150].
- è una sequenza di evento
periodica con un periodo di 350 msec, con un requisito di tempo Hard ed
una finestra temporale [0,350].
- La risposta associata ad è multi
azione (multi actions) con differenti priorità
.
- La risposte associate ad ed sono a
singola azione, rispettivamente
ed 
.
- Le azioni usano la CPU, con utilizzo non atomico, e con una politica di utilizzo a priorità fissata (fixed priority).
Il tempo di una situazione in tempo reale può essere descritto utilizzando le quattro tabelle seguenti.
Tabella 2‑1:Esempio di tabella di eventi.
Tabella 2‑2: Esempio di tabella di risposte.
Tabella 2‑3: Esempio di tabella di azioni.
Una volta che un sistema in tempo reale è stato descritto, deve essere analizzato nel dominio temporale. Ci sono vari metodi e tecniche per analizzare la schedulabilità: la più importante di queste utilizza le informazioni presenti nella tabella degli eventi, nella tabella delle risposte ,in quella delle azioni, e nella tabella delle risorse. In questo modo una informazione ricavata è normalmente descritta nella tabella delle tecniche.
Tabella 2‑4: Esempio di tabella di tecniche.
Le tabelle seguenti riportano la sintesi del formalismo e possono essere utilizzate per descrivere situazione in tempo reale complesse.
Tabella 2‑5: Tabella degli eventi.
Tabella 2‑6: Tabella
delle risposte.
Tabella 2‑7: Tabella delle azioni.
Tabella 2‑8: Tabella delle risorse.
Tabella 2‑9: Tabella delle tecniche.
Capitolo 3 :Modello di sistemi in tempo reale: un approccio di base
Una situazione in tempo reale può essere modellata con un approccio di base ,descritto in questo capitolo ed avente le seguenti proprietà:
- Una schedulazione a proprietà fissata non su un sistema operativo.
- La CPU e la data rate sono le uniche risorse contese.
- Le situazioni in tempo reale sono relative ad un ambiente in cui è presente un solo processore.
3.1 Gestire eventi periodici con una deadline entro o dopo la fine dei periodi (senza condivisione di dati)
3.1.1 Eventi periodici nel tempo
Supponendo di considerare una
situazione in tempo reale descritta dalle seguenti tabelle:
Tabella 3‑1: Eventi periodici nel tempo con deadline minore o uguale al periodo –
Tabella degli eventi.
Tabella 3‑2: Eventi periodici nel tempo con deadline minore o uguale al periodo – Tabella delle risposte.
Tabella 3‑3: Eventi periodici nel tempo con deadline minore o uguale al periodo – Tabella delle azioni.
Tabella 3‑4: Eventi periodici nel tempo con deadline minore o uguale al periodo – Tabella delle risorse.
In tale modo una situazione in tempo reale è caratterizzata dalle seguenti proprietà:
- Ciascuna risposta possiede una
singola azione che è implementata come un singolo task.
- Ciascun task ha una sola deadline
con assegnamento monotonico della priorità (ad esempio la deadline più
corta corrisponde la priorità più alta).
- Tutti gli eventi sono eventi di tipo timed.
Lo pseudocodice mostrato nella figura sottostante rappresenta un paradigma di implementazione del task 1 che può essere utilizzato per ciascuno dei task.
Figura 3‑1: Eventi periodici nel tempo con deadline minori o uguali al periodo – Pseudocodice.
La tabella delle tecniche associate ad una situazione in tempo reale è mostrata subito sotto.
Tabella 3‑5: Eventi periodici nel tempo con deadline minore o uguale al periodo – Tabella delle tecniche.
3.1.2 Eventi ambientali periodici
Supponendo di considerare una situazione in tempo reale descritta dalle successive tabelle:
Tabella 3‑6: Eventi ambientali periodici con deadline minore o uguale al periodo – Tabella degli eventi.
Tabella 3‑7: Eventi ambientali periodici con deadline minore o uguale al periodo – Tabella delle risposte.
Tabella 3‑8: Eventi ambientali periodici con deadline minore o uguale al periodo – Tabella delle azioni.
Tabella 3‑9: Eventi ambientali periodici con deadline minore o uguale al periodo – Tabella delle risorse.
In tale modo una situazione in tempo reale è caratterizzata dalle seguenti proprietà:
·
Tutti i task possiedono una deadline con assegnamento monotonico
di priorità.
·
Due azioni con differenti proprietà sono associate con e2: un
ciclo di servizio di interrupt è seguito da un task applicativo per la maggior
parte della risposta.
·
La priorità HW possiede la priorità più alta rispetto a tutte le
altre.
· e1 ed e3 sono eventi di tipo timed; e2 è un evento di tipo environmental.
Lo pseudocodice nella figura sottostante rappresenta un paradigma di
implementazione per 
.
Figura 3‑2: Eventi ambientali periodici con deadline minore o uguale al periodo – Pseudocodice.
La tabella delle tecniche associata alla situazione in tempo reale è la
seguente:
Tabella 3‑10: Eventi ambientali periodici con deadline minore o uguale al periodo – Tabella delle tecniche.
3.2 Gestione di eventi periodici aventi deadline entro la fine dei periodi (senza condivisione di dati)
L’estensione della risposta oltre il periodo può essere causata da una serie di condizioni. Alcuni esempi sono:
- Una risposta a bassa frequenza
compiuta ad alta priorità che introduce un’imprevista interferenza.
- Un alto utilizzo totale della CPU.
3.2.1 Eventi periodici nel tempo
Ipotizzando di considerare una situazione in tempo reale descritta dalla seguente tabella:
Tabella 3‑11: Eventi periodici con deadline dopo il periodo – Tabella degli eventi.
Tabella 3‑12: Eventi periodici con deadline dopo il periodo – Tabella delle risposte.
Tabella 3‑13: Eventi periodici con deadline dopo il periodo – Tabella delle azioni.
Tabella 3‑14: Eventi periodici con deadline dopo il periodo – Tabella delle risorse.
In tale modo una situazione in tempo reale è caratterizzata dalle seguenti proprietà:
- Ciascuna risposta possiede
un’unica azione che viene implementata come un singolo task.
- Tutti gli eventi sono di tipo
timed.
- L’occorrenza di ciascun evento è
processata o messa in coda, ma in ogni caso non viene perduta.
- Anche se e2 si presenta ogni 83 msec, sono permessi 500 msec per la risposta.
Lo pseudocodice nella figura sottostante mostra un paradigma di implementazione
per il task 2.
Figura 3‑3: Eventi periodici con deadline dopo il periodo – Pseudocodice.
Nella maggior parte dei kernel il sistema Sleep_Until viene chiamato immediatamente e ritorna quando il next_time è maggiore o uguale del tempo corrente; in questo caso il blocco di “if” può essere eliminato.
La tabella delle tecniche associata con una situazione in tempo reale è la seguente:
Tabella 3‑15: Eventi periodici con deadline dopo il periodo – Tabella delle tecniche.
3.2.2 Eventi ambientali periodici
Ipotizzando di considerare una situazione in tempo reale descritta dalle seguenti tabelle:
Tabella 3‑16: Eventi ambientali periodici con deadline dopo il periodo – Tabella degli eventi.
Tabella 3‑17: Eventi ambientali periodici con deadline dopo il periodo – Tabella delle risposte.
Tabella 3‑18: Eventi ambientali periodici con deadline dopo il periodo – Tabella delle azioni.
Tabella 3‑19: Eventi ambientali periodici con deadline dopo il periodo – Tabella delle risorse.
In tale modo una situazione in tempo reale è caratterizzata dalle seguenti proprietà:
- L’occorrenza di ciascun evento è
messa in coda via software.
- Anche se e2 si presenterà ogni 83 msec, sono ammessi 500 msec per la risposta.
Lo pseudocodice nella figura sottostante rappresenta una paradigma dell’implementazione del task 2.
Figura 3‑4: Eventi ambientali periodici con deadline dopo il periodo – Pseudocodice.
La tabella delle tecniche associata con una situazione in tempo reale è la seguente:
Tabella 3‑20: Eventi ambientali periodici con deadline dopo il periodo – Tabella delle tecniche.
3.3 Gestione di eventi periodici con dati condivisi
La condivisione di dati porta all’introduzione di blocchi di temporali. La notazione seguente è utilizzata per gli algoritmi di analisi della schedulabilità:
è il ritardo bloccante che
subisce l’evento 
.
- m è il numero di risorse.
- n è il numero di eventi.
è il limite massimo di
priorità della risorsa r.
è la quantità di tempo in
cui l’evento utilizzerà la risorsa r.
Con una sola risorsa disponibile, si accorcia fino a
.
Se l’evento non utilizza la risorsa r,
allora è
nullo.
3.3.1 Uso del protocollo di Masking-Interrupt (IMP)
Ogni task che utilizza una risorsa se ne garantisce l’accesso esclusivo tramite il mascheramento di tutti gli interrupt prima di utilizzare la risorsa e smascherandoli dopo averla utilizzata. Mascherare gli interrupt corrisponde ad impostare la priorità del task a livello degli interrupt HW.
Ipotizzando di considerare una situazione in tempo reale descritta dalle seguenti tabelle:
Tabella 3‑21: Uso dell’ IMP – Tabella degli eventi.
Tabella 3‑22: Uso dell’ IMP – Tabella delle risposte.
Tabella 3‑23: Uso dell’ IMP – Tabella delle azioni.
Tabella 3‑24: Uso dell’ IMP – Tabella delle risorse.
Lo pseudocodice nella figura sottostante mostra il paradigma di una implementazione per il task 2, che può essere utilizzato da altri task che condividono delle risorse.
Figura 3‑5: Uso dell’ IMP – Pseudocodice.
Nella maggior parte dei kernel il sistema Sleep_Until viene chiamato immediatamente e ritorna quando il next_time è maggiore o uguale del tempo corrente; in questo caso il blocco di “if” può essere eliminato.
Il protocollo di mascheramento dell’interrupt, usato in accordo col paradigma nello pseudocodice garantisce che la risposta possa essere bloccata almeno da una singola sezione critica. Per computare il ritardo bloccante associato con ciascun evento, può essere utilizzato l’algoritmo seguente:
- Passo 1: Ordinare gli eventi
nella tabella delle tecniche in modo decrescente (il livello con priorità
più alta per primo).
- Passo 2: Inizializzare b = 0.
- Passo 3: Cominciare con l’evento a priorità più bassa; impostare i = n.
- Passo 4: Calcolare il ritardo
bloccante (blocking delay);
.
- Passo 5: Aggiornare la variabile
bloccante; if (
.
·
Passo 6: Iterare. 
, if (
) vai al passo 4, in caso contrario terminare l’algoritmo.
La tabella delle tecniche associata con una situazione in tempo reale è la seguente:
Tabella 3‑25: Uso dell’ IMP – Tabella delle tecniche.
3.3.2 uso del protocollo Highest Locker (HLP)
Condividendo più risorse si introducono anche dei problemi nuovi rispetto al caso di condivisione
di un'unica risorsa.
Due di questi problemi sono la deadlock (punto morto) ed il chain blocking (blocco della catena). Una insieme di risposte è in uno stato di deadlock quando ogni risposta dell’insieme sta utilizzando una risorsa e sta aspettando che un’altra risorsa si liberi che deve essere rilasciata da un’altra risposta dell’insieme. Il chain blocking è un tipo di blocco che può manifestarsi ogni volta che viene richiesto un nuovo bloccaggio di una risorsa.
Nella maggior parte degli algoritmi di schedulazione sono stati concepiti sia per affrontare l’accesso mutuamente esclusivo a più risorse, sia per risolvere problemi di deadlock e di chain blocking. Uno di questi algoritmi di schedulazione è basato sul protocollo highest locker o sul protocollo immediate ceiling. Tutte le risorse hanno un limite massimo di priorità definito, prima della compilazione, come il più alto livello di priorità tra tutti i task che potrebbero potenzialmente utilizzare quella determinata risorsa. Pertanto, quando un task ha bisogno di una risorsa in fase run-time il suo livello di priorità viene impostato ad un livello più alto rispetto al livello massimo di priorità della risorsa; nessun altro task che utilizza quella risorsa può essere fare richiesta della risorsa quando questa è in uso (nessun task che utilizza una risorsa può essere sospeso durante una
sezione critica; può essere generato un chain blocking.
Inoltre, se l’implementazione dell’ HLP non utilizza una coda di attesa per i thread bloccati su una sezione critica occupata, può manifestarsi un comportamento anormale).
Ipotizziamo di avere a che fare con una situazione in tempo reale descritta dalle seguenti tabelle:
Tabella 3‑26: Uso dell’ HLP – Tabella degli eventi.
Tabella 3‑27: Uso dell’ HLP – Tabella delle risposte.
Tabella 3‑28: Uso dell’ HLP – Tabella delle azioni.
Tabella 3‑29: Uso dell’ HLP – Tabella delle risorse.
Lo pseudocodice nella figura sottostante mostra il paradigma di un implementazione per il task 2. Può essere utilizzata per qualsiasi task che condivida delle risorse.
Figura 3‑6: Uso dell’ HLP – Pseudocodice.
Nella maggior parte dei kernel il sistema Sleep_Until viene chiamato immediatamente e ritorna quando il next_time è maggiore o uguale del tempo corrente; in questo caso il blocco di “if” può essere eliminato.
Generalmente ogni risorsa possiede un livello massimo differente. I livelli più alti nell’esempio sono invece identici e pari a 19 per semplicità. E’ importante notare che la priorità è inizialmente impostata al valore originale e successivamente incrementata fino a raggiungere il tetto massimo
per la risorsa.
Questo approccio assicura che l’effetto di bloccaggio sulle risposte a priorità più alta corrisponda al ritardo bloccante maggiore e non alla somma delle fasi di esecuzione delle sezioni critiche.
Il protocollo
HLP garantisce che una risposta può essere bloccata almeno una volta da una
sezione critica avente un livello di priorità più basso. Per calcolare il
ritardo bloccante associato ad ogni evento, è possibile utilizzare l’algoritmo
seguente; l’elemento 
è l’elemento di un array
monodimensionale che indica il massimo contributo ad un ritardo bloccante dalla
risorsa r.
- Passo 1: Ordinare gli eventi
nella tabella delle tecniche secondo la loro priorità in modo decrescente
(dalla più alta alla più bassa).
- Passo 2: Inizializzare l’array
monodimensionale a zero; ovvero impostare a zero il valore di ogni
elemento dell’array.
- Passo 3: Iniziare con l’evento a
priorità inferiore, sia
.
- Passo 4. Calcolare il ritardo
bloccante,
;
- Passo 5: Aggiornare l’array: per
ogni risorsa condivisa dall’evento
:
if (
)
;
dove è l’ammontare di
tempo per cui l’evento utilizzerà la risorsa r; è impostato a
zero nel caso non utilizzi la risorsa.
- Passo 6: Controllare il tetto massimo (ceiling) di ogni risorsa r
if (
) <terminare
l’algoritmo>;
else if (
) 
;
Dove
è la
priorità del task i-1 e è il tetto massimo della risorsa r.
·
Passo 7: Iterare. i = i-1, andare al passo 4.
La tabella delle tecniche associata con una situazione in tempo reale è la seguente, dove le risposte eseguite alla medesima priorità e che utilizzano una stessa risorsa sono collassate in un’unica azione.
Tabella 3‑30: Uso dell’ HLP – Tabella delle tecniche.
3.4 Gestione di eventi aperiodici: Arrivi limitati con hard deadline
Gli arrivi aperiodici sono limitati
da un minimo tempo di inter-arrivo.
Ipotizzando di avere a che fare con una situazione in tempo reale descritta
dalle seguenti tabelle:
Tabella 3‑31: Arrivi limitati con hard deadline – Tabella degli eventi.
Tabella 3‑32: Arrivi limitati con hard deadline – Tabella delle risposte.
Tabella 3‑33: Arrivi limitati con hard deadline – Tabella delle azioni.
Tabella 3‑34: Arrivi limitati con hard deadline – Tabella delle risorse.
Per affrontare eventi aperiodici è necessario considerare i seguenti punti chiave.
- Tipo di riconoscimento
dell’evento: l’occorrenza dell’evento avviene tramite l’interrupt di un
processore o un ciclo di polling sullo stato del flag dell’evento?
- Priorità di un servizio
aperiodico: è la risposta eseguita a livello di priorità HW, SW, o combinata
?
- Capacità di
esecuzione: L’utilizzo della CPU per un evento aperiodico è limitato in
qualche modo attraverso la limitazione del tempo di esecuzione dei
processi o del tempo di arrivo ?
Poiché gli interrupt provvedono a fornire un servizio su richiesta, riescono ad offrire tempi di risposta rapidi. Tuttavia, questo servizio ad alta priorità può essere potenzialmente dannoso per la schedulabilità di task con un basso livello di priorità. Inoltre, se l’ipotesi di arrivi limitati è violata, possono esserci gravi conseguenze sui task a bassa priorità. D’altra parte, il polling consente di governare a priori, in modo predicibile, gli eventi aperiodici (la conseguenza di una violazione dell’ipotesi sul minimo tempo di interarrivo è conosciuta e limitata), ma non consente di avere servizi su richiesta; in questo modo, la concomitanza di deadline vicine e brevi periodi di polling
possono portare ad un overhead eccessivo.
Possono essere utilizzate quattro differenti implementazioni per affrontare eventi aperiodici limitati
·
Implementazione 1: utilizza gli interrupt per riconoscere gli
eventi. Il servizio di tipo aperiodico è garantito attraverso una priorità a
livello HW e non è utilizzata una esplicita politica per limitare il tempo di
esecuzione di task ad alta priorità. Perciò questa soluzione può essere
pericolosa quando il numero degli arrivi eccede il limite. Può essere
utilizzato quando i tempi della risposta sono molto corti e il tempo di
esecuzione al oltre il limite è noto, ed i burst degli arrivi aperiodici sono
fisicamente impossibili.
·
Implementazione 2: utilizza gli interrupt per riconoscere gli
eventi. Tuttavia un servizio di tipo aperiodico è garantito prevalentemente a
livello di priorità SW. Utilizzando questa implementazione il progettista può
raggiungere un compromesso tra un rapido tempo della risposta e l’effetto
dell’intrusività dell’interrupt. Purtroppo questa implementazione, come la
precedente, può causare situazioni pericolose se viene superato il limite del
tempo di arrivo.
·
Implementazione 3: utilizza il polling, una metodologia sicura e
ben conosciuta. Il servizio aperiodico viene eseguito a livello di priorità SW.
Il tempo di risposta dipende dal periodo di polling.
· Implementazione 4: come l’implementazione 2 utilizza gli interrupt per riconoscere gli eventi, ed il servizio aperiodico è garantito prevalentemente a livello di priorità SW. Diversamente dalla implementazione 2, viene utilizzato l’algoritmo sporadic server. Adoperando questo algoritmo si ottiene un tempo della risposta simile a quello della implementazione 2, ma si è sicuri riguardo al tempo di arrivo.
Gli aspetti critici relativi all’implementazione 1 e 2 sono già stati trattati in precedenza.
3.4.1 Gestione di eventi aperiodici: Arrivi limitati con hard deadline -Polling
Riguardo alla implementazione 3, bisogna prendere in considerazione le seguenti proprietà:
- Ogni risposta periodica ha una
singola azione implementata come un singolo task.
- Ogni risposta aperiodica ha due
eventi ad essa associati: il primo evento è l’occorrenza dell’evento
aperiodico, il secondo evento è l’evento di polling (che è controlla se
l’evento si è verificato e necessita di essere processato).
- Il progettista dell’applicazione assegna la priorità ai task di polling.
Ipotizzando di avere a che fare con una situazione in tempo reale descritta dalle seguenti tabelle:
Tabella 3‑35: Arrivi limitati con hard deadline – Tabella degli eventi - Polling.
Tabella 3‑36: Arrivi limitati con hard deadline – Tabella delle risposte - Polling.
Tabella 3‑37: Arrivi limitati con hard deadline – Tabella delle azioni - Polling.
Tabella 3‑38: Arrivi limitati con hard deadline – Tabella delle risorse - Polling.
La risposta agli
eventi e1 ed e2 usa l’operatore di select: p1 e p2 sono eseguiti
incondizionatamente mentre le azioni a1 e/o a2 è/sono eseguita/e solo se uno o
più eventi si sono presentati durante il periodo di polling precedente e non
sono ancora stati processati.
Il caso peggiore del tempo della risposta per un evento aperiodico si ha se l’evento si verifica subito dopo che il task di polling ha controllato l’arrivo degli eventi. Perciò, la relazione tra il periodo di polling (Tpoll), la deadline (Dpoll) e la deadline degli eventi aperiodici (D) deve soddisfare:
Applicando questa regola all’evento di polling p1, e ipotizzando che la deadline Dpoll sia uguale al periodo Tpoll,
5 (msec) – Tpoll 0 Dpoll, allora
5(msec) – Tpoll = Tpoll
Tpoll = 2.5 msec
Le proprietà di tutti I task, sia periodici che di polling, devono essere assegnati in accordo con la deadline o con un assegnamento a rate monotonica.
Lo pseudocodice sottostante rappresenta l’implementazione della gestione di interrupt per un task di polling.
Figura 3‑7: Task di polling - Pseudocodice.
Il sistema sembrerà essere periodico. Tuttavia, siccome l’esecuzione predominate dei task di polling avviene quando si presenta un evento aperiodico, l’analisi diventa complicata rispetto al caso puramente periodico.
Il task di polling è formato da due parti. La prima parte dei task di polling (p1 o p3) sono eseguiti ad ogni periodo di polling. Questa parte controlla semplicemente il flag dell’evento, calcola l’inizio del prossimo periodo di polling e chiama il sistema di Sleep_Until. Questa parte è trattata come un task periodico.
La seconda parte (a1 o a2) viene eseguita in modo condizionale, a seconda che l’evento aperiodico si sia presentato durante l’ultimo periodo di polling. Questa parte può essere trattata come un task periodico utilizzando il minimo intervallo (dall’evento e1 o e3) come periodo e il tempo di processazione dell’evento come tempo di esecuzione. Tuttavia, in determinate circostanze, questo trattamento può portare a risultati ottimistici quando si stima l’analisi di schedulabilità di eventi a bassa priorità (può presentarsi un effetto di esecuzione differita). Per affrontare questa situazione, si può fare un ulteriore test per assicurasi che i risultati non siano ottimistici e per correggere il tempo della risposta se è ottimistico.
3.4.2 Gestione di eventi aperiodici: Arrivi limitati con hard deadline - Sporadic Server
Lo sporadic server è un meccanismo per la schedulazione di eventi aperiodici che garantiscono un impatto di schedulabilità sugli altri task. Per quanto riguarda lo sporadic server, bisogna prendere in considerazione le seguenti proprietà:
- Ogni risposta periodica ha una
singola azione che è implementata come un singolo task.
- Ogni risposta
aperiodica è formata da due azioni. La prima azione è implementata come la
gestione di un interrupt, ed eseguita per un periodo di tempo molto corto
(tipicamente eseguendo solamente le istruzioni a servizio dell’interrupt e
per il reset dell’HW); la seconda azione è implementata come un generico
task che viene attivato da un gestore di interrupt. Questo task è
schedulato utilizzando lo sporadic server.
- Il gestore di interrupt è
eseguito con il livello di priorità più alto (che di solito corrisponde
alla priorità HW).
- Le priorità dei task sono assegnate in accordo con un assegnamento di tipo monotonico.
La situazione in tempo reale descritta sopra diventa la seguente:
Tabella 3‑39: Arrivi limitati con hard deadline – Tabella degli eventi – Sporadic Server.
Tabella 3‑40: Arrivi limitati con hard deadline – Tabella delle risposte – Sporadic Server.
Tabella 3‑41: Arrivi limitati con hard deadline – Tabella delle azioni – Sporadic Server.
Tabella 3‑42: Arrivi limitati con hard deadline – Tabella delle risorse – Sporadic Server.
Le azioni i1 ed i3 sono eseguite con un livello di priorità HW. Si assume che il livello di priorità di i1 sia maggiore di quello di i3 (i1 maschera gli interrupt che i3 chiama).
L’algoritmo
sporatic server (SS) genera un task ad alta priorità per soddisfare i task
aperiodici. L’algoritmo SS conserva il tempo di esecuzione di server al suo
livello di priorità fino a che non si verifica una richiesta aperiodica.
L’algoritmo SS riempie il tempo di esecuzione del server dopo che alcuni o
tutti i tempi di esecuzione sono occupati dall’esecuzione di un task
aperiodico.
I seguenti punti sono usati per spiegare il metodo di riempimento del tempo di
esecuzione dell’algoritmo SS:
rappresenta il livello di
priorità del task al quale il sistema lo sta eseguendo.
è uno dei livelli di priorità
del sistema. I livelli di priorità sono numerati in modo consecutivo
secondo la loro priorità dove 
rappresenta il livello di
priorità più alta, e 
al secondo livello di priorità
e così via.
- Active è il termine usato per
descrivere un livello di priorità. Un livello di priorità è
considerato attivo se il livello corrente di priorità del sistema è maggiore
o uguale al più alto dei livello di priorità di.
- Idle è il termine che ha il
significato opposto rispetto ad active. Un livello di priorità è idle se
il livello corrente di priorità del sistema è inferiore rispetto al
livello di priorità di .
rappresenta il tempo di
reintegrazione per il livello di priorità . Questo è il tempo in cui
avviene l’esecuzione per lo sporadic server del livello di priorità che sarà
riempito. Tuttavia il tempo di reintegrazione è impostato allo
stesso livello di priorità del tempo corrente più il periodo di .
L’algoritmo sporadic server è caratterizzato dai tre seguenti parametri:
·
Priorità (priorità): la priorità alla quale la risposta ad un
evento aperiodico viene eseguita.
· Capacità di esecuzione (execution capacity): è la capacità di un tempo di esecuzione che è assegnata a dei task periodici. I task periodici possono essere eseguiti alla priorità predefinita dello sporadic server, se c’è una sufficiente capacità di esecuzione. Quando la capacità è esausta, i task aperiodici devono abbandonare il processore o essere eseguiti con
una priorità di background.
· Periodo di reintegrazione: la quantità di tempo che deve intercorrere prima che sia ripristinata la capacità di esecuzione esausta.
Per determinare il tempo per reintegrare il periodo di esecuzione consumato dallo sporadic server bisogna considerare due operazioni separate (1) determinare il tempo durante il quale ogni tempo di esecuzione può essere reintegrato e (2) determinare l’ammontare del tempo di esecuzione che potrebbe essere reintegrato. Una volta che entrambe le operazioni sono concluse, la reintegrazione può essere effettuata. Il tempo in cui queste operazioni sono compiute dipende dal tempo di esecuzione disponibile dello sporadic server e dallo stato active o idle del livello di priorità dello sporadic server.
La regole per queste due operazioni sono definite nei punti seguenti per uno sporadic server
eseguito a livello di priorità .
1.
Se il server ha un tempo di esecuzione disponibile, il tempo di
reintegrazione è
impostato quando il livello di priorità dello sporadic server diventa attivo o
la capacità del server si è esaurita ed non può essere reintegrato fino a
che la capacità del server diventa maggiore di zero e è attivo. In tutti i casi
il valore di è
impostato ad un valore uguale al valore di tempo corrente più il periodo di .
2.
La quantità di tempo di esecuzione da reintegrare può essere determinata
quando il livello di priorità dello sporadic server diventa idle oppure quando
il tempo di esecuzione disponibile dello sporadic server è stato esaurito.
L’ammontare di tempo per reintegrare è uguale alla quantità di tempo di
esecuzione del server consumato dall’istante in cui lo stato di passa da idle ad
active.
L’implementazione
dell’algoritmo SS richiede dei meccanismi a livello del kernel o supporti a
livello run time. Tuttavia, se le ipotesi e le restrizioni seguenti possono
essere applicate, è possibile applicare un algoritmo SS semplificato
implementato a livello applicativo:
· Il caso peggiore del tempo di esecuzione per ogni task aperiodico deve essere conosciuto. Ciascun tempo di un task aperiodico utilizza il suo sporadic server; è ipotizzato che i task aperiodici consumano un ammontare di tempo di esecuzione dello sporadic server pari alù
peggior
tempo di esecuzione dei task aperiodici.
· I task aperiodici che utilizzano gli sporadic server devono contare su uno sporadic server per essere eseguiti. In altre parole, un task aperiodico non può essere eseguito come task a bassa priorità sia quando è esaurita la capacità dello sporadic server, sia quando il processore è idle oppure come task ad alta priorità mentre viene reintegrata la capacità di
qualche
sporadic server.
· Ad uno sporadic server non è consentito soddisfare un task fino a che non possiede un tempo di esecuzione superiore o uguale al caso peggiore del tempo di esecuzione di un task aperiodico. Se uno sporadic server non possiede una capacità sufficiente per servire completamente un task aperiodico, il task aperiodico deve attendere fino a che il tempo di esecuzione disponibile dello sporadic server non è reintegrato ad un valore maggiore o uguale al caso peggiore del tempo di esecuzione di un task aperiodico. E’ necessario fare questa restrizione perché una volta che lo sporadic server comincia a schedulare un task aperiodico, non ha modo di sospendere quel servizio fino a che il suo tempo di esecuzione
non è
esaurito.
· Poiché il task dello sporadic server non può localizzare lo stato active o idle dei livelli di priorità nel sistema senza un apposito kernel o un meccanismo di supporto a run time, si deve usare una versione semplificata della politica di reintegrazione dello sporadic server.
Una
versione semplificata è la seguente:
ü
Per definizione un livello di priorità dello sporadic server deve
essere active se il suo tempo di esecuzione comincia ad essere consumato.
Perciò, utilizzando il tempo di esecuzione durante il quale il tempo di
esecuzione dello sporadic server è inizialmente consumato, come origine da cui
sono determinati i tempi di reintegrazione non è possibile provvedere ad una
schedulazione di reintegrazione eseguita prima della individuazione dello stato
active/idle dei livelli di priorità.
ü In tale modo una politica di reintegrazione semplificata necessita che il tempo di esecuzione dello sporadic server sia schedulato per la reintegrazione un periodo dopo che il servizio dello sporadic server è iniziato.
Un inconveniente di questa politica di reintegrazione semplificata è che
qualche reintegrazione non si verifichi il più presto possibile.
Lo pseudocodice sottostante rappresenta l’implementazione di un gestore di interrupt e la versione semplificata dello sporadic server (nell’esempio si assume anche che tutte le richieste aperiodiche possiedano lo stesso WCET).
Figura 3‑8: Sporadic Server – Pseudocodice.
Capitolo 4 :Trovare un metodo di schedulabilità
4.1 Uso di un limite di utilizzo per l’intera situazione in tempo reale.
In presenza delle seguenti circostanze, si può utilizzare un limite di utilizzo per controllare la schedulabilità dell’intera situazione in tempo reale.
- Le deadline devono corrispondere
al termine del periodo.
- Una o tutte le azioni associate
con ciascun evento hanno lo stesso valore di priorità.
- Le priorità sono assegnate in
accordo con la teoria di rate monotonica.
L’analisi di schedulabilità deve essere fatta attraverso i seguenti passi:
Passo 1 – Calcolare l’utilizzo totale per di tutti gli eventi
Passo 2 – Calcolare il periodo di
blocco
Passo 3 – Calcolare il limite di utilizzo
Passo 4 – Confrontare il limite di utilizzo con il limite effettivo di utilizzo
Se questa disuguaglianza è verificata, allora l’insieme dei task è schedulabile.
Esempio passo-passo
Notare la tabella delle tecniche seguente.
Tabella 4‑1: Esempio di schedulabilità – Tabella delle tecniche.
Passo 1 – Calcolare l’utilizzo totale per di tutti gli eventi
Passo 2 – Calcolare il periodo di blocco
Passo 3 – Calcolare il limite di utilizzo
Passo 4 – Confrontare il limite di utilizzo con il limite effettivo di utilizzo
L’insieme dei task risulta schedulabile.
4.2 Utilizzo dei limiti di utilizzazione per ciascun evento quando le deadline sono entro il periodo.
Sotto i seguenti punti, è possibile usare i limiti di utilizzo per ogni evento con deadline entro il periodo per controllare la schedulabilità di una sequenza di eventi:
- Le deadline devono essere minori
o uguali alla fine dei periodi.
- Una o tutte le azioni associate
con ciascun evento possiedono il medesimo valore di priorità
- Le priorità sono assegnate
liberamente (non necessariamente secondo una rate monotonica o tramite la
teoria delle deadline monotoniche)
L’analisi di
schedulabilità per una generica sequenza di eventi può essere calcolata tramite
i passi seguenti:
Passo 1 – Identificare l’insieme H degli eventi che sono processati con una priorità maggiore o uguale alla priorità Pi associata ad ei.
Partizionare H
in due sottoinsiemi, H = H1 U Hn, dove H1 raggruppa tutte le sequenze di eventi
che aventi un periodo maggiore o uguale a Di, la deadline associata a ei,
mentre Hn è invece costituito da tutte le sequenze di eventi minori di Di. Il
sottoinsieme H1 è designato a sostenere le sequenze di eventi che possono
liberare ei per una sola volta prima della sua deadline in Di; mentre le
sequenze degli eventi nell’insieme Hi liberano ei ancora più tempo prima di Di.
Passo 2 – Calcolare il limite effettivo dell’utilizzo totale per la sequenza di
eventi ei
Il limite effettivo dell’utilizzo totale è costituito da due termini.
- L’utilizzo totale degli eventi
dell’insieme Hn più
- Il tempo di esecuzione di ei, sommato al ritardo bloccante, sommato al tempo di liberazione prima degli eventi di h1, tutto diviso per il periodo di ei.
Così
Passo 3 – Determinare il limite di
utilizzo 
Con
Passo 4 – Confrontare l’utilizzo
effettivo con il limite di utilizzo
Se il limite di effettivo è minore
o uguale al limite di utilizzo 
, la sequenza degli eventi ei
incontra la sua deadline.
I passi sopra elencati devono essere applicati a ciascuna sequenza di eventi che
ha esigenza di tempi della risposta quando la schedulabilità della intera
situazione in tempo reale è richiesta.
Esempio passo-passo.
Vedi la tabella delle tecniche seguente e controlla la schedulabilità di e4.
Tabella 4‑2: Esempio di schedulabilità – Tabella delle tecniche.
Passo 1 - Identificare l’insieme H
delle sequenze di eventi che sono processati a priorità maggiore o uguale alla
priorità 
associata
ad 
Passo 2 – Calcolare il limite
effettivo di utilizzo totale per la sequenza di eventi
Passo 3 – Determinare il limite di
utilizzo
Passo 4 – Confrontare l’effettivo
utilizzo con il limite di utilizzo
La sequenza degli eventi è schedulabile.
Capitolo 5 :Ottenere una valutazione precisa di schedulabilità con deadline e bloccaggio arbitrari
Se l’effettivo
utilizzo della sequenza di eventi ei non è superiore a 1,0 la sua deadline può
essere oltre il relativo periodo ed il bloccaggio può essere arbitrario; i
passi seguenti possono essere utilizzati per controllare la schedulabilità
della sequenza di eventi ei.
Questi passi devono essere applicati ad ogni sequenza di eventi con requisiti
di tempestività.
Passo 1 – Calcolare un valore
approssimato di 
per il tempo di completamento del
primo job nel periodo di occupazione.
Dove le sequenze di eventi sono in ordine di priorità, e1 è la sequenza di eventi a più alta priorità.
Passo 2 – Inizializzare il contatore k ad 1
Il contatore k può assumere valori da 1 al numero dei job, nel periodo di occupazione. Il contatore k è incrementato ogni volta che il tempo di esecuzione del prossimo job è preso in considerazione.
Passo 3 – Calcolare la prossima
approssimazione 
Dove è la funzione di tetto massimo (ad esempio arrotonda x all’intero vicino più alto).
Passo 4 – Determinare se
l’approssimazione è il tempo di completamento del job
Passo 5 – Determinare il tempo
della risposta del job
Mentre il passo 5 viene eseguito è uguale a 
quindi:
Passo 6 – Controlla se è terminato il periodo di occupazione
Passo 7 – Determinare il peggior caso del tempo della risposta
Il massimo
valore di tutti i 
con b che varia da 1 a k, questo valore è il caso peggiore del tempo della risposta della sequenza di eventi ei.
Esempio passo-passo.
Considerare la seguente tabella delle tecniche, e calcolare il caso peggiore del tempo della risposta di e2.
Tabella 5‑1: Esempio di schedulabilità – Tabella delle tecniche.
Passo 1 –
Calcolare un valore approssimato di per il tempo di completamento del
primo job nel periodo di occupazione.
Passo 2 – Inizializzare il contatore k ad 1
k = 1
Passo 3 – Calcolare la prossima
approssimazione
Passo 4 – Determinare se
l’approssimazione è il tempo di completamento del job
Passo 3 – Calcolare la prossima
approssimazione
Passo 4 – Determinare se
l’approssimazione è il tempo di completamento del job
Passo 5 – Determinare il tempo
della risposta del job
Mentre il passo 5 viene eseguito è uguale a quindi:
Dove 
è il caso peggiore del tempo della
risposta del primo job di e2.
Passo 6 – Controllare se è terminato il periodo di occupazione
Passo 3 – Calcolare la prossima
approssimazione
Passo 4 – Determinare se
l’approssimazione è il tempo di completamento del job
Passo 3 – Calcolare la prossima
approssimazione
Passo 4 – Determinare se
l’approssimazione è il tempo di completamento del job
Passo 5 – Determinare il tempo
della risposta del job
Mentre il passo 5 viene eseguito è uguale a quindi:
Dove 
è il caso peggiore del tempo della
risposta del secondo job di e2.
Passo 6 – Controllare se è terminato il periodo di occupazione
Passo 7 – Determinare il peggior caso del tempo della risposta
Ci sono due job
nel periodo di occupazione. Il massimo tra e è 160 ms, che è uguale al valore
della deadline e2.
La sequenza di eventi e2 può essere completata entro la sua deadline.
Capitolo 6 :Analisi di schedulabilità: alcuni esempi
6.1 Analisi di schedulabilità: eventi a tempo periodico con deadline minori o uguali al periodo.
Ipotizzando di avere una situazione in tempo reale descritta nella tabella seguente:
Tabella 6‑1: Esempio di schedulabilità – Tabella delle tecniche.
Le tecniche del
limite di utilizzo descritte nel capitolo 4 sono eccessivamente caute per
l’intero insieme dei task o per la sequenza di eventi e3: entrambe le tecniche
portano a false disuguaglianze, perciò non si può fare nessuna asserzione sulla
schedulabilità.
Pertanto, la schedulabilità per la sequenza di eventi e3 deve essere verificata
utilizzando la tecnica descritta al capitolo 5.
Passo 1 – Calcolare un valore
approssimato di per il tempo di completamento del
primo job nel periodo di occupazione.
Passo 2 – Inizializzare il contatore k ad 1
k = 1
Passo 3 – Calcolare la prossima
approssimazione
Passo 4 – Determinare se
l’approssimazione è il tempo di completamento del job
Passo 3 – Calcolare la prossima
approssimazione
Passo 4 – Determinare se
l’approssimazione è il tempo di completamento del job
Passo 3 – Calcolare la prossima
approssimazione
Passo 4 – Determinare se
l’approssimazione è il tempo di completamento del job
Passo 5 – Determinare il tempo
della risposta del job
Mentre il passo 5 viene eseguito è uguale a quindi:
Passo 6 – Controllare se è terminato il periodo di occupazione
Passo 7 – Determinare il peggior caso del tempo della risposta
E’ presente solo un job nel periodo
di occupazione, perciò 
è il caso peggiore della risposta
della sequenza di eventi e3. Pertanto 
è minore della deadline: e3 è
schedulabile
Per controllare la schedulabilità delle sequenze di eventi e1 ed e2, si può applicare il semplice metodo descritto nel capitolo 4.1
Passo 1 – Calcolare l’utilizzo totale per tutti gli eventi
Passo 2 – Calcolare il termine di bloccaggio
Passo 3 – Calcolare il limite di utilizzo
Passo 4 – Confrontare il limite di utilizzo con il limite di utilizzo totale effettivo
L’insieme di tutti i task risulta schedulabile.
6.2 Analisi di schedulabilità: eventi a tempo periodico con deadline maggiore o uguale al periodo
Ipotizzando di avere una situazione come quella descritta nella seguente tabella (la tabella è la medesima del capitolo 3, ma con le sequenze di eventi ordinate in modo decrescente).
Tabella 6‑2: Esempio di schedulabilità – Tabella delle tecniche.
La tecnica descritta nel capitolo 5 può essere impiegata per controllare la schedulabilità della
sequenza di eventi e5 (vecchio e2).
D’altra parte, la tecnica descritta nel capitolo 5 può essere applicata all’insieme degli eventi vecchio e1, vecchio e3, vecchio e4 e vecchio e5.
Passo 1 – Calcolare un valore
approssimato di per il tempo di completamento del
primo job nel periodo di occupazione.
Passo 2 – Inizializzare il contatore k ad 1
k = 1
Passo 3 – Calcolare la prossima
approssimazione
Passo 4 – Determinare se
l’approssimazione è il tempo di completamento del job
Passo 3 – Calcolare la prossima
approssimazione
Passo 4 – Determinare se
l’approssimazione è il tempo di completamento del job
Passo 3 – Calcolare la prossima
approssimazione
Passo 4 – Determinare se
l’approssimazione è il tempo di completamento del job
Passo 3 – Calcolare la prossima
approssimazione
Passo 4 – Determinare se
l’approssimazione è il tempo di completamento del job
Passo 5 – Determinare il tempo
della risposta del job
Mentre il passo 5 viene eseguito è uguale a quindi:
Passo 6 – Controllare se è terminato il periodo di occupazione
Passo 3 – Calcolare la prossima
approssimazione
Passo 4 – Determinare se
l’approssimazione è il tempo di completamento del job
Passo 7 – determinare il caso peggiore del tempo della risposta
Poiché 
è l’unico
disponibile, il caso peggiore del tempo della risposta della sequenza di eventi
e5 è di 297 msec. Tuttavia, poiché è inferiore rispetto alla relativa deadline,
e5 (vecchio e2) incontra la sua deadline.
Riguardo ad e1, e2 (vecchio e3), e3 (vecchio e4), e4 (vecchio e5), il metodo descritto nel capitolo 5 conduce ai passi:
Passo 1 – Calcolare l’utilizzo totale per tutti gli eventi
Passo 2 – Calcolare il termine di bloccaggio
Passo 3 – Calcolare il limite di utilizzo
Passo 4 – Confrontare il limite di utilizzo con il limite di utilizzo totale effettivo
L’insieme dei task è schedulabile.
Se l’implementazione è fatta considerando un approccio guidato dagli interrupt, allora la situazione in tempo reale è quella descritta nella tabella riportata qui sotto; l’insieme dei task è schedulabile, ma i tempi delle risposte sono peggiori (ad esempio il caso peggiore del tempo della risposta di e2b è 303 msec)
Tabella 6‑3: Esempio di schedulabilità – Tabella delle tecniche.
In questo caso il peggioramento della performance è causato dalla tempo di interrupt ad alta priorità.
6 .3 Analisi di schedulabilità: eventi a tempo periodico con deadline inferiori o uguali al periodo e risposte con azioni eseguite con differenti priorità.
Ipotizzando di avere una situazione in tempo reale descritta nella tabella sottostante.
Tabella 6‑4: Esempio di schedulabilità – Tabella delle tecniche.
La sequenza degli eventi e2 è eseguita attraverso due azioni a diversa priorità. Perciò non possiamo utilizzare nessuna tecnica descritta nei capitoli precedenti (esistono alcune tecniche efficienti in
letteratura, ma sono complesse).
Tuttavia, da quando la deadline per entrambe le azioni a2.1 e a2.2 è la stessa ed è uguale al periodo, l’analisi di schedulabilità può essere formulata considerando a2.1 ed a2.2 come associate a due eventi indipendenti. Questo modello non prende in considerazione l’offset di a2.2 rispetto ad a2.1 e ciò è più prudente.
Applicando la tecnica descritta al capitolo 5, l’insieme dei task appare schedulabile. Iniziando da e3:
Passo 1 – Calcolare un valore
approssimato di per il tempo di completamento del
primo job nel periodo di occupazione.
Passo 2 – Inizializzare il contatore k ad 1
k = 1
Passo 3 – Calcolare la prossima
approssimazione
Passo 4 – Determinare se
l’approssimazione è il tempo di completamento del job
Passo 3 – Calcolare la prossima
approssimazione
Passo 4 – Determinare se
l’approssimazione è il tempo di completamento del job
Passo 3 – Calcolare la prossima
approssimazione
Passo 4 – Determinare se
l’approssimazione è il tempo di completamento del job
Passo 5 – Determinare il tempo
della risposta del job
Mentre il passo 5 viene eseguito è uguale a quindi:
Passo 6 – Controllare se è terminato il periodo di occupazione
Passo 7 – Determinare il caso peggiore del tempo della risposta
Il caso peggiore del tempo della risposta della sequenza di eventi e3 è 300 msec (minore della sua deadline).
Per i task rimanenti, si applica la tecnica descritta nel catitolo 5.1. L’insieme dei task risulta schedulabile.
Capitolo 7 :Realizzazione del tool software
Il tool software realizzato è stato scritto in C#, un linguaggio di programmazione semplice, moderno, flessibile ed orientato agli oggetti. Il C# (si pronuncia “C sharp”) deriva dal miglioramento dei linguaggi C, C++ e in piccola parte di Java e risulta subito familiare a chi possiede esperienza in C++. Inoltre unisce l’alta produttività del Visual Basic e la potenza del C++ ed è incluso, in aggiunta con altri linguaggi, in Visual Studio 7.0. Utilizzando questo linguaggio innovativo si ha accesso alla piattaforma NWGS (Next Generation Windows Services) che include un runtime engine comune ed un’estesa libreria di classi. L’ambiente .net definisce un Subset Language Common (CLS), una sorta di lingua franca, che assicura l’interoperabilità tra i linguaggi CLS-compilant e le librerie di classi. Ciò permette di utilizzare librerie scritte in altri linguaggi come Visual Basic e Visual C++.
Il software realizzato ha lo scopo primario di analizzare la schedulabiltà di un set di task per un sistema in tempo reale, che pertanto presenta vincoli di tipo temporale da soddisfare.
Le informazioni necessarie e sufficienti per tale analisi di schedulabilità sono contenute nella tabella delle tecniche. Nei capitoli precedenti ne sono riportati diversi esempi.
7.1 Tipico scenario di utilizzo del tool realizzato
Un tipico scenario di utilizzo del tool è mostrato in figura 7.1.
Figura 7‑1: Scenario tipico di utilizzo del tool.
Avendo a disposizione un set di tasks ed avendo definito il tipo (ciclico, sporadico ecc...) , il periodo, la priorità, il nome ed il numero identificativo di ciascuno di essi, si caricano nel target CPU e si mandano in esecuzione. Al termine dell’esecuzione, o del suo fallimento, si importano tutte le informazioni sulla schedulazione del set di tasks tramite il tool proprietario “Visual Scheduler”. Ciò avviene mettendosi in comunicazione con il target CPUtramite porta seriale (RS 232) e leggendo il buffer nel quale sono stati registrati gli eventi di schedulazione.
A causa della limitata dimensione del buffer circolare, sono generalmente disponibili unicamente gli ultimi 2000 eventi di schedulazione, che mediamente, considerando che un tic (ovvero il clock del target CPU utilizzato) corrisponde a 2 msec, forniscono informazioni sulla
schedulazione degli ultimi 4 secondi.
Dopo aver acquisito i dati di schedulazione è necessario salvarli in un file binario con estensione “vtd”. A questo punto è possibile importare il file vtd appena creato e procedere ad analizzare la schedulabilità del set di tasks, a seguito della quale si possono effettuare delle modifiche, ad esempio impostando diversamente i valori di priorità o del periodo (arrival pattern), individuare quali sono i tasks critici che potrebbero causare lo sforamento della relativa deadline o di quelle dei tasks aventi priorità inferiore. Dopo aver apportato tutte le modifiche necessarie, si aggiorna il codice binario e si carica sul target CPU.
Attraverso l’iterazione delle fasi appena descritte si può ottenere una buona ottimizzazione del sistema in tempo reale incrementandone prestazioni ed affidabilità.
Il target CPU è un modulo di calcolo rimovibile utilizzato in vari apparati come ALM, TMM, RIM, ERTMS con i quali si interfaccia attraverso un bus proprietario (Profibus), mentre è in grado di comunicare con l’esterno tramite porte seriali (RS 232 ed RS 485).
La scheda dual layer ospita due unità di calcolo identiche che sono mutuamente interfacciate attraverso dei disaccoppiatori ottici, inoltre vi sono 8 banchi di memoria ram e 2 eprom.
Figura 7‑2:Target CPU (visione frontale).
Il tool può
funzionare anche in modo stand-alone, ovvero senza doversi interfacciare con
altri applicativi software o dispositivi hardware. In questo caso è sufficiente
creare un nuovo progetto, compilare, tramite l’editor intergrato, la tabella
delle tecniche ed analizzare la schedulabiltà del sistema.
In entrambi i casi d’uso si può esportare il progetto corrente in un file
testuale in formato xml contenente tutte le informazioni sui tasks e sulle
analisi effettuate, generare un report testuale e grafico in formato html ,
ottimizzare la schedulabilità attraverso una procedura automatica di
permutazione delle priorità dei tasks e di altrettante analisi di
schedulabilità del sistema a cui viene associato un costo da minimizzare e
salvare tutti i settaggi dell’applicazione.
7.2 Funzionalità del tool
Di seguito sono elencate le funzionalità principali del software realizzato.
7.2.1 Importazione ed esportazione dei dati
Formato “vtd”
Il software realizzato è in grado di leggere ed interpretare i file binari, con estensione “vtd” generati dal tool proprietario “Visual Scheduler”, contenente le informazioni sui tasks e sulla schedulazione effettuata.
Per importare o esportare dati in formato “vtd” ciccare sui pulsanti “Import Vtd” ed “Export Vtd” presenti nella toolbar della finestra principale dell’applicazione.
Figura 7‑3: Importazione / Esportazione in formato “vtd”.
I files “vtd”, sono costituiti dai seguenti dati scritti in formato binario.
Informazioni sul formato del file e sul numero dei tasks
· Stringa sztag. Identifica il tipo di file: se il valore è diverso da “VTD” il file è considerato non valido.
· Long Lver. Identifica la versione del file attraverso un valore numerico. Attualmente esistono due versioni 3.x.x e 4.x.x.
· Long LtaskInfoItem. Indica il numero dei tasks presenti nella successiva parte del file
Struct[] TaskInfo. L’array di struct contiene le informazioni relative ai tasks. La dimensione dell’array di struct corrisponde al valore di LtaskInfoItem.
· String szName. Indica il nome del task.
· Int id. Rappresenta l’id numerico ed univoco del task.
· Int Period. Indica il periodo del task.
· Int Priorità. Indica la priorità del task.
· Int Type. Rappresenta il tipo di task: ciclico, sporadico o indefinito.
· Int Seq. Indica l’ordine di lettura (univoco).
· Single Utilization. Rappresenta l’utilizzo di CPU del task.
Struct SchedStatus. La struttura contiene le informazioni relative agli eventi di schedulazione acquisiti dal target CPU.
· Long Llenght. Indica il numero di dati validi acquisiti.
· Struct Aevents[]. Contiene gli eventi di schedulazione.
§ Long Time. Rappresenta il tempo espresso in msec in cui è avvenuto l’evento.
§ Byte Status . Rappresenta lo stato del task schedulato (running).
§ Byte Id. Rappresenta il numero identificativo del task relativo all’evento accaduto.
Poiché il tool proprietario è scritto in Visual Basic 6 ed il file “vtd” contiene struct mappate direttamente su disco, nasce un forte problema di interoperabilità tra i due tools a causa del differente linguaggio di programmazione utilizzato (Visual Basic 6 vs C#).
Per risolvere questo problema è stato scelto di realizzare una DLL scritta in VB6 in grado di leggere direttamente le struct presenti su file e contestualmente di generare un file di testo in cui vengono inseriti tutti i dati letti attraverso le struct.
In questo modo il passaggio dei dati avviene attraverso un file di testo, che non presenta particolari problemi o controindicazioni.
Le immagini seguenti mostrano in dettaglio la metodologia di interoperabilità tra i due tool.
Figura 7‑4: Interoperabilità diretta non supportata.
Figura 7‑5: Interoperabilità attraverso la dll scritta in VB6 e utilizzata dal codice C# come oggetto COM.
Per quanto riguarda l’esportazione dei dati in formato “vtd” sono valide le stesse metodologie e motivazioni dell’importazione.
Formato “xml”
Al fine di poter salvare ulteriori informazioni, oltre a quelle presenti nel formato “vtd”, è stato scelto di utilizzare il formato xml per la sua versatilità d’impiego e leggibilità da altri applicativi, nonché per l’ampia flessibilità che permette di aggiungere dati e campi senza compromettere la leggibilità dei dati. Ciò garantisce la possibilità di includere nuove funzionalità ed informazioni senza dover ricorrere a filtri di conversione per leggere le varie versioni dei files.
Ad esempio nel corso della realizzazione del tool, sono state introdotte alcune funzionalità di analisi ed ottimizzazione che comportavano l’aggiunta di nuovi dati da includere nel salvataggio e nel successivo caricamento. Grazie alla flessibilità dell’xml il tool è in grado di leggere, senza utilizzare filtri, anche files relativi alle prime versioni del tool che non comprendevano tali campi.
Per importare o esportare dati in formato “xml” (table) ciccare sui pulsanti “Import Table” ed “Export Table” presenti nella toolbar della finestra principale dell’applicazione.
Figura 7‑6: Importazione / Esportazione in formato “xml”.
Durante la lettura dei dati, avviene un controllo di correttezza degli stessi, sia a livello di formato xml che individua ed in taluni casi corregge automaticamente errori di sintassi (mancanza di chiusura dei tag etc..), sia a livello di tipo e valore dei dati (valori negativi dove non consentiti etc…). Per quanto riguarda la scrittura è possibile definire il livello di indentazione, senza, ovviamente, compromettere la successiva lettura.
La seguente figura mostra un esempio di file in formato xml.
<?xml version="1.0" standalone="no"?>
<Info>
<name>VTD</name>
<version>0</version>
<tasks>6</tasks>
</Info>
<TaskInfo>
<Task1>
<Id>1</Id>
<Name>Task 1</Name>
<Seq>1</Seq>
<Period>1000</Period>
<Priority>0</Priority>
<Type>1</Type>
<Utilization>20</Utilization>
<Deadline>100</Deadline>
<Blocking>0</Blocking>
</Task1>
………………….
Figura 7‑7: Esempio di file in formato xml.
Tramite una finestra di dialogo, visualizzata automaticamente durante il caricamento ed il salvataggio dei dati, viene mostrato lo stato di avanzamento della lettura o della scrittura del file attraverso una progressbar e due label testuali. Inoltre, in caso di errori durante la lettura, viene comunicato all’utente il tipo di errore (ad esempio “errore chiusura del tag taskinfo”) ed il codice numerico corrispondente, utile per il debug e la correzione manuale del file.
Figura 7‑8: Finestra di dialogo durante le operazioni di lettura/scrittura su file.
7.2.3 Creazione di un nuovo progetto
Per creare un nuovo progetto da zero, ovvero senza importare file in formato
“vtd” o “xml” è necessario ciccare sul pulsante “New table” ed immettere
successivamente i dati attraverso l’editor integrato.
Figura 7‑9: Creazione di un nuovo progetto.
Se non è stato caricato o creato precedentemente alcun progetto, è possibile crearne uno automaticamente ciccando sul pulsante di editazione dei dati.
7.2.4 Editazione dei dati
Per editare e/o visualizzare i dati relativi alle informazioni sui task è necessario ciccare sul pulsante “Edit Table” nella toolbar nella finestra principale dell’applicazione.
Figura 7‑10: Editazione dei dati.
Sarà mostrata la finestra presente nella seguente figura.
Figura 7‑11:Finestra di editazione dei dati.
Le caselle nelle diverse colonne della tabella sono caratterizzate da un colore di sfondo (anche se la differenza di colore è minima per non disturbare la visualizzazione). La prima colonna mostra, in sola lettura, il numero sequenziale ed univoco che caratterizza i tasks. Le colonne “Id”, “Arrival Patt.”, “Priority”, “Usage”, “Deadline” e “Blocking” corrispondono agli omonimi campi delle tabelle delle tecniche, le cui informazioni sono essenziali per la caratterizzazione dei tasks e per l’analisi della schedulabilità. Le rimanenti colonne “Type” e “Name” individuano rispettivamente il tipo del task (periodico, sporadico e indefinito) ed il nome (label).
L’immissione dei dati nei vari campi della tabella è soggetta alle seguenti regole:
|
Campo |
Sola lettura |
Tipo dato |
Min val |
Max Val |
Univoco |
|
Seq |
Si |
Intero |
0 |
Max of int |
Si |
|
Id |
No |
Intero |
0 |
Max of int |
Si |
|
Name |
No |
Stringa alfanumerica |
nessuno |
nessuno |
Si |
|
Arrival Patt. |
No |
Intero |
0 |
Max of int |
No |
|
Priority |
No |
Intero |
0 |
Max of int |
No |
|
Type |
No |
Combo Box (tendina) |
nessuno |
nessuno |
No |
|
Usage |
No |
Floating point |
0 |
Max of float |
No |
|
Deadline |
No |
Intero |
0 |
Max of int |
No |
|
Blocking |
No |
Intero |
0 |
Max of int |
No |
Tabella 7‑1: Regole
di immissione dei dati.
Chiudendo il form o ciccando sul pulsante “Check errors” vengono controllati tutti i campi della tabella al fine di verificare se rispettano le regole elencate in tabella. In caso contrario i campi che possiedono valori non conformi vengono evidenziati in rosso per facilitarne la correzione e ritornano al colore di sfondo normale qualora si editi nella casella di testo. Questo controllo scongiura errori di battitura che porterebbero a risultati non attesi o a potenziali errori in fase di analisi o ottimizzazione della schedulabilità.
La seguente figura mostra la procedura di individuazione degli errori nelle varie colonne.
Figura 7‑12: Individuazione degli errori.
Per inserire una nuova riga, che corrisponde ad un nuovo task, è sufficiente cliccare sul pulsante “New” oppure sull’asterisco rosso presente nella riga editata in basso, come mostrato nella figura seguente.
Figura 7‑13: Inserimento di un nuovo task.
Il tool propone in automatico ed in modo parametrizzabile un nome ed un numero identificativo univoco per i nuovi tasks. Nel caso in cui, ad esempio, il numero progressivo di default per il task n-esimo, sia già stato utilizzato per un altro task (a causa di cancellazioni di righe o di modifica) il tool propone un nuovo numero identificativo di valore più basso possibile in modo da poter riempire eventuali salti nella numerazione.
Per eliminare una riga cliccare sulla “x” rossa a destra. E’ necessario che esistano almeno 2 task: in caso contrario la cancellazione non sarà effettuata.
Per scorrere le
righe non visibili, utilizzare la barra di scorrimento verticale, oppure la
rotellina del mouse.
E’ possibile massimizzare e ridimensionare la finestra per una migliore
visualizzazione in ogni risoluzione (superiore a 640 x 480 pixel).
Ciccando sul nome delle colonne della tabella è possibile effettuare il sort delle stesse, orinandole in modo ascendente o discendente, in modo alternato (al primo click si ottiene un ordinamento ascendente ed al secondo uno discendente).
Figura 7‑14: Ordinamento delle colonne della tabella.
La possibilità di effettuare l’ordinamento delle varie colonne può rivelarsi particolarmente utile ad esempio per individuare immediatamente la presenza di tasks che utilizzano molta CPU, o che richiedono di essere schedulati con frequenza elevata.
Editazione del commento e di una descrizione breve
E’ possibile inserire un commento multi linea ed una breve descrizione del set di tasks caricati ,tramite un semplice editor testuale, come mostrato nella figura seguente.
Figura 7‑15: Inserimento di un commento ed una breve descrizione.
Le caselle di testo (in sola lettura) sulla destra del form forniscono un’utile
indicazione sui caratteri digitati.
7.2.5 Analizzatore / ottimizzatore di schedulabilità
A seguito del caricamento o dell’editazione dei dati, è possibile analizzare la schedulabilità del sistema in tempo reale grazie all’analizzatore presente nel tool.
L’analisi si basa sulla computazione dell’algoritmo descritto all’inizio del capitolo 5; la scelta di tale algoritmo deriva dalla sua flessibilità che consente di considerare task che possiedono periodo e deadline arbitrari.
Il seguente codice (semplificato) esegue l’analisi di schedulabilità implementando l’algoritmo scelto.
// H[][] è la matrice di float che contiene le approssimazioni.
// E[][] è la matrice di float che contiene il tempi della risposta.
// SATasks è l’oggetto contenente i dati relativi alle informazioni sui tasks.
// R[] è il vettore booleano che indica la schedulabilità dei tasks.
// Hmax[] è il vettore float che contiene il valore di worst case.
int n = 0; // # approssimazione
float sommatoria = 0; // variabile locale
// Cicla i task
for (int i = 0; i < SATasks.numtask ; i++)
{
// Passo 1 -> Calolare il tempo di completamento per il primo job
Step1:
n = 0;
// Calcola la sommatoria
sommatoria = 0;
for (int j = 0; j <= i; j++)
{
sommatoria = sommatoria + ((float) (SATasks.TaskInfo[j].utilization));
}
H[i][n] = SATasks.TaskInfo[i].blocking + sommatoria;
// Passo 2 -> inizializzare k
Step2:
k = 1;
// Passo 3 -> Calcolo a la prossima approssimazione
Step3:
n++;
sommatoria = 0;
int round = 0;
for (int j = 0; j <= (i-1); j++)
{
double rn = ((double)(((double) H[i][(n-1)]) / ((double)SATasks.TaskInfo[j].period)));
round = GlobalFunc.roundmax(rn);
sommatoria = sommatoria + round * ((float) (SATasks.TaskInfo[j].utilization));
}
H[i][n] = SATasks.TaskInfo[i].blocking + k * ((float)(SATasks.TaskInfo[i].utilization)) + sommatoria;
// Passo 4 -> Confronto
Step4:
int cfr = 0;
cfr = ((k-1)* SATasks.TaskInfo[i].period) + SATasks.TaskInfo[i].deadline; if (H[i][n] > cfr )
{
// Termina fallendo
R[i] = false;
Hmax[i] = -1;
goto Step8;
}
if (!(H[i][n] == H[i][n-1])) goto Step3;
// Passo 5 -> Calcolo il tempo della risposta
Step5:
E[i][k] = H[i][(n-1)] - (SATasks.TaskInfo[i].period * (k-1));
// Passo 6 -> Controllare se è terminato il busy period
Step6:
if (E[i][k] <= SATasks.TaskInfo[i].period) goto Step7;
k++;
H[i][n] = H[i][n] + ((float)(SATasks.TaskInfo[i].utilization));
goto Step3;
// Passo 7 -> Determinare il peggior caso della risposta
Step7:
float max = 0;
int kmax = 0;
bool schy = true;
for (int j = 1; j <= k ;j++)
{
if (E[i][j] > max)
{
max = E[i][j];
kmax = j;
}
}
if (max > SATasks.TaskInfo[i].deadline) schy = false;
Hmax[i] = max;
R[i] = schy;
}
Il risultato dell’analisi è contenuto nei vettori R[] Hmax[].
Il vettore R[] booleano indica se i tasks sono schedulabili, mentre il vettore di float Hmax[] contiene i valori relativi al worst case della risposta. Questi valori possono essere sfruttati per ottenere ulteriori indicazioni sulla schedulabilità, più precise, introducendo un margine relativo alla deadline ed al caso peggiore della risposta.
Dove WCRisp corrisponde ad ogni singolo valore di Hmax[].
Se il worst case della risposta corrisponde alla rispettiva deadline il numeratore della frazione è nullo e di conseguenza il margine è zero.
Se invece la
risposta tende a zero, oppure è molto minore della deadline, la frazione
tenderà ad 1.
Ne consegue che il margine può variare da 0 a 100 e rappresenta la percentuale di margine di schedulabilità: più questo valore è elevato, maggiore sarà
l’affidabilità del sistema in termini di probabilità.
Non è possibile analizzare tasks aventi un periodo nullo.
I tasks non corrispondenti a questi requisiti non vengono analizzati, ma nella realtà, potrebbero peggiorare i tempi della risposta e portare al fallimento il sistema in real-time, quindi è necessario comunque tenerne conto.
Per visualizzare l’analizzatore cliccare sul pulsante “Analyze” nella toolbar come mostrato in figura.
Figura 7‑16: Analisi di schedulabilità ed ottimizzazione.
Verrà visualizzata una nuova finestra come mostrato in figura.
Figura 7‑17: Finestra vuota dell’analizzatore.
Attraverso questa finestra è possibile effettuare le seguenti operazioni:
· Analisi di schedulabilità.
· Ripristino (pulizia) della finestra.
· Ottimizzazione della schedulabilità in base alla permutazione della priorità dei tasks.
· Ottimizzazione della schedulabilità secondo rate monotonic.
· Cattura della visualizzazione corrente in una immagine (gif, jpg).
· Selezione dei tasks da ottimizzare.
Analisi di schedulabilità
Per effettuare l’analisi è necessario premere il pulsante “Launch” come indicato in figura.
Figura 7‑18: Avvio dell’analisi di schedulabilità.
Comparirà una barra di avanzamento e successivamente verrà mostrato il risultato dell’analisi effettuata.
Figura 7‑19: Visualizzazione dell’analisi.
In primo piano viene mostrato un riepilogo complessivo del risultato dell’analisi.
Figura 7‑20: Riepilogo complessivo dell’analisi.
Nella label inferiore viene indicato se il set dei tasks risulta schedulabile, mentre nella parte superiore della finestra popup è presente una torta che mostra il margine di schedulabilità, qualora il set sia schedulabile.
Un’altra informazione importante è il minimo margine di schedulabilità, siccome anche un solo task che non viene schedulato entro la deadline comporta il fallimento dell’intero sistema.
Per conoscere con maggiore dettaglio quali sono i task schedulabili ed, in caso affermativo, il rispettivo margine, è sufficiente consultare la finestra di analisi.
Figura 7‑21: Finestra di analisi di schedulabilità.
Nella colonna sinistra della finestra sono mostrati i nomi dei tasks. Accanto ad ognuno sono presenti delle righe aventi differenti colori: rosso e verde.
Figura 7‑22: Dettaglio di analisi.
I tratti di colore verde, che terminano con una barretta verticale dello stesso colore, indicano il tempo stimato della risposta nel caso peggiore (worst case execution time),mentre analogamente i tratti di colore rosso indicano la deadline.
Al fine di ottimizzare la leggibilità delle informazioni mostrate e di attrarre l’attenzione dell’utente verso le potenziali criticità, sono applicati dei cerchi marroni (o degli ellissi) qualora il margine sia inferiore ad un valore stabilito (parametrizzabile attraverso il pannello dei settaggi) di default impostato a 25%.
Nella colonna a destra sono riportati i margini di schedulabilità in differenti colori a seconda del rispettivo valore: in colore nero se il margine è elevato, in rosso se il margine è basso, e in blu nel caso intermedio. Anche in questo caso le soglie di discriminazione sono parametrizzabili attraverso il pannello dei settaggi dell’applicazione.
Se un task non è schedulabile viene evidenziato in colore rosso per una immediata individuazione.
Figura 7‑23: Esempio di task non schedulabile.
In uno scenario in cui vi sia uno o più tasks non schedulabili, la finestra di popup di riepilogo complessivo di analisi sarà simile a quella mostrata nella seguente figura.
Figura 7‑24: Esempio di sistema non schedulabile.
Per pulire la finestra è sufficiente cliccare sul pulsante “Clear” nella toolbar della finestra.
Ottimizzazione della schedulabilità
Il tool comprende due tipi di ottimizzazione della schedulabilità: entrambi agiscono modificando il valore delle priorità dei tasks.
I due metodi modificano i valori di priorità effettuando tutte le permutazioni possibili oppure secondo il criterio di “rate monotonic”.
Ottimizzazione tramite permutazione
Come accennato in precedenza, questo metodo di ottimizzazione scambia i valori delle priorità dei tasks effettuando ogni volta una nuova analisi di schedulabilità.
Ad ogni analisi viene associato un valore numerico calcolato tramite una funzione di costo parametrizzabile.
La funzione di costo può essere parametrizzata come segue:
ü Rispetto al margine dei task schedulabili:
· Lineare : C += coeffcosto * margin
· Quadratica : C += coeffcosto * margin^2
· Cubica : C += coeffcosto * margin^3
· Parabolica: C += coeffcosto * margin^2 + margin
· Log 10 C+= coeffcosto * Log10(margin*1000 + 1)
· Log e C+= coeffcosto * Log(margin*1000+1)
· Radice quadrata C+= coeffcosto * Sqrt(margin*1000)
· Radice cubica C+= coeffcosto * Pow(margin*1000, 1/3)
·
Mixed C+= coeffcosto * margin^2 + margin * 10 +
Log(margin * 1000)*10
ü Per i task non schedulabili
· Lineare : C += coeffcostons * nonsched
· Quadratica : C += coeffcostons * nonsched^2
· Cubica : C += coeffcostons * nonsched^3
· Parabolica: C += coeffcostons * nonsched^2 + nonsched
ü Al termine dell’analisi : C += margweight * costominmargin
Dove “margin” è il margine di schedulabilità del task i-esimo, “coeffcosto”, “coeffcostons” e “margweight” sono coefficienti parametrizzabile, “nonsched” è il numero dei tasks non schedulabili e “costominmargin” è il costo associato al task avente il minor margine.
Al termine di tutte le analisi viene ritornato il valore delle priorità dell’analisi con il minor costo associato.
Per effettuare le permutazioni delle priorità si utilizza un metodo ricorsivo,
il cui codice è riportato in basso.
main
{
……
// chiama la funzione che effettua la permutazione delle priorità
Permutazione((int)SARTasks.numtask,0,(int)SARTasks.numtask);
……
}
// Funzione che effettua la permutazione di elementi
private void Permutazione(int max,int a,int z)
{
int scambio;
int k;
// Se il segmento di array contiene almeno due elementi, si
// procede.
if ( (z - a) >= 1 )
{
// Inizia un ciclo di scambi tra l'ultimo elemento e uno
// degli altri contenuti nel segmento di array
for ( k = z; k >= a; k-- )
{
// Scambia i valori.
scambio = Q[k];
Q[k] = Q[z];
Q[z] = scambio;
// Esegue una chiamata ricorsiva per permutare un
// segmento più piccolo dell'array.
Permutazione( max, a, z-1 );
// Scambia i valori.
scambio = Q[k];
Q[k] = Q[z];
Q[z] = scambio;
}
}
else
{
// chiama la funzione che effettua il calcolo di schedulabilità
Ottim(max);
y++;
}
}
Le permutazioni possibili per n cifre: n! (n fattoriale).
Ad esempio per un numero di 3 cifre, effettuando tutte le permutazioni possibili si ottiene:
numero = 123;
1) permutazione 1 = 123;
2) permutazione 2 = 132;
3) permutazione 3 = 213;
4) permutazione 4 = 231;
5) permutazione 5 = 321;
6) permutazione 6 = 312;
il numero di permutazioni ottenute è p = n! = 3! = 3*2*1 = 6.
Poiché il numero di permutazioni dipende dal fattoriale, ne consegue che al crescere di n (anche per valori relativamente bassi), cresceranno a dismisura.
Nel nostro caso, permutando n task si ottiene il seguente numero di permutazioni:
|
n |
permutazioni |
|
1 |
1 |
|
2 |
2 |
|
3 |
6 |
|
4 |
24 |
|
5 |
120 |
|
6 |
720 |
|
7 |
5040 |
|
8 |
40320 |
|
9 |
362880 |
|
10 |
362880 |
|
11 |
39916800 |
|
12 |
479001600 |
Tabella 7‑2: Tabella di crescita del
fattoriale di un numero.
Figura 7‑25: Grafico di crescita del fattoriale di un numero.
Ne consegue che per un numero elevato di tasks da ottimizzare, è necessario effettuare un numero eccessivo di analisi e l’operazione si prolunga per molto tempo.
Tipicamente fino a 8 tasks questo
tipo di ottimizzazione richiede pochi secondi, mentre si prolunga per oltre 5
minuti per 10 tasks da ottimizzare (i valori possono variare a seconda delle
caratteristiche del calcolatore utilizzato).
Poiché l’operazione di ottimizzazione può richiedere anche molto tempo si è
deciso di lanciare un nuovo thread, sia per migliorare le prestazioni (non solo
se si hanno 2 processori), ma anche per non bloccare l’interfaccia grafica
dell’applicazione.
Per avviare l’ottimizzazione premere il pulsante “Optimize P” nella toolbar della finestra come mostrato in figura.
Figura 7‑26: Ottimizzazione con metodo delle permutazioni.
E’ possibile sospendere temporaneamente l’operazione, mandarla in background, oppure abortirla.
Durante l’operazione viene mostrato il form seguente che fornisce anche indicazioni sullo stato di avanzamento dell’ottimizzazione.
Figura 7‑27: Finestra di dialogo durante il processo di l’ottimizzazione.
Al termine dell’operazione viene proposta la configurazione corrispondente alla permutazione di priorità avente il minimo costo.
In questo modo è possibile confrontare la nuova configurazione con quella di partenza e decidere se aggiornarla.
La figura seguente illustra il risultato dell’ ottimizzazione.
Figura 7‑28: Esempio di ottimizzazione.
Se si accetta la nuova configurazione, i valori delle priorità saranno automaticamente aggiornati in modo da poterli visualizzare nell’editor ed esportare.
Ottimizzazione tramite rate monotonic
Questo metodo di ottimizzazione si basa sulla regola di “rate monotonic” che imposta il valore delle priorità dei tasks in base al rispettivo periodo (arrival pattern) rendendo più prioritari i task che necessitano di essere schedulati frequentemente.
L’esempio seguente mostra come opera l’ottimizzazione “rate monotonic”.
|
Id |
Name |
Arrival Pattern |
Priority |
Usage |
Deadline |
Blocking |
|
1 |
Task 1 |
10 |
0 |
5,2 |
20 |
0 |
|
2 |
Task 2 |
15 |
2 |
10,1 |
30 |
0 |
|
3 |
Task 3 |
30 |
3 |
3 |
60 |
0 |
|
4 |
Task 4 |
60 |
7 |
20 |
120 |
0 |
|
5 |
Task 5 |
500 |
9 |
10,3 |
1000 |
0 |
|
6 |
Task 6 |
750 |
10 |
50,2 |
1500 |
0 |
Tabella 7‑3: Esempio
di priorità ordinate secondo la regola “rate monotonic”.
Per avviare la procedura di ottimizzazione secondo il criterio di “rate monotonic” cliccare sul pulsante “Optimize R” nella toolbar della finestra come mostrato in figura.
Figura 7‑29: Avvio dell’ottimizzazione secondo il criterio di “rate monotonic”.
La figura seguente illustra il risultato dell’ ottimizzazione.
Figura 7‑30: Esempio di ottimizzazione secondo il criterio di “rate monotonic”.
Se si accetta la nuova configurazione, i valori delle priorità saranno automaticamente aggiornati in modo da poterli visualizzare nell’editor ed esportare.
Selezione dei tasks da ottimizzare
In alcuni casi, può non essere conveniente per vincoli di varia natura, modificare la priorità di uno o più tasks. Ad esempio non è accettabile modificare la priorità di un task che deve necessariamente essere prioritario per garantire un servizio critico.
Inoltre, escludere in modo oculato, alcuni tasks dall’ottimizzazione permette di ridurre il tempo impiegato per compiere l’operazione, anche se i risultati potrebbero essere non ottimali.
Se si esclude, ad esempio, un task che possiede un valore di utilizzo di CPU particolarmente elevato ed una deadline relativamente breve, l’ottimizzazione della schedulazione potrebbe non fornire i risultati ottimali.
La riduzione dei tasks da ottimizzare è fortemente consigliata se il loro numero supera le 10 unità, in particolar modo se si effettua l’ottimizzazione che utilizza la permutazione delle priorità che è computazionalmente onerosa.
Per selezionare i tasks premere il pulsante “Select Tasks” sulla toolbar della finestra.
Figura 7‑31: Selezione dei tasks da ottimizzare.
Sarà visualizzata una finestra simile a quella in figura.
Figura 7‑32: Finestra di selezione dei tasks da ottimizzare.
Cattura dell’immagine corrente
Il tool realizzato consente di effettuare uno screenshot del contenuto della finestra corrente e di salvarla come immagine in formato “gif” o “jpg”. Poiché il numero di colori utilizzati dall’analizzatore è limitato, conviene utilizzare il formato “gif” infatti l’immagine non viene distorta se, come in questo caso, i colori utilizzati possono essere contenuti nella tavolozza (palette).
Per salvare in un’immagine il contenuto della finestra corrente premer il tasto “Capture” presente toolbar dell’analizzatore.
Figura 7‑33: Screenshot del contenuto della finestra dell’analizzatore di schedulabilità (toolbar).
Si ottiene un risultato simile a quello riportato in figura (è utilizzato il formato “gif”).
Figura 7‑34: Screenshot del contenuto della finestra dell’analizzatore di schedulabilità.
Questa immagine può essere utile, ad esempio, se inclusa in un documento
descrittivo del sistema in tempo reale per mostrarne l’analisi di
schedulabilità.
7.2.6 Visualizzatore degli eventi di schedulazione
A seguito dell’importazione di un file in formato “vtd” o in formato “xml”, se generati a partire da un file di tipo “vtd”, è possibile visualizzare come è avvenuta la schedulazione attraverso il visualizzatore degli eventi integrato nel tool.
Le informazioni, secondo quanto descritto all’inizio di questo capitolo, derivano dalla lettura del buffer di log degli eventi di schedulazione deltarget CPU. Per questo motivo, creando un nuovo progetto senza partire da un file “vtd” queste informazioni non sono disponibili.
Le seguenti righe mostrano come vengono salvate tali informazioni in formato “xml”.
<Schedstatus>
<Lsem>0</Lsem>
<Lindex>0</Lindex>
<Llenght>0</Llenght>
<Aevents>
<Time>0</Time>
<Status>0</Status>
<Taskid>0</Taskid>
<Time>0</Time>
<Status>0</Status>
<Taskid>0</Taskid>
<Time>0</Time>
<Status>0</Status>
<Taskid>0</Taskid>
<Time>0</Time>
<Status>0</Status>
<Taskid>0</Taskid>
………………………….
</Aevents>
<Schedstatus>
Figura 7‑35: Esempio di salvataggio delle informazioni degli eventi di schedulazione.
Per avviare il visualizzatore degli eventi premere il pulsante “View” nella toolbar nella finestra principale dell’applicazione come mostrato in figura.
Figura 7‑36: Avvio del visualizzatore degli eventi.
Verrà visualizzata una finestra simile a quella mostrata nella seguente figura.
Figura 7‑37: Finestra di visualizzazione degli eventi.
La possibilità di visualizzare come si è svolta la schedulazione aiuta in molti casi a individuarne le criticità effettive o potenziali ed a trovare soluzioni migliorative.
Il visualizzatore contiene un numero di tracce pari al numero totale dei tasks del sistema.
Ogni traccia può essere interpretata nel modo seguente:
Figura 7‑38: Interpretazione delle tracce del visualizzatore.
1) “Glitch”: il task non è riuscito ad essere schedulato poiché la CPU è stata richiesta da un altro task a priorità maggiore.
2) Il task è stato eseguito per un tic (unità di tempo minima).
3) Il task in stato “running” è stato interrotto al termine di un tic, ma ha continuato ad essere eseguito poiché possiede un valore di priorità maggiore di quella del task interrompente. E’ il caso duale rispetto al punto 1.
4)
Il task è eseguito in modo continuativo per pù di un tic.
Le tracce forniscono indicazioni precise su come è stato schedulato ogni task: interpretando correttamente questi dati è possibile ricavare alcune informazioni importanti.
Ad esempio è indicativo verificare la regolarità di un task periodico: se appare essere molto regolare, è probabile che non sia stato “interrotto” da un context switch avvenuto per schedulare un processo a priorità più alta, perciò è più probabile che il task sia schedulato rispettando la deadline. Solitamente sono visibilmente più irregolari i tasks con una periodo relativamente lungo ed un utilizzo di CPU limitato. Al contrario un task periodico la cui esecuzione sia particolarmente irregolare indica che altri task a priorità maggiore hanno causato un interruzione temporanea della sua esecuzione. Sono visibilmente irregolari tasks con un periodo relativamente breve e che richiedono un elevato utilizzo di CPU. In questo caso può essere maggiormente probabile lo sforamento della deadline, anche se ciò dipende anche dal comportamento e dalle caratteristiche dei tasks a priorità maggiore, nonché dal margine rispetto alla decadine (come verrà spiegato successivamente).
L’immagine seguente mostra un esempio di tasks schedulati in modo particolarmente regolare.
Figura 7‑39: Esempio di task visibilmente regolare.
L’immagine seguente mostra un esempio di tasks schedulati in modo non visibilmente regolare.
Figura 7‑40: Esempio di task visibilmente non regolare.
Il visualizzatore degli eventi comprende alcune funzionalità che possono essere di aiuto all’utente per una migliore fruizione del tool:
· Zoom delle tracce.
· Righello per l’individuazione del tempo in cui sono avvenuti gli eventi (ruler).
· Barra di scorrimento verticale ed orizzontale con supporto della rotellina del mouse.
· Ingrandimento e ridimensionamento della finestra.
· Visualizzazione della deadline.
· Visualizzazione dei tic.
· Screenshot del contenuto della finestra corrente.
· Barra verticale di indicazione.
· Barra di stato.
· Ordinamento delle tracce.
Zoom delle tracce
Per ingrandire o ridurre l’ingrandimento premere i pulsanti “Zoom +” e “Zoom -” nella toolbar della finestra.
Lo zoom varia da un minimo di 1 ad un massimo di 80 ingrandimenti. L’incremento ed il decremento dell’ingrandimento, che avviene ad ogni pressione dei tasti di impostazione dello zoom, può essere impostato a piacere attraverso il pannello dei settaggi, così come lo zoom iniziale.
Le seguenti figure mostrano la visualizzazione degli eventi utilizzando uno zoom minimo e massimo.
Figura 7‑41: Visualizzazione con ingrandimento minimo.
Figura 7‑42: Visualizzazione con ingrandimento massimo.
Righello per l’individuazione del tempo in cui sono avvenuti gli eventi (ruler).
E’ stato inserito un indicatore graduato, simile ad un righello, nella finestra del visualizzatore degli eventi al fine di individuare il tempo in cui questi sono avvenuti.
Il formato del righello viene automaticamente modificato a seconda dello zoom impostato.
Le immagini seguenti mostrano la modifica del formato del righello in base all’ingrandimento (per gli zoom intermedi le tacche diventano più spaziate).
Figura 7‑43: Formati possibile del righello.
|
Zoom immagine |
Intervallo di zoom |
|
Zoom 2 |
1 - 2 |
|
Zoom 3 |
3 - 5 |
|
Zoom 4 |
6 - 14 |
|
Zoom 5 |
15 -29 |
|
Zoom 6 |
30 - 64 |
|
Zoom 7 |
65 - 80 |
Tabella 7‑4: Corrispondenza
dello zoom.
Barra di scorrimento verticale ed orizzontale con supporto della rotellina del mouse.
Muovendo la barra di scorrimento verticale è possibile visualizzare nella finestra tutti i tasks presenti nel progetto. In alternativa si può utilizzare la rotellina de mouse, se presente.
Muovendo la barra di scorrimento orizzontale si sposta l’intervallo temporale di visualizzazione.
Ingrandimento e ridimensionamento della finestra.
E’ consentito ingrandire la finestra ridimensionandola in modo da aumentare o ridurre l’intervallo temporale di visualizzazione ed ottimizzare la visuale della finestra in base alla risoluzione corrente dello schermo. Inoltre è possibile massimizzare la finestra tramite doppio click sul bordo superiore.
Visualizzazione della deadline.
Una informazione estremamente utile per verificare l’affidabilità del sistema è la visualizzazione della deadline nel visualizzatore degli eventi di schedulazione.
L’informazione
della deadline non è presente tra i dati relativi agli eventi di schedulazione.
Nonostante nel target CPU venga verificato il rispetto della deadline per ogni
task, tale informazione non è riportata nel buffer circolare che viene letto
dal tool proprietario “Visual Scheduler” e pertanto non è presente all’interno
dei file “vtd”.
Tuttavia si è deciso di integrare ugualmente l’informazione inserendo una griglia a pettine che può essere spostata dall’utente. La visualizzazione della deadline, insieme agli eventi di schedulazione, aiuta a valutare quanto tempo intercorre tra il completamento del job relativo ad un task e la sua deadline. Se l’ultima esecuzione del task, che porta al completamento dello stesso, è molto vicina alla deadline, l’affidabilità del sistema potrebbe non essere elevata poiché in situazioni sfavorevoli, il task può non essere portato a termine entro la deadline, causando il fallimento del sistema in tempo reale.
Per attivare la visualizzazione della deadline premere il tasto “Grid deadline” come mostrato nella seguente figura.
Figura 7‑44: Attivazione della visualizzazione della deadline.
La prima
occorrenza della deadline avviene in corrispondenza della prima esecuzione di
ciascun task.
La figura seguente illustra un esempio di visualizzazione della deadline.
Figura 7‑45: Visualizzazione della deadline.
Nella seguente immagine si può notare in dettaglio che il task è completato con un buon margine rispetto alla deadline, nonostante richieda un discreto utilizzo di CPU e la sua esecuzione venga interrottà più volte.
Figura 7‑46: Dettaglio di visualizzazione della deadline.
Lo spostamento (shift) laterale della griglia della deadline può essere effettuato ciccando il tasto destro del mouse sulla traccia, oppure in alternativa attraverso la barra di scorrimento orizzontale attivabile dal pannello dei settaggi.
Figura 7‑47: Attivazione della barra di scorrimento orizzontale per la griglia della deadline.
Visualizzazione dei tic.
La visualizzazione dei tic all’interno della finestra del visualizzatore degli eventi di schedulazione può essere di aiuto per valutare il periodo di esecuzione di un task senza dover consultare la scala graduata presente nel righello.
Per attivare la visualizzazione della deadline premere il tasto “Grid tic” come mostrato nella seguente figura.
Figura 7‑48: Attivazione della griglia dei tic.
Si ottiene una visualizzazione simile a quella mostrata nella seguente figura.
Figura 7‑49: Visualizzazione dei tic nella finestra degli eventi di schedulazione.
Screenshot del contenuto della finestra corrente.
Al fine di poter esportare la visualizzazione corrente in modo da inserirla, ad esempio, all’interno di un documento, ne è stato previsto il salvataggio in un formato immagine “gif” o “jpg”. Valgono le stesse considerazioni sul tipo di formato enunciate nel paragrafo di cattura dell’immagine relativa all’analizzatore di schedulabilità.
Barra verticale di indicazione.
E’ stata inserita una barra verticale, di colore verde, che è possibile spostare sulle tracce cliccando sopra di esse con il tasto sinistro del mouse.
Figura 7‑50: Barra verticale di indicazione.
Nella barra di stato viene visualizzato l’istante di tempo in cui si trova la barra verticale.
Barra di stato.
La barra di stato fornisce indicazioni sulla posizione iniziale delle tracce visualizzate, sull’ingrandimento, sulla posizione corrente della splitbar e mostra il tipo di ordinamento delle tracce.
Figura 7‑51: Barra di stato.
Ordinamento delle tracce.
E’ possibile ordinare le tracce secondo il valore di priorità, periodo, utilizzo, nome ed identificativo dei tasks corrispondenti in modo ascendente o discendente.
E’ particolarmente utile ordinare le tracce rispetto al valore di priorità (in modo discendente, dal più prioritario al meno prioritario) poiché è immediatamente evidente che i tasks meno prioritari sono eseguiti solo dopo che i tasks con priorità maggiore sono completati.
Per ordinare le tracce selezionare la voce desiderata dalla tendina del pulsante “Sort” nella toolbar della finestra e premerlo. Ad ogni pressione viene invertito l’ordine delle tracce ottenendo un ordinamento ascendente o discendente.
Figura 7‑52: Ordinamento delle tracce.
7.2.7 Generazione del report HTML.
In molti casi è utile poter esportare un riepilogo contenente le informazioni sui task, sulle analisi effettuate sul set e sulle azioni intraprese.
E’ stato scelto di utilizzare il formato HTML poiché si presta particolarmente bene ad essere diffuso e letto facilmente attraverso i comuni browser, in quanto standard.
La prima parte del report è costituita dalla tabella delle tecniche, la seconda dall’immagine dell’analisi complessiva di schedulabilità (se effettuata) e la terza parte da informazioni generali sul set dei tasks comprendente i parametri utilizzati per l’ottimizzazione..
Per visualizzare la finestra di generazione del report HTML premere il pulsante “Report” nella toolbar del form principale come mostrato in figura.
Figura 7‑53: Avvio del generatore di report.
Dalla finestra visualizzata premere sul tasto “Generate” nella toolbar, come mostrato in figura.
Figura 7‑54: Generazione del report HTML (toolbar).
Dopo alcuni secondi il report sarà visualizzabile all’interno della finestra che contiene un OLE del browser Internet Explorer.
Un esempio di report è riportato di seguito.
Tecnique table
|
Id |
Name |
Arrival Pattern |
Priority |
Type |
Usage |
Deadline |
Blocking |
|
1 |
CHKTRD |
20 |
0 |
Periodic |
0 |
40 |
0 |
|
2 |
EVHNDL |
16 |
3 |
Periodic |
2,53 |
32 |
0 |
|
3 |
MEMTST |
556 |
201 |
Periodic |
7,56 |
1112 |
0 |
|
4 |
CPUTST |
5002 |
60 |
Periodic |
0 |
10004 |
0 |
|
5 |
TIMMNG |
1000 |
230 |
Periodic |
0,9 |
2000 |
0 |
|
6 |
WDOUUTI |
26 |
50 |
Periodic |
1,2 |
52 |
0 |
|
7 |
SERIO |
334 |
203 |
Periodic |
4,84 |
668 |
0 |
|
8 |
ALRSENS |
146 |
160 |
Periodic |
1,05 |
292 |
0 |
|
9 |
IDVMULX |
54 |
100 |
Periodic |
2,39 |
108 |
0 |
|
10 |
ODOMET |
100 |
150 |
Periodic |
16,31 |
200 |
0 |
|
11 |
MVBV |
242 |
190 |
Periodic |
6,8 |
484 |
0 |
|
12 |
NVRAM |
252 |
180 |
Periodic |
2,05 |
504 |
0 |
|
14 |
CTODLTX |
50 |
70 |
Periodic |
2,31 |
100 |
0 |
|
16 |
APPLENV |
104 |
1 |
Periodic |
0 |
208 |
0 |
|
17 |
APPLSW |
104 |
170 |
Periodic |
12,91 |
208 |
0 |
|
13 |
CTODLRX |
0 |
2 |
Sporadic |
0 |
0 |
0 |
|
15 |
SPECENV |
0 |
252 |
Sporadic |
0 |
0 |
0 |
|
18 |
Tsk 18 |
0 |
0 |
Undef |
34,45 |
0 |
0 |
Analysis report
The set is schedulable
Informations
|
General information |
|
|
Short description |
|
|
Comment |
|
|
File Type |
Table loaded |
|
Version |
4 |
|
Total tasks |
18 |
|
File Load |
C:\Documents and Settings\lorenzo\Desktop\tmmottimizzata.xml |
|
File Save |
Not saved |
|
Modified |
Yes |
|
Optimization |
|
|
Optimized |
Yes |
|
Optimization type |
Permutation method |
|
Considered tasks |
10 / 18 |
|
Non schedulable tasks |
0 / 10 |
|
Total percentual of time used |
8 % |
|
Minimum margin |
78 % |
|
Used cost type function |
Linear |
|
Used cost coefficient |
1 |
|
Used cost coefficient for minimum margin |
5 |
|
Used cost type function for non schedulable tasks |
Linear |
|
Used cost coefficient for non schedulable tasks |
100000 |
Salvataggio del report
Per salvare il report visualizzato premere il pulsante “Save” nella toolbar della finestra come mostrato in figura.
Figura 7‑55: Salvataggio del report HTML.
Poiché il nome del file contenente l’immagine è univoco è possibile salvare diversi report in una stessa cartella.
Ovviamente, grazie alla universalità del formato HTML, è possibile pubblicare su web i report salvati o se necessario importarli in un documento Word (come in questo caso) oppure stamparli su carta utilizzando il comune browser.
Caricamento del report
Per caricare un report HTML premere il pulsante “Load” nella toolbar della finestra come mostrato in figura.
Figura 7‑56: Caricamento del report HTML.
I files di report sono esclusivamente “informativi” e non sono utilizzabili per importare dati nel progetto, al contrario dei file “vtd” o “xml”.
7.2.6 Pannello dei settaggi dell’applicazione
Alcuni parametri dell’applicazione sono parametrizzati: attraverso il pannello dei settaggi è possibile modificarne i valori.
Ogni finestra
dell’applicazione include nella toolbar un pulsante 
tramite il quale si accede al pannello
delle impostazioni che è costituito dai seguenti pannelli:
1) General
2) Editor
3) Analyzer
4) Optimyzer
5) Viewer
6) Import/Export
7) Load/Save
General
Figura 7‑57: Pannello dei settaggi: General
|
Nome |
Significato |
|
Version |
Versione del tool |
|
New Project default name |
Nome di default per un nuovo progetto |
|
Empty Project default name |
Nome di default per un progetto vuoto (iniziale) |
|
Max tasks |
Numero massimo dei tasks accettabili |
|
Splash Screen Active |
Millisecondi per cui viene mostrato lo splashscreen |
Tabella 7‑5: Significato delle impostazioni nel pannello General.
Editor
Figura 7‑58: Pannello dei settaggi: Edit.
|
Nome |
Significato |
|
New Task Name |
Nome proposto per un nuovo task |
Tabella 7‑6: Significato delle impostazioni nel pannello Edit.
Analyzer
Figura 7‑59: Pannello dei settaggi: Analyzer.
|
Nome |
Significato |
|
Bar height |
Altezza della barra di terminazione delle tracce |
|
Warning under % margin |
Soglia di segnalazione inferiore |
|
Green % margin |
Margine sopra il quale il tag % è di colore verde |
|
Red & margin |
Margine sotto il quale il tag % è di colore rosso |
|
Relative to others / absolute |
Imposta il fondoscala delle tracce |
Tabella 7‑7: Significato delle impostazioni nel pannello Analyzer.
Optimyzer
Figura 7‑60: Pannello dei settaggi: Optimyzer.
|
Nome |
Significato |
|
Cost function type |
Tipo di funzione costo (basata sul margine) |
|
Cost nonsched type |
Tipo di funzione costo per i tasks non schedulabili |
|
Cost coefficient |
Coefficiente per la funzione costo |
|
Cost coefficient nonsched |
Coefficiente di costo per i tasks non schedulabili |
|
Cost coefficient min margin |
Coefficiente di costo per il minimo margine |
Tabella 7‑8: Significato delle impostazioni nel pannello Optimyzer.
Viewer
Figura 7‑61: Pannello dei settaggi: Viewer.
|
Nome |
Significato |
|
Zoom step |
Incremento / decremento dello zoom |
|
Initial zoom |
Zoom iniziale all’avvio del form |
|
Horiz. Scroll grid deadline |
Attivazione della scrollbar orizzontale per la deadline |
|
Horiz scroll precision (main) |
Accuratezza della scrollbar orizzontale principale |
Tabella 7‑9: Significato delle impostazioni nel pannello Viewer.
Import/Export
Figura 7‑62: Pannello dei settaggi: Import/Export.
|
Nome |
Significato |
|
Warnings |
Attivazione / Disattivazione degli avvisi |
|
Xml spaces indent |
Indentazione nel file xml |
|
mSec Wait (normal) |
Millisecondi di attesa normale |
|
mSec Wait (small) |
Millisecondi di attesa breve |
|
mSec Wait (err) |
Millisecondi di attesa lunga |
|
Divider refresh screen |
Livello di aggiornamento dello schermo |
Tabella 7‑10: Significato delle impostazioni nel pannello Import/Export.
Load/Save
Figura 7‑63: Pannello dei settaggi: Load/Save.
E’ possibile salvare le impostazioni dell’applicazione su un file in formato xml e caricarle successivamente. Inoltre il caricamento delle impostazioni può essere effettuato in modo automatico all’avvio dell’applicazione.
Il formato utilizzato è “xml” anche in questo caso.
Una parte del file che contiene le impostazioni è mostrato nelle righe seguenti:
<?xml version="1.0" standalone="no"?>
<Settings>
<General>
<FileAutoload></FileAutoload>
<Autoload>False</Autoload>
<Projectvoid>Empty</Projectvoid>
<Projectnew>New_Project1</Projectnew>
<Version>Beta</Version>
<MaxTasks>2000</MaxTasks>
<MaxUtilization>100000</MaxUtilization>
<SplashTime>3500</SplashTime>
<Tic>2</Tic>
</General>
………………
</Settings>
Per poter leggere il file delle impostazioni automaticamente è stato scelto di utilizzare i registry di Windows ®.
Vengono inserite due nuove chiave nei registry di Windows ® il cui valore indica la directory ed il nome del file da leggere e se deve essere caricato in modo automatico.
Figura 7‑64: Chiave di registro inserita.
All’avvio dell’applicativo vengono cercate le chiavi di registro: nel caso in cui esistano e sia stato scelto di effettuare il caricamento automatico delle impostazioni, il file indicato dalla chiave “File” viene letto in background e vengono aggiornati i valori dei settaggi presenti.
7.2.7 Altre features presenti nel tool realizzato
Splashscreen
E’ stato inserito uno splashscreen, ovvero un’immagine visualizzata automaticamente all’avvio dell’applicazione. La visualizzazione dello splashscreen è utile per “intrattenere” l’utente durante la lettura del file contenente le impostazioni, qualora previsto.
Lo splashscreen realizzato è mostrato nella seguente figura.
Figura 7‑65: Splashscreen.
Anche in questo caso è stato utilizzato un nuovo thread per gestire le operazioni in background.
Riepilogo informativo
Nella finestra principale dell’applicazione è presente un set di informazioni utili per poter visualizzare le caratteristiche principali del progetto corrente.
Il riepilogo è differenziato in 4 parti:
1) General: contiene informazioni generiche come ad esempio il file di origine del progetto, se necessita di essere salvato o se è stato modificato.
2) Actions: contiene informazioni sulle azioni intraprese come l’editazione, l’analisi o l’ottimizzazione.
3) Optimization / Analysis: fornisce indicazioni sulla schedulabilità del sistema o sull’ottimizzazione effettuata (se questi dati sono disponibili).
4) Tasks set: contiene informazioni sul numero di task presenti nel sistema, sull’utilizzo medio etc….
Inoltre è mostrata la descrizione breve associata al progetto.
Queste indicazioni sono presenti immediatamente dopo la creazione di un nuovo progetto o a seguito dell’importazione di un file “vtd” o “xml”.
Risulta di particolare importanza la presenza dell’indicazione del campo che segnala se il set dei tasks è stato modificato a seguito della creazione poiché in caso affermativo le informazioni sulla schedulazione da parte del target CPU non sono più valide.
L’immagine seguente mostra un esempio di riepilogo informativo associato ad un progetto caricato.
Figura 7‑66:Esempio di riepilogo informativo per un progetto.
Riduzione ad icona in “tray icon”
Se la finestra principale viene minimizzata, attraverso l’apposito “control box” o tramite doppio click sulla barra degli strumenti, l’applicazione viene mandata in “tray icon”.
La finestra viene ripristinata attraverso un click del mouse sull’icona.
Figura 7‑67: Tray icon.
Creazione di un pacchetto di installazione
Per facilitare
la dissuasione e la fruibilità del tool realizzato è stato creato un pacchetto
di installazione MSI che esegue il setup del programma e registra tutte le dll
necessarie.
E’ necessario però che il framework “Dotnet” ridistribuibile sia presente (è
scaricabile gratuitamente dal sito www.microsoft.com
ed è incluso negli aggiornamenti di windows Xp e sarà presente nel nuovo
sistema operativo Microsoft Longhorn).
Inserimento dei tooltip
Al fine di migliorare la comprensione dei vari elementi visualizzati nelle finestre dell’applicazione, sono state inserite delle etichette (tooltip), attivate automaticamente dopo qualche secondo che il puntatore del mouse rimane fermo sull’ elemento, che contengono informazioni utili all’utente.
La seguente figura mostra la visualizzazione di un tooltip.
Figura 7‑68: Visualizzazione Tooltip.
Capitolo 8 :Risultati
Le prove consistono prevalentemente nell’analisi di schedulabilità e nell’ottimizzazione di set di tasks creati attraverso l’editazione o tramite l’importazione di dati dal target CPU (in formato “vtd”).
Test 1: Verifica del corretto funzionamento
Il primo test effettuato rappresenta una verifica di funzionamento del tool avendo ricreato il sistema dell’esempio relativo all’algoritmo di analisi di schedulabilità implementato (vedi capitolo 5: a pagina 58).
Si seguito si riporta la tabella delle tecniche relativa al test effettuato.
Tabella 8‑1: Tabella delle tecniche (test 1).
Il report dell’analisi di schedulabilità per l’intero set è la seguente.
Figura 8‑1: Analisi di schedulabiltà (test 1).
Nell’esempio il worst case del “response time” per il task e2 risultava essere 160msec, pari al valore della deadline (caso limite).
Anche nell’analisi effettuata dal tool è chiaramente riscontrabile che il tempo della risposta del task e2 corrisponde alla sua deadline. Si noti anche che il margine è nullo.
L’analisi effettuata risulta corretta.
Test 2: (prova1.xml)
E’ stato creato un sistema caratterizzato come segue:
|
Id |
Name |
Arrival Pattern |
Priority |
Type |
Usage |
Deadline |
Blocking |
|
1 |
Task 1 |
100 |
0 |
Periodic |
20 |
100 |
0 |
|
2 |
Task 2 |
150 |
1 |
Periodic |
40 |
160 |
20 |
|
3 |
Task 3 |
350 |
2 |
Periodic |
40 |
350 |
0 |
|
4 |
Task 4 |
400 |
3 |
Periodic |
5 |
200 |
0 |
|
5 |
Task 5 |
500 |
4 |
Periodic |
3 |
200 |
2 |
|
6 |
Task 6 |
600 |
5 |
Periodic |
10 |
140 |
0 |
Il sistema risulta schedulabile . Il margine medio è del 45%
e quello minimo dell’1%
Figura 8‑2: Analisi di schedulabiltà (test 2).
Sono state effettuate diverse
ottimizzazioni utilizzando funzioni di costo e parametri differenti.
I risultati ottenuti sono riportati in tabella.
|
Numero analisi |
Tipo |
Funzione costo |
Coeff |
Funzione costo n.s. |
Coeff n.s. |
Coeff min |
Sche |
Margine |
Margine minimo |
|
Non ottim. |
/ |
/ |
/ |
/ |
/ |
/ |
Si |
45 |
1 |
|
1 |
P |
Lineare |
1 |
Lineare |
100000 |
5 |
Si |
69 |
44 |
|
2 |
P |
Quadratica |
1 |
Lineare |
100000 |
5 |
Si |
60 |
50 |
|
3 |
P |
Parabolica |
1 |
Lineare |
100000 |
5 |
Si |
60 |
50 |
|
4 |
P |
Cubica |
1 |
Lineare |
100000 |
5 |
No |
57 |
0 |
|
5 |
P |
Log base 10 |
1 |
Lineare |
100000 |
5 |
Si |
73 |
38 |
|
6 |
P |
Log base e |
1 |
Lineare |
100000 |
5 |
Si |
73 |
38 |
|
7 |
P |
Radice quadrata |
1 |
Lineare |
100000 |
5 |
Si |
73 |
38 |
|
8 |
P |
Radice cubica |
1 |
Lineare |
100000 |
5 |
Si |
73 |
38 |
|
9 |
P |
Mista |
1 |
Lineare |
100000 |
5 |
Si |
65 |
47 |
|
10 |
P |
Lineare |
1 |
Lineare |
100000 |
1 |
Si |
73 |
38 |
|
11 |
P |
Lineare |
1 |
Lineare |
100000 |
13 |
Si |
65 |
47 |
|
12 |
P |
Lineare |
2 |
Lineare |
1 |
0 |
No |
67 |
0 |
|
13 |
R |
/ |
/ |
/ |
/ |
/ |
Si |
45 |
1 |
Tabella 8‑2: Risultati dell’ottimizzazione.
I risultati
evidenziano che è possibile ottenere un significativo miglioramento
dell’affidabilità del sistema attraverso l’ottimizzazione (in presenza di
talune impostazioni).
Sono da prediligere le soluzioni 2 e 3 poiché presentano un discreto margine e
possiedono il margine minimo più elevato. Infatti anche un solo task che non
venga completato entro la sua deadline porta al fallimento l’intero sistema.
Test 3: (ALM N mA.vtd)
Il test prende in considerazione un caso reale costituito un insieme di tasks schedulati nell’apparato ALM.
Il sistema è caratterizzato come segue:
|
Id |
Name |
Arrival Pattern |
Priority |
Type |
Usage |
Deadline |
Blocking |
|
1 |
CHKTRD |
20 |
0 |
Periodic |
0 |
40 |
0 |
|
2 |
EVHNDL |
10 |
1 |
Periodic |
2,38 |
20 |
0 |
|
3 |
MEMTST |
560 |
201 |
Periodic |
6,86 |
1120 |
0 |
|
4 |
CPUTST |
5000 |
230 |
Periodic |
0 |
10000 |
0 |
|
5 |
TIMMNG |
1000 |
2 |
Periodic |
0,68 |
2000 |
0 |
|
6 |
CICLACT |
50 |
60 |
Periodic |
6,87 |
100 |
0 |
|
7 |
NVRAM |
300 |
200 |
Periodic |
2,65 |
600 |
0 |
|
8 |
DBGTOOL |
250 |
95 |
Periodic |
4,93 |
500 |
0 |
|
9 |
WATCHDG |
24 |
53 |
Periodic |
0,65 |
48 |
0 |
|
11 |
APPLSW |
250 |
100 |
Periodic |
37,1 |
500 |
0 |
|
10 |
RX_CTO |
0 |
51 |
Sporadic |
2,92 |
0 |
0 |
|
12 |
SPECENV |
0 |
252 |
Sporadic |
0 |
0 |
0 |
|
13 |
Tsk 13 |
0 |
0 |
Undef |
37,71 |
0 |
0 |
Il sistema risulta schedulabile . Il margine medio è del 92% e quello minimo dell’84%.
Figura 8‑3 Analisi di schedulabiltà (test 3).
Sono state effettuate diverse
ottimizzazioni utilizzando funzioni di costo e parametri differenti.
I risultati ottenuti sono riportati in tabella.
|
Numero analisi |
Tipo |
Funzione costo |
Coeff |
Funzione costo n.s. |
Coeff n.s. |
Coeff min |
Sche |
Margine |
Margine minimo |
|
Non ottim. |
/ |
/ |
/ |
/ |
/ |
/ |
Si |
92 |
84 |
|
1 |
P |
Lineare |
1 |
Lineare |
100000 |
5 |
Si |
94 |
83 |
|
2 |
P |
Quadratica |
1 |
Lineare |
100000 |
5 |
Si |
92 |
84 |
|
3 |
P |
Parabolica |
1 |
Lineare |
100000 |
5 |
Si |
92 |
84 |
|
4 |
P |
Cubica |
1 |
Lineare |
100000 |
5 |
Si |
92 |
84 |
|
5 |
P |
Log base 10 |
1 |
Lineare |
100000 |
5 |
Si |
93 |
81 |
|
6 |
P |
Log base e |
1 |
Lineare |
100000 |
5 |
Si |
93 |
81 |
|
7 |
P |
Radice quadrata |
1 |
Lineare |
100000 |
5 |
Si |
93 |
83 |
|
8 |
P |
Radice cubica |
1 |
Lineare |
100000 |
5 |
Si |
94 |
81 |
|
9 |
P |
Mista |
1 |
Lineare |
100000 |
5 |
Si |
94 |
83 |
|
10 |
P |
Lineare |
1 |
Lineare |
100000 |
1 |
Si |
94 |
81 |
|
11 |
P |
Lineare |
1 |
Lineare |
100000 |
20 |
Si |
93 |
84 |
|
13 |
R |
/ |
/ |
/ |
/ |
/ |
Si |
91 |
84 |
Poiché il sistema di partenza è già
stato ottimizzato, non vi è un significativo miglioramento della sua
affidabilità.
Tuttavia la soluzione 11 risulta migliorativa rispetto al caso di partenza.
Tutte le soluzioni sono caratterizzate da risultati simili tra loro.
Test 4: (non schedulabile)
E’ stato creato un sistema caratterizzato come segue:
|
Id |
Name |
Arrival Pattern |
Priority |
Type |
Usage |
Deadline |
Blocking |
|
1 |
Task 1 |
15 |
0 |
Periodic |
3 |
30 |
2 |
|
2 |
Task 2 |
250 |
1 |
Periodic |
15 |
400 |
0 |
|
3 |
Task 3 |
105 |
2 |
Periodic |
20,29 |
120 |
0 |
|
4 |
Task 4 |
500 |
3 |
Periodic |
85 |
700 |
0 |
|
5 |
Task 5 |
330 |
4 |
Periodic |
5 |
600 |
0 |
|
6 |
Task 6 |
100 |
5 |
Periodic |
22 |
120 |
0 |
|
7 |
Task 7 |
70 |
6 |
Periodic |
2 |
140 |
0 |
|
8 |
Task 8 |
1000 |
7 |
Periodic |
15 |
1500 |
0 |
Il sistema risulta NON schedulabile.
The set is not schedulabile
Figura 8‑4: Analisi di schedulabiltà (test 4).
Sono state effettuate diverse
ottimizzazioni utilizzando funzioni di costo e parametri differenti.
I risultati ottenuti sono riportati in tabella.
|
Numero analisi |
Tipo |
Funzione costo |
Coeff |
Funzione costo n.s. |
Coeff n.s. |
Coeff min |
Sche |
Margine |
Margine minimo |
|
Non ottim. |
/ |
/ |
/ |
/ |
/ |
/ |
No |
56 |
0 |
|
1 |
P |
Lineare |
1 |
Lineare |
100000 |
5 |
Si |
74 |
45 |
|
2 |
P |
Quadratica |
1 |
Lineare |
100000 |
5 |
Si |
74 |
45 |
|
3 |
P |
Parabolica |
1 |
Lineare |
100000 |
5 |
Si |
74 |
45 |
|
4 |
P |
Cubica |
1 |
Lineare |
100000 |
5 |
No |
74 |
0 |
|
5 |
P |
Log base 10 |
1 |
Lineare |
100000 |
5 |
Si |
71 |
29 |
|
6 |
P |
Log base e |
1 |
Lineare |
100000 |
5 |
Si |
71 |
29 |
|
7 |
P |
Radice quadrata |
1 |
Lineare |
100000 |
5 |
Si |
73 |
45 |
|
8 |
P |
Radice cubica |
1 |
Lineare |
100000 |
5 |
Si |
72 |
45 |
|
9 |
P |
Mista |
1 |
Lineare |
100000 |
5 |
Si |
74 |
45 |
|
10 |
P |
Lineare |
1 |
Lineare |
100000 |
1 |
Si |
74 |
45 |
|
11 |
P |
Lineare |
1 |
Lineare |
100000 |
20 |
Si |
74 |
45 |
|
13 |
R |
/ |
/ |
/ |
/ |
/ |
Si |
73 |
45 |
Nella quasi totalità dei casi il sistema è divenuto schedulabile e presenta discreti margini di schedulabilità.
Capitolo 9 :Conclusione
Dalle prove effettuate risulta che l’analisi di schedulabilità risulta corretta, e che il sistema può essere reso maggiormente affidabile attraverso l’esecuzione dell’ottimizzazione.
Il tool realizzato è attualmente utilizzato da A.S.F (Ansaldo Segnalamento Ferroviario).
Alcuni dati
Il software comprende 13 differenti finestre (form), 5 controlli utente e le righe di codice sono in totale più di 10.000.
Utilizza funzioni grafiche,
multithreading, librerie dinamiche(dll), Windows ® registry ,OLE e supporta la
rotellina del mouse. Inoltre è in grado di leggere e scrivere in formato XML ed
HTML.
Appendice. Sintassi per descrivere situazioni in tempo
reale.
In questa appendice è presente una breve descrizione della sintassi suggerita per descrivere una situazione in tempo reale: i parametri in corsivo indicano che il parametro è ulteriormente suddiviso in termini di altri parametri nella sintassi.
I parametri non in corsivo hanno già stati definiti in precedenza o sono usati come stringhe letterali.
Bibliografia
- S.Sabina. Course on hard real time systems. Ansaldo Segnalamento Ferroviario (Hrt Course).