În această lucrare, termenul „mașină de stare finită“ se înțelege un algoritm care poate fi într-unul dintr-un număr mic de state. „Stat“ - este un fel de condiție care definește o relație predeterminată de semnale de intrare și de ieșire și semnalele de intrare și stările ulterioare. cititor inteligent va nota că mașinile de stat descrise în acest articol, ea Mealy. mașină Mealy - este o mașină de stare finită în cazul în care rezultatele sunt funcții ale stării actuale și de intrare, spre deosebire de aparatul Moore în care ieșirile - o funcție numai de stat. În ambele cazuri, starea următoare - este o funcție de starea curentă și semnalul de intrare.
Luați în considerare un exemplu simplu de o mașină de stare finită. Imaginați-vă că trebuie să recunoască secvența „//“ caractere într-un șir de caractere de text. Figura 1 prezintă modul în care acest lucru se realizează cu ajutorul unui automat finit. Primul slash aspect nu transmite la ieșire, dar conduce la faptul că tranzițiile mașinii la al doilea stat. Dacă în a doua mașină de stat nu este un slash, acesta este returnat în primul rând, așa cum trebuie să aveți 2 slash-uri consecutive. Dacă a doua bară oblică este găsit, aparatul emite un semnal „gata“.
Vă recomandăm să utilizați următoarea abordare a dezvoltării finite automate:
- Aflați ce are nevoie clientul.
- Asigurați-o diagramă de tranziție de stare
- Coda „scheletul“ al unei mașini de stat fără a detalia operațiunile de tranziție.
- Asigurați-vă că tranzițiile funcționează corect.
- pasajele înguste detalii.
Să considerăm un exemplu mai interesantă a unei mașini de stare finită - un program care controlează retragerea și extinderea trenul de aterizare. Deși majoritatea aeronavei, această procedură se realizează printr-un mecanism de control electro-hidraulic (pur și simplu pentru că nu există nici un computer de bord), în unele cazuri, cum ar fi vehiculele aeriene fără pilot, este necesar să se utilizeze software-ul de control.
Pentru a începe, să se ocupe cu echipamentul. unelte de aterizare a aeronavei este format dintr-un picior din față, trenul de aterizare principal stânga și trenul de aterizare principal dreapta. Acestea sunt conduse de un mecanism hidraulic. O pompă cu motor hidraulic aplică o presiune de acționare de putere. pompa este activată sau dezactivată prin intermediul software-ului. Calculatorul reglează poziția direcției de supapă - „în jos“ sau „sus“ pentru a permite presiunii de a ridica sau coborî șasiul. Fiecare tren de aterizare are un comutator de limitare: una dintre ele este închis, în cazul în care șasiul este ridicat, celălalt - în cazul în care este înregistrată în poziția „în jos“. Pentru a stabili dacă aeronava la sol, limitatorul de pe piciorul suport din față este închis în cazul în care greutatea aeronavei este pe piciorul din față. mijloacele de comandă pilot constau brat superior / inferior și șasiul trei bulbi (una pentru fiecare picior), care poate fi oprit, lumina verde (poziția „în jos“) sau lumină roșie (poziția „tranziție“).
Și acum pentru dezvoltarea unei mașini de stare finită. Primul și cel mai dificil pas - este de a înțelege așteptările reale ale clienților. Unul dintre avantajele unei mașini de stare finită este că ea forțează programatorul să se gândească prin toate cazurile posibile și, în consecință, de a primi de la client toate informațiile necesare. De ce cred că aceasta este cea mai grea etapă? Și de câte ori vă dau o descriere a problemei ca aceasta: Nu împingeți șasiu, în cazul în care aeronava este la sol.
Desigur, acest lucru este important, dar clientul consideră că toate aceste capete. Dar ceea ce despre alte cazuri? Este suficient pentru a trage șasiu într-un moment în care aeronava părăsește sol? Ce se întâmplă dacă avionul va sări la movilă de pe pista? Ce se întâmplă dacă pilotul va pune maneta schimbătorului de viteze la „sus“, la momentul de parcare și, în consecință, începe să decoleze? Fie că, în acest caz, să mizeze mai mult?
Unul dintre avantajele de gândire în ceea ce privește o mașină de stare finită este că se poate desena rapid o diagramă de tranziție de stare de pe placa de proiecție, direct în fața clientului, iar prin procesul cu el. tranziție de stare acceptate este o denumire de „eveniment care a cauzat tranziția“ / „semnal de ieșire, ca urmare a tranziției“. Dacă vom dezvolta doar ceea ce a solicitat inițial clientul ( „Nu împingeți șasiu, în cazul în care aeronava este la sol“), atunci vom obține aparatul prezentat în Figura 2.
La elaborarea diagrama de tranziție de stare (sau orice alt algoritm), rețineți următoarele:
- Calculatoarele sunt foarte rapid în comparație cu echipamente mecanice
- inginer mecanic, care explică ce trebuie făcut, probabil, nu știe despre calculatoare și algoritmii de tot pe care le cunoașteți. Și acest lucru este, de asemenea, un lucru pozitiv, altfel nu ar fi necesar!
- Cum va programul, dacă încalci un piese mecanice sau electrice?
mașină de stat, în funcție de ceea ce este într-adevăr nevoie la client, este prezentat în figura 3. Aici, dorim să împiedice retragerea de aterizare de viteze, atâta timp cât acesta cu siguranță nu va fi în aer. În acest scop, după deschiderea mașinii comutator touchdown pentru câteva secunde este în așteptare. De asemenea, dorim să răspundă la marginea în creștere a pârghiei pilot și nu la nivelul la care se va evita probleme dacă cineva impulsionează maneta, în timp ce aeronava se află în parcare. Retragerea sau extinderea șasiului durează câteva secunde, iar noi trebuie să fim pregătiți pentru situația în care pilotul în cursul acestei operații se va răzgândi și deplasați maneta în direcția opusă. De asemenea, rețineți că în cazul în care avionul va ateriza din nou, până când vom fi în stare să «În așteptare pentru decolare», timer-ul va reporni și retragerea șasiului va avea loc numai în cazul în care aeronava va fi în aer timp de 2 secunde.
Punerea în aplicare a unei mașini de stare finită
Listarea 1 - aceasta este realizarea mea a mașinii de stare finită se arată în figura 3. Să discutăm câteva dintre detaliile codului.
În primul rând, este posibil să observați că funcționalitatea fiecărui stat este implementată funcția separată C. Desigur, ai putea pune în aplicare o mașină utilizând instrucțiunea de comutare cu un caz `th separat pentru fiecare stat, dar poate duce la funcții foarte lungi (10-20 de linii de cod la starea 1 pentru fiecare din cele 20-30 de state). Aceasta poate duce, de asemenea, la erori dacă modificați codul în etapele finale de testare. Poate că n-ați uitat declarația pauză la sfârșitul case`a, dar pentru mine au existat astfel de cazuri. un cod de stare nu va cădea în alt cod dacă pentru fiecare stat va avea o funcție separată.
Pentru a evita utilizarea comutatorului declarației, folosesc o serie de indicii pentru funcțiile statelor, iar variabila utilizată ca un index de matrice, declara un tip enum.
Un alt lucru evident - la acest punct, codul nu joacă un rol special. El doar se mută de la un stat la altul. Aceasta este o importantă etapă intermediară și nu ar trebui să fie ignorate. Apropo, ar fi frumos pentru a adăuga o declarație de imprimare, semnat între directivele conditionale de compilare (# ifdef DEBUG. # Endif), care ar afișa starea curentă și valorile semnalelor de intrare.
Cheia succesului constă în codul care determină tranziția statelor, și anume, Se constată că nu a fost introducerea de date.
În cazul în care codul este trecut corect prin intermediul statului, pasul următor devine scris „umplutura“ a codului, care este exact ceea ce face ca semnalul de ieșire. Amintiți-vă că fiecare pasaj are un semnal de intrare (un eveniment care a determinat-o) și de ieșire (dispozitivul hardware IO, la fel ca în exemplul nostru). De multe ori, este util să se stabilească un tabel de tranziție.
În stare de tranziție tabel un rând la o tranziție de stare.
Atunci când codifică o mașină de stat încerca să salveze puterea lui - o corelare accentuată între cerințele clientului și codul. Va trebui să se ascundă detalii despre echipamentul la un alt nivel de funcții, de exemplu, la un cod de mașină de stat cât mai mult posibil ca o diagramă de tranziție de masă și starea de tranziție de stat. O astfel de simetrie ajută la prevenirea erorilor, și explică de ce mașinile de stat sunt o parte importantă din arsenalul de sisteme embedded programator. Desigur, ai putea obține același efect prin stabilirea steaguri și un set infinit de imbricate în cazul în care, dar va fi foarte dificil să țină evidența codului și se compară cu dorințele clientului.
cod Fragment din Listarea 2 se extinde funcția RaisingGear (). Rețineți că codul pentru funcția RaisingGear () tinde să reflecte imaginea 2 rânduri ale tabelului de tranziție pentru stare Ridicarea Gear.
void RaisingGear (void)
/ * După ce sunt ridicate toate switch-uri, du-te la starea „a ridicat șasiu * /
if ((nosegear_is_up == MADE) (Leftgear_is_up == MADE) (Rtgear_is_up == MADE))
Amintiți-vă că evita statele ascunse. Latența se produce atunci când din cauza lenei, încercați să adăugați substate condiționată în loc să adăugați condiția particulară. De exemplu, în cazul în care codul procesează același semnal de intrare în moduri diferite (de exemplu, inițiază diferite tranziții de stat), în funcție de modul, acesta este un stat ascuns. În acest caz, aș fi crezut, nu dacă este sau nu să rupă această stare pentru doi? Utilizarea stărilor ascunse anulează avantajul de a folosi o mașină de stat.
Ca un exercițiu, puteți extinde aparatul de stat, pe care tocmai l-am considerat, adăugând la ciclul timeout sau retrage pentru a extinde trenul de aterizare, deoarece inginer mecanic nu vrea să pompă hidraulică a lucrat pentru mai mult de 60 de secunde. În cazul în care ciclul este finalizat, pilotul ar trebui să fie avertizați prin trecerea lumina verde și roșu, și el ar trebui să poată să se deplaseze din nou maneta pentru a încerca din nou. Puteți cere, de asemenea, un inginer mecanic ipotetic, ca efectul asupra pompei inversă traseu în timpul funcționării, pentru că se întâmplă în 2 atunci când pilotul se răzgândește. Desigur, mecanicul vă că un negativ va spune. Atunci cum ați schimba aparatul de stat pentru a opri pompa repede la schimbarea de direcție?
Frumusetea codificării sub forma unor algoritmi finite automate este faptul că planul de testare este aproape să se scrie în mod automat. Tot ce trebuie să faceți - este de a trece prin fiecare tranziție de stare. Eu de obicei, o fac cu un marker în mână, lovind săgeata de pe diagrama de tranziție de stat pe măsură ce trec cu succes testul. Aceasta este o modalitate buna de a evita „stările ascunse“ - în testele care le lipsesc mai des decât condiția specifică.
Acest lucru necesită răbdare considerabile și o mulțime de cafea, deoarece chiar și o mașină de stat de dimensiuni medii poate avea până la 100 de tranziții diferite. De altfel, numărul de clicuri - aceasta este o modalitate foarte bună de a măsura complexitatea sistemului. Acesta din urmă este determinată de cerințele clientului, iar aparatul de stat face ca volumul aparent de testare. Cu abordare mai puțin organizată, cantitatea de testare necesară poate fi la fel de impresionant, dar o faci pur si simplu nu va învăța.
Foarte convenabil de a utiliza în declarațiile de cod de imprimare care de ieșire starea curentă, valorile semnalelor de intrare și ieșire. Acest lucru vă permite să observe cu ușurință ceva care exprimă „programul de testare Regula de aur“: verifică dacă programul realizează planul său, precum și ceea ce nu face nimic în plus. Cu alte cuvinte, dacă veți obține numai rezultatele pe care le așteptați, și ce altceva se întâmplă în afară de asta? Fie că este „jenant“ de tranziție de stat, de exemplu, afirmă că o șansă să meargă de, un singur ciclu de repetare? Schimbarea dacă semnalele de ieșire atunci când nu vă așteptați? În mod ideal, semnalele de ieșire ale printfs dvs. au mult pentru a reaminti tabelul de tranziție de stare.
În cele din urmă - și acest lucru se aplică la orice firmware, nu doar software-ul bazat pe automate finite - Fiți foarte atenți atunci când porniți mai întâi software-ul pe hardware reale. Este foarte ușor de a face o greșeală cu polaritatea semnalului - „Oh, m-am gândit că“ 1 „înseamnă a ridica șasiu, și“ 0 „- pentru al coborî.“ În multe cazuri, echipamentul meu asistent este folosit temporar „comutator de pui“ pentru protecția componentelor valoroase, în timp ce el nu era sigur că software-ul meu se mișcă obiectele în direcția cea bună.
Atunci când sunt făcute toate cerințele clientului, pot rula o mașină de stare de această complexitate în câteva zile. Aproape întotdeauna mașinile fac ceea ce vreau. Cel mai dificil lucru - este, desigur, pentru a înțelege exact ce vrea clientul și asigurați-vă că clientul însuși știe ce vrea. Aceasta din urmă ia mult mai mult timp!
Martin Gomez "Machine Punerea în aplicare de stat Embedded". traducere liberă - ChipEnable.Ru
Ei bine, de exemplu, nu atât de prost, dar cel puțin sistemul dvuhzadachnuyu PB (măsurarea conectate s), cu utilizarea de întreruperi. Și totuși, și cum să facă pentru a elimina factorul uman atunci când membrii listarea typedef și numele de funcții în matrice de indicii, pentru că ar trebui să fie strict sincronizate, iar dacă acestea sunt 100 de bucăți și adăugate la momente diferite, puteți la întâmplare nechayno perturba ordinea lor. De fiecare dată pentru a verifica ce?
După cum spune proverbul: „Ai de gând să încerce să mulțumească pe toată lumea, nu va multumi pe nimeni“
După cum spune proverbul: „Ai de gând să încerce să mulțumească pe toată lumea, nu va multumi pe nimeni“
Pash, totul este în regulă, este mai bine să aibă un fir de pe forum, și există un exemplu mai simplu / mai complex, dacă este necesar
Multumesc pentru articol
Ei bine, de exemplu, nu atât de prost, dar cel puțin sistem PB dvuhzadachnuyu (conexiune de măsurare) folosind întrerupe. Și totuși, și cum să facă pentru a elimina factorul uman atunci când membrii listarea typedef și numele de funcții în matrice de indicii, pentru că ar trebui să fie strict sincronizate, iar dacă acestea sunt 100 de bucăți și adăugate la momente diferite, puteți la întâmplare nechayno perturba ordinea lor. De fiecare dată pentru a verifica ce?
Vă mulțumesc foarte mult pentru articol!
Apropo, pentru a se potrivi enum constant cu matrice de indicii funcții, în opinia mea, este convenabil să se utilizeze un preprocesor, de exemplu:
cod:
#define FunctionItem (id, fun) id
typedef enum #include "fi.h"
> State_Type;
#undef FunctionItem
#define FunctionItem (id, fun) distracție
void (* state_table []) () = #include "fi.h"
>;
În cazul în care fi.h acest fișier:
cod:
FunctionItem (GEAR_DOWN = 0, GearDown),
FunctionItem (WTG_FOR_TKOFF, WtgForTakeoff),
FunctionItem (RAISING_GEAR, RaisingGear),
FunctionItem (GEAR_UP, GearUp),
FunctionItem (LOWERING_GEAR, LoweringGear)
Notă absența unei virgule în ultimul rând