Riassunto Informatica industriale

Riassunto informatica industriale

Tommaso Giannoni
Luca Cialdi
Giugno 2015

Introduzione

Analizzeremo la diversificazione tra "sistemi embedded" e sistemi "general purpose": è una differenza di utilizzo (di un computer).

In particolare:

• Embedded = 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).
• General purpose: vi è la capacità di modificare i programmi aggiungendo nuove funzionalità (abbiamo solo un limite fisico, cioè CPU, RAM, ecc.).

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

Infine, in un sistema embedded, la fase di testing costa quanto la fase dello sviluppo software.

1 - Comportamento a stati finiti di un sistema embedded

Gli algoritmi di controllo nascono come algoritmi continui, ma in realtà dobbiamo lavorare in termini discreti.

Il compito di tali algoritmi è quello di decidere qual è l'output che deve andare agli attuatori.

Il comportamento discreto dell'algoritmo si dice "event driven", cioè guidato dagli eventi.

L'output di tali algoritmi è dato sia dall'input (sensori) che dallo stato del processore, il quale è dato da una serie di variabili di stato.

Per vedere tali algoritmi abbiamo bisogno delle macchine a stati: tali macchine sono raffigurate come grafi, in cui ogni nodo rappresenta un particolare stato ed ogni arco rappresenta una particolare transizione.

ASF e riconoscitori di linguaggi

Automi a stati finiti (ASF): servono per il riconoscimento di stringhe di un dato linguaggio.

Definiamo:

• Alfabeto (dizionario): insieme di simboli V.
• V* : insieme di tutte le parole (stringhe) composte da simboli in V.
• Linguaggio: sottoinsieme finito di V* = (, , , ).

Possiamo dunque definire un ASF come una quadrupla dove:

• 0  è un insieme finito di stati.
•  ∈ è lo stato iniziale 0.
•  ∈ è l'insieme degli stati finali ′.
•  ∶ × → , = ′ funzione di transizione ( ).

∗ ∗⊆ × × Relazione di raggiungibilità: ∗ ∗ ∗ ∗ ∗1 2 ′ ′ … = … ∈ Ovvero sse 1 2 1 2 1 ∗∗ ′ ⊆ ∈ ⇔ ′ ∈

Un linguaggio è riconosciuto da un automa A se 0 I linguaggi riconosciuti dagli automi sono i cosiddetti "linguaggi regolari".

Un'applicazione di tali linguaggi sono le espressioni regolari, in cui la moltiplicazione equivale ad un AND e la somma ad un OR. Da notare che in questa notazione, l' * significa "0 o più volte" (molteplicità).

Si deve essere in grado di riconoscere le espressioni aritmetiche (applicazione). E' un linguaggio di parentesi; il più semplice dei quali è dove con si indicano le parentesi aperte, e con le parentesi chiuse.

Purtroppo a meno di limiti imposti, il numero delle parentesi può essere infinito e quindi non è un ASF; poiché ≤ ASF riconosce con fissato. Per risolvere tale problema (memoria limitata dato grande a piacere) introduciamo l'Automa a pila.

Tale automa utilizza per l'appunto una pila (stack) con le consuete operazioni di PUSH e POP: così facendo riesco a definire un ASF con memoria (idealmente) illimitata.

Un linguaggio riconoscibile da un automa a pila si dice "context-free" (non dipende dal contesto in cui si applica). Dunque un linguaggio caratteristico della classe dei linguaggi context-free è il linguaggio.

Da notare però che l'automa a pila non riesce a riconoscere linguaggi del tipo: per risolvere tale problema si introduce un'ulteriore pila aggiuntiva; così facendo si possono implementare tutti gli algoritmi possibili.

In generale, i sistemi embedded sono progettati per pensare con memoria limitata (non è vero per sistemi general purpose).

Introduciamo adesso la Macchina di Turing: macchina che legge su un nastro (infinito) invece che su di una pila.

Secondo la tesi di Church, un qualsiasi metodo per scrivere algoritmi è equivalente ad una macchina di Turing.

