Bugun biz pulemyotlar haqida gaplashamiz, lekin askarlar qo'llarida ushlab turadigan qurollar haqida emas rus armiyasi. Biz avtomatik dasturlash kabi mikrokontrollerlarni dasturlashning qiziqarli uslubi haqida gaplashamiz. Aniqrog'i, bu hatto dasturlash uslubi emas, balki butun kontseptsiya bo'lib, uning yordamida mikrokontroller dasturchisi o'z hayotini ancha osonlashtirishi mumkin. Buning yordamida dasturchiga taqdim etilgan ko'plab vazifalar dasturchini bosh og'rig'idan xalos qilib, ancha oson va sodda tarzda hal qilinadi. Aytgancha, avtomatik dasturlash ko'pincha deyiladi SWITCH texnologiyasi.

Shuni ta'kidlashni istardimki, ushbu postni yozishga ilhom sabab bo'lgan SWITCH texnologiyasi haqidagi maqolalar turkumi Vladimir Tatarchevskiy. Maqolalar turkumi "Mikrokontrollerlar uchun amaliy dasturlarni ishlab chiqishda SWITCH texnologiyasidan foydalanish" deb nomlanadi.

Aytgancha, men dasturlashga bag'ishlangan bir qator maqolalarni rejalashtirdim, unda men AVR mikrokontrollerlari uchun dasturlash texnikasini batafsil ko'rib chiqaman, o'tkazib yuborma…. Xo'sh, ketaylik!

Dastur dasturchi tomonidan berilgan buyruqlarni ketma-ket bajaradi. Muntazam uchun kompyuter dasturi Dastur o'z ishini yakunlab, bajarilishini to'xtatganda, o'z ishining natijalarini monitorda aks ettirganda, bu mutlaqo normaldir.

Mikrokontroller dasturi o'z bajarilishini shunchaki yakunlay olmaydi. Tasavvur qiling-a, siz pleer yoki magnitafonni yoqdingiz. Siz quvvat tugmasini bosdingiz, kerakli qo'shiqni tanladingiz va musiqadan bahramand bo'ldingiz. Biroq, musiqa qulog'ingizning quloq pardasini tebranishini to'xtatganda, o'yinchi qotib qoldi va tugmachalarni bosishga, daf bilan raqsga tushishingizga hech qanday munosabat bildirmadi.

Buning nimasi yomon? Hammasi yaxshi - o'yinchining chuqurligidagi boshqaruvchi o'z dasturini bajarishni tugatdi. Ko'ryapsizmi, bu qandaydir noqulay.

Shunday qilib, biz mikrokontroller uchun dastur shunchaki to'xtamasligi kerak degan xulosaga keldik. Aslida, shunday bo'lishi kerak cheksiz tsikl- Faqat shu holatda futbolchimiz to'g'ri ishlagan bo'lardi. Keyinchalik men sizga qanday dizaynlar borligini ko'rsataman. dastur kodi mikrokontrollerlar uchun bu hatto dizaynlar emas, balki ba'zi dasturlash uslublari.

Dasturlash uslublari.

"Dasturlash uslublari" qandaydir tushunarsiz ko'rinadi, lekin yaxshi. Bu bilan men nima demoqchiman, tasavvur qilaylik, odam ilgari hech qachon dasturlash bilan shug'ullanmagan, ya'ni u butunlay noob.

Bu odam dasturlash bo'yicha ko'plab kitoblarni o'qigan va tilning barcha asosiy konstruksiyalarini o'rgangan.U asta-sekin ma'lumot to'pladi, chunki endi ma'lumotlarga kirish cheksizdir. Bularning barchasi yaxshi, lekin uning birinchi dasturlari qanday ko'rinishga ega bo'ladi? Nazarimda, u falsafa qilmaydi, balki oddiydan murakkabgacha bo‘lgan yo‘ldan boradi.

Shunday qilib, bu uslublar oddiy darajadan murakkabroq, ammo ayni paytda samaraliroq bosqichga olib boradigan qadamlardir.

Avvaliga men hech narsa haqida o'ylamagan edim dizayn xususiyatlari dasturlar. Men shunchaki dastur mantig'ini shakllantirdim - oqim sxemasini chizdim va kod yozdim. Shuning uchun men rakega yugurishda davom etdim. Ammo bu birinchi marta tashvishlanmadim va "oddiy tsikl" uslubini ishlatdim, keyin uzilishlardan foydalana boshladim, keyin avtomatik mashinalar bor edi va biz ketdik ...

1. Oddiy aylanish. Bunday holda, dastur hech qanday hiyla-nayranglarsiz ishlaydi va bu o'zining ijobiy va salbiy tomonlariga ega. Yagona afzallik - bu yondashuvning soddaligi, siz ayyor dizaynlarni o'ylab topishingiz shart emas, siz o'ylaganingizdek yozasiz (asta-sekin o'z qabringizni qazish).

