Введення в кінцеві автомати

Кінцевий автомат (у сучасній англомовній літературі використовується також виразніше, на погляд автора, позначення, що не має хорошого російського еквіваленту, — state machineщо дослівно перекладається як машина станів) є пристроєм, що має внутрішню пам'ять (змінні стани), а також набір входів і виходів. Об'єм внутрішньої пам'яті біля кінцевих автоматів, як випливає з назви, кінцевий. Автомати з необмеженим об'ємом внутрішньої пам'яті називаються безконечними автоматамине реалізовуються і використовуються лише в теоретичних Побудовах (Мінський 1971].
Проте деякі різновиди теоретично безконечних автоматів — наприклад, стекові — можуть бути реалізовані у формі автоматів з практично необмеженою пам'яттю — наприклад, досить глибоким стеком — і знаходять практичне вживання, наприклад при синтаксичному аналізі мов з вкладеними структурами [Кормен/лейзерсон/рівест 2000].
Робота автомата полягає в тому, що він аналізує стани своїх входів, і, залежно від значень входів і свого внутрішнього стану, змінює значення виходів і внутрішній стан. Правила, в з ответствии з якими відбувається зміна, описуються таблицею або діаграмою переходів. Діаграма переходів є граф, вершини якого відповідають допустимим станам внутрішніх змінних автомата, а ребра — допустимим переходам між ними. Переходи між вершинами направлені: наявність переходу з А у В не означає, що існує перехід з У в А. Налічие переходу в обох напрямах символізується двома ребрами, що сполучають одну пару вершин. Такий граф називається орієнтованим [Кормен/лейзерсон/рівест 2000]. Таблиця переходів може розглядатися як матричне представлення діаграми переходів.
Блок-схеми (мал. 10.5) є звичайним способом візуалізація графів переходів і використовуються для опису алгоритмів з 60-х років. Будь-який алгоритм, що виконується на нейманівському для фону комп'ютері з кінцевим об'ємом пам'яті (а також будь-який фізично здійснимий алгоритм), може бути описаний як кінцевий автомат і змальований у вигляді блок-схеми.
Біля кінцевих автоматів з обмеженим числом допустимих значень входів, граф переходів завжди кінцевий, хоча і може містити цикли (замкнуті дороги) і контури (сукупності різних доріг, що наводять до однієї і тієї ж вершини). Зрозуміло, що для автомата з графом, що містить цикли, неможливо гарантувати финитности — завершення роботи за кінцевий час. Як відомо, завдання доказу финитности алгоритму, хоча і вирішена в багатьох окремих випадках, в загальному випадку алгоритмічно нерозв'язна [Мінський 1971].
Стосовно драйверів зовнішніх пристроїв, циклічний граф може відповідати повторним спробам виконання операції після її не-'удачи. Зрозуміло, що на практиці кількість таких спроб слід обмежувати. Найпростіший спосіб такого обмеження — введення лічильника спроб. Формально після цього стану з різними значеннями лічильника перетворюються на набори станів, а граф переходів стає ациклічним (мал. 10.6), але для чималої кількості повторень знову-таки неозорим, тому на практиці часто використовують скорочену блок-схему, в якій стану з різними значеннями лічильника циклу зображаються як один стан.

Мал. 10.5. Блок-схема драйвера

