Danes bomo govorili o strojnicah, vendar ne o tistih, ki jih imajo vojaki v rokah Ruska vojska. Govorili bomo o tako zanimivem slogu programiranja mikrokontrolerjev, kot je avtomatsko programiranje. Natančneje, to sploh ni slog programiranja, ampak celoten koncept, zahvaljujoč kateremu lahko programer mikrokrmilnika močno olajša svoje življenje. Zahvaljujoč temu se številne naloge, ki so predstavljene programerju, rešijo veliko lažje in preprosteje, kar programerja razbremeni glavobolov. Mimogrede, samodejno programiranje se pogosto imenuje SWITCH tehnologija.

Rad bi omenil, da je bil navdih za pisanje te objave serija člankov o tehnologiji SWITCH Vladimir Tatarčevski. Serija člankov se imenuje “Uporaba tehnologije SWITCH pri razvoju aplikacijske programske opreme za mikrokrmilnike.” Zato bom v tem članku poskušal podati predvsem primer delujoče kode in njen opis.

Mimogrede, načrtoval sem serijo člankov, posvečenih programiranju, v katerih bom podrobno obravnaval tehnike programiranja mikrokrmilnikov AVR, Ne spreglejte…. No, pa gremo!

Program dosledno izvaja ukaze, ki jih dodeli programer. Za redno računalniški program Popolnoma normalno je, da je program zaključil z izvajanjem in ustavil izvajanje, medtem ko rezultate svojega dela prikazuje na monitorju.

Program mikrokrmilnika ne more preprosto zaključiti svojega izvajanja. Samo predstavljajte si, da ste vklopili predvajalnik ali magnetofon. Pritisnili ste gumb za vklop, izbrali želeno skladbo in uživali v glasbi. Ko pa je glasba prenehala vibrirati po bobniču v ušesu, je predvajalnik zmrznil in se nikakor ni odzval na pritiskanje gumbov, še manj pa na vaš ples s tamburino.

Kaj je narobe s tem? Vse je v redu – krmilnik, tisti v globinah vašega predvajalnika, je enostavno končal z izvajanjem svojega programa. Vidite, to je nekako neprijetno.

Od tod torej sklepamo, da se program za mikrokontroler enostavno ne sme ustaviti. V bistvu bi moralo biti neskončni cikel- samo v tem primeru bi naš predvajalnik deloval pravilno. Nato vam bom pokazal, kateri dizajni obstajajo. programsko kodo pri mikrokontrolerjih to niti niso dizajni, ampak neki stili programiranja.

Slogi programiranja.

"Slogi programiranja" zveni nekako nerazumljivo, a dobro. Kaj hočem s tem povedati? Predstavljajmo si, da človek še nikoli ni programiral, se pravi, da je totalni noob.

Ta oseba je prebrala veliko knjig o programiranju in preučila vse osnovne konstrukcije jezika.Podatke je zbiral po koščkih, saj je zdaj dostop do informacij neomejen. To je vse lepo in prav, toda kako bodo videti njegovi prvi programi? Zdi se mi, da ne bo filozofiral, ampak bo šel po poti od preprostega k zapletenemu.

Ti slogi so torej koraki, ki vodijo od preproste ravni do bolj zapletene, a hkrati bolj učinkovite.

Sprva nisem razmišljal o nobenem oblikovne značilnosti programi. Preprosto sem oblikoval logiko programa – narisal diagram poteka in napisal kodo. Zato sem kar naprej naletel na grablje. Ampak to je bilo prvič, ko nisem skrbel in sem uporabil slog "preproste zanke", nato sem začel uporabljati prekinitve, potem so bili avtomati in gremo ...

1. Preprosto zankanje. V tem primeru se program vrti brez trikov, kar ima svoje prednosti in slabosti. Edina prednost je preprostost pristopa, ni vam treba izumljati zvitih modelov, pišete, kot mislite (postopoma si kopljete grob).

