امروز در مورد مسلسل ها صحبت خواهیم کرد، اما نه آنهایی که سربازان در دست دارند ارتش روسیه. ما در مورد سبک جالب برنامه نویسی میکروکنترلرها مانند برنامه نویسی خودکار صحبت خواهیم کرد. به عبارت دقیق تر، این حتی یک سبک برنامه نویسی نیست، بلکه یک مفهوم کامل است که به لطف آن یک برنامه نویس میکروکنترلر می تواند زندگی خود را بسیار آسان تر کند. به لطف آن بسیاری از وظایف ارائه شده به برنامه نویس بسیار راحت تر و ساده تر حل می شود و سردرد برنامه نویس را از بین می برد. به هر حال، برنامه نویسی خودکار اغلب نامیده می شود تکنولوژی SWITCH.

می خواهم توجه داشته باشم که الهام بخش نوشتن این پست بوده است سری مقالات در مورد تکنولوژی SWITCH ولادیمیر تاتارچفسکی. مجموعه مقالات «استفاده از فناوری SWITCH در توسعه نرم‌افزارهای کاربردی برای میکروکنترلرها» نام دارد، بنابراین در این مقاله سعی می‌کنم بیشتر یک نمونه از کدهای کاری و توضیحات آن را بیان کنم.

به هر حال، من مجموعه ای از مقالات اختصاص داده شده به برنامه نویسی را برنامه ریزی کرده ام، که در آن تکنیک های برنامه نویسی را برای میکروکنترلرهای AVR با جزئیات در نظر خواهم گرفت. از دست نده…. خب بریم!

برنامه به طور مداوم دستورات تعیین شده توسط برنامه نویس را اجرا می کند. برای معمولی برنامه کامپیوتریزمانی که برنامه اجرای خود را به پایان رسانده و اجرای خود را متوقف کرده و در عین حال نتایج کار خود را بر روی مانیتور نمایش می دهد کاملا طبیعی است.

یک برنامه میکروکنترلر نمی تواند به سادگی اجرای خود را به پایان برساند. فقط تصور کنید که پخش کننده یا ضبط صوت را روشن کرده اید. دکمه پاور را فشار داده، آهنگ مورد نظر را انتخاب کرده و از موسیقی لذت ببرید. با این حال، وقتی موسیقی از ارتعاش پرده گوش شما متوقف شد، پخش کننده یخ کرد و به هیچ وجه به فشار دادن دکمه ها واکنشی نشان نداد، حتی کمتر به رقص شما با تنبور.

چه اشکالی دارد؟ همه چیز خوب است - کنترلر، کنترل کننده ای که در اعماق پخش کننده شما قرار دارد، به سادگی اجرای برنامه خود را به پایان رسانده است. می بینید، به نوعی ناخوشایند است.

بنابراین از اینجا نتیجه می گیریم که برنامه برای میکروکنترلر به سادگی نباید متوقف شود. در اصل، باید باشد چرخه بی پایان- فقط در این صورت بازیکن ما به درستی کار می کند. در ادامه به شما نشان خواهم داد که چه طرح هایی وجود دارد. کد برنامهبرای میکروکنترلرها، اینها حتی طرح نیستند، بلکه برخی از سبک های برنامه نویسی هستند.

سبک های برنامه نویسی

"سبک های برنامه نویسی" تا حدی نامفهوم به نظر می رسد، اما اوه خوب. با این چه می‌خواهم بگویم؟ بیایید تصور کنیم که یک نفر قبلاً برنامه‌نویسی نکرده است، یعنی او یک نوب کامل است.

این شخص کتاب های زیادی در زمینه برنامه نویسی خوانده و تمام ساختارهای اولیه زبان را مطالعه کرده است.او اطلاعات را ذره ذره جمع آوری کرد، زیرا اکنون دسترسی به اطلاعات نامحدود است. این همه خوب و خوب است، اما اولین برنامه های او چگونه خواهد بود؟ به نظر من او فلسفه نخواهد کرد، بلکه مسیر ساده به پیچیده را دنبال خواهد کرد.

بنابراین این سبک‌ها مراحلی هستند که از یک سطح ساده به یک سطح پیچیده‌تر، اما در عین حال مؤثرتر منجر می‌شوند.

اولش به هیچکدوم فکر نکردم ویژگی های طراحیبرنامه ها. من به سادگی منطق برنامه را تشکیل دادم - یک فلوچارت کشیدم و کد نوشتم. به همین دلیل است که من مدام به یک چنگک می افتم. اما این اولین باری بود که نگران نشدم و از سبک "حلقه ساده" استفاده کردم، سپس شروع به استفاده از وقفه کردم، سپس ماشین های خودکار وجود داشتند و ما می رویم ...

1. حلقه زدن ساده. در این حالت برنامه بدون هیچ ترفندی لوپ می شود و این مزایا و معایب خود را دارد. تنها مزیت آن سادگی رویکرد است، شما نیازی به طرح های حیله گر ندارید، همانطور که فکر می کنید می نویسید (به تدریج قبر خود را حفر کنید).

