Riassunto Informatica industriale

Introduzione

Analizzeremo la differenza tra:

• Embedded sistemi (incapsulato): si produce qualcosa che sta all'interno di un altro sistema fisico; il software che è a bordo dell'oggetto rimane tale per tutta la vita dell'oggetto stesso (es. centralina automobile). Tali sistemi embedded svolgono una o più funzioni, tipicamente non modificabili (sono sistemi che svolgono funzioni specifiche).
• General purpose sistemi (ad uso generale): sono sistemi più generici in cui abbiamo la possibilità di modificare i programmi aggiungendo nuove funzionalità.

Il malfunzionamento dei sistemi embedded è più catastrofico rispetto ad un malfunzionamento di un sistema general purpose (si pensi all'impianto frenante di un'auto).

Comportamento a stati finiti di un sistema embedded

Algoritmi di controllo

Gli algoritmi di controllo hanno il compito di decidere qual è l'output che deve andare agli attuatori, a seconda degli eventi raccolti dai sensori. Questo comportamento degli algoritmi è detto event-driven, cioè guidato dagli eventi.

Macchine a stati finiti

Per vedere tali algoritmi si utilizzano le macchine a stati finiti (FSM), ovvero macchine raffigurate come grafi, in cui ogni nodo rappresenta un particolare stato ed ogni arco rappresenta una particolare transizione.

Definiamo lo stato di IDLE (o stato ozioso) come uno stato di attesa da cui possiamo muoverci verso un altro stato solo con il verificarsi di un determinato evento (come se fosse uno stato di attesa della macchina che attende un segnale).

Automi a stati finiti

Gli automi a stati finiti (ASF) servono per riconoscere le stringhe di un linguaggio.

Definiamo perciò:

• Alfabeto Σ (o dizionario): insieme finito di simboli (es: Σ = {a, b, c}).
• Σ*: insieme di tutte le parole di lunghezza finita costituite da simboli di Σ (es: Σ* = {a, b, aa, ab, ...}).
• Linguaggio L: sottoinsieme finito di Σ* (ovvero L ⊆ Σ*).

Possiamo definire un ASF come una quadrupla (Q, Σ, δ, q₀, F) dove:

• Q è un insieme finito di stati.
• q₀ ∈ Q è uno stato iniziale.
• F ⊆ Q è un insieme di stati finali.
• δ è la funzione di transizione tra stati (δ: Q × Σ → Q).

Linguaggi regolari

I linguaggi riconosciuti dagli automi a stati finiti sono i cosiddetti linguaggi regolari, ovvero linguaggi composti da espressioni regolari.

Esempio: Linguaggio L = {a, b, aa, ab, ...}

Espressione regolare: (a|b)*