Void main(void) ( initial_AL(); //inicializacija zunanjih naprav while(1) ( Leds_BLINK(); //funkcija LED utripalnik signal_on(); //funkcija za vklop signala signal_off(); //funkcija za izklop signala l=button(); //spremenljivka, odgovorna za pritiskanje gumbov switch(l) //Odvisno od vrednosti spremenljivke se izvede eno ali drugo dejanje ( primer 1: ( Deistvie1(); //Namesto funkcije je lahko pogojni operator Deistvie2 (); //ali več drugih vej zamenja primer Deistvie3(); Deistvie4(); Deistvie5(); ); primer 2: ( Deistvie6(); Deistvie7(); Deistvie8(); Deistvie9(); Deistvie10(); ) ; . . . . . ) ) )

Delovna točka programa se premika po vrsti. V tem primeru se vsa dejanja, pogoji in cikli izvajajo zaporedno. Koda se začne upočasnjevati, vstaviti morate veliko dodatnih pogojev in s tem otežiti zaznavanje.

Vse to zelo zmede program, zaradi česar je koda preplet pogojev. Posledično tej kodi ni mogoče ničesar dodati ali odvzeti; postane kot monoliten kos. Seveda, ko obseg ni velik, je kodo mogoče spremeniti, a dlje ko gre, težje postane.

S tem pristopom sem napisal več programov; niso bili veliki in precej funkcionalni, vendar je jasnost pustila veliko želenega. Da bi dodal kakšen nov pogoj, sem moral prebrskati celotno kodo, ker je bilo vse povezano. To je povzročilo veliko napak in preglavic. Prevajalnik je preklinjal, kolikor je mogel, razhroščevanje takšnega programa se je spremenilo v pekel.

2. Zanka + prekinitve.

Neskončni cikel zaviranja lahko delno razrešite z uporabo prekinitev. Prekinitve pomagajo izstopiti iz začaranega kroga, pomagajo, da ne zamudite pomembnega dogodka in dodajajo dodatne funkcije (prekinitve časovnikov, zunanje prekinitve).

Recimo, da lahko uporabite prekinitev za obdelavo gumbov ali sledenje pomembnemu dogodku. Posledično postane program bolj vizualen, a nič manj zmeden.

Na žalost vas prekinitev ne bo rešila pred zmešnjavo, v katero se program spremeni. Nemogoče je razdeliti na dele, kar je ena sama celota.

3. Samodejno programiranje.

Tukaj smo prišli do glavna tema tega člena. Programiranje v končnih avtomatih odpravlja pomanjkljivosti, ki so značilne za prva dva primera. Program postane enostavnejši in enostaven za spreminjanje.

Program, napisan v avtomatskem slogu, je podoben stikalu, ki se glede na pogoje preklopi v eno ali drugo stanje. Število stanj je programerju na začetku znano.

Grobo rečeno, je kot stikalo za luč. Obstajata dve stanju vklopa in izklopa ter dva stanja vklopa in izklopa. No, najprej najprej.

Implementacija večopravilnosti v stikalni tehnologiji.

Mikrokrmilnik je sposoben nadzorovati obremenitev, utripati LED diode, slediti pritiskom tipk in še veliko več. Toda kako narediti vse to hkrati? Obstaja veliko rešitev za rešitev te težave. Najenostavnejši od njih, ki sem ga že omenil, je uporaba prekinitev.

Med delovanjem programa, ko pride do prekinitve, se krmilnik odvrne od izvajanja programske kode in za kratek čas izvede drug del programa, za katerega je odgovorna prekinitev. Prekinitev bo delovala, nato pa se bo delovna točka programa nadaljevala od točke, kjer je bil regulator s prekinitvijo prekinjen (beseda sama pove, da je regulator prekinjen).

Drug način izvajanja večopravilnosti je uporaba operacijski sistemi. Da, res so se že začeli pojavljati majhni operacijski sistemi, ki jih je mogoče uporabiti na krmilniku z nizko porabo energije. Toda pogosto se ta metoda izkaže za nekoliko odveč. Konec koncev, zakaj bi zapravljali vire krmilnika z nepotrebnim delom, ko pa lahko to opravite z majhnimi stroški.

V programih, napisanih s tehnologijo stikala, je podobna "iluzija" večopravilnosti dosežena zahvaljujoč sistemu sporočanja. Napisal sem "iluzija", ker je to dejansko tako, ker program fizično ne more izvajati različnih delov kode hkrati. O sistemu sporočanja bom govoril malo naprej.

Sistem sporočanja.

S sistemom za sporočanje lahko razrešite številne procese in ustvarite iluzijo večopravilnosti.

Recimo, da potrebujemo program, v katerem se LED preklopi. Tukaj imamo dva stroja, recimo jima LEDON - stroj odgovoren za vklop LED in LEDOFF stroj - stroj odgovoren za izklop LED.

Vsak od strojev ima dve stanji, to pomeni, da je stroj lahko v aktivnem stanju ali v neaktivnem stanju, kot je stikalo vklopljeno ali izklopljeno.

Ko je en stroj aktiviran, LED sveti, ko je aktiviran drugi, LED ugasne. Poglejmo majhen primer:

Int main(void) ( INIT_PEREF(); //inicializacija perifernih naprav (LED) InitGTimers(); //inicializacija časovnikov InitMessages(); //inicializacija mehanizma za obdelavo sporočil InitLEDON(); //inicializacija stroja LEDON InitLEDOFF(); // inicializacija LEDOFF avtomata SendMessage(MSG_LEDON_ACTIVATE); //aktivacija LEDON sei(); //Omogoči prekinitve //Glavna zanka programa while(1) ( ProcessLEDON(); //iteracija LEDON avtomat ProcessLEDOFF(); //iteracija LEDOFF avtomata ProcessMessages (); //obdelava sporočila ); )

V vrsticah 3-7 se pojavljajo različne inicializacije, zato nas to sedaj ne zanima posebej. Toda potem se zgodi naslednje: preden začnemo glavno zanko (while(1)), pošljemo stroju sporočilo

Pošlji sporočilo (MSG_LEDON_ACTIVATE)

odgovoren za osvetlitev LED. Brez tega majhnega koraka naš organ ne bo deloval. Nato glavno delo opravi glavna neskončna zanka while.

Majhna digresija:

Sporočilo ima tri stanja. Stanje sporočila je namreč lahko neaktivno, nastavljeno vendar neaktivno in aktivno stanje.

Izkazalo se je, da je bilo sporočilo sprva neaktivno, ko smo sporočilo poslali, je prejelo status "nameščeno, vendar neaktivno". In to nam daje naslednje. Ko se program izvaja zaporedno, naprava LEDON ne prejme sporočila. Pride do nedejavne iteracije stroja LEDON, v kateri sporočila preprosto ni mogoče prejeti. Ker ima sporočilo status »nameščeno, vendar neaktivno«, program nadaljuje z izvajanjem.

Ko vsi stroji mirujejo, pride na vrsto funkcija ProcessMessages(). Ta funkcija je vedno postavljena na konec zanke, potem ko so končane vse ponovitve avtomatov. Funkcija ProcessMessages() preprosto premakne sporočilo iz stanja "nastavljeno, vendar neaktivno" v stanje "aktivno".

Ko neskončna zanka zaključi drugi krog, postane slika popolnoma drugačna. Ponovitev stroja ProcessLEDON ne bo več v mirovanju. Naprava bo lahko prejela sporočilo, prešla v osvetljeno stanje in tudi poslala sporočilo. Naslovljeno bo na napravo LEDOFF in življenski krog sporočila bodo ponovljena.

Opozoriti želim, da so sporočila, ki imajo stanje »aktivno«, uničena, ko naletijo na funkcijo ProcessMessages. Zato lahko sporočilo prejme le en stroj. Obstaja še ena vrsta sporočil - oddajna sporočila, vendar jih ne bom upošteval; dobro so obravnavana tudi v člankih Tatarčevskega.

Časovniki

S pomočjo pravilne organizacije izmenjave sporočil lahko nadzorujemo vrstni red delovanja končnih avtomatov, ne moremo pa tega storiti zgolj s sporočili.

Verjetno ste opazili, da prejšnji fragment programa, naveden kot primer, ne bo deloval, kot je predvideno. Stroji bodo izmenjevali sporočila, LED diode se bodo zamenjale, vendar tega ne bomo videli. Videli bomo le slabo osvetljeno LED.

To je zato, ker nismo razmislili, kako pravilno obravnavati zamude. Navsezadnje ni dovolj, da LED diode izmenično prižigamo in ugašamo, LED se mora v vsakem stanju zadržati, recimo sekundo.

Algoritem bo naslednji:

Lahko kliknete za povečavo

Na tem blokovnem diagramu sem pozabil dodati, da ko se časovnik odkljuka, se seveda izvede dejanje - prižge ali ugasne LED.

1. V stanje vstopimo s sprejemom sporočila.

2. Preverimo odčitke časovnika/števca, če je štetje doseženo, potem izvedemo dejanje, drugače pa si preprosto pošljemo sporočilo.

3. Pošljite sporočilo naslednji napravi.

4. Izhod

Pri naslednjem vnosu se vse ponovi.

Program na tehnologiji SWITCH. Trije koraki.

Napišimo program v končnih avtomatih in za to bomo morali narediti le tri preprosti koraki. Program bo preprost, vendar je vredno začeti s preprostimi stvarmi. Ustrezal nam bo program s preklopno LED. To je zelo dober primer, torej ne izumljajmo ničesar novega.

Program bom sestavil v jeziku SI, vendar to sploh ne pomeni, da morate v končnih avtomatih pisati samo v C, povsem mogoče je uporabiti kateri koli drug programski jezik.

Naš program bo modularen in bo zato razdeljen na več datotek. Imeli bomo naslednje module:

• Modul glavne programske zanke vsebuje datoteke leds_blink.c, HAL.c, HAL.h
• Modul časovnika vsebuje datoteke timers.c, timers.h
• Modul za obdelavo sporočil vsebuje datoteke messages.c, messages.h
  
• Strojni modul 1 vsebuje datoteke ledon.c, ledon.h
• Strojni modul 2 vsebuje datoteke ledoff.c, ledoff .h

Korak 1.

Ustvarimo projekt in vanj takoj povežemo datoteke naših statičnih modulov: timers.c, timers.h, messages.c, messages.h.

Datoteka leds_blink.c modula glavne programske zanke.

#include "hal.h" #include "messages.h" //modul za obdelavo sporočil #include "timers.h" //modul timers //Prekinitve časovnika //############## # ##################################################### ############################## ISR(TIMER0_OVF_vect) // skok po prekinitvenem vektorju (prekoračitev števca T0) ( ProcessTimers(); //Upravljalnik prekinitve časovnika) //############################################ # ######################################## int main(void) ( INIT_PEREF(); //inicializacija perifernih naprav (LED) InitGTimers(); //inicializacija časovnikov InitMessages(); //inicializacija mehanizma za obdelavo sporočil InitLEDON(); //inicializacija stroja LEDON InitLEDOFF (); StartGTimer( TIMER_SEK); //Zaženi časovnik SendMessage(MSG_LEDON_ACTIVATE); //aktiviraj avtomat FSM1 sei(); //Omogoči prekinitve //Glavna zanka programa while(1) ( ProcessLEDON(); // ponovitev avtomata LEDON ProcessLEDOFF(); ProcessMessages( ); //obdelava sporočila ); )

Prve vrstice povezujejo preostale module z glavnim programom. Tukaj vidimo, da sta modul časovnika in modul za obdelavo sporočil povezana. Naslednji v besedilu programa je prekinitveni vektor prelivanja.

Za glavni program lahko rečemo, da se začne z vrstico int main (void). In začne se z inicializacijo vsega. Tukaj inicializiramo periferijo, to je, nastavimo začetne vrednosti za vhodno/izhodna vrata primerjalnika in vse ostale vsebine krmilnika. Vse to naredi funkcija INIT_PEREF; izvajamo jo tukaj, čeprav je njeno glavno telo v datoteki hal.c.

Nato vidimo inicializacijo časovnikov, modul za obdelavo sporočil in inicializacijo avtomatov. Tukaj se tudi te funkcije preprosto zaženejo, čeprav so same funkcije zapisane v datotekah svojih modulov. Poglejte, kako priročno je. Glavno besedilo programa ostaja lahko berljivo in ni natrpano z odvečno kodo, ki vam bo lomila noge.

Glavne inicializacije so končane, zdaj moramo zagnati glavno zanko. Da bi to naredili, pošljemo začetno sporočilo in tudi navijemo uro - zaženemo časovnik.

StartGTimer(TIMER_SEK); //Zaženi časovnik SendMessage(MSG_LEDON_ACTIVATE); //aktiviraj stroj FSM1

In glavni cikel je, kot sem že rekel, videti zelo preprost. Zapišemo funkcije vseh strojev, preprosto jih zapišemo v stolpec, ne da bi upoštevali vrstni red. Te funkcije so upravljalniki avtomatov in se nahajajo v modulih avtomatov. To avtomatsko piramido dopolnjuje funkcija modula za obdelavo sporočil. Seveda sem vam to povedal že prej, ko smo se ukvarjali s sistemom pošiljanja sporočil. Zdaj lahko vidite, kako izgledata še dve datoteki modula glavnega cikla programa

Hal.h je datoteka glave modula glavne zanke programa.

#ifndef HAL_h #define HAL_h #include #vključi //Standardna knjižnica vključno s prekinitvami #define LED1 0 #define LED2 1 #define LED3 2 #define LED4 3 #define Komparator ACSR //comparator #define ViklKomparator 1<

Kot ste morda opazili, ta datoteka sama po sebi ne vsebuje niti ene vrstice izvršljive kode - vse so zamenjave makrov in povezovalne knjižnice. Če imate to datoteko, si preprosto olajšate življenje, izboljša vidljivost.

Toda datoteka Hal.c je že izvršljiva datoteka in kot sem že omenil, vsebuje različne inicializacije perifernih naprav.

#include "hal.h" void INIT_PEREF(void) ( //Inicializacija V/I vrat //############################ ### ################################################# ### ##### Komparator = ViklKomparator; //inicializacija primerjalnika - izklop DDRD = 1<

No, pokazal sem modul glavnega cikla programa. Zdaj moramo narediti še zadnji korak, napisati moramo module samih avtomatov.

3. korak

Vse, kar moramo storiti, je napisati module za končne avtomate, v našem primeru stroj LEDON in stroj LEDOFF. Za začetek bom podal besedilo programa za avtomatsko napravo za osvetlitev LED, datoteka ledon.c.

//datoteka ledon.c #include "ledon.h" #include "timers.h" #include "messages.h" unsigned char ledon_state; //stanje spremenljivke void InitLEDON(void) ( ledon_state=0; //tukaj lahko inicializirate druge //samodejne spremenljivke, če so na voljo) void ProcessLEDON(void) ( switch(ledon_state) ( primer 0: //neaktivno stanje if(GetMessage ( MSG_LEDON_ACTIVATE)) //če je sporočilo, bo sprejeto ( //in časovnik bo preverjen if(GetGTimer(TIMER_SEK)==one_sek) //če je časovnik odštel 1 sekundo, nato izvedite ( StopGTimer(TIMER_SEK ); PORTD = 1<

Tukaj so v prvih vrsticah, kot vedno, povezane knjižnice in deklarirane spremenljivke. Sledijo funkcije, ki smo jih že spoznali. To je inicializacijska funkcija avtomata InitLEDON in funkcija samega upravljalnika avtomata ProcessLEDON.

V telesu upravljalnika so funkcije iz časovnega modula in sporočilnega modula že obdelane. In logika samega stroja temelji na zasnovi stikalnega ohišja. In tukaj lahko opazite, da je krmilnik stroja mogoče tudi zakomplicirati z dodajanjem več stikal za velike in male črke.

Datoteka glave za stroj bo še enostavnejša:

//datoteka fsm1 #ifndef LEDON_h #define LEDON_h #include "hal.h" void InitLEDON(void); void ProcessLEDON(void); #endif

Sem vključimo povezovalno datoteko hal.h in navedemo tudi prototipe funkcij.

Datoteka, odgovorna za izklop LED, bo videti skoraj enako le v zrcalni sliki, zato je ne bom prikazal tukaj - nerad :)

Vse projektne datoteke lahko prenesete s te povezave ====>>> POVEZAVA.

Samo trije koraki in naš program je dobil končano obliko, kar pomeni, da je moje današnje poslanstvo zaključeno in je čas, da ga zaključim. Zdi se mi, da bodo informacije v tem članku zelo koristne za vas. Toda resnično korist bo prineslo šele, ko boste to znanje uporabili v praksi.

Mimogrede, načrtoval sem številne zanimive projekte, ki bodo še posebej zanimivi, zato se prepričajte naročite se na nove članke . Prav tako nameravam poslati dodatna gradiva, zato se mnogi že naročajo prek glavne strani spletnega mesta. Naročite se lahko tudi tukaj.

No, zdaj imam res vse, zato vam želim veliko sreče, odličnega razpoloženja in se spet vidimo.

Od n/n Vladimir Vasiljev

Teorija avtomatov

Opredelitev stroja in njegove sorte. Tabele in grafi prehodov in izhodov. Podavtomatski stroji. Reducirani avtomatski izrek

Operacije s stroji

Pretvarjanje Mealyjevega stroja v Moorov stroj in Moorovega stroja v Mealyjev stroj. Ekvivalentnost avtomatov. Razlikovanje stanj avtomatov. Minimizacija avtomatov. Sinteza avtomatov. Stroji za prepoznavanje

Avtomatski stroj je sistem mehanizmov in naprav, v katerem so procesi sprejemanja, pretvorbe in prenosa energije, materialov in informacij popolnoma avtomatizirani.Izraz "avtomatski stroj" se uporablja v dveh vidikih:

1) tehnični,