Void main(void) ( initial_AL(); //دستورالعمل کردن وسایل جانبی while(1) (Leds_BLINK(); //function فلاشر ال ای دی signal_on(); //تابع روشن کردن سیگنال signal_off(); //عملکرد خاموش کردن سیگنال l=button(); //متغیر مسئول فشار دادن دکمه‌ها سوئیچ(l) //بسته به مقدار متغیر، یک عمل یا عمل دیگری انجام می‌شود (مورد 1: ( Deistvie1(); //به جای یک تابع می‌تواند یک عملگر شرطی Deistvie2 وجود داشته باشد. ()؛ //یا چندین شاخه دیگر، Deistvie3(); Deistvie4(); Deistvie5();؛ case 2: (Deistvie6(); Deistvie7(); Deistvie8(); Deistvie9(); Deistvie10();) ; . . . . . . . . ) ))

نقطه عملیاتی برنامه به ترتیب حرکت می کند. در این حالت، تمام اعمال، شرایط و چرخه ها به صورت متوالی اجرا می شوند. کد شروع به کند شدن می کند، شما باید شرایط اضافی زیادی را وارد کنید، در نتیجه درک را پیچیده می کنید.

همه اینها به شدت برنامه را گیج می کند و کد را به یک درهم از شرایط تبدیل می کند. در نتیجه، هیچ چیزی را نمی توان به این کد اضافه کرد یا حذف کرد؛ مانند یک قطعه یکپارچه می شود. البته وقتی حجم زیاد نباشد، کد قابل تغییر است، اما هر چه جلوتر می رود، سخت تر می شود.

با استفاده از این رویکرد، من چندین برنامه نوشتم؛ آنها بزرگ و کاملاً کاربردی نبودند، اما وضوح آنها چیزهای زیادی را برای دلخواه باقی می گذاشت. برای اضافه کردن شرایط جدید، مجبور شدم کل کد را بررسی کنم، زیرا همه چیز گره خورده بود. این باعث خطاها و سردردهای زیادی شد. کامپایلر تا جایی که می توانست نفرین کرد، اشکال زدایی چنین برنامه ای به جهنم تبدیل شد.

2. حلقه + قطع می کند.

شما می توانید تا حدودی چرخه ترمز بی پایان را با استفاده از وقفه حل کنید. وقفه ها به خارج شدن از یک دایره باطل کمک می کند، کمک می کند یک رویداد مهم را از دست ندهید، و عملکردهای اضافی را اضافه کنید (وقفه های تایمر، وقفه های خارجی).

فرض کنید می توانید از یک وقفه برای پردازش دکمه ها یا ردیابی یک رویداد مهم استفاده کنید. در نتیجه، برنامه بصری تر می شود اما کمتر گیج کننده نیست.

متأسفانه، وقفه شما را از آشفتگی که برنامه به آن تبدیل می کند، نجات نمی دهد. نمی توان آن چیزی را که یک کل واحد است به اجزا تقسیم کرد.

3. برنامه نویسی خودکار.

اینجا داریم به موضوع اصلیاین مقاله برنامه نویسی در ماشین های حالت محدود، معایب ذاتی دو مثال اول را از بین می برد. این برنامه ساده تر می شود و به راحتی قابل تغییر است.

برنامه ای که به سبک خودکار نوشته می شود شبیه یک سوئیچ است که بسته به شرایط به یک حالت یا حالت دیگر تغییر می کند. تعداد حالت ها در ابتدا برای برنامه نویس مشخص است.

به طور کلی، آن را مانند یک کلید چراغ است. دو حالت روشن و خاموش و دو حالت روشن و خاموش وجود دارد. خوب، اول چیزها.

پیاده سازی چند وظیفه ای در فناوری سوئیچ.

میکروکنترلر قادر به کنترل بار، چشمک زدن LED ها، ردیابی ضربه های کلید و موارد دیگر است. اما چگونه می توان همه اینها را همزمان انجام داد؟ راه حل های زیادی برای حل این مشکل وجود دارد. ساده ترین آنها که قبلاً ذکر کردم استفاده از وقفه است.

در حین کار برنامه، زمانی که وقفه رخ می دهد، کنترل کننده از اجرای کد برنامه منحرف می شود و به طور خلاصه قطعه دیگری از برنامه را که وقفه مسئول آن است اجرا می کند. وقفه کار می کند، سپس نقطه عملیاتی برنامه از نقطه ای که کنترل کننده با وقفه قطع شده است ادامه می یابد (خود کلمه نشان می دهد که کنترل کننده قطع شده است).

یکی دیگر از راه های اجرای چند وظیفه ای استفاده از آن است سیستم های عامل. بله، در واقع، سیستم‌عامل‌های کوچک از قبل ظاهر شده‌اند، که می‌توانند روی یک کنترل‌کننده کم مصرف استفاده شوند. اما اغلب این روش تا حدودی زائد به نظر می رسد. به هر حال، چرا منابع کنترلر را با کارهای غیرضروری هدر دهید، در حالی که می توانید با هزینه کمی از پس آن برآیید.

در برنامه هایی که با استفاده از فناوری سوئیچ نوشته شده اند، به لطف سیستم پیام رسانی، "توهم" مشابهی از چندوظیفه به دست می آید. من "توهم" را نوشتم زیرا در واقع چنین است، زیرا یک برنامه از نظر فیزیکی نمی تواند بخش های مختلف کد را همزمان اجرا کند. در مورد سیستم پیام رسان کمی بیشتر صحبت خواهم کرد.

سیستم پیام رسانی

شما می توانید فرآیندهای متعددی را حل کنید و با استفاده از یک سیستم پیام رسانی، توهم چند وظیفه ای را ایجاد کنید.

فرض کنید به برنامه ای نیاز داریم که در آن LED روشن شود. در اینجا ما دو ماشین داریم، بیایید آنها را LEDON نامگذاری کنیم - دستگاه مسئول روشن کردن LED و دستگاه LEDOFF - دستگاهی که مسئول خاموش کردن LED است.

هر یک از ماشین ها دو حالت دارند، یعنی ماشین می تواند در حالت فعال یا غیرفعال باشد، مانند یک کلید روشن یا خاموش.

هنگامی که یک دستگاه فعال می شود، LED روشن می شود، زمانی که دیگری فعال می شود، LED خاموش می شود. بیایید به یک مثال کوچک نگاه کنیم:

Int main(void) ( INIT_PEREF(); //راه‌اندازی تجهیزات جانبی (LED) InitGTimers(); //راه‌اندازی تایمرها InitMessages(); //راه‌اندازی مکانیسم پردازش پیام InitLEDON(); //راه‌اندازی اولیه ماشین LEDON InitLEDOFF(); // مقدار دهی اولیه خودکار LEDOFF SendMessage(MSG_LEDON_ACTIVATE)؛ //فعال کردن LEDON sei(); //فعال کردن وقفه ها //حلقه اصلی برنامه while(1) (ProcessLEDON(); //تکرار LEDON خودکار ProcessLEDOFF(); //تکرار خودکار LEDOFF ProcessMessages (); //پردازش پیام؛ )

در خطوط 3-7 مقداردهی اولیه‌های مختلفی رخ می‌دهد، بنابراین ما در حال حاضر علاقه خاصی به این موضوع نداریم. اما پس از آن موارد زیر اتفاق می افتد: قبل از شروع حلقه اصلی (while(1))، پیامی به دستگاه ارسال می کنیم.

ارسال پیام (MSG_LEDON_ACTIVATE)

مسئول روشنایی LED بدون این قدم کوچک، اندام ما کار نخواهد کرد. در مرحله بعد، حلقه اصلی infinite while کار اصلی را انجام می دهد.

یک انحراف کوچک:

پیام سه حالت دارد. یعنی وضعیت پیام می تواند غیر فعال، تنظیم شده اما غیرفعال و حالت فعال باشد.

معلوم شد که پیام در ابتدا غیر فعال بوده است، زمانی که پیام را ارسال کردیم، وضعیت "نصب شده اما غیر فعال" را دریافت کرد. و این موارد زیر را به ما می دهد. هنگامی که برنامه به صورت متوالی اجرا می شود، دستگاه LEDON پیام را دریافت نمی کند. یک تکرار غیرفعال در ماشین LEDON رخ می دهد که در آن پیام به سادگی قابل دریافت نیست. از آنجایی که پیام وضعیت "نصب شده اما غیر فعال" را دارد، برنامه به اجرای خود ادامه می دهد.

بعد از اینکه همه ماشین ها بیکار شدند، نوبت به تابع ()ProcessMessages می رسد. این تابع همیشه در انتهای حلقه قرار می گیرد، پس از اتمام تمام تکرارهای خودکار. تابع ProcessMessages () به سادگی یک پیام را از حالت "تنظیم اما غیر فعال" به حالت "فعال" منتقل می کند.

هنگامی که حلقه بی نهایت دور دوم را کامل می کند، تصویر کاملاً متفاوت می شود. تکرار دستگاه ProcessLEDON دیگر بیکار نخواهد بود. دستگاه قادر به دریافت پیام، رفتن به حالت روشن و همچنین ارسال پیام به نوبه خود خواهد بود. خطاب به دستگاه LEDOFF و چرخه زندگیپیام ها تکرار خواهد شد

من می خواهم توجه داشته باشم که پیام هایی که حالت "فعال" دارند وقتی با عملکرد ProcessMessages روبرو می شوند از بین می روند. بنابراین، پیام فقط توسط یک دستگاه قابل دریافت است. نوع دیگری از پیام وجود دارد - پیام های پخش، اما من آنها را در نظر نمی گیرم؛ آنها همچنین در مقالات تاتارچفسکی به خوبی پوشش داده شده اند.

تایمرها

با کمک سازماندهی صحیح تبادل پیام، می‌توانیم ترتیب عملکرد ماشین‌های حالت محدود را کنترل کنیم، اما تنها با پیام‌ها نمی‌توانیم این کار را انجام دهیم.

احتمالاً متوجه شده اید که قطعه برنامه قبلی که به عنوان مثال ارائه شده است، آنطور که در نظر گرفته شده است کار نخواهد کرد. ماشین ها پیام ها را رد و بدل می کنند، LED ها تغییر می کنند، اما ما آن را نمی بینیم. ما فقط یک LED کم نور خواهیم دید.

این به این دلیل است که ما فکر نکردیم که چگونه تاخیرها را به درستی مدیریت کنیم. از این گذشته، روشن و خاموش کردن متناوب ال ای دی ها برای ما کافی نیست؛ ال ای دی باید در هر حالت، مثلا برای یک ثانیه، بماند.

الگوریتم به صورت زیر خواهد بود:

برای بزرگنمایی می توانید کلیک کنید

من فراموش کردم در این بلوک دیاگرام اضافه کنم که وقتی تایمر پایین می آید، البته یک عمل انجام می شود - روشن کردن LED یا خاموش کردن آن.

1. با پذیرش پیام وارد حالت می شویم.

2. ما قرائت های تایمر / شمارنده را بررسی می کنیم، اگر شمارش رسیده باشد، عمل را انجام می دهیم، در غیر این صورت به سادگی یک پیام برای خود ارسال می کنیم.

3. یک پیام به دستگاه بعدی ارسال کنید.

4. خارج شوید

در ورودی بعدی همه چیز تکرار می شود.

برنامه در تکنولوژی SWITCH. سه مرحله

بیایید یک برنامه در ماشین های حالت محدود بنویسیم و برای این کار فقط سه مورد نیاز داریم مراحل ساده. این برنامه ساده خواهد بود، اما ارزش شروع با چیزهای ساده را دارد. برنامه ای با LED سوئیچینگ برای ما مناسب است. این خیلی مثال خوب، پس بیایید چیز جدیدی اختراع نکنیم.

من برنامه را به زبان SI می نویسم، اما این به هیچ وجه به این معنا نیست که در ماشین های حالت محدود فقط باید به زبان C بنویسید؛ استفاده از هر زبان برنامه نویسی دیگری کاملاً ممکن است.

برنامه ما ماژولار خواهد بود و بنابراین به چندین فایل تقسیم می شود. ما ماژول های زیر را خواهیم داشت:

• ماژول حلقه برنامه اصلی شامل فایل های leds_blink.c، HAL.c، HAL.h است.
• ماژول تایمر حاوی فایل های timers.c، timers.h است
• ماژول پردازش پیام حاوی فایل‌های messages.c، messages.h
  
• ماژول ماشین 1 حاوی فایل های ledon.c، ledon.h است
• ماژول ماشین 2 حاوی فایل های ledoff.c است, ledoff .h

مرحله 1.

ما یک پروژه ایجاد می کنیم و بلافاصله فایل های ماژول های استاتیک خود را به آن متصل می کنیم: timers.c، timers.h، messages.c، messages.h.

فایل leds_blink.c از ماژول حلقه برنامه اصلی.

#include "hal.h" #include "messages.h" //message processing module #include "timers.h" //timers module //Timer interrupts //############# ############################################### ############################ ISR(TIMER0_OVF_vect) // پرش در امتداد بردار وقفه (سرریز تایمر شمارنده T0) ( ProcessTimers(); // کنترل کننده وقفه تایمر) //######################################## ############################################### main(void) ( INIT_PEREF(); //راه‌اندازی ابزارهای جانبی (LED) InitGTimers(); //راه‌اندازی تایمرها InitMessages(); //راه‌اندازی مکانیسم پردازش پیام InitLEDON(); //راه‌اندازی اولیه ماشین LEDON InitLEDOFF ()؛ StartGTimer( TIMER_SEK)؛ //شروع تایمر SendMessage(MSG_LEDON_ACTIVATE)؛ //فعال کردن خودکار FSM1 sei(); //فعال کردن وقفه ها //حلقه اصلی برنامه while(1) (ProcessLEDON(); // تکرار خودکار LEDON ProcessLEDOFF(); ProcessMessages(); //پردازش پیام؛ )

خطوط اول ماژول های باقی مانده را به برنامه اصلی متصل می کند. در اینجا می بینیم که ماژول تایمر و ماژول پردازش پیام به هم متصل شده اند. بعدی در متن برنامه بردار وقفه سرریز است.

می توان گفت برنامه اصلی با خط int main (void) شروع می شود. و با مقداردهی اولیه همه چیز شروع می شود. در اینجا ما لوازم جانبی را مقداردهی اولیه می کنیم، یعنی مقادیر اولیه را برای پورت های ورودی/خروجی مقایسه کننده و سایر محتویات کنترلر تنظیم می کنیم. همه اینها توسط تابع INIT_PEREF انجام می شود؛ ما آن را در اینجا اجرا می کنیم، اگرچه بدنه اصلی آن در فایل hal.c است.

در ادامه شاهد راه اندازی اولیه تایمرها، ماژول پردازش پیام و مقداردهی اولیه خودکارها هستیم. در اینجا این توابع نیز به سادگی راه اندازی می شوند، اگرچه خود توابع در فایل های ماژول های آنها نوشته شده است. ببینید چقدر راحت است. متن اصلی برنامه به راحتی خوانده می شود و با کدهای اضافی که پاهای شما را می شکند، درهم نمی شود.

مراحل اولیه به پایان رسیده است، اکنون باید حلقه اصلی را شروع کنیم. برای انجام این کار، ما یک پیام شروع ارسال می کنیم و همچنین ساعت خود را خاموش می کنیم - تایمر را شروع می کنیم.

StartGTimer (TIMER_SEK)؛ //شروع تایمر SendMessage(MSG_LEDON_ACTIVATE); //دستگاه FSM1 را فعال کنید

و چرخه اصلی، همانطور که قبلاً گفتم، بسیار ساده به نظر می رسد. ما عملکرد همه ماشین ها را یادداشت می کنیم، به سادگی آنها را بدون رعایت ترتیب در یک ستون می نویسیم. این توابع کنترل کننده های خودکار هستند و در ماژول های خودکار قرار دارند. این هرم خودکار با عملکرد ماژول پردازش پیام تکمیل می شود. البته این را قبلاً زمانی که با سیستم ارسال پیام سروکار داشتیم به شما گفتم. اکنون می توانید ببینید که دو فایل دیگر از ماژول چرخه اصلی برنامه چگونه هستند

Hal.h فایل هدر ماژول حلقه اصلی برنامه است.

#ifndef HAL_h #تعریف HAL_h #شامل #عبارتند از //کتابخانه استاندارد شامل وقفه ها #define LED1 0 #define LED2 1 #define LED3 2 #define LED4 3 #define Komparator ACSR //comparator #define ViklKomparator 1<

همانطور که ممکن است متوجه شده باشید، این فایل ذاتاً حاوی یک خط کد اجرایی نیست - همه جایگزین‌های ماکرو و کتابخانه‌های متصل هستند. داشتن این فایل فقط زندگی را بسیار آسان می کند، دید را بهبود می بخشد.

اما فایل Hal.c در حال حاضر یک فایل اجرایی است، و همانطور که قبلاً اشاره کردم، حاوی مقداردهی اولیه محیطی مختلف است.

#include "hal.h" void INIT_PEREF(void) (//Initializing ports I/O //########################### ### ############################################ ### ##### Komparator = ViklKomparator؛ //آغاز کردن مقایسه کننده - خاموش کردن DDRD = 1<

خب ماژول چرخه اصلی برنامه رو نشون دادم حالا فقط باید مرحله آخر رو برداریم باید خود ماژول های اتوماتا رو بنویسیم.

مرحله 3.

تنها کاری که ما باید انجام دهیم این است که ماژول هایی را برای ماشین های حالت محدود بنویسیم، در مورد ما ماشین LEDON و ماشین LEDOFF. برای شروع، متن برنامه را برای دستگاه خودکاری که LED را روشن می کند، فایل ledon.c می دهم.

//file ledon.c #include "ledon.h" #include "timers.h" #include "messages.h" char ledon_state بدون علامت; //state متغیر void InitLEDON(void) ( ledon_state=0; //اینجا می توانید سایر متغیرهای //اتوماتیک را در صورت وجود مقداردهی اولیه کنید) void ProcessLEDON(void) ( switch(ledon_state) ( case 0: //inactive status if(GetMessage ( MSG_LEDON_ACTIVATE)) //اگر پیامی وجود داشته باشد، پذیرفته می‌شود (//و تایمر بررسی می‌شود if(GetGTimer(TIMER_SEK)==one_sek) //اگر تایمر 1 ثانیه است، سپس اجرا کنید ( StopGTimer(TIMER_SEK ؛ PORTD = 1<

اینجا مثل همیشه در خطوط اول کتابخانه ها به هم وصل شده و متغیرها اعلام می شوند. بعد ما توابعی را داریم که قبلاً ملاقات کرده ایم. این تابع مقداردهی اولیه خودکار InitLEDON و عملکرد خود کنترل کننده خودکار ProcessLEDON است.

در بدنه کنترل کننده، عملکردهای ماژول تایمر و ماژول پیام قبلاً پردازش شده اند. و منطق خود ماشین بر اساس طراحی کیس سوئیچ ساخته شده است. و در اینجا می توانید متوجه شوید که کنترل کننده دستگاه نیز می تواند با اضافه کردن چندین سوئیچ کیس پیچیده شود.

فایل هدر برای دستگاه حتی ساده تر خواهد بود:

فایل //fsm1 #ifndef LEDON_h #define LEDON_h #include "hal.h" void InitLEDON(void); void ProcessLEDON(void); #endif

در اینجا ما فایل پیوند دهنده hal.h را اضافه می کنیم و نمونه های اولیه تابع را نیز نشان می دهیم.

فایلی که مسئول خاموش کردن LED است فقط در تصویر آینه تقریباً یکسان به نظر می رسد ، بنابراین من آن را در اینجا نمایش نمی دهم - من تمایلی ندارم :)

می توانید تمامی فایل های پروژه را از این لینک دانلود کنید ====>>> ارتباط دادن.

فقط سه مرحله باقی مانده است و برنامه ما فرم تمام شده ای پیدا کرده است، به این معنی که ماموریت امروز من به پایان رسیده است و زمان آن است که آن را به پایان برسانم. به نظر من اطلاعات ارائه شده در این مقاله برای شما بسیار مفید خواهد بود. اما تنها زمانی سود واقعی به همراه خواهد داشت که این دانش را در عمل به کار ببرید.

به هر حال، من تعدادی پروژه جالب برنامه ریزی کرده ام که به خصوص جالب خواهند بود، پس حتماً این کار را انجام دهید مشترک شدن در مقالات جدید . من همچنین قصد دارم مطالب اضافی را ارسال کنم، بنابراین بسیاری از آنها در حال حاضر از طریق صفحه اصلی سایت مشترک می شوند. شما همچنین می توانید در اینجا مشترک شوید.

خوب، الان واقعا همه چیز دارم، بنابراین برای شما آرزوی موفقیت دارم، روحیه خوبی داشته باشید و دوباره شما را ببینم.

از n/a ولادیمیر واسیلیف

تئوری خودکار

تعریف ماشین و تنوع آن جداول و نمودارهای انتقال و خروجی. ماشین های زیر اتوماتیک. قضیه خودکار کاهش یافته

عملیات با ماشین آلات

تبدیل ماشین Mealy به ماشین Moore و ماشین Moore به ماشین Mealy. معادل سازی خودکار تمایز حالت های خودکار. به حداقل رساندن خودکارها سنتز اتومات. ماشین های تشخیص

ماشین اتوماتیک سیستمی از مکانیسم ها و وسایلی است که در آن فرآیندهای دریافت، تبدیل و انتقال انرژی، مواد و اطلاعات به طور کامل اتوماتیک می باشد.اصطلاح ماشین اتوماتیک در دو جنبه به کار می رود:

1) فنی،

