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 ad 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 0

1

- = 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 minimia 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