Void main(void) ( initial_AL(); //periferik qurilmalarni ishga tushirish while(1) ( Leds_BLINK(); //funksiya LED chirog'i signal_on(); //signalni yoqish funksiyasi signal_off(); //signalni o'chirish funksiyasi l=button(); //tugmachalarni bosish uchun mas'ul o'zgaruvchi switch(l) //O'zgaruvchining qiymatiga qarab u yoki bu amal bajariladi ( 1-holat: ( Deistvie1(); //Funksiya o'rniga Deistvie2 shartli operatori bo'lishi mumkin. (); //yoki yana bir nechta shoxchalar kommutatsiya holati 2: ( Deistvie7(); Deistvie9(); . ) )

Dasturning ishlash nuqtasi tartibda harakatlanadi. Bunday holda, barcha harakatlar, shartlar va tsikllar ketma-ket bajariladi. Kod sekinlasha boshlaydi, siz juda ko'p qo'shimcha shartlarni kiritishingiz kerak, bu esa idrokni murakkablashtiradi.

Bularning barchasi dasturni juda chalkashtirib yuboradi va kodni shartlar chigaliga aylantiradi. Natijada, bu koddan hech narsa qo'shib bo'lmaydi yoki olib tashlanmaydi, u monolit bo'lakka aylanadi. Albatta, ovoz balandligi katta bo'lmaganda, kodni o'zgartirish mumkin, lekin u qanchalik uzoqqa borsa, shunchalik qiyin bo'ladi.

Ushbu yondashuvdan foydalanib, men bir nechta dasturlarni yozdim, ular katta emas va juda funktsional edi, ammo ravshanlik juda ko'p narsani talab qildi. Ba'zi yangi shartlarni qo'shish uchun men butun kodni qazib olishim kerak edi, chunki hamma narsa bog'langan edi. Bu juda ko'p xatolar va bosh og'rig'iga sabab bo'ldi. Kompilyator iloji boricha la'natladi, bunday dasturni tuzatish do'zaxga aylandi.

2. Loop + uzilishlar.

Siz uzilishlar yordamida cheksiz tormozlanish davrini qisman hal qilishingiz mumkin. Interruptlar shafqatsiz doiradan chiqishga yordam beradi, muhim voqeani o'tkazib yubormaslikka yordam beradi va qo'shimcha funktsiyalarni qo'shadi (taymerlardan uzilishlar, tashqi uzilishlar).

Aytaylik, siz tugmalarni qayta ishlash yoki muhim voqeani kuzatish uchun uzilishdan foydalanishingiz mumkin. Natijada, dastur ko'proq vizual bo'ladi, lekin kamroq chalkashmaydi.

Afsuski, to'xtatib qo'yish sizni dasturga aylanadigan tartibsizlikdan qutqarmaydi. Bir butun bo'lgan narsani qismlarga bo'lish mumkin emas.

3. Avtomatik dasturlash.

Mana biz yetib boryapmiz asosiy mavzu ushbu maqoladan. Cheklangan holat mashinalarida dasturlash dastlabki ikkita misolga xos bo'lgan kamchiliklarni yo'q qiladi. Dastur oddiyroq va o'zgartirish oson bo'ladi.

Avtomatik uslubda yozilgan dastur, shartlarga qarab, u yoki bu holatga o'tadigan kommutatorga o'xshaydi. Davlatlar soni dastlab dasturchiga ma'lum.

Taxminan aytganda, bu yorug'lik kalitiga o'xshaydi. Ikkita holat yoqilgan va o'chirilgan va ikkita shart yoqilgan va o'chirilgan. Xo'sh, birinchi narsa.

Kommutator texnologiyasida multitaskingni amalga oshirish.

Mikrokontroller yukni boshqarish, yonib-o'chadigan LEDlar, tugmachalarni bosish va boshqa ko'p narsalarni boshqarishga qodir. Ammo bularning barchasini bir vaqtning o'zida qanday qilish kerak? Ushbu muammoni hal qilish uchun ko'plab echimlar mavjud. Men yuqorida aytib o'tganimdek, ulardan eng oddiyi - uzilishlardan foydalanish.

Dasturning ishlashi vaqtida, uzilish sodir bo'lganda, boshqaruvchi dastur kodini bajarishdan chalg'itadi va uzilish uchun javobgar bo'lgan dasturning boshqa qismini qisqacha bajaradi. Uzilish ishlaydi, so'ngra dasturning ishlash nuqtasi boshqaruvchi uzilish bilan to'xtatilgan nuqtadan davom etadi (so'zning o'zi kontroller uzilib qolganligini bildiradi).

Ko'p vazifani amalga oshirishning yana bir usuli - foydalanish operatsion tizimlar. Ha, haqiqatan ham, kam quvvatli boshqaruvchida ishlatilishi mumkin bo'lgan kichik operatsion tizimlar allaqachon paydo bo'la boshladi. Ammo ko'pincha bu usul biroz ortiqcha bo'lib chiqadi. Axir, nima uchun nazoratchining resurslarini keraksiz ishlar bilan behuda sarflash kerak, agar siz ozgina xarajat bilan ishlaysiz.

Switch texnologiyasidan foydalangan holda yozilgan dasturlarda xabar almashish tizimi tufayli shunga o'xshash ko'p vazifali "xayol" olinadi. Men "illuziya" ni yozdim, chunki bu aslida shunday, chunki dastur jismoniy jihatdan bir vaqtning o'zida kodning turli bo'limlarini bajara olmaydi. Men xabar almashish tizimi haqida biroz keyinroq gaplashaman.

Xabarlar tizimi.

Siz ko'plab jarayonlarni hal qilishingiz va xabar almashish tizimidan foydalanib, ko'p vazifali xayolotni yaratishingiz mumkin.

Aytaylik, bizga LED o'rnatilgan dastur kerak. Bu erda ikkita mashinamiz bor, keling, ularni LEDON deb ataymiz - LEDni yoqish uchun mas'ul mashina va LEDOFF mashinasi - LEDni o'chirish uchun mas'ul bo'lgan mashina.

Mashinalarning har biri ikkita holatga ega, ya'ni mashina faol yoki faol bo'lmagan holatda bo'lishi mumkin, masalan, yoqish yoki o'chirish.

Bir mashina yoqilganda, LED yonadi, ikkinchisi yoqilganda, LED o'chadi. Keling, kichik bir misolni ko'rib chiqaylik:

Int main(void) ( INIT_PEREF(); // periferik qurilmalarni (LED) ishga tushirish InitGTimers(); // taymerlarni ishga tushirish InitMessages(); //xabarlarni qayta ishlash mexanizmi InitLEDON(); //LEDON mashinasini ishga tushirish InitLEDOFF(); // LEDOFF mashinasini ishga tushirish SendMessage(MSG_LEDON_ACTIVATE); //LEDON mashinasini faollashtirish //ProcessLEDON(); mashina LEDON ProcessLEDOFF();

3-7-qatorlarda turli ishga tushirishlar sodir bo'ladi, shuning uchun biz hozir bu bilan unchalik qiziqmayapmiz. Ammo keyin quyidagilar sodir bo'ladi: asosiy tsiklni boshlashdan oldin (while(1)) biz mashinaga xabar yuboramiz.

SendMessage(MSG_LEDON_ACTIVATE)

LEDni yoritish uchun javobgardir. Bu kichik qadamsiz organimiz ishlamaydi. Keyinchalik, asosiy ishni asosiy cheksiz while tsikli bajaradi.

Kichik bir chekinish:

Xabar uchta holatga ega. Ya'ni, xabar holati nofaol, o'rnatilgan, lekin faol bo'lmagan va faol holat bo'lishi mumkin.

Ma'lum bo'lishicha, xabar dastlab nofaol edi, biz xabarni yuborganimizda u "o'rnatilgan, lekin faol emas" maqomini oldi. Va bu bizga quyidagilarni beradi. Dasturni ketma-ket bajarayotganda, LEDON mashinasi xabarni qabul qilmaydi. LEDON mashinasining bo'sh iteratsiyasi sodir bo'ladi, bunda xabarni qabul qilib bo'lmaydi. Xabar "o'rnatilgan, lekin faol emas" holatiga ega bo'lganligi sababli, dastur o'z bajarilishini davom ettiradi.

Barcha mashinalar ishlamay qolgandan keyin navbat ProcessMessages() funksiyasiga keladi. Avtomatlarning barcha takrorlashlari tugallangandan so'ng, bu funktsiya har doim tsiklning oxiriga joylashtiriladi. ProcessMessages() funksiyasi oddiygina xabarni "o'rnatilgan, lekin nofaol" holatidan "faol" holatga o'tkazadi.

Cheksiz pastadir ikkinchi turni tugatsa, rasm butunlay boshqacha bo'ladi. ProcessLEDON mashinasining iteratsiyasi endi bo'sh turmaydi. Mashina xabarni qabul qilishi, yoqilgan holatga o'tishi va o'z navbatida xabar yuborishi mumkin. Bu LEDOFF mashinasiga murojaat qilinadi va hayot davrasi xabarlar takrorlanadi.

Shuni ta'kidlashni istardimki, "faol" holatga ega bo'lgan xabarlar ProcessMessages funksiyasiga duch kelganda yo'q qilinadi. Shuning uchun xabarni faqat bitta mashina qabul qilishi mumkin. Xabarning yana bir turi bor - efir xabarlari, lekin men ularni Tatarchevskiyning maqolalarida ko'rib chiqmayman;

Taymerlar

Xabar almashinuvini to'g'ri tashkil etish yordamida biz cheklangan holat mashinalarining ishlash tartibini nazorat qilishimiz mumkin, ammo biz buni faqat xabarlar bilan amalga oshira olmaymiz.

Ehtimol, misol sifatida keltirilgan oldingi dastur fragmenti mo'ljallanganidek ishlamasligini payqadingiz. Mashinalar xabar almashadi, LEDlar o'zgaradi, lekin biz buni ko'rmaymiz. Biz faqat xira yoritilgan LEDni ko'ramiz.

Buning sababi, biz kechikishlarni qanday qilib to'g'ri hal qilishni o'ylamaganmiz. Axir, LEDlarni navbatma-navbat yoqish va o'chirish etarli emas, LED har bir holatda, bir soniya davomida turishi kerak;

Algoritm quyidagicha bo'ladi:

Kattalashtirish uchun bosing

Men ushbu blok-sxemaga qo'shishni unutibman, taymer o'chirilganda, albatta, harakat amalga oshiriladi - LEDni yoqish yoki uni o'chirish.

1. Biz xabarni qabul qilish orqali davlatga kiramiz.

2. Biz taymer/taymer ko'rsatkichlarini tekshiramiz, agar hisob yetgan bo'lsa, unda biz harakatni bajaramiz, aks holda biz o'zimizga shunchaki xabar yuboramiz.

3. Keyingi mashinaga xabar yuboring.

4. Chiqish

Keyingi kirishda hamma narsa takrorlanadi.

SWITCH texnologiyasi bo'yicha dastur. Uch qadam.

Cheklangan holat mashinalarida dastur yozamiz va buning uchun faqat uchtasini bajarishimiz kerak bo'ladi oddiy qadamlar. Dastur oddiy bo'ladi, lekin oddiy narsalardan boshlashga arziydi. Kommutatsiya LEDli dastur bizga mos keladi. Bu juda yaxshi misol, shuning uchun yangi narsalarni ixtiro qilmaylik.

Men dasturni SI tilida tuzaman, lekin bu umuman cheklangan davlat mashinalarida faqat C tilida yozish kerak degani emas, boshqa har qanday dasturlash tilidan foydalanish mumkin;

Bizning dasturimiz modulli bo'ladi va shuning uchun bir nechta fayllarga bo'linadi. Bizda quyidagi modullar bo'ladi:

• Asosiy dastur tsiklining moduli leds_blink.c, HAL.c, HAL.h fayllarini o'z ichiga oladi.
• Taymer moduli timers.c, timers.h fayllarini o'z ichiga oladi
• Xabarlarni qayta ishlash moduli messages.c, messages.h fayllarini o'z ichiga oladi
  
• Mashina moduli 1 ledon.c, ledon.h fayllarini o'z ichiga oladi
• Mashina moduli 2 ledoff.c fayllarini o'z ichiga oladi,ledoff.h

1-qadam.

Biz loyiha yaratamiz va darhol unga statik modullarimiz fayllarini ulaymiz: timers.c, timers.h, messages.c, messages.h.

Asosiy dastur tsikli modulining leds_blink.c fayli.

#include "hal.h" #include "messages.h" //xabarni qayta ishlash moduli #include "timers.h" //taymer moduli //Taymer uzilishlari //############# # ################################################# ########################## ISR(TIMER0_OVF_vect) // uzilish vektori bo'ylab o'tish (taymer T0 hisoblagichi) ( ProcessTimers(); //Taymer uzilishini ishlov beruvchi) //######################################### ################################################ int main(void) ( INIT_PEREF(); // periferik qurilmalarni (LED) ishga tushirish InitGTimers(); //taymerlarni ishga tushirish InitMessages(); //xabarlarni qayta ishlash mexanizmi InitLEDON(); //LEDON mashinasini ishga tushirish InitLEDOFF (); StartGTimer( TIMER_SEK); //Taymerni ishga tushirish(MSG_LEDON_ACTIVATE); //FSM1 sei()ni yoqish //ProcessLEDON(); //iteratsiya; LEDON ProcessLEDOFF( );

Birinchi qatorlar qolgan modullarni asosiy dasturga ulaydi. Bu erda biz taymer moduli va xabarni qayta ishlash moduli ulanganligini ko'ramiz. Dastur matnida keyingi o'rinda toshib ketish vektori joylashgan.

Asosiy dastur int main (void) qatoridan boshlanadi deyish mumkin. Va bu hamma narsani ishga tushirish bilan boshlanadi. Bu erda biz tashqi qurilmalarni ishga tushiramiz, ya'ni solishtirgichning kirish / chiqish portlari va kontrollerning boshqa barcha tarkibi uchun boshlang'ich qiymatlarni o'rnatamiz. Bularning barchasi INIT_PEREF funksiyasi orqali amalga oshiriladi, garchi uning asosiy qismi hal.c faylida bo'lsa ham, biz uni shu yerda ishga tushiramiz.

Keyinchalik biz taymerlarni ishga tushirishni, xabarlarni qayta ishlash modulini va avtomatlarni ishga tushirishni ko'ramiz. Bu erda bu funktsiyalar ham oddiygina ishga tushiriladi, garchi funktsiyalarning o'zi ularning modullari fayllarida yozilgan. Bu qanchalik qulay ekanligini ko'ring. Dasturning asosiy matni o'qish uchun qulay bo'lib qoladi va oyoqlaringizni sindiradigan ortiqcha kod bilan to'ldirilmaydi.

Asosiy ishga tushirishlar tugadi, endi biz asosiy tsiklni boshlashimiz kerak. Buning uchun biz boshlash xabarini yuboramiz, shuningdek soatimizni o'rab olamiz - biz taymerni ishga tushiramiz.

StartGTimer(TIMER_SEK); //SendMessage taymerini ishga tushiring(MSG_LEDON_ACTIVATE); //FSM1 mashinasini faollashtiring

Va asosiy tsikl, men aytganimdek, juda oddiy ko'rinadi. Biz barcha mashinalarning funktsiyalarini yozamiz, ularni tartibni kuzatmasdan, oddiygina ustunga yozamiz. Bu funksiyalar avtomat ishlov beruvchilardir va avtomat modullarida joylashgan. Ushbu avtomatik piramida xabarni qayta ishlash moduli funktsiyasi bilan yakunlanadi. Albatta, biz xabar yuborish tizimi bilan shug'ullanganimizda, men buni allaqachon aytdim. Endi siz dasturning asosiy tsikl modulining yana ikkita fayli qanday ko'rinishini ko'rishingiz mumkin

Hal.h - bu dasturning asosiy sikl modulining sarlavha fayli.

#ifndef HAL_h #define HAL_h #include #o'z ichiga oladi //Standart kutubxona, shu jumladan uzilishlar #define LED1 0 #define LED2 1 #define LED3 2 #define LED4 3 #define Komparator ACSR //comparator #define ViklKomparator 1<

Siz sezganingizdek, bu faylda bajariladigan kodning bitta qatori mavjud emas - bularning barchasi makro almashtirishlar va bog'lovchi kutubxonalardir. Ushbu faylga ega bo'lish hayotni juda osonlashtiradi, ko'rinishni yaxshilaydi.

Lekin Hal.c fayli allaqachon bajariladigan fayl bo'lib, yuqorida aytib o'tganimdek, u turli periferik ishga tushirishlarni o'z ichiga oladi.

#include "hal.h" void INIT_PEREF(void) ( //I/U portlarini ishga tushirish //#################################### ### ############################################## ### ##### Komparator = ViklKomparator //taqqoslagichni ishga tushirish - DDRDni o'chirish = 1<

Xo'sh, men dasturning asosiy tsiklining modulini ko'rsatdim, endi biz oxirgi qadamni qo'yishimiz kerak, biz avtomatlarning modullarini yozishimiz kerak.

3-qadam.

Biz qilishimiz kerak bo'lgan yagona narsa - cheklangan holat mashinalari uchun modullarni yozish, bizning holatlarimizda LEDON mashinasi va LEDOFF mashinasi. Boshlash uchun men LEDni yoritadigan avtomatik qurilma uchun dastur matnini beraman, fayl ledon.c.

//ledon.c fayli #include "ledon.h" #include "timers.h" #include "messages.h" unsigned char ledon_state; //holat o'zgaruvchisi void InitLEDON(void) ( ledon_state=0; //bu yerda siz boshqa //agar mavjud bo'lsa avtomatik o'zgaruvchilarni ishga tushirishingiz mumkin) void ProcessLEDON(void) ( switch(ledon_state) ( 0-holat: //faol bo'lmagan holat if(GetMessage () MSG_LEDON_ACTIVATE)) //agar xabar bo'lsa, u qabul qilinadi ( //va taymer tekshiriladi, agar(GetGTimer(TIMER_SEK)==one_sek) //agar taymer 1 soniya ishlagan bo'lsa, keyin bajaring ( StopGTimer(TIMER_SEK) PORTD = 1<

Bu erda, birinchi qatorlarda, har doimgidek, kutubxonalar ulanadi va o'zgaruvchilar e'lon qilinadi. Keyin bizda allaqachon tanishgan funktsiyalar mavjud. Bu InitLEDON avtomatining ishga tushirish funktsiyasi va ProcessLEDON avtomat ishlov beruvchisining o'zi funksiyasi.

Ishlovchining korpusida taymer moduli va xabar modulining funktsiyalari allaqachon qayta ishlanadi. Va mashinaning o'zi mantig'i kommutator dizayni asosida yaratilgan. Va bu erda siz mashina ishlov beruvchisi bir nechta kalitlarni qo'shish orqali ham murakkab bo'lishi mumkinligini ko'rishingiz mumkin.

Mashina uchun sarlavha fayli yanada sodda bo'ladi:

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

Bu erda biz hal.h bog'lovchi faylni kiritamiz va funksiya prototiplarini ham ko'rsatamiz.

LEDni o'chirish uchun mas'ul bo'lgan fayl faqat oyna tasvirida deyarli bir xil ko'rinadi, shuning uchun men uni bu erda ko'rsatmayman - istamayman :)

Barcha loyiha fayllarini ushbu havoladan yuklab olishingiz mumkin ====>>> LINK.

Faqat uchta qadam bor va bizning dasturimiz tugallangan shaklga ega bo'ldi, ya'ni mening bugungi missiyam tugadi va uni yakunlash vaqti keldi. Menimcha, ushbu maqolada keltirilgan ma'lumotlar siz uchun juda foydali bo'ladi. Ammo bu bilimlarni amalda qo'llaganingizdagina haqiqiy foyda keltiradi.

Aytgancha, men bir qator qiziqarli loyihalarni rejalashtirganman, ular ayniqsa qiziqarli bo'ladi, shuning uchun ishonch hosil qiling yangi maqolalarga obuna bo'ling . Men qo'shimcha materiallarni ham yuborishni rejalashtirmoqdaman, shuning uchun ko'pchilik allaqachon saytning asosiy sahifasi orqali obuna bo'lmoqda. Bu yerda ham obuna boʻlishingiz mumkin.

Xo'sh, endi menda hamma narsa bor, shuning uchun sizga omad, ajoyib kayfiyat tilayman va yana ko'rishguncha.

Vladimir Vasilevdan

Avtomatlar nazariyasi

Mashinaning ta'rifi va uning xilma-xilligi. O'tish va chiqishlarning jadvallari va grafiklari. Sub-avtomatik mashinalar. Qisqartirilgan avtomat teoremasi

Mashinalar bilan operatsiyalar

Mealy mashinasini Mur mashinasiga va Mur mashinasini Mealy mashinasiga aylantirish. Avtomatlarning ekvivalentligi. Avtomatlarning holatini farqlash. Avtomatlarni minimallashtirish. Avtomatlarning sintezi. Tanish mashinalari

Avtomatik mashina - bu energiya, materiallar va ma'lumotlarni qabul qilish, aylantirish va uzatish jarayonlari to'liq avtomatlashtirilgan mexanizmlar va qurilmalar tizimi "Avtomatik mashina" atamasi ikki jihatdan ishlatiladi:

1) texnik,

2) matematik.