2) ریاضی

در رویکرد ریاضی، خودکار به عنوان یک مدل ریاضی از یک دستگاه فنی درک می شود که باید ورودی، حالت های داخلی و خروجی داشته باشد. هیچ اطلاعاتی در مورد جزئیات ساختار دستگاه نباید وجود داشته باشد.

در رویکرد فنی، یک ماشین به عنوان یک دستگاه کاملا واقعی در نظر گرفته می شود، به عنوان مثال، یک باجه تلفن، یک دستگاه خودکار و غیره، در این صورت طبیعتاً جزئیات ساختار داخلی دستگاه مشخص است.

یک مورد خاص و مهم از خودکار، خودکار دیجیتال (DA) است که در آن فرآیندهای دریافت، تبدیل، ذخیره سازی و صدور اطلاعات دیجیتال به طور کامل خودکار است.

از دیدگاه سیگنال‌های DA، تعریف سیستمی مفید است که بتواند سیگنال‌های ورودی را دریافت کند، تحت تأثیر آنها، از یک حالت به حالت دیگر منتقل شود، آن را تا رسیدن سیگنال ورودی بعدی حفظ کند و سیگنال‌های خروجی تولید کند.

اگر مجموعه سیگنال های ورودی X، حالت های S و سیگنال های خروجی Y محدود باشند، یک DA محدود در نظر گرفته می شود. کامپیوتر داده های ورودی را به داده های خروجی پردازش می کند (نتیجه)، اما این نتیجه نه تنها با داده های ورودی، بلکه با وضعیت فعلی رایانه نیز مطابقت دارد. داده هایی که در حافظه کامپیوتر ذخیره می شوند، به عنوان مثال، نتایج محاسبات قبلی، برنامه های محاسباتی.