2) matematični.

V matematičnem pristopu je avtomat razumljen kot matematični model tehnične naprave, ki mora imeti vhode, notranja stanja in izhode. Ne bi smelo biti informacij o podrobnostih zgradbe naprave.

V tehničnem pristopu se stroj razume kot zelo resnična naprava, na primer telefonska govorilnica, prodajni avtomat itd. V tem primeru so seveda znane podrobnosti o notranji strukturi naprave.

Poseben in pomemben primer avtomata je digitalni avtomat (DA), v katerem so procesi sprejemanja, pretvorbe, shranjevanja in izdajanja digitalnih informacij popolnoma avtomatizirani.

Z vidika DA signalov je koristno definirati sistem, ki lahko sprejema vhodne signale, pod njihovim vplivom prehaja iz enega stanja v drugega, ga vzdržuje do naslednjega vhodnega signala in proizvaja izhodne signale.

DA velja za končnega, če so končni nizi vhodnih signalov X, stanj S in izhodnih signalov Y. Končni avtomat je lahko povezan z napravo, kot je računalnik. Računalnik predela vhodne vhodne podatke v izhodne podatke (rezultat), vendar ta rezultat ne ustreza samo vhodnim podatkom, temveč tudi trenutnemu stanju računalnika, tj. podatki, ki so shranjeni v računalniškem pomnilniku, na primer rezultati predhodnih izračunov, računski programi.