Matematik yondashuvda avtomat deganda texnik qurilmaning matematik modeli tushuniladi, u kirishlar, ichki holatlar va chiqishlarga ega bo'lishi kerak. Qurilmaning tuzilishi tafsilotlari haqida hech qanday ma'lumot bo'lmasligi kerak.

Texnik yondashuvda mashina deganda juda haqiqiy qurilma tushuniladi, masalan, telefon kabinasi, savdo avtomati va boshqalar.Bu holda, tabiiyki, qurilmaning ichki tuzilishining tafsilotlari ma'lum.

Avtomatning alohida va muhim holati raqamli avtomat (DA) bo'lib, unda raqamli ma'lumotlarni qabul qilish, o'zgartirish, saqlash va berish jarayonlari to'liq avtomatlashtirilgan.

DA signallari nuqtai nazaridan kirish signallarini qabul qila oladigan, ularning ta'siri ostida bir holatdan ikkinchi holatga o'tadigan, keyingi kirish signali kelguncha uni saqlab turadigan va chiqish signallarini ishlab chiqaradigan tizimni aniqlash foydalidir.

Agar X kirish signallari, S holatlari va Y chiqish signallari to'plami chekli bo'lsa, DA chekli hisoblanadi, masalan, kompyuter kabi qurilma bilan. Kompyuter kiruvchi kirish ma'lumotlarini chiqish ma'lumotlariga (natijaga) qayta ishlaydi, ammo bu natija nafaqat kirish ma'lumotlariga, balki kompyuterning joriy holatiga ham mos keladi, ya'ni. kompyuter xotirasida saqlanadigan ma'lumotlar, masalan, oldingi hisob-kitoblar natijalari, hisoblash dasturlari.

