Теорія операційної системи

:: Меню ::

Головна
Представлення даних в обчислювальних системах
Машинні мови
Завантаження програм
Управління оперативною пам'яттю
Сегментна і сторінкова віртуальна пам'ять
Комп'ютер і зовнішні події
Паралелізм з точки зору програміста
Реалізація багатозадачності на однопроцесорних комп'ютерах  
Зовнішні пристрої
Драйвери зовнішніх пристроїв
Файлові системи
Безпека
Огляд архітектури сучасних ОС

:: Друзі ::

Карта сайту
 

:: Статистика ::

 

 

 

 

 

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

Кінцевий автомат (у сучасній англомовній літературі використовується також виразніше, на погляд автора, позначення, що не має хорошого російського еквіваленту, — 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 як дискретні значення цієї змінної — покажчики на функції оброблювальні конкретні достатки.

 

:: Реклама ::

 

:: Посилання ::


 

 

 


Copyright © Kivik, 2017