کار مخاطب هدف در زمان خودکار انجام می شود که با تعداد دوره های دریافت سیگنال های ورودی تعیین می شود.

خودکار انتزاعی یک مدل ریاضی از یک دستگاه گسسته است که دارای یک کانال ورودی است که دنباله‌هایی از نمادهای یک زبان، یک کانال خروجی را دریافت می‌کند که از آن دنباله‌هایی از نمادهای زبان دیگر گرفته می‌شود و در هر لحظه در حالتی قرار دارد. از زمان گسسته به صورت گرافیکی، یک خودکار انتزاعی در شکل ارائه شده است.

کلمات زبان ورودی را می توان با نمادهایی از مجموعه X=(x 1 , x 2 ,...x n ) نشان داد که به نام الفبای ورودی، و کلمات زبان خروجی نمادهایی از مجموعه Y=(y 1 ,y 2 ,...y p ) هستند که نامیده می شود الفبای خروجی. مجموعه حالت های خودکار S=(s 1 ,s 2 ,...s m ) نامیده می شود. الفبای ایالت ها.

مفهوم حالت ماشینبرای توصیف سیستم‌هایی استفاده می‌شود که سیگنال‌های خروجی آن‌ها نه تنها به سیگنال‌های ورودی در یک زمان معین، بلکه به برخی تاریخچه‌های قبلی نیز بستگی دارد. سیگنال هایی که قبلا در ورودی های سیستم دریافت شده اند. بنابراین، اتوماتای ​​دیجیتال به مدارهای متوالی اطلاق می شود که همانطور که قبلا ذکر شد دارای حافظه هستند. مفهوم حالت خودکار مربوط به برخی از خاطرات گذشته است، بنابراین معرفی این مفهوم اجازه می دهد تا زمان به عنوان یک متغیر صریح حذف شود و خروجی ها به عنوان تابعی از حالت ها و ورودی ها بیان شوند.

عملکرد یک خودکار انتزاعی باید در رابطه با فواصل زمانی خاص در نظر گرفته شود، زیرا هر بازه گسسته تیبا سیگنال خروجی آن y(t) مطابقت خواهد داشت. در نتیجه، عملکرد ماشین از طریق بازه های زمانی گسسته با مدت زمان محدود در نظر گرفته می شود. در تئوری انتزاعی اتوماتای ​​دیجیتال، اعتقاد بر این است که سیگنال های ورودی در شروع هر یک بر روی یک خودکار سنکرون عمل می کنند. من- آن بازه (کوانتوم) زمان تخصیص یافته توسط پالس هماهنگ سازی (چرخه) مربوطه، و تغییر در حالت های داخلی دستگاه در فواصل زمانی بین پالس های همگام سازی مجاور رخ می دهد، زمانی که هیچ تاثیری از سیگنال های ورودی وجود ندارد.