Аналіз повної або скороченої блок-схеми алгоритму методами теорії графів, хоча і не може однозначно дати відповідь на питання про його финитности, може надати значну допомогу в оцінці алгоритму, у тому числі і в пошуку "вузьких" з точки зору финитности місць. У [Кнут 2000) наводяться приклади такого аналізу для деяких простих алгоритмів.
Алгоритми основної маси реально вживаних програм (що особливо використовують змінні стани великого об'єму) мають абсолютно Неозорі блок-схеми. Частково це обходиться декомпозицією програмного комплексу на окремі модулі з більш осяжною функціональністю і алгоритмом, але все-таки далеко не для всіх алгоритмів вистава у вигляді кінцевого автомата природно.

Мал. 10.6. Розгортання циклів в графі стану

З іншого боку, ряд навіть досить складних алгоритмів природним чином описується автоматами з невеликим числом станів, які можуть бути закодовані однією скалярною змінною стану або стеком таких змінних. Такі автомати знаходять вживання в найрізноманітніших завданнях: лексичному і синтаксичному розборі контекстно-вільних і багатьох типах контекстно-зв'язаних мов [Кормен/ Пейзерсон/рівест 2000 1, реалізації мережевих протоколів, завданнях корпоративного документообігу (Керн/лінд 2000] і ін. Зокрема, легко зрозуміти, що обговорюваний нами алгоритм драйвера відноситься саме до цієї категорії алгоритмів.
Два основні підходи до реалізації кінцевих автоматів — це розгорнуті (unrolled) автомати і автомати загального вигляду. Прикладом розгорнутого кінцевого автомата є код основної нитки прикладу 10.2. Зрозуміло, що розгортанню піддаються лише автомати з вельми специфічною — лінійною або деревовидною — структурою графа станів, і якщо в процесі уточнення вимог ми з'ясуємо, що структура автомата повинна побут складнішою, нам доведеться повністю реорганізувати код.
Автомат загального вигляду виглядає дещо складніше, але, навчившись розпізнавати його конструкцію, легко розробляти такі програми заданий ний блок-схемі і, навпаки, відновлювати граф станів за кодом програми. Головною перевагою грамотно реалізованого кінцевого автомата є легкість модифікації: якщо граф переходів зрадите нам треба буде змінити код лише тих вузлів, які торкнулися зміною.
Приклади реалізації кінцевих автоматів такого типа на процедурній мові програмування наводяться в багатьох підручниках програмуванню наприклад [Грогоно 1982). Найчастіше реалізація складається з циклу, умовою виходу з якого є досягнення автоматом фінального стану, і розміщеного в телі циклу оператора обчислюваного переходу із змінною стану як селектор. Кінцевий автомат, схожий на цю класичну реалізацію, приведений в прикладі 10.4.

Приклад 10.4. Кінцевий автомат драйвера контроллера IDE/ATA для OS/2

VOID NEAR STARTSM( NPACB npACB )
}
/* ------------------------------------------------ */
* Перевірка лічильника використань Асв*/
/* -------------------- */
/* Автомат реентрантен для кожного АСВ / *
/* ------------------------------------------------ */
DISABLE
npACB->UseCount++;
iff npACB->UseCount == 1 )
{
do
{
ENABLE
do
{
npACB->Flags &= ~ACBF_WAITSTATE;
switch (npACB->State) {
case ACBS__START :
StartState(npACB);
break;
case ACBS_INTERRUPT:
InterruptState(npACB);
break;
case ACBS_DONE:
DoneState(npACB);
break;
case ACBS_SUSPEND:
SuspendState(npACB);
break;
case ACBS_RETRY:
RetryState(npACB);
break;
case ACBS_RESETCHECK:
ResetCheck(npACB);
break/case ACBS_ERROR:
ErrorState(npACB);
break;
while ( !(npACB->Flags & ACBF WAITSTATE) );
DISABLE
I
while ( — npACB->UseCount ) ;

Кінцевий автомат драйвера OS/2
Не дивлячись на простоту, приклад 10.4 потребує коментарів. Параме! функції startSM — АСВ (Adapter Control Block — блок управління адаптері! так в OS/2 називається блок змінних стану пристрою). АСЗ містить покажчик на чергу запитів IORB (Input/Output Request Block — блок запиту на ввод/вывод) і скалярну змінну state, яка вказує, в якому стані зараз знаходиться обробка першого запиту в черзі. За кодом цього стану визначається, яку функцію слід викликати. У тілах этк функцій, залежно від результату операції, відбувається установка наступного значення змінною стану і, можливо, прапора ACB_WAITSTATE.
Функція startSM (Start State Machine) викликається як з функції обработн запитів, так і з обробника переривання. Тому перед входом в собс венозний автомат і після виходу з нього коштує код, що використовує поле nрАСЕ >UseCount як змінну прапора, аби не допустити одночасного входу в автомат з обох можливих ниток виконання. Звернете також увагу, що макросами ENABLE і DISABLE (заборона і дозвіл переривань оточена робота із змінною прапора, але не сам автомат.
(Як вправа читачеві пропонується зрозуміти, як же забезпечуєте виклик функції interruptstate, якщо під час переривання основний поті драйвера все ще знаходився в телі автомата.
Повний текст драйвера IDE/ATA для OS/2 включений в стандартне постачання DDK (Driver Development Kit— набір інструментів [для] розробника драйверів), який може бути знайдений на сайті [www.ibm.com OS/2 DDK].

Побудований нами в прикладі 10.3 код зовні зовсім не схожий на примі 10.4, але, насправді, також є кінцевим автоматом як змінною стану використовується змінна fdd->handier як дискретні значення цієї змінної — покажчики на функції оброблювальні конкретні стани.