Delo ciljne publike poteka v avtomatskem času, ki je določen s številom obdobij prejema vhodnih signalov.

Abstraktni avtomat je matematični model diskretne naprave, ki ima en vhodni kanal, ki sprejema zaporedja simbolov nekega jezika, en izhodni kanal, iz katerega se jemljejo zaporedja simbolov nekega drugega jezika, in je v vsakem trenutku v nekem stanju. diskretnega časa. Grafično je abstraktni avtomat predstavljen na sl.

Besede vhodnega jezika lahko predstavimo s simboli množice X=(x 1 ,x 2 ,...x n ), ki jo imenujemo vnosna abeceda, in besede izhodnega jezika so simboli množice Y=(y 1 ,y 2 ,...y p ), ki se imenuje izhodna abeceda. Množica stanj avtomata S=(s 1 ,s 2 ,...s m ) se imenuje abeceda držav.

Koncept stanje stroja se uporablja za opis sistemov, katerih izhodni signali niso odvisni samo od vhodnih signalov v danem trenutku, ampak tudi od neke prejšnje zgodovine, tj. signale, ki so bili prej sprejeti na sistemskih vhodih. Zato se digitalni avtomati nanašajo na zaporedna vezja, ki imajo, kot smo že omenili, pomnilnik. Koncept stanja avtomata ustreza nekemu spominu na preteklost, zato je uvedba tega koncepta omogoča, da se čas izloči kot eksplicitna spremenljivka in da se izhodi izrazijo kot funkcija stanj in vhodov.

Delovanje abstraktnega avtomata je treba obravnavati glede na določene časovne intervale, ker vsak diskretni interval t bo ustrezal njegovemu izhodnemu signalu y(t). Posledično se delovanje stroja obravnava skozi diskretne časovne intervale končnega trajanja. V abstraktni teoriji digitalnih avtomatov se verjame, da vhodni signali delujejo na sinhroni avtomat na začetku vsakega jaz- tisti interval (kvant) časa, ki ga dodeli ustrezni sinhronizacijski impulz (cikel), in sprememba notranjih stanj stroja se pojavi v časovnih intervalih med sosednjimi sinhronizacijskimi impulzi, ko ni vpliva vhodnih signalov.

