Principio fondamentale:
le macchine a stati finiti sono spesso utilizzate per risolvere determinati tipi di problemi di controllo, in cui il flusso di controllo può essere rappresentato come un movimento attraverso una serie di stati diversi. Esistono diverse definizioni e descrizioni pratiche di una macchina a stati finiti; a livello teorico, è simile a un automa che risponde a uno stimolo specifico modificando il proprio stato. Per dare un'espressione specifica e comune, può essere considerata, ad esempio, come un automa che reagisce alla stringa di input passando attraverso una serie di stati. Se viene raggiunto lo stato desiderato, la stringa di input diventa equivalente all'espressione comune.
Nell'ambito del software di controllo, è comune assumere la natura finita e deterministica della macchina a stati finiti come base del suo modello computazionale. Ciò significa fondamentalmente che il numero di stati o combinazioni di stati possibili è finito e che la macchina a stati finiti può avere un solo stato in un dato momento. Vedremo in seguito che la regola di un solo stato alla volta può essere attenuata, ma l'aspetto rilevante è che lo stato del flusso è una proprietà deterministica.
Se l'implementazione delle macchine a stati nel software è una novità per te, ecco i concetti più importanti:
Stati: Uno stato può essere considerato una descrizione sintetica dello stato attuale del sistema. Ad esempio, si consideri un dispositivo periferico che può avere tre modalità operative alternative al livello più alto: acceso, spento o standby.
Eventi: Un evento è un messaggio di input per la macchina a stati. L'evento può causare un cambiamento di stato della macchina a stati. Premere il pulsante di accensione su un televisore in modalità standby è un tipo di evento che, con un po' di fortuna, riporterà il televisore in funzione, ovvero allo stato acceso.
Transizioni: Una transizione è un percorso diretto da uno stato a un altro. Una transizione viene solitamente designata con un nome di evento, che indica che la transizione si verificherà se l'evento specificato si verifica mentre la macchina a stati si trova nello stato iniziale della transizione. Il risultato finale è che la macchina a stati cambia stato e passa allo stato di destinazione della transizione. Per complicare le cose, o meglio, per aumentare la potenza espressiva della notazione delle macchine a stati, una transizione può essere "protetta" da condizioni di watchdog che devono essere soddisfatte affinché la transizione abbia luogo.
Azioni – Un'azione è un'attività da eseguire da parte della macchina a stati in un momento specifico. Generalmente, un'azione esegue un'operazione nell'ambiente, come la lettura o la scrittura su un dispositivo di I/O. Le azioni possono essere associate a transizioni, oppure possono essere specificate come azioni di input e output in stati specifici.
Questi concetti sono fondamentali per l'approccio formale alla progettazione delle macchine a stati, che troveremo come sottoinsieme del linguaggio di modellazione UML.
Oltre alle nozioni di base,
consideriamo un esempio semplice tratto da un manuale: un problema orientato agli stati. Cerchiamo di trovare un'implementazione adeguata su una macchina a stati. In questo caso, esistono due soluzioni diverse, ognuna con i propri vantaggi e svantaggi, e la scelta dipende dalla valutazione dei rispettivi pro e contro.
Il problema: “Una strada principale trafficata interseca una strada locale poco trafficata. Lungo la strada locale sono posizionati dei rilevatori che attivano un segnale C quando un veicolo è in attesa di attraversare la strada principale. Il controllore del semaforo dovrebbe funzionare come segue: finché non viene rilevato alcun veicolo sulla strada locale, i semafori devono rimanere verdi in direzione della strada principale. Se viene rilevato un veicolo sulla strada locale, i semafori sulla strada principale devono cambiare da giallo a rosso, consentendo ai semafori sulla strada locale di diventare verdi. I semafori sulla strada locale rimangono verdi ogni volta che viene rilevato un veicolo sulla strada locale e mai per un intervallo prestabilito per consentire al traffico di fluire sulla strada principale. Se queste condizioni sono soddisfatte, i semafori sulla strada locale cambieranno da verde a giallo e poi a rosso, consentendo ai semafori sulla strada principale di tornare verdi. Anche se ci sono veicoli in attesa di attraversare la strada principale, questi devono rimanere verdi per un intervallo prestabilito.” 1
Questo esercizio si concentra su una prospettiva hardware, ma con un po' di licenza artistica può essere adattato a un ambiente software. Si noti che l'esempio utilizza la convenzione secondo cui la luce gialla appare sempre da sola (in alcune parti del mondo si usano convenzioni diverse). Tuttavia, questo non influisce sulla difficoltà del problema; semplicemente semplifica l'individuazione delle possibili combinazioni di colori.
L'approccio più semplice alla progettazione di una macchina a stati può essere descritto come segue:
1. Identificare eventi e azioni
2. Identificare gli stati
3. Raggruppare per gerarchie
4. Raggruppare per concorrenza
5. Aggiungere transizioni
6. Aggiungere sincronizzazioni.
Questa non è una ricetta prescrittiva, ma piuttosto un approccio che in genere si rivela utile per strutturare una soluzione, indipendentemente dagli strumenti e dai metodi di implementazione scelti.
Analizziamo più a fondo la questione.
Iniziamo esaminando la descrizione del problema, cercando possibili eventi e azioni. Cosa costituisce un evento nel contesto di una macchina a stati? In parole semplici, un evento è un trigger che può potenzialmente causare un cambiamento di stato della macchina a stati e l'esecuzione di un'azione. Nel caso dei semafori, possiamo individuare una serie di potenziali eventi:
L'arrivo del traffico sulla strada locale è un evento che ha implicazioni per il funzionamento del semaforo.
A tal proposito, si possono considerare i seguenti intervalli di tempo:
- Il tempo minimo in cui il semaforo della strada principale rimane verde. Questo valore può essere utilizzato anche come tempo fisso di permanenza del semaforo verde sulla strada locale in
presenza di traffico.
- Il ritardo tra il passaggio al giallo e il passaggio al giallo per entrambe le strade.
Gli intervalli di ritardo non sono eventi in sé; piuttosto, la fine di un intervallo può essere considerata un evento. In pratica, questo ci lascia con due eventi: un evento per l'intervallo lungo durante il periodo di semaforo verde su entrambe le strade e un altro evento per il ritardo breve e uniforme durante la transizione attraverso la sequenza semaforica tra rosso e verde e viceversa.
Questo ci lascia con tre eventi, che possiamo chiamare LocalRoadTrafficEvent, LongEvent e ShortEvent.
Quindi, cosa costituisce un'azione in questo problema? Cambiare il colore del semaforo è un'azione tipica. L'unica domanda è se cambiare il colore del semaforo su entrambe le strade costituisca una o due azioni. La risposta è che in realtà è una questione di convenzione. Possiamo considerarla come due azioni separate, ognuna delle quali gestisce una delle strade, oppure possiamo vederla come un'unica azione. Scelgo di considerarla come due azioni separate, per ragioni che diventeranno chiare in seguito.
Scelgo di chiamare le azioni ConfigureLocalRoadLight() e ConfigureMainRoadLight(); ogni azione accetta un parametro di colore che indica il colore desiderato.
L'idea è che gli eventi che abbiamo scelto attiveranno dei cambiamenti in determinate situazioni in cui verranno visualizzati i colori del semaforo.
Abbiamo anche bisogno di un modo per tenere traccia degli intervalli di tempo, quindi introduciamo un'azione speciale chiamata azione timer. Il suo scopo è avviare un contatore timer per un intervallo specificato e tenere traccia di un evento che verrà attivato quando il timer raggiungerà la fine. Per semplicità, chiameremo questa azione timer `ActionTemp()`.
Per comprendere meglio la logica di controllo del sistema semaforico, dobbiamo conoscere i possibili stati e le transizioni tra di essi. La prima soluzione utilizzerà queste osservazioni:
in qualsiasi momento, i semafori visualizzeranno una delle seguenti combinazioni di colori: {VERDE, ROSSO}, {GIALLO, ROSSO}, {ROSSO, ROSSO}, {ROSSO, GIALLO}, {ROSSO, VERDE}, {ROSSO, GIALLO}. In base alle regole operative di un semaforo, è chiaro che altre combinazioni non dovrebbero essere consentite per evitare di introdurre rischi per il traffico che attraversa contemporaneamente l'incrocio di entrambe le strade. Il primo colore di ogni coppia è il semaforo per la strada principale.
Esiste una sequenza fissa in cui verranno visualizzate le combinazioni di colori indicate sopra: {VERDE, ROSSO}, {GIALLO, ROSSO}, {ROSSO, ROSSO}, {ROSSO, GIALLO}, {ROSSO, VERDE}, {ROSSO, GIALLO}, {ROSSO, ROSSO}, {GIALLO, ROSSO}, e poi si torna alla prima combinazione per ricominciare.
Non ci vuole molto per vedere ogni fase della sequenza come un possibile stato, poiché include chiaramente lo stato del sistema in un dato momento. Le transizioni tra gli stati verrebbero quindi attivate dai diversi intervalli di tempo per ogni cambio di colore. Supponendo che la sequenza inizi con un semaforo verde per la strada principale, l'intera sequenza viene attivata da un LocalRoadTrafficEvent.
Il lettore attento avrà notato che ci sono alcune duplicazioni nella sequenza di combinazioni di colori sopra. Ad esempio, la combinazione "entrambi i semafori rossi" appare due volte. Dobbiamo considerarle come un unico stato o due? Ho scelto di trattare tutte le posizioni nella sequenza come stati separati. Questa decisione implica che le transizioni tra gli stati dovrebbero essere il più semplici possibile.
Abbiamo già le basi sotto forma di un insieme di eventi, alcune azioni e un insieme di stati candidati.
La Figura 2 mostra il progetto in notazione UML. Gli stati proposti sono rappresentati in forma circolare con transizioni denominate in base agli eventi corrispondenti. Gli stati prevedono anche azioni di input per cambiare il colore del semaforo. Come si può notare, solo lo stato iniziale richiede la configurazione di entrambi i semafori per garantire un avvio corretto della sequenza; per gli altri stati, è sufficiente modificare il colore di un solo semaforo rispetto allo stato precedente. Questo spiega l'utilizzo di due diverse funzioni di azione. Lo stato iniziale è indicato dalla transizione tra lo stato iniziale e lo stato corrente, rappresentata da un piccolo cerchio nell'angolo in alto a sinistra.
La semantica UML utilizza lo stato iniziale e la transizione da esso per puntare allo stato di partenza desiderato, il che significa che possiamo esprimere l'inizializzazione del sistema direttamente nel diagramma. La transizione non prevede alcun evento ed è implicita nell'avvio.
Dal punto di vista di una macchina a stati, questo progetto è quasi completo, ma manca la gestione di un intervallo minimo di verde per la strada principale. Possiamo risolvere questo problema in diversi modi, ma la seguente soluzione sembra piuttosto semplice.
Introduciamo una piccola gerarchia nel modello creando una macchina a stati all'interno dello stato MainGreen_LocalRed. Questa macchina a stati è composta da due stati più lo pseudo-stato iniziale. Ogni volta che si entra nello stato circostante, verrà attivato anche lo stato NewGreen.
Quando scade un lungo intervallo di tempo, iniziato all'ingresso in MainGreen_LocalRed, facciamo in modo che la piccola macchina a stati cambi stato in LocalRoadEventOK. Ora sappiamo che l'intervallo minimo di verde per il semaforo sulla strada principale è trascorso e che ora dovrebbe essere corretto (OK) "diventare verde" sulla strada locale se c'è traffico.
L'ultimo elemento necessario per mantenere l'intervallo verde minimo sulla strada principale è una "protezione" nella transizione dallo stato GreenMain_RedLocal. Questa transizione dovrebbe essere sovrascritta solo se viene attivato lo stato LocalRoadEventOK. Ciò può essere espresso come una condizione di stato positiva o una sincronizzazione positiva nella transizione. Le modifiche risultanti sono visibili nella Figura 3.
Questa soluzione non è perfetta perché non tiene conto del fatto che il traffico che arriva sulla strada locale durante l'intervallo verde minimo sulla strada principale rimane fermo fino all'arrivo di un'altra auto allo scadere dell'intervallo. Per ovviare a questo problema, è necessario registrare qualsiasi LocalRoadTrafficEvent che si verifica durante l'intervallo verde in modo da poter intraprendere le azioni appropriate allo scadere dell'intervallo. Non studieremo qui una soluzione completa al problema, ma se si tenta di progettarne una, i seguenti punti indicano una possibile strada da seguire:
introdurre una variabile di avviso interna nella macchina a stati che viene azzerata ad ogni ingresso dello stato verde sulla strada principale.
Introduciamo una "reazione interna" nello stato verde della strada principale che attiva l'allarme se viene ricevuto un LocalRoadTrafficEvent, eventualmente con NewGreen come stato di protezione.
Una "reazione di ingresso" nello stato LocalRoadEventOK che invia un segnale se l'allarme viene attivato all'ingresso nello stato (un segnale è un evento speciale che la macchina a stati stessa può inviare).
Una transizione al giallo che attiva il segnale e avvia un breve intervallo di temporizzazione.
Esistono altri modi per affrontare questo problema, ma richiedono una sintassi UML più complessa, troppo estesa per essere trattata qui.
Le macchine a stati software differiscono dalle loro controparti hardware in quanto la macchina a stati software deve rilevare e reagire agli eventi nell'ambiente hardware. Ciò significa che il modello computazionale delle macchine a stati software si basa su un ciclo di rilevamento-evento-reazione all'evento composto da passaggi discreti, mentre una macchina a stati hardware può reagire "simultaneamente" a un segnale modificato su un determinato pin. (Sebbene la variazione effettiva delle porte logiche sia, ovviamente, un'attività discreta a livello di bit.) Ad esempio, un insieme di segnali hardware può essere combinato in una porta logica per produrre un evento quando una determinata combinazione di segnali è presente sul lato di ingresso. In un ambiente software, è necessario lasciare che siano gli interrupt e i driver di dispositivo a eseguire la combinazione, oppure lasciare che lo faccia la macchina a stati. (A meno che non si abbia il controllo della progettazione hardware.)
Un approccio diverso
Come sottolineato all'inizio, esiste almeno un modo completamente diverso per risolvere lo stesso problema, che prevede la modellazione delle macchine a stati come due regioni parallele all'interno della stessa macchina a stati di alto livello. Questo ha il vantaggio che la soluzione completa può essere vista come un sistema composto da componenti separati e semi-indipendenti. Lo spazio non consente un commento più approfondito, ma è possibile consultarlo online all'indirizzo www.iar.com/p236597/p236597_eng.php
.
La soluzione esatta scelta non è in realtà importante, ma in generale è bene mantenere le cose il più semplici possibile. L'utilizzo di uno strumento di progettazione grafica come IAR visualSTATE per la progettazione di macchine a stati è un modo pratico per elevare il livello di astrazione, poiché un buon strumento fornisce supporto per aspetti quali la generazione di codice, il test e la simulazione e la verifica delle capacità del modello.
Autore: Anders Holmberg, IAR Systems
Maggiori informazioni o un preventivo