La macchina può dunque riconoscere i linguaggi "context-dependent".

Esistono però altri linguaggi detti linguaggi semidecidibili e linguaggi indecidibili: per i primi esistono algoritmi per cui se la parola appartiene al linguaggio allora lo scopro, ma se non appartiene non so se lo scopro (cioè entro in un loop); per i secondi invece non esistono algoritmi che possono dire se una parola appartiene o meno al linguaggio.

Esiste dunque una classificazione dei linguaggi, detta classificazione di Chomsky:

• = Linguaggi semidecidibili e indecidibili 0 ⊂ ⊂ ⊂ ⊂.
• = Linguaggi context-dependent 3 2 1 01.
• = Linguaggi context-free 2.
• = Linguaggi regolari 3.

Vediamo dunque che "linguaggio" o "problema" sono sinonimi.

Per linguaggi che non sono in , per riconoscere se una parola appartiene al linguaggio, ho bisogno di una 3 memoria idealmente illimitata.

Possiamo dunque fare anche una classificazione di problemi:

• ∋ Problemi indecidibili - problemi semidecidibili 0.
• ∋ , problemi decidibili con memoria illimitata 2 1.
• ∋ Problemi decidibili con memoria fissata 3.

Per problemi con memoria illimitata, tale memoria dipende (e varia) in proporzione della taglia dell'input.

Si usano dunque due "filoni" per misurare le proprietà di un problema:

• Computabilità: decidere se un problema è decidibile oppure no.
• Complessità (computazionale): misura del tempo e dello spazio occupato da un algoritmo che tratta un particolare problema.

Nei sistemi embedded non ho bisogno (o non ho) una memoria illimitata; nei sistemi general purpose posso aggiungere memoria anche run-time, quasi illimitata (blocco dato dai limiti fisici). 2 , ,

Questo ci fa capire che nei sistemi embedded posso implementare linguaggi , ma non ; e dunque gli 3 2 1 0 algoritmi che posso implementare sono solo ed esclusivamente macchine a stati finiti.

La classificazione dei linguaggi permette di determinare classi di decidibilità di problemi.

Un esempio di tali classi è il cosiddetto problema dell'equivalenza: voglio sapere se per identici input su due diverse macchine di Turing A e B, implementate con lo stesso linguaggio di programmazione (C), ho stessi output.

Purtroppo la soluzione a questo problema non esiste.

Se per assurdo esistesse, tale risultato mi darebbe anche una proprietà di correttezza: se A è corretto e B è equivalente ad A, allora anche B è corretto.

Nemmeno per gli automi a pila riesco a risolvere il problema dell'equivalenza. L'unico modo per trovare una soluzione al problema dell'equivalenza è quello di lavorare in linguaggi (stessa 3 cosa vale per i problemi di correttezza).

Come abbiamo appena visto, lavorare in ha dei grandissimi vantaggi; ma purtroppo si perdono alcune proprietà: 3