Maqsadli auditoriyaning ishi kirish signallarini qabul qilish davrlari soni bilan belgilanadigan avtomatik vaqtda amalga oshiriladi.

Mavhum avtomat - bu bitta kirish kanaliga ega bo'lgan, til belgilarining ketma-ketligini, bitta chiqish kanaliga ega bo'lgan, boshqa biron bir tilning belgilar ketma-ketligi olinadigan va har bir daqiqada qandaydir holatda bo'lgan diskret qurilmaning matematik modeli. diskret vaqt. Grafik jihatdan mavhum avtomat tasvirda keltirilgan.

Kiritish tilidagi so'zlar X=(x 1 ,x 2 ,...x n ) to'plamning belgilari bilan ifodalanishi mumkin, bu deyiladi. kirish alifbosi, va chiqish tilining soʻzlari Y=(y 1 ,y 2 ,...y p ) toʻplamning belgilari boʻlib, ular deyiladi. chiqish alifbosi. Avtomatning S=(s 1 ,s 2 ,...s m ) holatlar to‘plami deyiladi. davlatlar alifbosi.

Kontseptsiya mashina holati chiqish signallari faqat ma'lum bir vaqtda kirish signallariga emas, balki ba'zi bir oldingi tarixga bog'liq bo'lgan tizimlarni tavsiflash uchun ishlatiladi, ya'ni. tizim kirishlarida ilgari qabul qilingan signallar. Shuning uchun, raqamli avtomatlar, yuqorida aytib o'tilganidek, xotiraga ega bo'lgan ketma-ket sxemalarni anglatadi. Avtomatning holati tushunchasi o'tmishdagi ba'zi xotiralarga mos keladi, shuning uchun bu kontseptsiyani kiritish vaqtni aniq o'zgaruvchi sifatida yo'q qilishga va natijalarni holatlar va kirishlar funktsiyasi sifatida ifodalashga imkon beradi.

Mavhum avtomatning ishlashi ma'lum vaqt oraliqlari bilan bog'liq holda ko'rib chiqilishi kerak, chunki har bir diskret interval t uning chiqish signaliga y(t) mos keladi. Shunday qilib, mashinaning ishlashi chekli davomiylikdagi diskret vaqt oraliqlari orqali ko'rib chiqiladi. Raqamli avtomatlarning mavhum nazariyasida kirish signallari har birining boshida sinxron avtomatda ishlaydi, deb ishoniladi. i- mos keladigan sinxronizatsiya impulsi (tsikllari) tomonidan ajratilgan vaqt oralig'i (kvantalari) va mashinaning ichki holatidagi o'zgarishlar kirish signallarining ta'siri bo'lmaganda, qo'shni sinxronlash impulslari orasidagi vaqt oralig'ida sodir bo'ladi.

"Holat" tushunchasi mashina tomonidan yaratilgan chiqish tilining belgilari va/yoki so'zlarining kirish tilining belgilari va/yoki so'zlariga funktsional bog'liqligini, mashina berilgan algoritmni amalga oshirishda o'rnatish uchun ishlatiladi. Avtomatning har bir holati uchun sOS va diskret vaqt [t] momentidagi har bir xOX belgisi uchun qurilma chiqishida yOY belgisi hosil bo'ladi. Bu bog'liqlik j avtomatining chiqish funksiyasi bilan aniqlanadi. Avtomatning har bir joriy holati uchun sOS va har bir xOX belgisi uchun diskret vaqt [t] momentida avtomat keyingi sOS holatiga o'tadi. Bu bog'liqlik y avtomatining o'tish funksiyasi bilan aniqlanadi. Avtomatning ishlashi ikkita ketma-ketlikni yaratishdan iborat: avtomatning keyingi holatlari ketma-ketligi (s 1[ s 2 s 3 ...) va chiqish belgilarining ketma-ketligi (y 1 y 2 y 3 ...), Belgilar ketma-ketligi uchun (x 1 x 2 x 3...) diskret vaqt momentlarida ochiladi t = 1,2,3,.... To'rtburchaklar qavslarda diskret vaqt momentlari ko'rsatiladi, ular aks holda soat sikllari deb ataladi. , qavs ichida - X, Y va S alifbolari belgilari ketma-ketligi.

Demak, chekli avtomatning matematik modeli uch asosli algebra bo‘lib, uning tashuvchilari uchta X, Y va S to‘plamlar, amallari esa ikkita j va y funksiyalardir.

Ushbu maqolada "cheklangan holat mashinasi" atamasi oz sonli holatlardan birida bo'lishi mumkin bo'lgan algoritmga ishora qiladi. "Holat" - kirish va chiqish signallari, shuningdek kirish signallari va keyingi holatlar o'rtasidagi berilgan munosabatni belgilaydigan muayyan shart. Aqlli o'quvchi ushbu maqolada tasvirlangan cheklangan holat mashinalari Mealy mashinalari ekanligini darhol ta'kidlaydi. Mealy mashinasi - bu cheklangan holat mashinasi bo'lib, unda chiqishlar joriy holat va kirish signali funktsiyalari bo'lib, chiqishlari faqat davlat funktsiyalari bo'lgan Mur mashinasidan farqli o'laroq. Ikkala holatda ham keyingi holat joriy holat va kirish signalining funktsiyasidir.

Oddiy chekli holat mashinasi misolini ko'rib chiqamiz. Tasavvur qiling-a, matn qatorida "//" belgilar ketma-ketligini tanib olishingiz kerak. 1-rasmda bu davlat mashinasi yordamida qanday amalga oshirilganligi ko'rsatilgan. Slashning birinchi ko'rinishi chiqish signalini ishlab chiqarmaydi, lekin mashinaning ikkinchi holatga o'tishiga olib keladi. Agar ikkinchi holatda mashina qiya chiziqni topmasa, u birinchisiga qaytadi, chunki u ketma-ket 2 ta qiyshiq chiziq mavjudligini talab qiladi. Agar ikkinchi chiziq topilsa, mashina "tayyor" signalini beradi.

Xaridorga nima kerakligini bilib oling.

Davlat o'tish diagrammasini yarating

Filial operatsiyalarini batafsil ko'rsatmasdan, davlat mashinasining "skeleti" ni kodlash.

O'tishlarning to'g'ri ishlashiga ishonch hosil qiling.

O'tish tafsilotlari haqida aniq bo'ling.

Sinovdan o'ting.

Davlat mashinasi misol

Keling, davlat mashinasining yanada qiziqarli misolini ko'rib chiqaylik - samolyotning qo'nish moslamasini tortib olish va kengaytirishni boshqaradigan dastur. Garchi ko'pchilik samolyotlar ushbu protsedurani elektro-gidravlik boshqaruv mexanizmi yordamida amalga oshirsa ham (shunchaki bortda kompyuter yo'qligi sababli), ba'zi hollarda, masalan, uchuvchisiz uchish apparatlarida, dasturiy ta'minotni boshqarishdan foydalanishga arziydi.