مفهوم "وضعیت" برای ایجاد وابستگی عملکردی نمادها و/یا کلمات زبان خروجی تولید شده توسط ماشین به نمادها و/یا کلمات زبان ورودی زمانی که ماشین یک الگوریتم معین را پیاده‌سازی می‌کند، استفاده می‌شود. برای هر حالت sОS خودکار و برای هر نماد xОX در لحظه زمان گسسته [t]، نماد yОY در خروجی دستگاه تولید می شود. این وابستگی توسط تابع خروجی خودکار j تعیین می شود. برای هر حالت فعلی sОS خودکار و برای هر نماد xОX در لحظه زمان گسسته [t]، خودکار به حالت بعدی sОS می رود. این وابستگی توسط تابع انتقال خودکار y تعیین می شود. عملکرد خودکار شامل تولید دو دنباله است: دنباله ای از حالت های بعدی خودکار (s 1[s 2s 3 ...) و دنباله ای از نمادهای خروجی (y 1 y 2 y 3 ...) که برای دنباله نمادها (x 1 x 2 x 3...) در لحظه های زمان گسسته t = 1،2،3، ... باز می شوند. ، در پرانتز - دنباله ای از حروف الفبای X، Y و S.

بنابراین مدل ریاضی یک خودکار محدود یک جبر سه پایه است که حامل های آن سه مجموعه X، Y و S و عملیات دو تابع j و y هستند.

در این مقاله، اصطلاح "ماشین حالت محدود" به الگوریتمی اطلاق می شود که می تواند در یکی از تعداد کمی از حالت ها باشد. "وضعیت" شرایط خاصی است که یک رابطه معین بین سیگنال های ورودی و خروجی و همچنین سیگنال های ورودی و حالت های بعدی را تعریف می کند. یک خواننده هوشمند بلافاصله متوجه خواهد شد که ماشین های حالت محدود که در این مقاله توضیح داده شده است ماشین های Mealy هستند. ماشین Mealy یک ماشین حالت محدود است که در آن خروجی ها توابعی از وضعیت فعلی و سیگنال ورودی هستند، برخلاف ماشین مور که در آن خروجی ها فقط توابع حالت هستند. در هر دو حالت، حالت بعدی تابعی از وضعیت فعلی و سیگنال ورودی است.

بیایید به مثالی از یک ماشین حالت محدود ساده نگاه کنیم. تصور کنید که در یک رشته متنی باید دنباله کاراکتر "//" را تشخیص دهید. شکل 1 نشان می دهد که چگونه این کار با استفاده از یک ماشین حالت انجام می شود. اولین ظاهر یک اسلش سیگنال خروجی تولید نمی کند، بلکه باعث می شود دستگاه به حالت دوم برود. اگر در حالت دوم دستگاه اسلش پیدا نکرد، به حالت اول برمی گردد، زیرا نیاز به وجود 2 اسلش پشت سر هم دارد. اگر اسلش دوم پیدا شود، دستگاه یک سیگنال "آماده" صادر می کند.

دریابید که مشتری به چه چیزی نیاز دارد.

یک نمودار انتقال حالت ایجاد کنید

رمزگذاری "اسکلت" یک ماشین حالت بدون جزئیات عملیات شاخه.

مطمئن شوید که انتقال ها به درستی کار می کنند.

در مورد جزئیات انتقال دقیق باشید.

امتحان بده

نمونه ماشین حالت

بیایید به مثال جالب‌تری از یک ماشین حالت نگاه کنیم - برنامه‌ای که عقب‌نشینی و گسترش ارابه فرود هواپیما را کنترل می‌کند. اگرچه اکثر هواپیماها این روش را با استفاده از مکانیزم کنترل الکتروهیدرولیک انجام می دهند (به سادگی به دلیل اینکه کامپیوتری در هواپیما وجود ندارد)، در برخی موارد، مانند هواپیماهای بدون سرنشین، ارزش استفاده از کنترل نرم افزاری را دارد.

ابتدا بیایید به تجهیزات نگاه کنیم. ارابه فرود هواپیما از یک دنده دماغه، یک ارابه فرود چپ اصلی و یک ارابه فرود سمت راست اصلی تشکیل شده است. آنها توسط یک مکانیسم هیدرولیک هدایت می شوند. یک پمپ هیدرولیک با هدایت الکتریکی فشار را به محرک برق می رساند. با استفاده از نرم افزار، پمپ روشن یا خاموش می شود. رایانه موقعیت سوپاپ جهت را - "پایین" یا "بالا" - تنظیم می کند تا فشار برای بالا بردن یا پایین آوردن ارابه فرود فراهم شود. هر یک از تکیه گاه های شاسی دارای یک سوئیچ محدود است: یکی از آنها در صورت بالا آمدن شاسی بسته می شود، دیگری - اگر در موقعیت پایین قفل شده باشد. برای تعیین اینکه آیا هواپیما روی زمین است یا خیر، زمانی که وزن هواپیما روی دنده دماغه باشد، یک سوئیچ محدود روی دنده دماغه بسته می شود. کنترل‌های خلبان شامل یک بازوی ارابه فرود بالا/پایین و سه چراغ (یکی برای هر پا) است که می‌تواند خاموش شود، سبز (موقعیت پایین) یا قرمز (موقعیت رفتن).

حالا بیایید به سمت توسعه یک ماشین حالت محدود برویم. اولین و سخت ترین مرحله درک انتظارات واقعی مشتری است. یکی از مزایای ماشین حالت محدود این است که برنامه نویس را مجبور می کند تا در تمام موارد ممکن فکر کند و در نتیجه تمام اطلاعات مورد نیاز را از مشتری دریافت کند. چرا این مرحله را سخت ترین مرحله می دانم؟ و چند بار به شما شرح وظایف مشابه این داده شده است: اگر هواپیما روی زمین است، ارابه فرود را جمع نکنید.

البته این مهم است، اما مشتری معتقد است که همه چیز به همین جا ختم می شود. بقیه موارد چطور؟ آیا جمع کردن ارابه فرود در لحظه بلند شدن هواپیما از زمین کافی است؟ اگر هواپیما روی دست انداز باند فرودگاه بپرد چه؟ اگر خلبان هنگام پارک کردن، چوب دنده را به سمت بالا حرکت دهد و در نتیجه شروع به بلند شدن کند، چه؟ آیا در این حالت باید ارابه فرود را بالا برد؟

یکی از مزیت‌های فکر کردن بر حسب ماشین حالت این است که می‌توانید به سرعت نمودار انتقال حالت را روی یک تابلوی طرح‌نما، درست در مقابل مشتری ترسیم کنید و کل فرآیند را با او طی کنید. تعیین زیر برای انتقال حالت پذیرفته شده است: "رویدادی که باعث انتقال شد" / "سیگنال خروجی در نتیجه انتقال". اگر ما فقط آنچه را که مشتری در ابتدا خواسته بود توسعه داده بودیم ("اگر هواپیما روی زمین است ارابه فرود را جمع نکنید")، ماشین نشان داده شده در شکل 2 را دریافت می کردیم.

هنگام ایجاد نمودار انتقال حالت (یا هر الگوریتم دیگری)، موارد زیر را در نظر داشته باشید:

کامپیوترها در مقایسه با تجهیزات مکانیکی بسیار سریع کار می کنند

مهندس مکانیکی که توضیح می دهد که چه کاری باید انجام شود، ممکن است به اندازه شما درباره کامپیوترها و الگوریتم ها اطلاعات نداشته باشد. و این نیز یک چیز مثبت است، در غیر این صورت نیازی به شما نخواهید داشت!

اگر یک قطعه مکانیکی یا الکتریکی خراب شود، برنامه شما چگونه عمل می کند؟

یک ماشین حالت بر اساس آنچه مشتری واقعاً نیاز دارد در شکل 3 نشان داده شده است. در اینجا می خواهیم از جمع شدن ارابه فرود هواپیما تا زمانی که قطعاً در هوا باشد جلوگیری کنیم. برای انجام این کار، پس از باز کردن سوئیچ فرود، دستگاه برای چند ثانیه منتظر می ماند. ما همچنین می‌خواهیم به لبه بالارونده اهرم خلبان پاسخ دهیم تا سطح، که اگر کسی اهرم را در حالی که هواپیما در پارک است حرکت دهد، از مشکل جلوگیری می‌کند. جمع کردن یا امتداد دادن ارابه فرود چند ثانیه طول می کشد و باید برای شرایطی آماده باشیم که خلبان در این عملیات نظر خود را تغییر دهد و اهرم را در جهت مخالف حرکت دهد. همچنین توجه داشته باشید که اگر هواپیما در حالت "در انتظار برخاستن" دوباره فرود بیاید، تایمر دوباره راه اندازی می شود و ارابه فرود تنها در صورتی جمع می شود که هواپیما به مدت 2 ثانیه در هوا باشد.

پیاده سازی یک ماشین حالت محدود

لیست 1 پیاده سازی من از ماشین حالت نشان داده شده در شکل 3 است. بیایید برخی از جزئیات کد را مورد بحث قرار دهیم.

/*فهرست 1*/

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

/*این آرایه حاوی اشاره گرهایی به توابع فراخوانی شده در حالت های خاص است*/

خالی(*state_table)() = (GearDown، WtgForTakeoff، RaisingGear، GearUp، LoweringGear);

State_Type curr_state;

InitializeLdgGearSM();

/*قلب ماشین این حلقه بی پایان است. تابع مربوطه

وضعیت فعلی، یک بار در هر تکرار فراخوانی می شود */

در حالی که (1) {

state_table();

DecrementTimer();

خالی InitializeLdgGearSM( خالی )

curr_state = GEAR_DOWN;

/*توقف تجهیزات، خاموش کردن چراغ ها و غیره*/

خالی GearDown( خالی )

/* اگر هواپیما به حالت انتظار بروید

روی زمین نبود و فرمان بلند کردن ارابه فرود را دریافت کرد*/

اگر((اهرم_دنده == بالا) && (اهرم_دنده_قبلی == پایین) && (سوئیچ_دنده == بالا)) (

curr_state = WTG_FOR_TKOFF;

prev_gear_lever = اهرم_دنده;

خالی RaisingGear( خالی )

اگر((nosegear_is_up == MADE) && (leftgear_is_up == MADE) && (rtgear_is_up == MADE)) (

curr_state = GEAR_UP;

/*اگر خلبان تصمیم خود را تغییر داد، به حالت "ارابه فرود پایین تر" بروید*/

اگر(اهرم_دنده == پایین) (

curr_state = LOWERING_GEAR;

خالی GearUp( خالی )

/*اگر خلبان اهرم را به موقعیت "پایین" برد،

به حالت «پایین‌آوردن ارابه فرود» می‌رویم*/

اگر(اهرم_دنده == پایین) (

curr_state = LOWERING_GEAR;

خالی WtgForTakeoff( خالی )

/* قبل از بالا بردن ارابه فرود صبر کنید.*/

اگر(تایمر<= 0.0) {

curr_state = RAISING_GEAR;

/*اگر دوباره لمس کردیم یا خلبان نظرش را تغییر داد، همه چیز را از نو شروع کنید*/

اگر((squat_switch == DOWN) || (اهرم_دنده == DOWN)) (

curr_state = GEAR_DOWN;

/* نمی خواهید از او بخواهید که اهرم را دوباره تغییر دهد

این فقط یک جهش بود.*/

prev_gear_lever = DOWN;

خالی Lowering Gear( خالی )

اگر(اهرم_دنده == بالا) (

curr_state = RAISING_GEAR;

اگر((nosegear_is_down == MADE) && (leftgear_is_down == MADE) &&(rtgear_is_down == MADE)) (

curr_state = GEAR_DOWN;

ابتدا، ممکن است متوجه شوید که عملکرد هر حالت توسط یک تابع C جداگانه پیاده سازی می شود. البته، می‌توان یک خودکار را با استفاده از یک دستور سوئیچ با یک مورد جداگانه برای هر حالت پیاده‌سازی کرد، اما این می‌تواند منجر به عملکرد بسیار طولانی شود (10-20 خط کد در هر حالت برای هر یک از 20-30 حالت) . اگر کد را در مراحل پایانی آزمایش تغییر دهید، ممکن است منجر به خطا شود. ممکن است هرگز یک عبارت break در پایان یک پرونده را فراموش نکرده باشید، اما چنین مواردی برای من اتفاق افتاده است. اگر برای هر حالت یک تابع جداگانه داشته باشید، کد یک حالت هرگز در کد دیگری ختم نمی شود.

برای جلوگیری از استفاده از دستور سوئیچ، من از آرایه ای از اشاره گرها برای بیان توابع استفاده می کنم و متغیر مورد استفاده به عنوان شاخص آرایه را از نوع enum اعلام می کنم.

برای سادگی، سخت‌افزار ورودی/خروجی مسئول خواندن وضعیت سوئیچ‌ها، روشن و خاموش کردن پمپ‌ها و غیره به صورت متغیرهای ساده نشان داده می‌شود. فرض می شود که این متغیرها "آدرس های جادویی" هستند که از طریق ابزارهای نامرئی با سخت افزار مرتبط هستند.

نکته واضح دیگر این است که کد در این مرحله واقعاً مهم نیست. او به سادگی از یک حالت به حالت دیگر حرکت می کند. این یک مرحله میانی مهم است و نباید نادیده گرفته شود. به هر حال، خوب است که دستورات چاپی را بین دستورالعمل های کامپایل شرطی (#ifdef DEBUG .. #endif) اضافه کنید که وضعیت فعلی و مقادیر سیگنال های ورودی را چاپ کند.

کلید موفقیت در کدی نهفته است که باعث انتقال حالت می شود، یعنی. تعیین می کند که ورود داده ها اتفاق افتاده است.

اگر کد از تمام حالت ها به درستی عبور کند، مرحله بعدی نوشتن "پر کردن" کد است، یعنی دقیقاً چه چیزی سیگنال خروجی را تولید می کند. به یاد داشته باشید که هر انتقال دارای یک سیگنال ورودی (رویدادی که باعث آن شد) و یک سیگنال خروجی (دستگاه ورودی/خروجی سخت افزاری، مانند مثال ما) دارد. اغلب مفید است که این را در قالب یک جدول انتقال حالت ثبت کنیم.

در جدول انتقال وضعیت، یک ردیف برای هر انتقال حالت وجود دارد.

هنگام کدنویسی یک ماشین حالت، سعی کنید قدرت آن را حفظ کنید - مطابقت واضحی بین نیازهای مشتری و کد. ممکن است لازم باشد جزئیات سخت افزاری را در یک لایه تابع دیگر پنهان کنید، برای مثال، کد ماشین حالت تا حد ممکن شبیه جدول انتقال حالت و نمودار انتقال حالت باشد. این تقارن به جلوگیری از خطاها کمک می کند و توضیح می دهد که چرا ماشین های حالت بخش مهمی از زرادخانه برنامه نویس سیستم های جاسازی شده هستند. البته، می‌توانید با چک‌باکس‌ها و تعداد بی‌نهایت عبارات تودرتو به همان اثر دست پیدا کنید، اما این کار ردیابی کد و مقایسه آن با خواسته‌های مشتری را بسیار دشوار می‌کند.

قطعه کد در لیست 2 تابع RaisingGear() را گسترش می دهد. توجه داشته باشید که کد تابع RaisingGear() با هدف منعکس کردن 2 ردیف جدول انتقال برای وضعیت Raising Gear است.

خالی RaisingGear( خالی )

/*بعد از بالا آمدن تمامی سوئیچ ها به حالت “شاسی بلند شده” می رویم*/

اگر((nosegear_is_up == MADE) && (leftgear_is_up == MADE) && (rtgear_is_up == MADE)) (

پمپ_موتور = خاموش;

چراغ های دنده = خاموش;

curr_state = GEAR_UP;

/*اگر خلبان نظر خود را تغییر داد، شروع به جمع کردن ارابه فرود کنید*/

اگر(اهرم_دنده == پایین) (

پمپ_جهت = DOWN;

curr_state = GEAR_LOWERING;

به یاد داشته باشید که از شرایط نهفته خودداری کنید. حالت پنهان زمانی رخ می دهد که به دلیل تنبلی، به جای اضافه کردن یک حالت خاص، سعی کنید یک حالت فرعی مشروط اضافه کنید. برای مثال، اگر کد شما سیگنال ورودی یکسان را به روش‌های متفاوتی پردازش می‌کند (یعنی انتقال حالت‌های متفاوتی را برحسب حالت ایجاد می‌کند)، در این صورت یک حالت پنهان است. در این مورد، من نمی خواهم بدانم که آیا این حالت باید به دو قسمت تقسیم شود؟ استفاده از حالت های پنهان، مزیت استفاده از ماشین حالت را نفی می کند.

به عنوان یک عمل، می‌توانید با اضافه کردن یک بازه زمانی به چرخه جمع‌کردن یا تمدید ارابه فرود، ماشین حالتی را که ما به آن نگاه کردیم، تمدید کنید، زیرا... مهندس مکانیک نمی خواهد پمپ هیدرولیک بیش از 60 ثانیه کار کند. اگر چرخه به پایان برسد، خلبان باید با تغییر چراغ سبز و قرمز هشدار داده شود و باید بتواند اهرم را دوباره حرکت دهد تا دوباره تلاش کند. همچنین ممکن است بخواهید از یک مهندس مکانیک فرضی بپرسید که تغییر جهت پمپ در حین کار کردن چه تاثیری بر پمپ دارد، زیرا در دو مورد زمانی اتفاق می افتد که خلبان نظر خود را تغییر دهد. البته مکانیک می گوید منفی است. سپس چگونه می توانید دستگاه حالت را تغییر دهید تا به سرعت پمپ را هنگام تغییر جهت متوقف کند؟

تست ماشین دولتی

زیبایی الگوریتم های کدنویسی به عنوان ماشین های حالت این است که طرح آزمایشی تقریباً به طور خودکار خودش را می نویسد. تنها کاری که شما باید انجام دهید این است که از طریق هر انتقال حالت عبور کنید. من معمولاً این کار را با یک نشانگر در دست انجام می‌دهم و فلش‌های روی نمودار انتقال حالت را هنگام گذراندن آزمون خط می‌کشم. این یک راه خوب برای جلوگیری از "حالت های پنهان" است - آنها در تست ها بیشتر از حالت های خاص نادیده گرفته می شوند.

این نیاز به صبر قابل توجه و قهوه زیاد دارد، زیرا حتی یک دستگاه حالت متوسط ​​​​می تواند تا 100 انتقال مختلف داشته باشد. به هر حال، تعداد انتقال ها یک راه عالی برای اندازه گیری پیچیدگی یک سیستم است. مورد دوم توسط نیازهای مشتری تعیین می شود و دستگاه دولتی دامنه آزمایش را آشکار می کند. با یک رویکرد کمتر سازماندهی شده، میزان آزمایش مورد نیاز ممکن است به همان اندازه چشمگیر باشد، اما شما به سادگی آن را نمی دانید.

استفاده از عبارات چاپی در کد شما بسیار راحت است که وضعیت فعلی و مقادیر سیگنال های ورودی و خروجی را نشان می دهد. این به شما امکان می‌دهد به راحتی آنچه را که قانون طلایی تست نرم‌افزار بیان می‌کند مشاهده کنید: بررسی کنید که برنامه کاری را که در نظر گرفته شده انجام می‌دهد، و همچنین اینکه هیچ کار غیرضروری انجام نمی‌دهد. به عبارت دیگر، آیا شما فقط خروجی هایی را که انتظار دارید دریافت می کنید و فراتر از آن چه اتفاقی می افتد؟ آیا انتقال حالت "دشوار" وجود دارد، به عنوان مثال. بیان می کند که به طور تصادفی تنها برای یک تکرار از حلقه عبور می کند؟ آیا زمانی که شما انتظار ندارید خروجی ها تغییر می کنند؟ در حالت ایده‌آل، خروجی پرینت‌اف‌های شما باید به‌طور محسوسی شبیه جدول انتقال حالت باشد.

در نهایت - و این در مورد هر نرم افزار تعبیه شده، نه فقط نرم افزار مبتنی بر ماشین دولتی - صدق می کند - اولین باری که نرم افزار را روی سخت افزار واقعی اجرا می کنید بسیار مراقب باشید. اشتباه گرفتن قطبیت سیگنال بسیار آسان است - "اوه، من فکر کردم 1 به معنای ارابه فرود بالا و 0 به معنای ارابه فرود پایین است." در بسیاری از موارد، دستیار سخت‌افزار من از یک "سوئیچ مرغ" موقت برای محافظت از اجزای ارزشمند استفاده می‌کند تا زمانی که مطمئن شود که نرم‌افزار من کارها را در جهت درست حرکت می‌دهد.

راه اندازی

وقتی تمام نیازهای مشتری برآورده شد، می توانم یک ماشین دولتی با پیچیدگی مشابه را در چند روز راه اندازی کنم. تقریباً همیشه ماشین ها کاری را که من می خواهم انجام می دهند. البته سخت ترین کار این است که بفهمیم مشتری دقیقا چه می خواهد و مطمئن شویم که مشتری خودش می داند چه می خواهد. دومی خیلی بیشتر طول می کشد!

مارتین گومز یک برنامه نویس در آزمایشگاه فیزیک کاربردی در دانشگاه جان هاپکینز است. درگیر توسعه نرم افزار برای پشتیبانی از پروازهای فضاپیماهای تحقیقاتی. 17 سال در زمینه توسعه سیستم های جاسازی شده کار کرد. مارتین دارای مدرک لیسانس علوم در مهندسی هوافضا و کارشناسی ارشد در مهندسی برق از دانشگاه کرنل است.

این مقاله ماشین‌های حالت محدود ساده و پیاده‌سازی آنها در C++ با استفاده از ساختارهای سوئیچ، جداول زمان اجرا و کتابخانه Boost Statechart را مورد بحث قرار می‌دهد.

معرفی

به طور کلی، یک ماشین حالت محدود، از دید کاربر، یک جعبه سیاه است که می توان چیزی را به آن منتقل کرد و چیزی را از آنجا دریافت کرد. این یک انتزاع بسیار راحت است که به شما امکان می دهد یک الگوریتم پیچیده را پنهان کنید و ماشین های حالت محدود نیز بسیار کارآمد هستند.

ماشین های حالت محدود در قالب نمودارهایی متشکل از حالت ها و انتقال ها به تصویر کشیده می شوند. بگذارید با یک مثال ساده توضیح دهم:

همانطور که احتمالا حدس زدید، این نمودار حالت یک لامپ است. حالت اولیه با یک دایره سیاه نشان داده می شود، انتقال با فلش ها، برخی از فلش ها برچسب گذاری می شوند - اینها رویدادهایی هستند که پس از آن دستگاه به حالت دیگری می رود. بنابراین، بلافاصله از حالت اولیه، خود را در حالت می یابیم چراغ خاموش- لامپ روشن نمی شود. اگر دکمه را فشار دهید، دستگاه حالت خود را تغییر می دهد و پیکان مشخص شده را دنبال می کند دکمه فشاری، در یک حالت نور روشن- لامپ روشن است شما می توانید از این حالت، دوباره به دنبال فلش، پس از فشار دادن دکمه، به حالت حرکت کنید چراغ خاموش.

جداول انتقال نیز به طور گسترده استفاده می شود:

کاربرد عملی ماشین های اتوماتیک

ماشین های حالت محدود به طور گسترده ای در برنامه نویسی استفاده می شوند. به عنوان مثال، تصور عملکرد یک دستگاه در قالب یک ماشین خودکار بسیار راحت است. این کار کد را ساده‌تر می‌کند و آزمایش و نگهداری آن را آسان‌تر می‌کند.

همچنین، ماشین‌های حالت محدود برای نوشتن انواع تجزیه‌کننده‌ها و تحلیل‌گرهای متن استفاده می‌شوند؛ با کمک آن‌ها می‌توانید به طور موثر زیر رشته‌ها را جستجو کنید؛ عبارات منظم نیز به ماشین حالت محدود ترجمه می‌شوند.

به عنوان مثال، ما یک خودکار برای شمارش اعداد و کلمات در متن پیاده سازی خواهیم کرد. برای شروع، اجازه دهید توافق کنیم که یک عدد دنباله ای از اعداد از 0 تا 9 با طول دلخواه در نظر گرفته شود که با کاراکترهای فضای خالی (فضا، برگه، خوراک خط) احاطه شده است. یک کلمه دنباله ای با طول دلخواه متشکل از حروف و همچنین احاطه شده توسط کاراکترهای فضای خالی در نظر گرفته می شود.

بیایید به نمودار نگاه کنیم:

از حالت اولیه به حالت می رسیم شروع کنید. ما کاراکتر فعلی را بررسی می کنیم و اگر یک حرف باشد، به حالت می رویم کلمهدر امتداد فلش مشخص شده به عنوان حرف. این حالت فرض می کند که ما در حال حاضر در حال بررسی یک کلمه هستیم؛ تجزیه و تحلیل نمادهای بیشتر یا این فرض را تأیید می کند یا آن را رد می کند. بنابراین، کاراکتر بعدی را در نظر بگیرید، اگر یک حرف است، وضعیت تغییر نمی کند (به فلش دایره ای که به عنوان علامت گذاری شده توجه کنید حرف). اگر کاراکتر یک حرف نیست، بلکه با یک کاراکتر فضای خالی مطابقت دارد، به این معنی است که فرض درست بود و کلمه را پیدا کردیم (ما از فلش پیروی می کنیم فضادر یک ایالت شروع کنید). اگر کاراکتر نه حرف است و نه فاصله، در این فرض اشتباه کرده ایم و دنباله مورد نظر ما یک کلمه نیست (فلش را دنبال کنید. ناشناختهدر یک ایالت پرش کنید).

قادر پرش کنیدما آنجا هستیم تا زمانی که با یک کاراکتر فضای خالی مواجه شویم. پس از شناسایی شکاف، پیکان را دنبال می کنیم فضادر یک ایالت شروع کنید. این برای رد کامل خطی که با الگوی جستجوی ما مطابقت ندارد ضروری است.

پس از ورود به ایالت شروع کنید، چرخه جستجو از ابتدا تکرار می شود. شاخه تشخیص اعداد مشابه شاخه تشخیص کلمه است.

خودکار با استفاده از دستورالعمل های سوئیچ

حالت اول ممکن است:

پس از آن ما روی خط تکرار می کنیم و نماد فعلی را به داخل دستگاه می کشیم. خود خودکار یک دستورالعمل سوئیچ است که ابتدا یک انتقال به بخش وضعیت فعلی را انجام می دهد. در داخل بخش یک ساختار if-else وجود دارد که بسته به رویداد (یک نماد ورودی)، وضعیت فعلی را تغییر می دهد:

const size_t طول = text.length(); برای (size_t i = 0 ; i ! = طول; ++ i) ( const char current = text[i] ; switch (وضعیت) ( case State_Start: if (std:: isdigit (current)) ( state = State_Number; ) else if (std:: isalpha (جاری)) (state = State_Word; ) break ; case State_Number: if (std:: isspace (current)) (

در اینجا ما به نمودار نگاه می کنیم - وضعیت فعلی عدد، رویداد فضا(یک کاراکتر فاصله مشاهده می شود)، به این معنی که عدد پیدا شده است:

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

نتیجه:

بازدهی بالا

سهولت پیاده سازی برای الگوریتم های ساده

- نگهداری مشکل است

تفسیر زمان اجرا

ایده این رویکرد ساده است - شما باید یک جدول انتقال ایجاد کنید، آن را پر کنید، و سپس، زمانی که یک رویداد رخ می دهد، وضعیت بعدی را در جدول پیدا کنید و انتقال را انجام دهید:

enum رویدادها (Event_Space، Event_Digit، Event_Letter، Event_Unknown) ; void ProcessEvent (رویداد رویدادها) ; ... struct Transition ( State BaseState_; Events Event_; State TargetState_; ) ; void AddTransition (ایالات از ایالت، رویداد رویدادها، ایالات به ایالت) ; ...typedef std::vector< transition>TransitionTable; TransitionTable Transitions_; ایالات CurrentState_;

پر کردن جدول:

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) ;

کاملاً واضح معلوم شد. قیمت برای شفافیت، عملکرد کندتر دستگاه است، که، با این حال، اغلب مهم نیست.

به طوری که ماشین، زمانی که رویدادهای خاصی رخ می دهد، بتواند کدی را مطلع کند، می توانید آن را با اطلاعات مربوط به انتقال به ساختار اضافه کنید ( انتقالنشانگر تابع ( عمل) که نامیده می شود:

typedef void (DynamicMachine::* Action) () ; struct Transition ( State BaseState_; Events Event_; State TargetState_; Action Action_; ) ; ... void AddTransition(States fromState, Events event, State toState, Action action) ; ...AddTransition(State_Number، Event_Space، State_Start و DynamicMachine::FoundNumber) ;

نتیجه:

انعطاف پذیری و دید

نگهداری راحت تر

- عملکرد کمتر در مقایسه با بلوک های سوئیچ

تفسیر زمان اجرا بهینه سازی سرعت

آیا می توان دید را با سرعت ترکیب کرد؟ بعید است که بتوان یک ماشین اتوماتیک را به اندازه یک ماشین اتوماتیک بر اساس بلوک های سوئیچ کارآمد ساخت، اما می توان شکاف را از بین برد. برای انجام این کار، باید یک ماتریس از جدول بسازید، به طوری که برای به دست آوردن اطلاعات مربوط به انتقال، نیازی به جستجو نداشته باشید، بلکه انتخابی را بر اساس وضعیت و شماره رویداد انجام دهید:

نتیجه با هزینه مصرف حافظه به دست می آید.

نتیجه:

انعطاف پذیری، دید

تاثير گذار

- مصرف حافظه (به احتمال زیاد ناچیز)

استیتچارت را تقویت کنید

ما چندین روش برای پیاده سازی یک ماشین حالت را خودتان مورد بحث قرار دادیم. برای تغییر، پیشنهاد می کنم کتابخانه ای برای ساخت ماشین آلات از Boost در نظر بگیرید. این کتابخانه بسیار قدرتمند است؛ قابلیت های ارائه شده به شما این امکان را می دهد که ماشین های حالت محدود بسیار پیچیده بسازید. ما به سرعت به آن نگاه خواهیم کرد.

بنابراین، ابتدا رویدادها را تعریف می کنیم:

رویدادهای فضای نام ( struct Digit : boost::statechart::event< Digit>( ) ؛ struct Letter : boost::statechart::event< Letter>( ) ؛ struct Space: boost::statechart::event< Space>( ) ؛ struct Unknown : boost::statechart::event< Unknown> { } ; }

خود ماشین (توجه داشته باشید که پارامتر الگوی دوم حالت اولیه است):

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

و خود ایالت ها. در داخل حالت ها، لازم است که نوع انتقال را توصیف کنیم ( واکنش ها، و اگر چندین انتقال وجود دارد، آنها را در لیست نوع boost::mpl::list لیست کنید. پارامتر قالب دوم ساده_حالت- نوع توصیف ماشین. انتقال ها با پارامترهای الگوی انتقال، یک جفت، توصیف می شوند رویداد - ایالت بعدی:

وضعیت های فضای نام ( ساختار Start : boost::statechart::simple_state< Start, Machine> < boost:: statechart :: transition < Events:: Digit , States:: Number >< Events:: Letter , States:: Word >> واکنش ها؛ ) ؛ struct Number : boost::statechart::simple_state< Number, Machine>( تقویت typedef::mpl::list< boost:: statechart :: transition < Events:: Space , States:: Start >, boost::statetechart::transition< Events:: Letter , States:: Skip >, boost::statetechart::transition< Events:: Unknown , States:: Skip >> واکنش ها؛ ) ؛ struct Word: boost::statechart::simple_state< Word, Machine>( تقویت typedef::mpl::list< boost:: statechart :: transition < Events:: Space , States:: Start >, boost::statetechart::transition< Events:: Digit , States:: Skip >, boost::statetechart::transition< Events:: Unknown , States:: Skip >> واکنش ها؛ ) ؛ struct Skip: boost::statechart::simple_state< Skip, Machine>( typedef boost::statechart::transition< Events:: Space , States:: Start >واکنش ها؛ ) ؛ )

دستگاه ساخته شده است، تنها چیزی که باقی می ماند این است که آن را مقداردهی کنید و می توانید از آن استفاده کنید:

ماشین آلات؛ machine.initiate(); ...machine.process_event(Events::Space());

نتیجه:

انعطاف پذیری، قابلیت گسترش

- بهره وری

کارایی

من یک برنامه آزمایشی برای بررسی عملکرد ماشین های ساخته شده نوشتم. من یک متن ~ 17 مگابایتی را از طریق دستگاه ها اجرا کردم. در اینجا نتایج این اجرا آمده است:

در حال بارگذاری متن طول متن: 17605548 بایت 0.19 ثانیه Running BoostMachine Words: 998002، اعداد: 6816 0.73 s Running DynamicMachine Words: 998002، اعداد: 6816 0.56 0.56 0.56 s ورد 8، 0.56 0.56 s 16 0.29 s اجرای SimpleMachine Words: 998002، اعداد : 6816 0.20 s

آنچه که بررسی نشده باقی مانده است

هنوز چندین پیاده سازی از ماشین های حالت محدود بدون پوشش باقی مانده است (من http://www.rsdn.ru/article/alg/Static_Finite_State_Machine.xml و http://www.rsdn.ru/article/alg/FiniteStateMachine.xml را توصیه می کنم) ، ژنراتورهایی که ماشین ها را از توضیحات می سازند، کتابخانه Meta State Machine از Boost نسخه 1.44.0، و همچنین توضیحات رسمی ماشین های حالت محدود. خواننده کنجکاو می تواند به تنهایی با همه موارد فوق آشنا شود.

نظریه اتوماتا شاخه ای از ریاضیات گسسته است که مدل های مبدل اطلاعات گسسته را مطالعه می کند. چنین مبدل‌هایی هم دستگاه‌های واقعی (کامپیوتر، موجودات زنده) و هم دستگاه‌های خیالی (نظریه‌های بدیهی، ماشین‌های ریاضی) هستند. اساساً، یک ماشین حالت محدود را می توان به عنوان یک دستگاه مشخص کرد م با داشتن کانال های ورودی و خروجی و در هر یک از لحظات گسسته زمانی که لحظه های ساعت نامیده می شود در یکی از حالت های نهایی قرار دارد.

توسط کانال ورودی در هر لحظه از زمان تی =1، 2، ... به دستگاه م سیگنال های ورودی می رسند (از مجموعه محدودی از سیگنال ها). قانون تغییر حالت در زمان بعدی بسته به سیگنال ورودی و وضعیت دستگاه در زمان فعلی تنظیم می شود. سیگنال خروجی به وضعیت و سیگنال ورودی در زمان جاری بستگی دارد (شکل 1).

ماشین حالت محدود یک مدل ریاضی از دستگاه های پردازش اطلاعات گسسته واقعی است.

ماشین حالت سیستم نامیده می شود A= (ایکس , س , Y ,  ,  )، جایی که ایکس , س , Y مجموعه های محدود غیر خالی دلخواه هستند و  و  - توابع، که از جمله:

یک دسته از ایکس ={آ 1 , ..., آ متر ) نامیده میشود الفبای ورودی ، و عناصر آن هستند سیگنال های ورودی ، دنباله آنها در است در کلمات رایج ;

یک دسته از س ={q 1 , ..., q n ) نامیده میشود بسیاری از ایالت ها خودکار و عناصر آن - ایالت ها ;

یک دسته از Y ={ب 1 , ..., ب پ ) نامیده میشود الفبای خروجی ، عناصر آن هستند سیگنال های خروجی ، دنباله آنها هستند کلمات خروجی ;

تابع  : ایکس  س س تماس گرفت تابع انتقال ;

تابع  :ایکس  س Y تماس گرفت تابع خروجی .

بدین ترتیب،  (ایکس , q )س ,  (ایکس , q )Y برای  ایکس ایکس , q س .

یک ماشین حالت محدود با یک دستگاه خیالی مرتبط است که به شرح زیر عمل می کند. می تواند در یکی از چندین ایالت باشد س ، سیگنال های مختلف را درک کنید ایکس و سیگنال های مختلف را صادر می کند Y .

2. روش های تعیین یک ماشین حالت محدود

چندین روش معادل برای تعریف اتوماتای ​​انتزاعی وجود دارد که از میان آنها می توان سه راه را نام برد: جدولی , هندسی و کاربردی .

2.1. وظیفه جدولی دستگاه

از تعریف خودکار چنین بر می آید که همیشه می توان آن را با یک جدول با دو ورودی شامل تی خطوط و پ ستون ها، جایی که در تقاطع ستون q و رشته ها آ مقادیر تابع هستند  (آ من , q j ),  (آ من , q j ).

q آ	q 1		q j		q n
آ 1	(آ 1 , q 1),  (آ 1 , q 1)		(آ 1 , q j ),  (آ 1 , q j )		(آ 1 , q n ),  (آ 1 , q n )
آ من	(آ من , q 1),  (آ من , q 1)		(آ من , q j ),  (آ من , q j )		(آ من , q n ),  (آ من , q n )
آ متر	(آ متر , q 1),  (آ متر , q 1)		(آ متر , q j ),  (آ متر , q j )		(آ متر , q n ),  (آ متر , q n )

2.2. تعیین خودکار با استفاده از نمودار مور

راه دیگر برای تعریف ماشین حالت محدود، گرافیکی است، یعنی استفاده از نمودار. خودکار به عنوان یک گراف جهت دار با برچسب نشان داده شده است جی(س , D ) با رئوس زیاد س و قوس های زیادی D ={(q j ,  (آ من , q j ))| q j س , آ من ایکس ، در حالی که قوس ( q j ,  (آ من , q j )) با جفت ( آ من ,  (آ من , q j )). بنابراین، با این روش، حالات ماشین با دایره هایی که نمادهای حالت در آنها نوشته شده است، نشان داده می شود q j (j = 1, …, n ). از هر دایره انجام می شود تی فلش ها (لبه های جهت دار) یک به یک مربوط به کاراکترهای الفبای ورودی ایکس ={آ 1 , ..., آ متر ). فلش مربوط به حرف آ من ایکس و از دایره خارج شد q j س ، به جفت نسبت داده می شود ( آ من ,  (آ من , q j ))، و این فلش به دایره مربوطه منتهی می شود  (آ من , q j ).

رسم حاصل نامیده می شود نمودار خودکار یا، نمودار مور . برای ماشین های نه چندان پیچیده، این روش بیشتر بصری است جدولی