Le espressioni regolari indicano come comporre tutte le parole del linguaggio (notiamo che la somma (+) indica un'opzione della stringa (OR) mentre la moltiplicazione (*) indica una ripetizione di zero o più volte del carattere indicato (AND)).

Linguaggi non regolari

Dobbiamo però riconoscere anche i linguaggi non regolari come ad esempio il linguaggio di parentesi con n > 0, dove con a si indicano le parentesi aperte e con b si indicano le parentesi chiuse.

Affinché tale linguaggio sia riconoscibile da un ASF, è importante però che il valore di n sia fissato (n ≤ k), altrimenti, se n è illimitato, avremmo un numero di parentesi infinito e quindi l'ASF non potrebbe ricordare tutti i possibili stati (servirebbe una memoria illimitata).

Automa a pila

Per risolvere questa situazione, possiamo utilizzare un automa a pila in cui possiamo eseguire le operazioni di PUSH (quando si legge a) e POP (quando si legge b).

In questo modo, possiamo definire un ASF con memoria idealmente illimitata (se la parola è finita allora la pila risulterà vuota e quindi la parola appartiene al linguaggio).

Un linguaggio riconoscibile da un automa a pila si dice context-free.

L’automa a pila però non riesce a riconoscere linguaggi del tipo aⁿbⁿcⁿ con n > 0 (detto linguaggio context-dependent).

Tale linguaggio può essere riconosciuto con un automa a due pile (ovvero quando si legge a si inserisce su due pile diverse (PUSH), quando si legge b si svuota una pila (POP) e quando si legge c si svuota l’altra pila (POP)).

Questo sistema può essere implementato anche con la macchina di Turing (il concetto è lo stesso dell’automa a due pile, però si utilizza una macchina che legge e scrive su un nastro infinito).

Linguaggi semidecidibili e indecidibili

Esistono anche altri linguaggi, detti linguaggi semidecidibili e indecidibili, per cui è difficile o impossibile realizzare degli algoritmi capaci di riconoscere se una parola appartiene al linguaggio.

Classificazione di Chomsky

Possiamo quindi suddividere i precedenti linguaggi secondo la cosiddetta classificazione di Chomsky:

• 0: linguaggi semidecidibili o indecidibili
• 1: linguaggi context-dependent
• 2: linguaggi context-free
• 3: linguaggi regolari
• 3: linguaggi finiti

N.B: L₃ ⊆ L₂ ⊆ L₁ ⊆ L₀

I linguaggi regolari e finiti (L₃ e L₃) sono riconoscibili con memorie limitate, perciò possono essere utilizzati per i sistemi embedded. Tutti gli altri linguaggi necessitano invece memorie illimitate, perciò possono essere impiegate nei sistemi general purpose (poiché in questi possiamo inserire memoria anche a run-time e quindi possiamo considerare la memoria illimitata).

Esempio di un ASF per riconoscere una parola

Esempio: Può capitare che in uno stato entri un simbolo che non fa parte della parola da riconoscere (ad esempio in q₀ può entrare anche b oppure c, ma in questo stato possiamo leggere soltanto a). Perciò, è fondamentale inserire un stato di errore, ulteriore stato, detto stato di errore, in cui l’automa blocca l’algoritmo (altrimenti si avrebbe una parola errata).

L’implementazione dell’automa può essere semplificata attraverso la matrice di transizione, che indica per quali valori possiamo avere la transizione da uno stato ad un altro stato (q₄ indica lo stato di errore).

Macchine a stati finiti: Mealy e Moore

Possiamo realizzare due tipi di macchine:

• Macchine di Mealy: la funzione di uscita dipende sia dagli ingressi che dagli stati attuali.
• Può essere rappresentata con una sestupla (Q, Σ, Δ, q₀, λ, η) dove:
• Q è un insieme finito di stati.
• q₀ ∈ Q è uno stato iniziale.
• Σ è un insieme di input.
• Δ è un insieme di output.
• δ è la funzione di transizione tra stati (δ: Q × Σ → Q).
• λ è la funzione di uscita (λ: Q × Σ → Δ).

• Macchine di Moore: la funzione di uscita dipende solamente dagli stati attuali.
• Può essere rappresentata con una sestupla (Q, Σ, Δ, q₀, η) identica alla precedente, tranne che la funzione di uscita diventa η: Q → Δ.

Tali macchine hanno un comportamento ciclico, ovvero si trovano in uno stato di attesa in cui si attende un particolare evento dall’esterno. All’arrivo di tale evento, la macchina si sposta in un secondo stato in cui viene trattato l’evento. Questo comportamento di reazione a seguito della ricezione di un evento proveniente dall’esterno è detto event-driven (o reattivo).

Eventi sincroni e asincroni

L’evento può essere notificato in due modi:

• Modo sincrono: tale sistema è detto anche attesa attiva, poiché il processore attende la variazione dei vari ingressi (detti polling di ingressi) senza compiere alcuna operazione. Quando si ha la variazione di uno o più input, allora il processore inizia a lavorare.
• Modo asincrono: si utilizzano le interruzioni, ovvero ci troviamo in un ciclo di attesa finché non si rileva un’interruzione. Una volta intercettata un’interruzione si esce dal ciclo e si esegue la reazione all’input. Terminata l’operazione, torniamo nel ciclo per attendere una nuova interruzione. Notiamo che in questo caso si risparmiano due cicli di clock (possono essere fondamentali per sistemi in real-time).

Sistemi real-time

Per sistema in tempo reale si intende un sistema il cui funzionamento dipende sia dal corretto calcolo funzionale che dal tempo in cui tale calcolo viene effettuato. Abbiamo due tipi di sistemi real-time:

• Soft real-time: i vincoli sui tempi di risposta non sono stringenti, poiché in alcuni casi possono non essere rispettati.
• Hard real-time: i vincoli sui tempi di risposta sono stringenti, poiché se non vengono rispettati il sistema è inutile o persino pericoloso.

Temporizzazione dell’algoritmo di controllo

Per il controllo digitale dei sistemi, si deve ricorrere ad una discretizzazione del tempo. Questo può essere fatto con il teorema di Nyquist-Shannon, il quale garantisce che se un segnale viene campionato ad una sufficiente frequenza, allora l’insieme dei campioni possono ricostruire il segnale senza perdita di informazioni.

In particolare, dice che, dato un segnale di cui si conosce la frequenza massima f_max, allora la frequenza minima di campionamento f_s per evitare la perdita di informazione dovrà essere f_s = 2f_max.

N.B: oltre alla discretizzazione temporale, abbiamo anche una discretizzazione del valore (approssimazione del valore per mancanza di precisione).

Le caratteristiche del sistema, perciò, definiscono una frequenza massima f_max, la quale definisce il periodo T = 1/f_max.

Possiamo dunque definire il periodo tipico dell’algoritmo di controllo come il ciclo in cui viene eseguito il codice dell’algoritmo (lettura, scrittura e calcolo). Tale codice, detto task, viene ripetuto ad ogni periodo.

Sincronizzazione con il tempo

Per rendere dipendente dal tempo il periodo T di un task possiamo procedere in due modi:

1. Sincronizzare l’esecuzione del codice del task con un evento di timer. Il Timer è una variabile che viene posta ad 1 quando scade il periodo e viene rimessa a 0 prima che si concluda l’esecuzione del codice del task. La struttura del programma è simile a quella di un sistema event-driven sincrono.
2. Far riferimento al clock del sistema. In questo caso si utilizza la funzione di sistema clock() che ritorna il valore attuale del clock. Ad ogni ciclo possiamo quindi verificare se il tempo attuale ha raggiunto il valore dato dal periodo sommato al tempo memorizzato all’inizio del periodo.

N.B: il clock deve essere una funzione monotona crescente.

Dobbiamo però assicurarci che il tempo effettivo di esecuzione del codice del task (detto et) sia sempre limitato superiormente dal valore di periodo (detto T), ovvero deve valere et < T.

WCET

Solitamente, il calcolo del tempo di esecuzione di un task (ovvero et) viene effettuato considerando il caso peggiore, detto WCET (Worst Case Execution Time). Dobbiamo però tenere conto di alcune considerazioni:

• Il calcolo del WCET, che si effettua andando a vedere quante e quali istruzioni vengono effettivamente eseguite nel caso peggiore, è in generale indecidibile per la possibile presenza di cicli illimitati.
• Il calcolo del WCET è complesso per architetture moderne (con pipeline, cache o prefetch) mentre è più semplice per architetture vecchie.
• Si devono considerare inibite le eventuali sorgenti indipendenti di ritardo non determinabili a priori nell’architettura hardware (es: DMA, interruzioni).
• Il calcolo richiede l’analisi del codice macchina.

Misurazione del WCET

L’alternativa al calcolo del WCET è la misurazione dei tempi effettivi di esecuzione del codice sulla macchina di riferimento. In generale, però, l’affidabilità di tale misura è solo statistica.

Metodo pratico di misura del WCET: considerando un’implementazione event-driven asincrona (con interruzioni), allora il codice del task deve concludere la sua esecuzione prima dell’interruzione.

Multitasking

Nel caso in cui il WCET sia molto minore del periodo (et ≪ T) allora si cerca di unificare più funzioni di controllo su uno stesso processore. Nasce così il concetto di multitasking, ovvero vengono eseguiti più task (ognuno con le sue caratteristiche funzionali e temporali) dallo stesso processore.

Parametri di un processo real-time

Come abbiamo visto, un processo real-time (o task real-time) è caratterizzato da due parametri: il tempo di esecuzione et (in genere fa riferimento al WCET) ed il periodo T.

Tramite questi due parametri possiamo calcolare il carico della CPU, detto CPU load, ovvero L = et/T.

N.B: in un sistema hard real-time è necessario che et < T perciò avremo L < 1.

Relazioni tra i parametri

Vediamo le relazioni tra i parametri et e T:

• Istante di rilascio: si definisce istante di rilascio di un task il momento in cui, alla scadenza del periodo precedente, si può far iniziare di nuovo il task;
• Deadline: si definisce l’istante di tempo entro cui l’esecuzione del task deve essere terminata (si può considerare come la somma tra istante di rilascio e T);

Non tutti i task di un sistema real-time sono periodici, ma possiamo avere anche task aperiodici. Inoltre, possiamo definire task sporadici, quei task aperiodici il cui istante di rilascio non può essere calcolato a priori. Tali task gestiscono gli eventi e sono caratterizzati da un tempo di risposta massimo richiesto.

Task di background

Infine, definiamo i task di background come task aperiodici che vengono eseguiti quando non abbiamo la necessità di eseguire gli altri task (in genere sono task di gestione o diagnostica).

N.B: i task sporadici possono essere trattati come i task periodici nel caso in cui la condizione di rilascio del task venga periodicamente testata, ovvero se T ≥ et + Δ. Inoltre, l’assunzione di una separazione minima Δ tra due invocazioni successive di un task sporadico implica che T ≥ Δ.

Priorità

Durante l’esecuzione di un multitasking, ad ogni task viene associata una priorità (tale valore è un numero intero), che permette di scegliere quali task eseguire per primi. Tipicamente, la priorità viene assegnata al tipo di task nel seguente modo: task sporadico, task aperiodico, task periodico e task di background.

In generale, la priorità in un sistema real-time deve essere assegnata in modo da garantire il rispetto della deadline.

Scheduling

Con il concetto di multitasking, però, nasce il problema del sequenziamento (o scheduling) dei task. Lo scheduling dei task si intende un meccanismo preposto alla scelta di una sequenza in cui eseguire i task stessi.

Poiché la realizzazione di uno scheduling può essere molto complessa, effettueremo delle semplificazioni:

• Si assume che l’applicazione sia composta da un insieme fisso di task (ovvero non si possono creare task dinamicamente);
• Ogni task è considerato di periodo fisso;
• I task sono indipendenti tra loro (ovvero, un task per essere eseguito non deve attendere il risultato di un altro task);
• Tutti i tempi di overhead sono ignorati;
• Tutti i task devono terminare nel periodo, cioè devono essere completati prima di una nuova esecuzione;
• Ogni task ha un tempo di esecuzione et fisso (ovvero il WCET è fisso);

Istante critico

N.B: una conseguenza dell’assunzione di indipendenza tra i vari task è che può esistere un istante, detto istante critico, in cui tutti i task saranno rilasciati contemporaneamente. Tale istante rappresenta il momento di massimo carico del processore.

Tipi di scheduling

Lo scheduling può essere:

• Statico: se la sequenza dei task viene decisa prima della loro esecuzione. Dato un insieme finito di task periodici, possiamo definire uno schema di scheduling la cui esecuzione ripetuta consente l’attivazione dei task alla loro frequenza. Lo schema è realizzato come un insieme di procedure, ognuna delle quali implementa il codice di una particolare task.
• Lo scheduling viene definito con una sequenza di invocazioni a tali procedure, e l'intera sequenza viene detta major cycle (la quale è suddivisa in gruppi di chiamate di procedure detti minor cycle che hanno lunghezza fissata).
• Un codice con scheduling statico è chiamato esecuzione ciclica.
• Se tutti i task hanno lo stesso periodo, vi è un solo minor cycle che coincide con il major cycle. Si può pensare in questo caso ad una soluzione che ordina le varie chiamate usando un vettore contenente i puntatori alle funzioni che implementano i task.