Birinchidan, uskunani ko'rib chiqaylik. Samolyotning qo'nish moslamasi burun moslamasi, asosiy chap qo'nish moslamasi va asosiy o'ng qo'nish moslamasidan iborat. Ular gidravlik mexanizm bilan boshqariladi. Elektr bilan boshqariladigan gidravlik nasos quvvat aktuatoriga bosim beradi. Dasturiy ta'minot yordamida nasos yoqiladi yoki o'chiriladi. Kompyuter yo'nalish klapanining o'rnini - "pastga" yoki "yuqoriga" - qo'nish moslamasini ko'tarish yoki tushirish uchun bosim o'tkazadi. Shassi tayanchlarining har birida chegara tugmasi mavjud: ulardan biri shassi ko'tarilsa, ikkinchisi - pastga holatda qulflangan bo'lsa, yopiladi. Samolyotning yerda ekanligini aniqlash uchun, agar samolyot og'irligi burun uzatmasida bo'lsa, burun tishli ustunidagi chegara tugmasi yopiladi. Uchuvchining boshqaruv elementlari yuqori/pastki qo'nish moslamasi qo'li va o'chirilishi mumkin bo'lgan uchta chiroqdan (har bir oyoq uchun bittadan), yashil (pastga holatida) yoki qizil (o'tish holati) dan iborat.

Endi chekli holat mashinasini ishlab chiqishga o'tamiz. Birinchi va eng qiyin qadam mijozning haqiqiy umidlarini tushunishdir. Cheklangan holat mashinasining afzalliklaridan biri shundaki, u dasturchini barcha mumkin bo'lgan holatlarni o'ylab ko'rishga majbur qiladi va natijada mijozdan barcha kerakli ma'lumotlarni oladi. Nega men buni eng qiyin bosqich deb bilaman? Va sizga necha marta shunga o'xshash vazifa tavsifi berilgan: agar samolyot erda bo'lsa, qo'nish moslamasini tortib olmang.

Albatta, bu muhim, ammo mijozning fikricha, hammasi shu erda tugaydi. Qolgan holatlar haqida nima deyish mumkin? Samolyot erdan ko'tarilgan paytda qo'nish moslamasini tortib olish kifoya qiladimi? Samolyot uchish-qo'nish yo'lagidagi to'qnashuvga tegsa-chi? Agar uchuvchi to'xtash vaqtida vites tayoqchasini "yuqoriga" holatiga o'tkazsa va natijada havoga ko'tarila boshlasa-chi? Bu holatda qo'nish moslamasini ko'tarish kerakmi?

Shtat mashinasi nuqtai nazaridan fikrlashning afzalliklaridan biri shundaki, siz tezda proyeksiya taxtasida, mijozning ko'z o'ngida holatga o'tish sxemasini chizishingiz va u bilan birga butun jarayonni bosib o'tishingiz mumkin. Davlatga o'tish uchun quyidagi belgi qabul qilinadi: "o'tishga sabab bo'lgan voqea" / "o'tish natijasida chiqish signali". Agar biz mijoz dastlab so'ragan narsani ishlab chiqqan bo'lsak ("agar samolyot yerda bo'lsa, qo'nish moslamasini tortib olmang"), keyin biz 2-rasmda ko'rsatilgan mashinani olgan bo'lardik.

Holatga o'tish diagrammasini (yoki boshqa algoritmni) yaratishda quyidagilarni yodda tuting:

Kompyuterlar mexanik uskunalarga nisbatan juda tez ishlaydi

Nima qilish kerakligini tushuntirib beradigan muhandis-mexanik kompyuterlar va algoritmlar haqida siz kabi ko'p bilmasligi mumkin. Va bu ham ijobiy narsa, aks holda sizga kerak bo'lmaydi!

Mexanik yoki elektr qismi buzilib qolsa, dasturingiz qanday ishlaydi?

Buyurtmachi haqiqatda talab qiladigan narsaga asoslangan davlat mashinasi 3-rasmda ko'rsatilgan. Bu erda biz samolyotning qo'nish moslamasi havoda aniq bo'lmaguncha orqaga tortilishining oldini olishni istaymiz. Buning uchun qo'nish tugmachasini ochgandan so'ng, mashina bir necha soniya kutadi. Shuningdek, biz uchuvchi dastagining sathidan ko'ra ko'tarilgan chetiga javob berishni xohlaymiz, bu esa samolyot parkda bo'lganida kimdir tutqichni harakatga keltirsa, muammolardan qochadi. Qo'nish moslamasini tortib olish yoki cho'zish bir necha soniya davom etadi va biz ushbu operatsiya davomida uchuvchi o'z fikrini o'zgartirishi va tutqichni teskari yo'nalishda harakatlantirishi mumkin bo'lgan vaziyatga tayyor bo'lishimiz kerak. Shuni ham yodda tutingki, agar biz "Uchib ketishni kutmoqdamiz" holatida samolyot yana qo'nsa, samolyot havoda 2 soniya bo'lsa, taymer qayta ishga tushadi va qo'nish moslamasi orqaga tortiladi.

Cheklangan holat mashinasini amalga oshirish

Ro'yxat 1 - bu 3-rasmda ko'rsatilgan davlat mashinasini amalga oshirishim. Keling, kodning ba'zi tafsilotlarini muhokama qilaylik.

/*1-ro‘yxat*/

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

/*Ushbu massiv ma’lum shtatlarda chaqiriladigan funksiyalarga ko‘rsatgichlarni o‘z ichiga oladi*/

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

State_Type curr_state;

InitializeLdgGearSM();

/*Mashinaning yuragi bu cheksiz halqadir. Tegishli funktsiya

Joriy holat, har bir iteratsiyada bir marta chaqiriladi */

esa (1) {

davlat_jadval();

DecrementTimer();

bekor InitializeLdgGearSM( bekor )

curr_state = GEAR_DOWN;

/*Uskunani to‘xtatish, chiroqlarni o‘chirish va h.k.*/

bekor GearDown( bekor )

/* Samolyot bo'lsa, kutish holatiga o'ting

Yerda emas va qo'nish moslamasini ko'tarish buyrug'ini oldi*/

agar((tishli_tutqich == YUQARI) && (oldingi_tishli_tutqich == DOWN) && (squat_switch == UP)) (

curr_state = WTG_FOR_TKOFF;

prev_gear_lever = vites_lever;

bekor RaisingGear( bekor )

agar((nosegear_is_up == MADE) && (leftgear_is_up == MADE) && (rtgear_is_up == MADE)) (

curr_state = GEAR_UP;

/*Agar uchuvchi oʻz qarorini oʻzgartirgan boʻlsa, “qoʻnish moslamasi past” holatiga oʻting*/

agar(tishli ushlagich == PASTGA) (

curr_state = LOWERING_GEAR;

bekor GearUp( bekor )

/*agar uchuvchi qo'lni “pastga” holatiga o'tkazgan bo'lsa,

Biz "tushirish moslamasi" holatiga o'tamiz */

agar(tishli ushlagich == PASTGA) (

curr_state = LOWERING_GEAR;

bekor WtgForTakeoff( bekor )

/* Qo'nish moslamasini ko'tarishdan oldin kuting.*/

agar(taymer<= 0.0) {

curr_state = RAISING_GEAR;

/*Agar biz yana teginsak yoki uchuvchi fikrini oʻzgartirsa, hammasini boshidan boshlang*/

agar((squat_switch == PASTGA) || (vitesli_tutqich == PASTGA)) (

curr_state = GEAR_DOWN;

/* Undan tutqichni qayta almashtirishni talab qilishni xohlamang

Bu shunchaki sakrash edi.*/

prev_gear_lever = DOWN;

bekor LoweringGear( bekor )

agar(tishli ushlagich == UP) (

curr_state = RAISING_GEAR;

agar((nosegear_is_down == MADE) && (leftgear_is_down == MADE) &&(rtgear_is_down == MADE)) (

curr_state = GEAR_DOWN;

Birinchidan, har bir holatning funksionalligi alohida C funktsiyasi tomonidan amalga oshirilishini sezishingiz mumkin. Albatta, har bir holat uchun alohida holatga ega bo'lgan switch bayonoti yordamida avtomatni amalga oshirish mumkin edi, lekin bu juda uzoq funktsiyaga olib kelishi mumkin (har bir 20-30 holat uchun har bir holat uchun 10-20 qator kod) . Sinovning oxirgi bosqichida kodni o'zgartirsangiz, bu ham xatolarga olib kelishi mumkin. Ish oxiridagi tanaffus bayonotini hech qachon unutmagandirsiz, lekin bunday holatlar men bilan sodir bo'lgan. Har bir shtat uchun alohida funktsiyangiz bo'lsa, bir davlat uchun kod hech qachon boshqasi uchun kodda tugamaydi.

Switch iborasidan foydalanmaslik uchun men funktsiyalarni ifodalash uchun ko'rsatkichlar qatoridan foydalanaman va massiv indeksi sifatida ishlatiladigan o'zgaruvchini enum tipidagi deb e'lon qilaman.

Oddiylik uchun kalitlarning holatini o'qish, nasoslarni yoqish va o'chirish va hokazolar uchun mas'ul bo'lgan kiritish-chiqarish apparati oddiy o'zgaruvchilar sifatida ifodalanadi. Ushbu o'zgaruvchilar ko'rinmas vositalar orqali apparat bilan bog'langan "sehrli manzillar" deb taxmin qilinadi.

Yana bir aniq narsa shundaki, kod hozircha muhim emas. U shunchaki bir holatdan boshqasiga o'tadi. Bu muhim oraliq bosqichdir va uni e'tiborsiz qoldirmaslik kerak. Aytgancha, kirish signallarining joriy holati va qiymatlarini chop etadigan shartli kompilyatsiya direktivalari (#ifdef DEBUG .. #endif) orasiga chop etish bayonotlarini qo'shish yaxshi bo'lar edi.

Muvaffaqiyatning kaliti davlatga o'tishni keltirib chiqaradigan kodda yotadi, ya'ni. ma'lumotlar kiritilishi sodir bo'lganligini aniqlaydi.

Agar kod barcha holatlardan to'g'ri o'tib ketsa, keyingi qadam kodni "to'ldirish" ni, ya'ni chiqish signalini ishlab chiqaradigan narsani yozishdir. Esda tutingki, har bir o'tishda kirish signali (uni keltirib chiqargan hodisa) va chiqish signali (bizning misolimizdagi kabi apparat kiritish-chiqarish qurilmasi) mavjud. Ko'pincha buni holatga o'tish jadvali shaklida olish foydalidir.

Davlat o'tish jadvalida har bir holatga o'tish uchun bitta qator mavjud.

Davlat mashinasini kodlashda uning kuchini saqlab qolishga harakat qiling - mijozning talablari va kod o'rtasidagi aniq muvofiqlik. Uskuna tafsilotlarini boshqa funktsiya qatlamida yashirish kerak bo'lishi mumkin, masalan, davlat mashina kodini imkon qadar holatga o'tish jadvali va holatga o'tish diagrammasi kabi ko'rinishi uchun. Ushbu simmetriya xatolarning oldini olishga yordam beradi va nima uchun davlat mashinalari o'rnatilgan tizimlar dasturchisi arsenalining muhim qismi ekanligini tushuntiradi. Albatta, xuddi shunday effektga tasdiqlash qutilari va cheksiz sonli ichki if ifodalari bilan erishishingiz mumkin, ammo bu kodni kuzatish va uni mijozning xohishi bilan solishtirishni juda qiyinlashtiradi.

Listing 2dagi kod parchasi RaisingGear() funksiyasini kengaytiradi. E'tibor bering, RaisingGear() funksiyasi kodi Raising Gear holati uchun o'tish jadvalining 2 qatorini aks ettirishga qaratilgan.

bekor RaisingGear( bekor )

/*Barcha kalitlar ko‘tarilgandan so‘ng biz “shassi ko‘tarilgan” holatiga o‘tamiz*/

agar((nosegear_is_up == MADE) && (leftgear_is_up == MADE) && (rtgear_is_up == MADE)) (

pump_motor = OFF;

gear_lights = O'CHISH;

curr_state = GEAR_UP;

/*Agar uchuvchi fikrini oʻzgartirsa, qoʻnish moslamasini tortib olishni boshlang*/

agar(tishli ushlagich == PASTGA) (

nasos_yo'nalishi = DOWN;

curr_state = GEAR_LOWERING;

Yashirin sharoitlardan qochishni unutmang. Yashirin holat, dangasalik tufayli ma'lum bir holatni qo'shish o'rniga shartli pastki holatni qo'shishga harakat qilganda paydo bo'ladi. Misol uchun, agar sizning kodingiz rejimga qarab bir xil kirish signalini turli yo'llar bilan qayta ishlasa (ya'ni, turli holat o'tishlarini ishga tushirsa), u yashirin holatdir. Bu holatda, bu davlatni ikkiga bo'lish kerakmi, deb o'ylayman? Yashirin holatlardan foydalanish davlat mashinasidan foydalanishning foydasini inkor etadi.

Amaliyot sifatida siz biz ko'rib chiqqan holat mashinasini qo'nish moslamasini tortib olish yoki uzaytirish davriga taym-aut qo'shish orqali kengaytirishingiz mumkin, chunki... Mexanik muhandis gidravlik nasosning 60 soniyadan ko'proq ishlashini xohlamaydi. Agar tsikl tugasa, uchuvchi yashil va qizil chiroqning o'zgarishi bilan ogohlantirishi kerak va qayta urinib ko'rish uchun qo'lni yana harakatlantira olishi kerak. Siz taxminiy mexanik muhandisdan nasos ishlayotgan vaqtda uning yo‘nalishini o‘zgartirishning nasosga qanday ta’siri borligini so‘rashingiz mumkin, chunki bu ikki holatda uchuvchi o‘z fikrini o‘zgartirganda sodir bo‘ladi. Albatta, mexanik buni salbiy deb aytadi. Keyin yo'nalishni o'zgartirganda nasosni tezda to'xtatish uchun davlat mashinasini qanday o'zgartirasiz?

Davlat mashina sinovi

Davlat mashinalari sifatida kodlash algoritmlarining go'zalligi shundaki, test rejasi deyarli avtomatik ravishda o'zini yozadi. Siz qilishingiz kerak bo'lgan yagona narsa - har bir shtatga o'tish. Men odatda buni qo'limdagi marker bilan bajaraman, ular sinovdan o'tganda holatga o'tish diagrammasidagi o'qlarni kesib o'tamiz. Bu "yashirin holatlar" dan qochishning yaxshi usuli - ular testlarda muayyan holatlarga qaraganda tez-tez o'tkazib yuboriladi.

Bu katta sabr-toqat va ko'p qahva talab qiladi, chunki hatto o'rta o'lchamdagi davlat mashinasida 100 tagacha turli xil o'tishlar bo'lishi mumkin. Aytgancha, o'tishlar soni tizimning murakkabligini o'lchashning ajoyib usuli hisoblanadi. Ikkinchisi mijozning talablari bilan belgilanadi va davlat mashinasi sinov doirasini aniq ko'rsatadi. Kamroq tashkillashtirilgan yondashuv bilan, talab qilinadigan test miqdori xuddi shunday ta'sirli bo'lishi mumkin, ammo siz buni bilmaysiz.

Kodingizda joriy holat va kirish va chiqish signallarining qiymatlarini aks ettiruvchi bosma bayonotlardan foydalanish juda qulay. Bu sizga dasturiy ta'minotni sinovdan o'tkazishning oltin qoidasi nimani anglatishini osongina kuzatish imkonini beradi: dastur o'zi uchun mo'ljallangan narsani bajarayotganligini, shuningdek, keraksiz hech narsa qilmasligini tekshiring. Boshqacha qilib aytadigan bo'lsak, siz faqat o'zingiz kutgan natijalarni olasizmi va bundan tashqari yana nima sodir bo'lmoqda? Har qanday "qiyin" davlat o'tishlari bormi, ya'ni. tsiklning faqat bir marta takrorlanishi uchun tasodifiy o'tishni aytadimi? Natijalar siz kutmaganda o'zgaradimi? Ideal holda, sizning printf-laringizning chiqishi sezilarli darajada o'tish jadvaliga o'xshash bo'lishi kerak.

Nihoyat - va bu faqat davlat mashinasiga asoslangan dasturiy ta'minotga emas, balki har qanday o'rnatilgan dasturiy ta'minotga taalluqlidir - dasturiy ta'minotni haqiqiy uskunada birinchi marta ishga tushirganingizda juda ehtiyot bo'ling. Signalning polaritesini noto'g'ri aniqlash juda oson - "Oh, men 1 qo'nish moslamasini yuqoriga ko'tarishni va 0 - qo'nish moslamasini pastga tushirishni anglatadi deb o'yladim". Ko'p hollarda, mening apparat yordamchim mening dasturiy ta'minotim narsalarni to'g'ri yo'nalishda harakatlantirayotganiga ishonch hosil qilmaguncha qimmatli komponentlarni himoya qilish uchun vaqtinchalik "tovuq kaliti" dan foydalanadi.

Ishga tushirish

Xaridorning barcha talablari bajarilganda, men bir necha kun ichida shunga o'xshash murakkablikdagi davlat mashinasini ishga tushirishim mumkin. Deyarli har doim mashinalar men xohlagan narsani qiladi. Eng qiyin narsa, albatta, mijoz nimani xohlashini aniq tushunish va mijozning o'zi nimani xohlashini bilishiga ishonch hosil qilishdir. Ikkinchisi ancha uzoq davom etadi!

Martin Gomes Jon Xopkins universiteti qoshidagi Amaliy fizika laboratoriyasining dasturchisi. Tadqiqot kosmik kemalarining parvozlarini qo'llab-quvvatlash uchun dasturiy ta'minotni ishlab chiqish bilan shug'ullanadi. 17 yil davomida o'rnatilgan tizimlarni ishlab chiqish sohasida ishlagan. Martin Aerokosmik muhandislik fanlari bakalavri va Kornel universitetining elektrotexnika fanlari magistri darajasiga ega.

Maqolada oddiy sonli holat mashinalari va ularni C++ da switch konstruksiyalari, ish vaqti jadvallari va Boost Statechart kutubxonasi yordamida amalga oshirish muhokama qilinadi.

Kirish

Taxminan aytganda, Cheklangan holat mashinasi, foydalanuvchi ko'zi bilan, biror narsani o'tkazish va u erdan biror narsa olish mumkin bo'lgan qora qutidir. Bu murakkab algoritmni yashirish imkonini beruvchi juda qulay abstraksiya bo'lib, chekli holat mashinalari ham juda samarali.

Cheklangan holat mashinalari holatlar va o'tishlardan iborat diagrammalar shaklida tasvirlangan. Oddiy misol bilan tushuntiraman:

Siz taxmin qilganingizdek, bu lampochkaning holat diagrammasi. Boshlang'ich holat qora doira bilan ko'rsatilgan, o'tishlar o'qlar bilan, ba'zi o'qlar etiketlangan - bu hodisalar shundan keyin mashina boshqa holatga o'tadi. Shunday qilib, biz dastlabki holatdan darhol o'zimizni davlatda topamiz Chiroq oʻchirilgan– chiroq yonmaydi. Agar siz tugmani bossangiz, mashina o'z holatini o'zgartiradi va belgilangan o'qni kuzatib boradi Bosish tugmasi, holatda Chiroq yoqilgan- chiroq yoqilgan. Siz tugmani bosganingizdan so'ng yana o'qdan keyin bu holatdan holatga o'tishingiz mumkin Chiroq oʻchirilgan.

O'tish jadvallari ham keng qo'llaniladi:

Avtomatik mashinalarning amaliy qo'llanilishi

Dasturlashda chekli holat mashinalari keng qo'llaniladi. Masalan, qurilmaning ishlashini avtomatik mashina shaklida tasavvur qilish juda qulay. Bu kodni soddalashtiradi va tajriba qilish va saqlashni osonlashtiradi.

Shuningdek, chekli holat mashinalari barcha turdagi parserlar va matn analizatorlarini yozish uchun ishlatiladi, siz pastki qatorlarni samarali qidirishingiz mumkin, shuningdek, chekli holat mashinasiga tarjima qilinadi;

Masalan, biz matndagi raqamlar va so'zlarni hisoblash uchun avtomatni amalga oshiramiz. Boshlash uchun, keling, raqam bo'sh joy belgilari (bo'sh joy, yorliq, satr tasmasi) bilan o'ralgan ixtiyoriy uzunlikdagi 0 dan 9 gacha bo'lgan raqamlar ketma-ketligi deb hisoblanishiga rozi bo'laylik. So'z ixtiyoriy uzunlikdagi harflardan tashkil topgan va shuningdek, bo'sh joy belgilari bilan o'ralgan ketma-ketlik deb hisoblanadi.

Keling, diagrammani ko'rib chiqaylik:

Dastlabki holatdan biz davlatga o'tamiz Boshlash. Biz joriy belgini tekshiramiz va agar u harf bo'lsa, biz davlatga boramiz So'z sifatida belgilangan strelka bo'ylab Xat. Bu holat, biz hozirda bir so'zni ko'rib chiqmoqdamiz, deb taxmin qiladi keyingi belgilar tahlili bu taxminni tasdiqlaydi yoki uni rad etadi; Shunday qilib, keyingi belgini ko'rib chiqing, agar u harf bo'lsa, u holda holat o'zgarmaydi (deb belgilangan dumaloq o'qga e'tibor bering. Xat). Agar belgi harf bo'lmasa, lekin bo'sh joy belgisiga to'g'ri kelsa, demak, bu taxmin to'g'ri edi va biz so'zni topdik (biz o'qni kuzatib boramiz) Kosmos bir holatda Boshlash). Agar belgi na harf, na bo'sh joy bo'lmasa, biz taxminda xato qildik va biz ko'rib chiqayotgan ketma-ketlik so'z emas (o'qni kuzatib boring) Noma'lum bir holatda Oʻtkazib yuborish).

Holatida Oʻtkazib yuborish biz bo'sh joy belgisiga duch kelmaguncha u erdamiz. Bo'shliq aniqlangandan so'ng, biz o'qni kuzatib boramiz Kosmos bir holatda Boshlash. Bu bizning qidiruv namunamizga mos kelmaydigan qatorni butunlay o'tkazib yuborish uchun kerak.

Davlatga kirgandan keyin Boshlash, qidiruv sikli boshidan takrorlanadi. Raqamni tanish bo‘limi so‘zni tanish bo‘limiga o‘xshaydi.

O'zgartirish ko'rsatmalaridan foydalangan holda avtomat

Birinchisi mumkin bo'lgan holatlar:

Shundan so'ng biz chiziq bo'ylab takrorlaymiz, joriy belgini mashinaga o'tkazamiz. Avtomatning o'zi birinchi navbatda joriy holat bo'limiga o'tishni amalga oshiradigan kalit ko'rsatmasi. Bo'lim ichida if-else konstruktsiyasi mavjud bo'lib, u hodisaga (kiruvchi belgi) qarab joriy holatni o'zgartiradi:

const size_t length = text.length(); uchun (size_t i = 0 ; i ! = uzunlik; ++ i) ( const char joriy = text[ i] ; switch (holat) ( case State_Start: if (std:: isdigit (joriy) ) ( state = State_Number; ) else if (std:: isalpha (joriy) ) ( state = State_Word; ) break case State_Number: if (std:: isspace (joriy) ) ();

Bu erda biz diagrammaga qaraymiz - hozirgi holat Raqam, hodisa Kosmos(bo'sh joy belgisi mavjud), bu raqam topilganligini bildiradi:

FoundNumber(); davlat = Holat_Start; ) else if (! std::isdigit(current) ) ( state = State_Skip; ) break ; case State_Word: if (std:: isspace (joriy) ) ( FoundWord() ; state = State_Start; ) else if (! std:: isalpha (joriy) ) ( state = State_Skip; ) break ; case State_Skip: if (std::isspace (joriy) ) ( state = State_Start; ) break ; ))

Natija:

Yuqori samaradorlik

Oddiy algoritmlar uchun amalga oshirish qulayligi

- Saqlash qiyin

Ish vaqti talqini

Ushbu yondashuvning g'oyasi oddiy - siz o'tish jadvalini yaratishingiz, uni to'ldirishingiz kerak, keyin voqea sodir bo'lganda, jadvaldagi keyingi holatni toping va o'tishni amalga oshiring:

enum Voqealar (Voqealar_Space, Voqea_raqami, Voqea_Xati, Voqea_noma'lum ); void ProcessEvent(Voqealar hodisasi); ... struct Transition (Stats BaseState_; Events Event_; States TargetState_;); ); void AddTransition(Shtatlardan Shtat, Voqealar hodisasi, Shtatlardan Shtatga); ...typedef std::vector< transition>O'tish jadvali; TransitionTable Transitions_; Davlatlar CurrentState_;

Jadvalni to'ldirish:

Qo'shishTransition(State_Start, Event_Digit, State_Number) ; AddTransition(State_Start, Event_Letter, State_Word) ; Qo'shishTransition(Holat_raqami, Voqea_bo'shlig'i, Holat_boshlash) ; Qo'shishTransition(State_Raqam, Voqea_Xat, Holat_O'tkazib yuborish) ; Qo'shishTransition(Holat_raqami, Voqea_noma'lum, Holat_o'tkazib yuborish) ; 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) ;

Bu juda aniq bo'lib chiqdi. Aniqlik uchun narx mashinaning sekin ishlashi bo'ladi, ammo bu ko'pincha muhim emas.

Mashina, ba'zi hodisalar sodir bo'lganda, ba'zi kodni xabardor qilishi uchun uni o'tish haqidagi ma'lumot bilan tuzilishga qo'shishingiz mumkin ( O'tish) funktsiya ko'rsatkichi ( Harakat), deb nomlanadi:

typedef void (DynamicMachine:: * Action) () ; struct Transition (Shatlar BaseState_; Voqealar hodisasi_; Shtatlar TargetState_; Action Action_; ); ... void AddTransition(Shtatlardan Shtat, Voqealar hodisasi, Shtatlardan Shtatga, Harakat harakati) ; ...AddTransition(State_Number, Voqealar_Space, Holat_Start, & DynamicMachine::FoundNumber) ;

Natija:

Moslashuvchanlik va ko'rinish

Xizmat qilish osonroq

- Kommutator bloklari bilan solishtirganda kamroq ishlash

Bajarilish vaqtini talqin qilish. Tezlikni optimallashtirish

Ko'rinishni tezlik bilan birlashtirish mumkinmi? Avtomatik mashinani kalit bloklari asosidagi avtomatik mashina kabi samarali qilish mumkin bo'lishi dargumon, ammo bo'shliqni yopish mumkin. Buni amalga oshirish uchun jadvaldan matritsani qurishingiz kerak, shunday qilib o'tish haqida ma'lumot olish uchun siz qidirishingiz shart emas, lekin holat va hodisa raqami bo'yicha tanlov qilishingiz kerak:

Natija xotira iste'moli hisobiga erishiladi.

Natija:

Moslashuvchanlik, ko'rinish

Samarali

- Xotira iste'moli (ehtimol ahamiyatsiz)

Davlat diagrammasini kuchaytiring

Biz davlat mashinasini o'zingiz amalga oshirishning bir necha usullarini muhokama qildik. O'zgartirish uchun men Boost-dan mashinalarni qurish uchun kutubxonani ko'rib chiqishni taklif qilaman. Ushbu kutubxona juda kuchli; Biz buni juda tez ko'rib chiqamiz.

Shunday qilib, birinchi navbatda biz voqealarni aniqlaymiz:

nomlar maydoni Voqealar ( struct Raqam : boost ::statechart :: voqea< Digit>( ); struct Letter : boost ::statechart :: voqea< Letter>( ); struct Space: boost::statechart::event< Space>( ); struct Noma'lum : boost::statechart::voqea< Unknown> { } ; }

Mashinaning o'zi (ikkinchi shablon parametri dastlabki holat ekanligini unutmang):

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

Va shtatlarning o'zlari. Shtatlarning ichida o'tishlarni tavsiflovchi turni aniqlash kerak ( reaktsiyalar), va agar bir nechta o'tishlar bo'lsa, ularni boost::mpl::list turlari ro'yxatiga kiriting. Shablonning ikkinchi parametri oddiy_holat– mashinani tavsiflovchi tur. O'tishlar o'tish shablonining parametrlari, juftlik bilan tavsiflanadi Tadbir - Keyingi holat:

nomlar maydoni Davlatlar ( struct Start : boost::statechart::simple_state< Start, Machine> < boost:: statechart :: transition < Events:: Digit , States:: Number >< Events:: Letter , States:: Word >> reaktsiyalar; ); 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 >> reaktsiyalar; ); 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 >> reaktsiyalar; ); struct O'tkazib yuborish: boost::statechart::simple_state< Skip, Machine>( typedef boost::statechart::transition< Events:: Space , States:: Start >reaktsiyalar; ); )

Mashina qurilgan, uni ishga tushirish qoladi va siz undan foydalanishingiz mumkin:

Mashina mashinasi; machine.initiate(); ... machine.process_event(Events::Space());

Natija:

Moslashuvchanlik, kengayish qobiliyati

- Samaradorlik

Ishlash

Men qurilgan mashinalarning ishlashini tekshirish uchun test dasturini yozdim. Men mashinalar orqali ~ 17 MB matnni ishlatdim. Mana yugurish natijalari:

Matnni yuklash Matn uzunligi: 17605548 bayt 0,19 s Running BoostMachine Words: 998002, raqamlar: 6816 0,73 s Running DynamicMachine Words: 998002, raqamlar: 6816 0,56 s Words:09Machine 16 0,29 s Running SimpleMachine Words: 998002, raqamlar: 6816 0,20 s

Ko'rib chiqilmagan narsa

Hali ham aniqlanmagan sonli holat mashinalarining bir nechta ilovalari mavjud (men http://www.rsdn.ru/article/alg/Static_Finite_State_Machine.xml va http://www.rsdn.ru/article/alg/FiniteStateMachine.xml ni tavsiya qilaman) , tavsiflardan mashinalar yaratuvchi generatorlar, Boost 1.44.0 versiyasidan Meta State Machine kutubxonasi, shuningdek, cheklangan holat mashinalarining rasmiy tavsiflari. Qiziquvchan o'quvchi yuqoridagilarning barchasi bilan mustaqil ravishda tanishishi mumkin.

Avtomatlar nazariyasi diskret maʼlumotlarni oʻzgartiruvchi modellarni oʻrganuvchi diskret matematikaning boʻlimidir. Bunday konvertorlar ham real qurilmalar (kompyuterlar, tirik organizmlar), ham xayoliy qurilmalar (aksiomatik nazariyalar, matematik mashinalar) hisoblanadi. Aslini olganda, cheklangan holat mashinasini qurilma sifatida tavsiflash mumkin M , kirish va chiqish kanallariga ega va soat momentlari deb ataladigan vaqtning har bir diskret momentida u yakuniy holatlardan birida bo'ladi.

Har bir daqiqada kirish kanali bo'yicha t =1, 2, ... qurilmaga M kirish signallari keladi (ba'zi chekli signallar to'plamidan). Keyingi vaqtda holatni o'zgartirish qonuni kirish signaliga va qurilmaning joriy vaqtdagi holatiga qarab o'rnatiladi. Chiqish signali joriy vaqtdagi holat va kirish signaliga bog'liq (1-rasm).

Cheklangan holat mashinasi axborotni qayta ishlash uchun haqiqiy diskret qurilmalarning matematik modelidir.

Davlat mashinasi tizim deb ataladi A= (X , Q , Y ,  ,  ), Qayerda X , Q , Y ixtiyoriy bo'sh bo'lmagan chekli to'plamlar va  Va  - funktsiyalari, ulardan:

bir guruh X ={a 1 , ..., a m ) deyiladi kirish alifbosi , va uning elementlari kirish signallari , ularning ketma-ketligi mavjud umumiy so'zlarda ;

bir guruh Q ={q 1 , ..., q n ) deyiladi ko'p davlatlar avtomat va uning elementlari - davlatlar ;

bir guruh Y ={b 1 , ..., b p ) deyiladi chiqish alifbosi , uning elementlari chiqish signallari , ularning ketma-ketligi chiqish so'zlari ;

funktsiyasi  : X  Q Q chaqirdi o'tish funktsiyasi ;

funktsiyasi  :X  Q Y chaqirdi chiqish funktsiyasi .

Shunday qilib,  (x , q )Q ,  (x , q )Y  uchun x X , q Q .

Cheklangan holat mashinasi xayoliy qurilma bilan bog'langan bo'lib, u quyidagicha ishlaydi. Bu ko'plab shtatlardan birida bo'lishi mumkin Q , turli signallarni idrok etish X va turli xil signallarni chiqaradi Y .

2. Cheklangan holat mashinasini ko'rsatish usullari

Mavhum avtomatlarni aniqlashning bir nechta ekvivalent usullari mavjud, ulardan uchtasini nomlash mumkin: jadvalli , geometrik Va funktsional .

2.1 Mashinaning jadval vazifasi

Avtomatning ta'rifidan kelib chiqadiki, u har doim ikkita kirishni o'z ichiga olgan jadval bilan belgilanishi mumkin T chiziqlar va P ustunlar, bu erda ustunning kesishmasida q va iplar A funktsiya qiymatlari qiymati  (a i , q j ),  (a i , 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 i	(a i , q 1),  (a i , q 1)		(a i , q j ),  (a i , q j )		(a i , q n ),  (a i , 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. Mur diagrammasi yordamida avtomatni belgilash

Cheklangan holat mashinasini aniqlashning yana bir usuli - grafik, ya'ni grafik yordamida. Avtomat yorliqli yo'naltirilgan grafik sifatida tasvirlangan G(Q , D ) ko'p uchlari bilan Q va ko'plab yoylar D ={(q j ,  (a i , q j ))| q j Q , a i X ), yoy esa ( q j ,  (a i , q j )) juftligi bilan belgilangan ( a i ,  (a i , q j )). Shunday qilib, bu usul bilan mashinaning holatlari davlat belgilari yoziladigan doiralar bilan ifodalanadi q j (j = 1, …, n ). Har bir doiradan u amalga oshiriladi T kirish alifbosi belgilariga mos keladigan o'qlar (yo'naltirilgan qirralar) X ={a 1 , ..., a m ). Harfga mos keladigan o'q a i X va doirani tark etish q j Q , juftlikka tegishli ( a i ,  (a i , q j )) va bu o'q mos keladigan doiraga olib keladi  (a i , q j ).

Olingan chizma deyiladi avtomat grafigi yoki, Mur diagrammasi . Juda murakkab bo'lmagan mashinalar uchun bu usul ko'proq ingl jadvalli.