Koncept "stanja" se uporablja za vzpostavitev funkcionalne odvisnosti simbolov in/ali besed izhodnega jezika, ki jih ustvari stroj, od simbolov in/ali besed vhodnega jezika, ko stroj izvaja dani algoritem. Za vsako stanje avtomata sОS in za vsak simbol xОX v trenutku diskretnega časa [t] se na izhodu naprave generira simbol yОY. Ta odvisnost je določena z izhodno funkcijo avtomata j. Za vsako trenutno stanje avtomata sОS in za vsak simbol xОX v trenutku diskretnega časa [t] preide avtomat v naslednje stanje sОS. To odvisnost določa prehodna funkcija avtomata y. Delovanje avtomata je sestavljeno iz generiranja dveh zaporedij: zaporedja naslednjih stanj avtomata (s 1[ s 2 s 3 ...) in zaporedja izhodnih simbolov (y 1 y 2 y 3 ...), ki se za zaporedje simbolov (x 1 x 2 x 3...) odvijajo v trenutkih diskretnega časa t = 1,2,3,.... V pravokotnih oklepajih navedite trenutke diskretnega časa, ki jih drugače imenujemo takti , v oklepajih - zaporedja znakov abecede X, Y in S.

Torej je matematični model končnega avtomata triosnovna algebra, katere nosilci so tri množice X, Y in S, operacije pa dve funkciji j in y.

V tem članku se izraz »končni avtomat« nanaša na algoritem, ki je lahko v enem od majhnega števila stanj. »Stanje« je določen pogoj, ki definira dano razmerje med vhodnimi in izhodnimi signali ter vhodnimi signali in kasnejšimi stanji. Inteligentni bralec bo takoj opazil, da so končni avtomati, opisani v tem članku, Mealyjevi stroji. Mealyjev stroj je končni avtomat, kjer so izhodi funkcije trenutnega stanja in vhodnega signala, v nasprotju z Mooreovim strojem, kjer so izhodi samo funkcije stanja. V obeh primerih je naslednje stanje funkcija trenutnega stanja in vhodnega signala.

Poglejmo primer preprostega končnega avtomata. Predstavljajte si, da morate v besedilnem nizu prepoznati zaporedje znakov “//”. Slika 1 prikazuje, kako se to izvede z uporabo državnega avtomata. Prvi pojav poševnice ne povzroči izhodnega signala, ampak povzroči, da naprava preide v drugo stanje. Če v drugem stanju stroj ne najde poševnice, se vrne v prvo, saj zahteva prisotnost 2 poševnic v vrsti. Če je najdena druga poševnica, stroj izda signal "pripravljen".

Ugotovite, kaj stranka potrebuje.

Ustvarite diagram prehoda stanja

Kodirajte "okostje" državnega stroja brez podrobnosti o operacijah veje.

Prepričajte se, da prehodi delujejo pravilno.

Bodite natančni glede podrobnosti prehoda.

Opravite test.

Primer državnega stroja

Poglejmo si bolj zanimiv primer državnega stroja – programa, ki nadzoruje umik in izteg podvozja letala. Čeprav večina letal izvaja ta postopek z uporabo elektrohidravličnega krmilnega mehanizma (preprosto zato, ker na krovu ni računalnika), je v nekaterih primerih, na primer pri brezpilotnih letalih, vredno uporabiti programsko krmiljenje.

Najprej si oglejmo opremo. Podvozje letala je sestavljeno iz nosnega kolesa, glavnega levega podvozja in glavnega desnega podvozja. Poganja jih hidravlični mehanizem. Električno gnana hidravlična črpalka dovaja tlak v pogon. S programsko opremo se črpalka vklopi ali izklopi. Računalnik prilagodi položaj usmerjevalnega ventila - "dol" ali "gor" -, da omogoči pritisk za dviganje ali spuščanje podvozja. Vsaka od opornikov šasije ima končno stikalo: ena od njih se zapre, če je šasija dvignjena, druga - če je zaklenjena v spodnjem položaju. Če želite ugotoviti, ali je letalo na tleh, se končno stikalo na oporniku nosnega zobnika zapre, ko je teža letala na nosnem zobniku. Pilotove krmilne naprave so sestavljene iz zgornje/spodnje roke podvozja in treh lučk (ena za vsako nogo), ki jih je mogoče izklopiti, zelene (navzdol) ali rdeče (položaj za pot).

Zdaj pa preidimo na razvoj končnega avtomata. Prvi in ​​najtežji korak je razumeti dejanska pričakovanja stranke. Ena od prednosti končnega avtomata je, da prisili programerja, da razmisli o vseh možnih primerih in posledično prejme vse zahtevane informacije od stranke. Zakaj menim, da je to najtežja faza? In kolikokrat ste že dobili podoben opis naloge: ne umikajte podvozja, če je letalo na tleh.

Seveda je to pomembno, vendar stranka meni, da se tu vse konča. Kaj pa ostali primeri? Ali je dovolj, da umaknete podvozje v trenutku, ko letalo vzleti s tal? Kaj pa, če letalo odskoči na neravnini na stezi? Kaj pa, če pilot med parkiranjem premakne prestavno ročico v zgornji položaj in posledično začne vzletati? Ali je treba v tem primeru dvigniti podvozje?

Ena od prednosti razmišljanja v smislu stroja stanj je, da lahko hitro narišete diagram prehoda stanja na projekcijsko tablo, tik pred stranko, in se z njo sprehodite skozi celoten proces. Sprejeta je naslednja oznaka za prehod stanja: "dogodek, ki je povzročil prehod"/"izhodni signal kot rezultat prehoda." Če bi razvili le to, kar je stranka prvotno zahtevala (»ne umakni podvozja, če je letalo na tleh«), bi prejeli stroj, prikazan na sliki 2.

Pri ustvarjanju diagrama prehoda stanj (ali katerega koli drugega algoritma) upoštevajte naslednje:

Računalniki delujejo zelo hitro v primerjavi z mehansko opremo

Strojni inženir, ki razlaga, kaj je treba narediti, morda ne ve toliko o računalnikih in algoritmih kot vi. In to je tudi pozitivna stvar, sicer vas ne bi potrebovali!

Kako se bo vaš program obnašal, če se pokvari mehanski ali električni del?

Stroj stanja, ki temelji na tem, kaj stranka dejansko zahteva, je prikazan na sliki 3. Tukaj želimo preprečiti, da bi se podvozje letala umaknilo, dokler ni zagotovo v zraku. Če želite to narediti, po odprtju pristajalnega stikala stroj počaka nekaj sekund. Prav tako se želimo odzvati na naraščajoči rob pilotove ročice in ne na raven, s čimer se bomo izognili težavam, če nekdo premakne ročico, medtem ko je letalo parkirano. Umik ali izvlečenje podvozja traja nekaj sekund, pripravljeni pa moramo biti na situacijo, da si bo pilot med tem posegom premislil in premaknil ročico v nasprotno smer. Upoštevajte tudi, da če letalo znova pristane, medtem ko smo v stanju "Čakanje na vzlet", se bo časovnik znova zagnal in podvozje se bo umaknilo le, če bo letalo v zraku 2 sekundi.

Izvedba končnega avtomata

Seznam 1 je moja izvedba državnega stroja, prikazanega na sliki 3. Pogovorimo se o nekaterih podrobnostih kode.

/*seznam 1*/

typedef enum(GEAR_DOWN = 0, WTG_FOR_TKOFF, RAISING_GEAR, GEAR_UP, LOWERING_GEAR) State_Type;

/*Ta niz vsebuje kazalce na funkcije, klicane v določenih stanjih*/

praznina(*state_table)() = (GearDown, WtgForTakeoff, RaisingGear, GearUp, LoweringGear);

State_Type curr_state;

InicializirajLdgGearSM();

/*Srce stroja je ta neskončna zanka. Funkcija ustreza

Trenutno stanje, klicano enkrat na ponovitev */

medtem (1) {

tabela_stanj();

DekrementTimer();

praznina InicializeLdgGearSM( praznina )

curr_state = GEAR_DOWN;

/*Ustavljanje opreme, ugašanje luči itd.*/

praznina Prestava dol( praznina )

/* Pojdi v stanje čakanja, če letalo

Ni na tleh in prejel je ukaz za dvig podvozja*/

če((prestavna_ročica == GOR) && (prejšnja_prestavna_ročica == DOL) && (stikalo za počep == GOR)) (

curr_state = WTG_FOR_TKOFF;

prev_gear_lever = prestavna_ročica;

praznina RaisingGear( praznina )

če((nosegear_is_up == IZDELAN) && (leftgear_is_up == IZDELAN) && (rtgear_is_up == IZDELAN)) (

curr_state = GEAR_UP;

/*Če je pilot spremenil svojo odločitev, pojdi v stanje “spuščeno podvozje”*/

če(prestavna_ročica == DOL) (

curr_state = LOWERING_GEAR;

praznina Pripravi se( praznina )

/*če je pilot premaknil ročico v položaj “dol”,

Preidemo v stanje "spuščanje podvozja"*/

če(prestavna_ročica == DOL) (

curr_state = LOWERING_GEAR;

praznina WtgForTakeoff( praznina )

/* Počakajte, preden dvignete podvozje.*/

če(časovnik<= 0.0) {

curr_state = RAISING_GEAR;

/*Če sva se spet dotaknila ali si je pilot premislil, začni znova*/

če((squat_switch == DOL) || (prestavna_ročica == DOL)) (

curr_state = GEAR_DOWN;

/* Ne želim zahtevati, da ponovno preklopi ročico

To je bil samo odboj.*/

prev_mear_lever = DOL;

praznina Spuščanje( praznina )

če(prestavna_ročica == GOR) (

curr_state = RAISING_GEAR;

če((nosegear_is_down == MADE) && (leftgear_is_down == MADE) &&(rtgear_is_down == MADE)) (

curr_state = GEAR_DOWN;

Najprej boste morda opazili, da je funkcionalnost vsakega stanja implementirana z ločeno funkcijo C. Seveda bi bilo možno implementirati avtomat z uporabo stavka switch z ločenim primerom za vsako stanje, vendar to lahko vodi do zelo dolge funkcije (10-20 vrstic kode na stanje za vsako od 20-30 stanj) . To lahko privede tudi do napak, če spremenite kodo v zadnjih fazah testiranja. Morda niste nikoli pozabili izjave o prekinitvi na koncu primera, vendar so se takšni primeri zgodili meni. Koda za eno stanje ne bo nikoli končala v kodi za drugo, če imate za vsako stanje ločeno funkcijo.

Da bi se izognil uporabi stavka switch, uporabljam matriko kazalcev za navajanje funkcij in deklariram, da je spremenljivka, ki se uporablja kot indeks matrike, tipa enum.

Zaradi enostavnosti je V/I strojna oprema, odgovorna za branje stanja stikal, vklapljanje in izklapljanje črpalk itd., predstavljena kot preproste spremenljivke. Predpostavlja se, da so te spremenljivke "čarobni naslovi", povezani s strojno opremo prek nevidnih sredstev.

Druga očitna stvar je, da koda na tej točki pravzaprav ni pomembna. Preprosto se premakne iz enega stanja v drugo. To je pomemben vmesni korak in ga ne smete prezreti. Mimogrede, lepo bi bilo dodati izjave o tiskanju med direktive pogojnega prevajanja (#ifdef DEBUG .. #endif), ki bi natisnile trenutno stanje in vrednosti vhodnih signalov.

Ključ do uspeha je v kodi, ki povzroči prehod stanja, tj. ugotovi, da je prišlo do vnosa podatkov.

Če koda pravilno preide skozi vsa stanja, je naslednji korak pisanje "polnjenja" kode, torej točno tisto, kar proizvede izhodni signal. Ne pozabite, da ima vsak prehod vhodni signal (dogodek, ki ga je povzročil) in izhodni signal (strojna V/I naprava, kot v našem primeru). Pogosto je koristno to zajeti v obliki tabele prehodov stanj.

V tabeli prehodov stanj je ena vrstica na prehod stanja.

Ko kodirate avtomat stanja, poskušajte ohraniti njegovo moč - jasno ujemanje med zahtevami stranke in kodo. Morda bo treba skriti podrobnosti strojne opreme v drugi funkcijski plasti, na primer, da bo koda stroja stanja čim bolj podobna tabeli prehodov stanj in diagramu prehodov stanj. Ta simetrija pomaga preprečevati napake in pojasnjuje, zakaj so avtomati stanja tako pomemben del arzenala programerja vgrajenih sistemov. Seveda bi lahko enak učinek dosegli s potrditvenimi polji in neskončnim številom ugnezdenih stavkov if, vendar bi bilo zaradi tega zelo težko slediti kodi in jo primerjati z željami stranke.

Delček kode v seznamu 2 razširja funkcijo RaisingGear(). Upoštevajte, da je cilj kode za funkcijo RaisingGear() zrcaljenje 2 vrstic prehodne tabele za stanje Raising Gear.

praznina RaisingGear( praznina )

/*Ko so vsa stikala dvignjena, gremo v stanje “dvignjeno podvozje”*/

če((nosegear_is_up == IZDELAN) && (leftgear_is_up == IZDELAN) && (rtgear_is_up == IZDELAN)) (

motor_črpalke = IZKLOP;

menjalniki = GASI;

curr_state = GEAR_UP;

/*Če si pilot premisli, začni umikati podvozje*/

če(prestavna_ročica == DOL) (

smer_črpalke = DOL;

curr_state = GEAR_LOWERING;

Ne pozabite se izogibati latentnim stanjem. Skrito stanje se pojavi, ko iz lenobe poskušate dodati pogojno podstanje namesto dodajanja določenega stanja. Na primer, če vaša koda obdeluje isti vhodni signal na različne načine (tj. sproži različne prehode stanj), odvisno od načina, potem je to skrito stanje. V tem primeru bi se vprašal, ali je treba to državo razdeliti na dvoje? Uporaba skritih stanj izniči korist uporabe stanja stroja.

Kot prakso lahko razširite stroj stanja, ki smo si ga pravkar ogledali, tako da dodate časovno omejitev ciklu umika ali podaljšanja podvozja, ker ... Strojni inženir ne želi, da hidravlična črpalka deluje dlje kot 60 sekund. Če se cikel konča, mora biti pilot opozorjen s preklopom zelene in rdeče luči in mora imeti možnost, da znova premakne ročico, da poskusi znova. Morda bi prav tako želeli vprašati hipotetičnega inženirja strojništva, kakšen je učinek obračanja smeri črpalke med delovanjem na črpalko, ker se to zgodi v dveh primerih, ko si pilot premisli. Seveda bo mehanik rekel, da je negativno. Kako bi potem spremenili državni stroj, da bi hitro zaustavil črpalko, ko spremenite smer?

Testiranje državnega stroja

Lepota kodirnih algoritmov kot državnih strojev je v tem, da se testni načrt skoraj samodejno napiše sam. Vse kar morate storiti je, da greste skozi vsak prehod stanja. Običajno to počnem z markerjem v roki in prečrtam puščice na diagramu prehoda med stanjem, ko opravijo test. To je dober način, da se izognete "skritim stanjem" - v testih so pogosteje zgrešena kot določena stanja.

To zahteva precej potrpežljivosti in veliko kave, saj ima lahko tudi srednje velik državni avtomat do 100 različnih prehodov. Mimogrede, število prehodov je odličen način za merjenje kompleksnosti sistema. Slednji je določen z zahtevami kupca, stanje stroj pa naredi obseg testiranja očiten. Z manj organiziranim pristopom je lahko količina potrebnih testiranj prav tako impresivna, vendar tega preprosto ne boste vedeli.

Zelo priročno je, da v kodi uporabite izjave za tiskanje, ki prikazujejo trenutno stanje in vrednosti vhodnih in izhodnih signalov. To vam omogoča, da zlahka opazujete, kaj izraža zlato pravilo testiranja programske opreme: preverite, ali program dela tisto, za kar je namenjen, in tudi, da ne počne ničesar nepotrebnega. Z drugimi besedami, ali prejemate le rezultate, ki jih pričakujete, in kaj se še dogaja poleg tega? Ali obstajajo »težki« prehodi držav, tj. stanja, ki naključno preidejo samo na eno ponovitev zanke? Ali se rezultati spremenijo, ko jih ne pričakujete? V idealnem primeru bi moral izpis vaših printfs opazno spominjati na tabelo prehodov stanj.

Nazadnje – in to velja za vsako vgrajeno programsko opremo, ne le za programsko opremo, ki temelji na stroju stanja – bodite zelo previdni, ko prvič zaženete programsko opremo na pravi strojni opremi. Zelo enostavno je napačno polariteto signala - "Oh, mislil sem, da 1 pomeni dvignjeno podvozje, 0 pa spuščeno podvozje." V mnogih primerih bi moj pomočnik za strojno opremo uporabil začasno "kokošje stikalo" za zaščito dragocenih komponent, dokler ni bil prepričan, da moja programska oprema premika stvari v pravo smer.

Kosilo

Ko so izpolnjene vse zahteve naročnika, lahko v nekaj dneh zaženem stanje stroja podobne kompleksnosti. Skoraj vedno stroji naredijo, kar hočem. Najtežje je seveda natančno razumeti, kaj stranka želi, in se prepričati, da stranka sama ve, kaj hoče. Slednje traja veliko dlje!

Martin Gomez je programer v Laboratoriju za uporabno fiziko na univerzi Johns Hopkins. Ukvarja se z razvojem programske opreme za podporo poletov raziskovalnih vesoljskih plovil. 17 let dela na področju razvoja vgrajenih sistemov. Martin je diplomiral iz vesoljskega inženiringa in magistriral iz elektrotehnike na univerzi Cornell.

Članek obravnava preproste končne avtomate in njihovo implementacijo v C++ z uporabo stikalnih konstrukcij, tabel izvajalnega časa in knjižnice Boost Statechart.

Uvod

Grobo povedano je končni avtomat skozi oči uporabnika črna skrinjica, v katero je mogoče nekaj prenesti in od tam nekaj prejeti. To je zelo priročna abstrakcija, ki vam omogoča, da skrijete zapleten algoritem, končni avtomati pa so tudi zelo učinkoviti.

Končni avtomati so prikazani v obliki diagramov, sestavljenih iz stanj in prehodov. Naj pojasnim s preprostim primerom:

Kot ste verjetno uganili, je to diagram stanja žarnice. Začetno stanje je označeno s črnim krogom, prehodi s puščicami, nekatere puščice so označene - to so dogodki, po katerih stroj preide v drugo stanje. Torej, takoj iz začetnega stanja se znajdemo v stanju Luč ugasnjena- lučka ne sveti. Če pritisnete gumb, bo naprava spremenila svoje stanje in sledila označeni puščici Pritisni gumb, v stanju Prižgana luč- lučka sveti. Iz tega stanja se lahko premaknete, spet po puščici, po pritisku na gumb v stanje Luč ugasnjena.

Pogosto se uporabljajo tudi prehodne tabele:

Praktična uporaba avtomatskih strojev

Končni avtomati se pogosto uporabljajo v programiranju. Na primer, zelo priročno je predstavljati delovanje naprave v obliki avtomatskega stroja. Tako bo koda preprostejša in lažja za eksperimentiranje in vzdrževanje.

Prav tako se končni avtomati uporabljajo za pisanje vseh vrst razčlenjevalcev in analizatorjev besedila; z njihovo pomočjo lahko učinkovito iščete podnize; regularni izrazi se tudi prevajajo v končni avtomat.

Na primer, implementirali bomo avtomat za štetje števil in besed v besedilu. Za začetek se dogovorimo, da bo številka štela zaporedje številk od 0 do 9 poljubne dolžine, obkroženo s presledki (presledek, tabulator, premik vrstice). Beseda se bo štela za zaporedje poljubne dolžine, sestavljeno iz črk in obdano s presledki.

Poglejmo diagram:

Iz začetnega stanja pridemo v stanje Začetek. Preverimo trenutni znak in če je črka, gremo v stanje Beseda vzdolž puščice, označene kot Pismo. To stanje predvideva, da trenutno razmišljamo o besedi; analiza nadaljnjih simbolov bo to domnevo potrdila ali ovrgla. Torej, razmislite o naslednjem znaku, če je črka, potem se stanje ne spremeni (upoštevajte krožno puščico, označeno kot Pismo). Če znak ni črka, ampak ustreza presledku, potem to pomeni, da je bila predpostavka pravilna in da smo besedo našli (sledimo puščici Vesolje v stanju Začetek). Če znak ni niti črka niti presledek, potem smo se zmotili pri predpostavki in zaporedje, ki ga obravnavamo, ni beseda (sledite puščici Neznano v stanju Preskoči).

Sposoben Preskoči tam smo, dokler ne naletimo na presledek. Ko zaznamo vrzel, sledimo puščici Vesolje v stanju Začetek. To je potrebno za popoln preskok vrstice, ki se ne ujema z našim iskalnim vzorcem.

Po vstopu v drž Začetek, se cikel iskanja ponovi od začetka. Veja za prepoznavanje številk je podobna veji za prepoznavanje besed.

Avtomat, ki uporablja navodila za stikalo

Prva so možna stanja:

Nato ponovimo vrstico in trenutni simbol potisnemo v stroj. Sam avtomat je preklopni ukaz, ki najprej izvede prehod v odsek trenutnega stanja. Znotraj razdelka je konstrukcija if-else, ki glede na dogodek (vhodni simbol) spremeni trenutno stanje:

const size_t length = text.length(); for (size_t i = 0; i! = length; ++ i) ( const char current = text[ i] ; switch (state) ( case State_Start: if (std:: isdigit (current) ) ( state = State_Number; ) else if (std:: isalpha (trenutno) ) ( stanje = State_Word; ) break ; case Številka_stanja: if (std:: isspace (trenutno) ) (

Tukaj pogledamo diagram - trenutno stanje številka, dogodek Vesolje(naleti na presledek), kar pomeni, da je številka najdena:

NajdenoŠtevilko() ; stanje = Začetek_stanja; ) else if (! std::isdigit(current) ) (stanje = State_Skip; ) break; case State_Word: if (std:: isspace (current) ) ( FoundWord() ; state = State_Start; ) else if (! std:: isalpha (current) ) ( state = State_Skip; ) break; case State_Skip: if (std::isspace (current) ) (stanje = State_Start; ) break; ) )

rezultat:

Visoka učinkovitost

Enostavnost izvedbe za preproste algoritme

- Težko vzdrževanje

Razlaga izvajalnega časa

Ideja tega pristopa je preprosta - ustvariti morate prehodno tabelo, jo izpolniti in nato, ko se zgodi dogodek, poiskati naslednje stanje v tabeli in narediti prehod:

enum Dogodki (Event_Space, Event_Digit, Event_Letter, Event_Unknown); void ProcessEvent(dogodek dogodkov); ... struct Transition (Stanje BaseState_; Dogodki Dogodek_; Stanje TargetState_; ) ; void AddTransition(State fromState, Events event, States toState) ; ...typedef std::vector< transition>TransitionTable; TransitionTable Transitions_; Države CurrentState_;

Izpolnjevanje tabele:

AddTransition(State_Start, Event_Digit, State_Number) ; AddTransition(State_Start, Event_Letter, State_Word) ; AddTransition(State_Number, Event_Space, State_Start) ; AddTransition(State_Number, Event_Letter, State_Skip) ; AddTransition(State_Number, Event_Unknown, State_Skip) ; AddTransition(State_Word, Event_Space, State_Start) ; AddTransition(State_Word, Event_Digit, State_Skip) ; AddTransition(State_Word, Event_Unknown, State_Skip) ; AddTransition(State_Skip, Event_Space, State_Start) ;

Izkazalo se je precej jasno. Cena za jasnost bo počasnejše delovanje stroja, kar pa pogosto ni pomembno.

Da lahko stroj, ko pride do določenih dogodkov, obvesti neko kodo, jo lahko dodate v strukturo z informacijami o prehodu ( Prehod) funkcijski kazalec ( Akcija), ki se bo imenovala:

typedef void (DynamicMachine::* Action) () ; struct Transition (Stanje BaseState_; Dogodki Dogodek_; Stanje TargetState_; Action Action_; ) ; ... void AddTransition(States fromState, Events event, States toState, Action action) ; ...AddTransition(State_Number, Event_Space, State_Start, & DynamicMachine::FoundNumber) ;

rezultat:

Prilagodljivost in vidnost

Lažje za vzdrževanje

- Nižja zmogljivost v primerjavi s stikalnimi bloki

Razlaga izvedbenega časa. Optimizacija hitrosti

Ali je mogoče združiti vidljivost s hitrostjo? Malo verjetno je, da bo mogoče narediti avtomatski stroj tako učinkovit kot avtomatski stroj, ki temelji na stikalnih blokih, vendar je mogoče zapolniti vrzel. Če želite to narediti, morate iz tabele sestaviti matriko, tako da vam za pridobitev informacij o prehodu ni treba iskati, ampak narediti izbor po stanju in številki dogodka:

Rezultat je dosežen na račun porabe pomnilnika.

rezultat:

Prilagodljivost, vidnost

Učinkovito

- Poraba pomnilnika (najverjetneje nepomembna)

Boost Statechart

Razpravljali smo o več načinih, kako sami implementirati državni stroj. Za spremembo predlagam, da razmislite o knjižnici za izdelavo strojev iz Boosta. Ta knjižnica je zelo zmogljiva; ponujene zmogljivosti vam omogočajo izdelavo zelo zapletenih končnih avtomatov. Ogledali si ga bomo kar na hitro.

Torej, najprej definiramo dogodke:

imenski prostor Dogodki ( struct Digit : boost::statechart::event< Digit>( ) ; struct Letter : boost::statechart::event< Letter>( ) ; struct Space: boost::statechart::event< Space>( ) ; struct Unknown : boost::statechart::event< Unknown> { } ; }

Sam stroj (upoštevajte, da je drugi parameter predloge začetno stanje):

struct Machine: boost::statechart::state_machine< Machine, States:: Start > { } ;

In same države. Znotraj stanj je treba določiti tip, ki opisuje prehode ( reakcije), in če obstaja več prehodov, jih navedite na seznamu tipov boost::mpl::list. Drugi parameter predloge preprosto_stanje– tip, ki opisuje stroj. Prehode opisujejo parametri prehodne predloge, par Dogodek - naslednje stanje:

Stanja imenskega prostora ( struct Start : boost::statechart::simple_state< Start, Machine> < boost:: statechart :: transition < Events:: Digit , States:: Number >< Events:: Letter , States:: Word >> reakcije; ) ; struct Number : boost::statechart::simple_state< Number, Machine>( typedef boost::mpl::list< boost:: statechart :: transition < Events:: Space , States:: Start >, boost::statechart::transition< Events:: Letter , States:: Skip >, boost::statechart::transition< Events:: Unknown , States:: Skip >> reakcije; ) ; struct Word: boost::statechart::simple_state< Word, Machine>( typedef boost::mpl::list< boost:: statechart :: transition < Events:: Space , States:: Start >, boost::statechart::transition< Events:: Digit , States:: Skip >, boost::statechart::transition< Events:: Unknown , States:: Skip >> reakcije; ) ; struct Preskoči: boost::statechart::simple_state< Skip, Machine>( typedef boost::statechart::transition< Events:: Space , States:: Start >reakcije; ) ; )

Stroj je sestavljen, vse kar ostane je, da ga inicializirate in lahko ga uporabljate:

Strojni stroj; machine.initiate(); ...machine.process_event(Events::Space());

rezultat:

Prilagodljivost, razširljivost

- Učinkovitost

Izvedba

Napisal sem testni program za preverjanje delovanja izdelanih strojev. Skozi stroje sem pregnal ~17 MB besedila. Tukaj so rezultati teka:

Nalaganje besedila Dolžina besedila: 17605548 bajtov 0,19 s Zagon BoostMachine Besede: 998002, številke: 6816 0,73 s Zagon DynamicMachine Besede: 998002, številke: 6816 0,56 s Zagon FastDynamicMachine Besede: 998002, številke: 6816 0,29 s Zagon SimpleMachine Words: 998002, številke : 6816 0,20 s

Kaj je ostalo nepregledano

Še vedno je nekaj izvedb končnih avtomatov nepokritih (priporočam http://www.rsdn.ru/article/alg/Static_Finite_State_Machine.xml in http://www.rsdn.ru/article/alg/FiniteStateMachine.xml) , generatorji, ki gradijo stroje iz opisov, knjižnica Meta State Machine iz različice Boost 1.44.0, kot tudi formalni opisi končnih avtomatov. Z vsem naštetim se lahko radovedni bralec seznani sam.

Teorija avtomatov je veja diskretne matematike, ki preučuje modele diskretnih pretvornikov informacij. Takšni pretvorniki so tako resnične naprave (računalniki, živi organizmi) kot namišljene naprave (aksiomatske teorije, matematični stroji). V bistvu lahko končni avtomat označimo kot napravo M , ki ima vhodne in izhodne kanale in je v vsakem od diskretnih časovnih trenutkov, imenovanih taktni trenutki, v enem od končnih stanj.

Po vhodnem kanalu v vsakem trenutku t =1, 2, ... v napravo M prihajajo vhodni signali (iz neke končne množice signalov). Zakon spremembe stanja ob naslednjem času se nastavi glede na vhodni signal in stanje naprave v trenutnem času. Izhodni signal je odvisen od stanja in vhodnega signala v trenutnem času (slika 1).

Končni avtomat je matematični model resničnih diskretnih naprav za obdelavo informacij.

Državni stroj imenovan sistem A= (X , Q , Y ,  ,  ), Kje X , Q , Y so poljubne neprazne končne množice in  in  - funkcije, od tega:

kup X ={a 1 , ..., a m ) je poklican vnosna abeceda , njeni elementi pa so vhodni signali , njihova zaporedja so v v običajnih besedah ;

kup Q ={q 1 , ..., q n ) je poklican veliko držav avtomat in njegovi elementi - države ;

kup Y ={b 1 , ..., b str ) je poklican izhodna abeceda , njegovi elementi so izhodni signali , njihova zaporedja so izstopne besede ;

funkcijo  : X  Q Q klical prehodna funkcija ;

funkcijo  :X  Q Y klical izhodna funkcija .

torej  (x , q )Q ,  (x , q )Y za  x X , q Q .

Končni avtomat je povezan z namišljeno napravo, ki deluje na naslednji način. Lahko je v enem od mnogih stanj Q , zaznavajo signale iz različnih X in oddajo signale iz različnih Y .

2. Metode za specifikacijo končnega avtomata

Obstaja več enakovrednih načinov za definiranje abstraktnih avtomatov, med katerimi lahko imenujemo tri: tabelarno , geometrijski in delujoč .

2.1 Tabelarna naloga stroja

Iz definicije avtomata sledi, da ga lahko vedno podamo s tabelo z dvema vhodoma, ki vsebujeta T vrstice in p stolpcih, kjer na presečišču kolon q in strune A so vrednosti funkcije  (a jaz , q j ),  (a jaz , q j ).

q a	q 1		q j		q n
a 1	(a 1 , q 1),  (a 1 , q 1)		(a 1 , q j ),  (a 1 , q j )		(a 1 , q n ),  (a 1 , q n )
a jaz	(a jaz , q 1),  (a jaz , q 1)		(a jaz , q j ),  (a jaz , q j )		(a jaz , q n ),  (a jaz , q n )
a m	(a m , q 1),  (a m , q 1)		(a m , q j ),  (a m , q j )		(a m , q n ),  (a m , q n )

2.2. Določanje avtomata z uporabo Moorovega diagrama

Drug način za definiranje končnega avtomata je grafični, to je z uporabo grafa. Avtomat je prikazan kot označen usmerjen graf G(Q , D ) z veliko vozlišči Q in veliko lokov D ={(q j ,  (a jaz , q j ))| q j Q , a jaz X ), medtem ko je lok ( q j ,  (a jaz , q j )) je označen s parom ( a jaz ,  (a jaz , q j )). Tako so pri tej metodi stanja stroja prikazana s krogi, v katerih so zapisani simboli stanja q j (j = 1, …, n ). Iz vsakega kroga se izvaja T puščice (orientirani robovi) ena proti ena, ki ustrezajo znakom vhodne abecede X ={a 1 , ..., a m ). Puščica, ki ustreza črki a jaz X in zapustite krog q j Q , je pripisan paru ( a jaz ,  (a jaz , q j )), ta puščica pa vodi do ustreznega kroga  (a jaz , q j ).

Nastala risba se imenuje avtomatski graf ali, Moorov diagram . Za manj zapletene stroje je ta metoda bolj vizualna kot tabelarno.