• Ho solo algoritmi che risolvono problemi limitati (quindi non sono risolvibili problemi come quello delle parentesi, a meno che non si mettano limiti su).
• Non possiamo avere un compilatore (poiché quest'ultimo deve necessariamente riconoscere le parentesi; e non posso creare file oggetto per eseguirli).

Macchine a stati finiti ′ ′ ∶ l'uscita è funzione dell'input ℯ dello stato corrente.

Macchine a stati finiti ′ ∶ l'uscita è funzione solamente degli stati correnti.

Nelle macchine a stati finiti per determinati input voglio specifici output.

Da qui si nota la differenza con i problemi decidibili, che sanno rispondere solo SI o NO alla domanda se una parola appartiene ad un linguaggio. (, , , , , )

Macchine di Mealy: sono dati dalla sestupla:

• 0 insieme finito di stati.
• ∈ stato iniziale 0.
• Insieme finito di input.
• Insieme finito di output.
• : × → funzione di transizione.
• : × → funzione di output.
• : →

Nelle macchine di Moore, la sestupla è identica ma cambia la funzione di output che diviene.

Extended finite state machine: si associano delle variabili alle macchine a stati finiti, e delle azioni per lavorare con tali variabili.

Bisogna stare attenti però ad imporre un limite superiore al dominio delle variabili, affinché possiamo lavorare con sistemi embedded. L'unico problema potrebbe essere causato dall'"esplosione (esponenziale) dello spazio degli stati".

Per descrivere il comportamento delle macchine a stati finiti usiamo un diagramma previsto dall'UML detto "State Chart Diagram" (Diagramma degli stati): i nodi di questo diagramma introducono una gerarchia di stati, poiché si possono trovare degli stati entro altri stati (annidamento), anche se comunque il numero di tali stati è sempre finito.

= Evento di input = controllo sulle variabili.

Sulle frecce che collegano i nodi troviamo tre concetti: output = assegnamento ad una variabile.

Grazie a tali diagrammi abbiamo la cosiddetta disciplina "model-based design driven", che permette di disegnare statecharts e di lavorare su questo modello tramite simulazioni, oltre alla generazione automatica del codice. 3

Implementazione di ASF

Vi sono due diverse implementazioni di un ASF, entrambi ricorrendo alla funzione "getch()" per leggere il prossimo carattere della stringa da riconoscere:

• Il primo metodo utilizza uno switch per ogni stato dell'automa (in cui si sceglie la transizione in base al simbolo letto).
• Il secondo usa una matrice di transizione del grafo, che restituisce il prossimo stato a partire dallo stato attuale e dal simbolo letto.

Implementazione di macchine a stati finiti

L'implementazione delle MSF non è diversa da quella delle ASF; si può difatti utilizzare il metodo basato su uno switch o quello con matrice di transizione (che in Mealy ha una matrice per il prossimo stato e una matrice per l'uscita, mentre in Moore ha una matrice per il prossimo stato e un vettore per l'uscita).

Possiamo astrarre da questa scelta di implementazione utilizzando due funzioni: next() e output().

Mealy Moore

int c; int c; //input //input
int stato=0; int i; int stato=0; int i;
while(TRUE) output(stato);
{ input(&c); while(TRUE) output(stato,c); { input(&c);
stato=next(stato,c); stato=next(stato,c); } output(stato);}

Si noti dunque che la principale differenza con l'implementazione di un ASF riconoscitore di linguaggi sta nell'utilizzo di un ciclo infinito (while(TRUE)). Questo poiché spesso un sistema embedded deve controllare un processo senza terminazione.

Dunque una volta conosciuta la definizione della MSF, la scrittura del codice è meccanica ed automatica.

Event-driven system

Un sistema è detto event-driven (o reattivo) quando, a seguito della ricezione di eventi provenienti dall'esterno, risponde con una reazione.

Un evento può essere notificato ad un sistema in due modi:

• Modo sincrono: con variazione del valore di una variabile.

while(TRUE)
if(input variato) {reazione all'input}

Se vi sono più variabili in ingresso, vi sarà un if per ciascuna variabile.

Un'implementazione di questo tipo si dice con attesa attiva perché il processore attende la variazione degli ingressi senza compiere alcuna operazione.

La reazione ad un input (fatta con una MSF) include la funzione next() che incapsula il test sulla variabile di input e in cui una variabile globale mantenga il valore dello stato corrente.

• Modo asincrono: attraverso le interruzioni e relativa routine di interruzione.

while(TRUE);

Anche in questo caso le routine di interruzione possono realizzare le funzione di transizione (next()) e di output() di una MSF, che deve essere inizializzata per denotare lo stato iniziale prima che il processore entri in attesa attiva. 4

In entrambe le soluzioni la struttura dell'algoritmo di controllo è comunque costituita da una fase di inizializzazione seguita da un ciclo infinito: all'interno del ciclo si leggono gli ingressi e si compiono le opportune azioni sulle uscite; che in un sistema embedded vengono dette lettura dei sensori e scrittura degli attuatori.

Molto importante da notare è il fatto che le due implementazioni si comportano diversamente dal punto di vista temporale: se gli eventi non si sovrappongono temporalmente, nella soluzione con interruzioni l'evento viene servito immediatamente; mentre nella soluzione in cui un ciclo testa periodicamente tutte le variabili di ingresso (polling) l'evento viene servito solo quando il processore arriva a testare la relativa variabile di ingresso.

Questo diverso trattamento ha quindi effetto sul tempo di risposta all'evento: sistemi con requisiti sui tempi di risposta si dicono sistemi real-time.

2 - Sistemi real-time

Sistema real-time: sistema il cui corretto funzionamento non dipende solamente da un corretto calcolo funzionale, ma anche dal tempo in cui questo calcolo viene effettuato.

• Soft real time: i vincoli sui tempi di risposta non sono stringenti, perché in qualche caso si può non rispettarli.
• Hard real time: i vincoli sui tempi di risposta sono stringenti, perché se non vengono rispettati il sistema è inutile o persino pericoloso.

Temporizzazione dell'algoritmo di controllo

Come già visto precedentemente, gli algoritmi di controllo di tipo discreto hanno la tipica struttura di un ciclo infinito che alterna la lettura dei sensori al calcolo delle risposte e del prossimo stato, al comando degli attuatori.

Per il controllo digitale dei sistemi, si deve ricorrere ad una discretizzazione temporale del controllo stesso: si usa il cosiddetto Teorema di Nyquist-Shannon, che garantisce che se un segnale viene campionato ad una sufficiente frequenza, l'insieme dei campioni basta a ricostruire il segnale senza perdita di informazioni.

In particolare ci dice che dato un segnale di cui si conosce la frequenza massima, la frequenza minima di 2 · = 2  campionamento (per evitare perdita di informazione) è, dunque. = 1/

Le caratteristiche del sistema controllato definiscono una frequenza massima, la quale definisce il periodo dell'algoritmo di controllo.

Dunque si può definire il periodo tipico dell'algoritmo di controllo: ad ogni periodo viene eseguito il codice dell'algoritmo (lettura, calcolo, scrittura); il codice ripetuto ogni periodo viene detto task.

Per rendere effettivamente dipendente dal tempo il periodo di un task, è possibile procedere in diversi modi:

1. Sincronizzare l'esecuzione del codice del task con un evento di timer.

main(){ "Timer" sarà una variabile che viene automaticamente messa ad 1 quando
//inizializzazione scade il periodo, e rimessa a 0 prima che si concluda l'esecuzione del
while(TRUE){ codice del task.
if(Timer){ Si noti la similarità con il "modo sincrono" per il modello event-driven: in
//codice del task questo caso l'evento è lo scadere del periodo.
}}}

Possiamo però pensare anche di ipotizzare una soluzione con interruzioni (cioè "modo asincrono"): si tiene un registro (inizializzato a che viene automaticamente decrementato ad ogni ciclo di clock, e che genera un'interruzione quando il suo valore arriva a 0; la routine di interruzione sarà il codice del task.

2. Far riferimento al clock di sistema.

time t; "getclock()" è una f. di sistema che ritorna il valore attuale del
//inizializzazione
t = getclock(); clock (di tipo time): in ogni ciclo possiamo controllare se il
while(TRUE){ tempo attuale ha raggiunto il valore dato dal periodo + il tempo
if (getclock()== Periodo+t) memorizzato all'inizio del periodo.
{ t = getclock(); (NB: il clock deve essere una f. monotona crescente)
}}//task code 5

Occorre però notare che in ogni caso bisogna assicurarsi che il tempo effettivo di esecuzione del codice del task < (detto ) sia sempre limitato superiormente dal valore di periodo (detto ), cioè deve valere:

L'analisi del tempo di esecuzione di un task deve considerare il caso peggiore: il WCET dà così un limite superiore al tempo di esecuzione del task, tenendo conto che:

• Il calcolo del WCET (da effettuare andando a vedere quante e quali istruzioni vengono effettuate dal task nel caso peggiore) è in generale indecidibile (a causa della possibile presenza di cicli illimitati nel codice).
• Se si conoscono programmi in cui esiste un limite ai cicli, il calcolo è semplice per archi