Главная >> Методички

Pages: |

| 2 |

«ПРОГРАММИРОВАНИЕ ИНФОРМАЦИОННО-УПРАВЛЯЮЩИХ СИСТЕМ НА ОСНОВЕ КОНЕЧНЫХ АВТОМАТОВ ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Факультет информационных ...»

-- [ Страница 1 ] --

В. Е. Зюбин

ПРОГРАММИРОВАНИЕ

ИНФОРМАЦИОННО-УПРАВЛЯЮЩИХ СИСТЕМ

НА ОСНОВЕ КОНЕЧНЫХ АВТОМАТОВ

http://reflex-language.narod.ru

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Факультет информационных технологий Кафедра информационно-измерительных систем В. Е. Зюбин

ПРОГРАММИРОВАНИЕ

ИНФОРМАЦИОННО-УПРАВЛЯЮЩИХ СИСТЕМ

НА ОСНОВЕ КОНЕЧНЫХ АВТОМАТОВ

Учебно-методическое пособие Новосибирск http://reflex-language.narod.ru ББК В185.12 + З- УДК 811.93+62-529+004. З- Зюбин В. Е. Программирование информационно-управляющих систем на основе конечных автоматов: Учеб.-метод. пособие / Новосиб. гос. ун-т.

Новосибирск, 2006. 96 с.

ISBN 5-94356-425-Х В учебно-методическом пособии рассматривается применение модели конечного автомата и его модификаций при создании информационноуправляющих систем. Анализируется специфика задач управления и языки, используемые для описания управляющих алгоритмов. Рассматриваются типовые алгоритмы, используемые при решении задач промышленной автоматизации.

Рецензент д-р техн. наук, проф. И. Ф. Клисторин Рекомендовано к изданию в качестве учебно-методического пособия ученым советом ФИТ НГУ © Новосибирский государственный университет, © Зюбин В. Е., ISBN 5-94356-425-Х http://reflex-language.narod.ru

Введение Для понятия «огонь» жрецы Древнего Египта имели более двадцати существительных. Для наводнения – более десяти. И это только дошедшие до нас слова. Та же картина у эскимосов: для снега у них существует более двух десятков различных слов. Перевод каждого такого эскимосского слова на русский язык займет несколько предложений. А ведь мы, в России, хорошо знакомы со снегом и для обозначения замерзшей воды имеем в запасе несколько вариантов: «наст», «иней», «лед», «снег». Африканец при переводе с эскимосского встретится с более серьезной проблемой: ведь у него в языке нет ни одного слова, обозначающего «снег». Разумеется, если хорошенько постарается, он все-таки сможет выразить свою мысль о «холодной-холодной белизне, на огне дающей воду», но результат будет весьма плачевен. Жителю жаркой Африки также непонятны и природные условия Крайнего Севера, и назначение большинства предметов из быта эскимоса, и приемы, необходимые для выживания. Случись ему оказаться в тундре, он, скорее всего, быстро погибнет от нехватки знаний.

В программировании ситуация очень сходна. Кроме королевства персональных компьютеров, где доминируют языки объектноориентированного программирования, существуют еще и удаленные, достаточно обширные области, для которых понятийный аппарат языков Си++ и Объектного Паскаля совсем не пригоден. И хотя многие программисты даже не догадываются о существовании этих областей, проводя всю свою жизнь в рамках компьютерного мэйнстрима, специалисты насчитывают более двух тысяч разных языков программирования, отличных по специфике, подходу и области использования.

Одна из таких областей – область промышленной автоматизации и автоматизации научных исследований. Станки, поточные линии, роботы, гибкие производственные комплексы, технологические процессы, сложное диагностическое и экспериментальное оборудование – в настоящее время практически вся промышленная автоматизация реализуется на цифровых системах управления. В качестве базового элемента систем управления используются программируемые логические контроллеры (ПЛК), которые имеют в своем составе микропроцессорный модуль, множество входов и выходов, и программное обеспечение – управляющий алгоритм (УА).

УА реализует разнообразные функции: контролирует значения входных / выходных сигналов, выполняет логические / арифметические операции, поддерживает необходимые значения параметров, обеспечивает связь с датчиками и исполнительными устройствами.

УА имеет специфику, которая либо отсутствует, либо не вполне четко проявляется в вычислительных задачах и пользовательских программах для персонального компьютера.

Во-первых, это наличие внешнего мира, объекта управления (ОУ), с которым УА постоянно обменивается данными. Через разнообразные датчики в УА непрерывным потоком поступают данные о текущем состоянии ОУ (температуре, давлении, скорости, напряжении, размерах и расстоянии, массе и т. д.) и происходящих событиях. На этот поток данных УА должен реагировать через органы управления (переключатели, клапаны, двигатели, насосы, источники тока, электромоторы), пытаясь привести ОУ в требуемое состояние. Непрерывный характер обмена УА с внешней средой делает неприменимой привычную схему вычисления «дано …, найти …», теряется смысл понятия исходных данных и конечного результата.

Во-вторых, в зависимости от событий на ОУ может в корне меняться характер обработки входных данных, например, при вхождении технологического процесса в критическую зону или при отказе одного из элементов. Поэтому УА должен «уметь» перестраиваться, или, другими словами, быть событийно-управляемым.

В-третьих, реакция УА должна соответствовать динамическим характеристикам ОУ, его физической природе и физическим процессам, протекающим на нем. Таким образом, функционирование УА предполагает большое число операций с временными интервалами: задержками, паузами, тайм-аутами.

В-четвертых, в УА необходимо отражать существование множества физических процессов, независимо протекающих на ОУ. Например, объект может иметь несколько отдельных контуров управления температурой, клапанов и (или) насосов. При наивной попытке организовать монолитное управление возникает необходимость рассматривать все возможные состояния системы целиком, что приводит к так называемому комбинаторному взрыву сложности, экспоненциальной зависимости размеров алгоритма от количества входных / выходных сигналов. В этой ситуации единственная возможность практически решить проблему – обеспечить независимость описания и логический параллелизм его исполнения.

Учебно-методическое пособие, которое вы держите в руках, преследует цель познакомить студента со спецификой информационно-управляющих систем, обеспечить его адекватным понятийным аппаратом для решения задач промышленной автоматизации и обучить его практическим приемам создания управляющих алгоритмов.

В качестве теоретической основы используется модель конечного автомата, очень удобная, но, к сожалению, не используемая в программистской практике так часто, как она того заслуживает.

Курс построен по следующей схеме. Сначала обсуждается общее понятие алгоритма и приводится история создания модели конечных автоматов. Рассматривается специфика задач управления, формулируются необходимые требования к понятийному аппарату. Проводится критический анализ модели конечного автомата на предмет соответствия этим требованиям. Рассматриваются полезные свойства модели и выявляются концептуальные проблем. Конструируется модель гиперпроцесса (гиперавтомата) для описания управляющих алгоритмов и понятийный аппарат, терминологически приближенный к современным тенденциям в области IT-индустрии. Приводятся способы реализации гиперпроцесса средствами процедурных языков программирования. Обсуждаются языки стандарта МЭК 61131-3 – проблемно-ориентированные языки, которые наиболее часто используются в промышленной практике. Дается описание языка Рефлекс и примеры решения типовых задач, возникающих при автоматизации промышленных объектов.

1. Конечный автомат 1.1. Исторические предпосылки создания модели конечного автомата Проблема определения понятия «алгоритм». На протяжении многих веков понятие алгоритма связывалось с числами и относительно простыми действиями над ними, да и сама математика была, по большей части, наукой о вычислениях, наукой прикладной. Чаще всего алгоритмы представлялись в виде математических формул. Порядок элементарных шагов алгоритма задавался расстановкой скобок, а сами шаги заключались в выполнении арифметических операций и операций отношения (проверки равенства, неравенства и т. д.). Часто вычисления были громоздкими, а вычисления вручную – трудоемкими, но суть самого вычислительного процесса оставалась очевидной. У математиков не возникала потребность в осознании и строгом определении понятия алгоритма, в его обобщении.

Но с развитием математики появлялись новые объекты, которыми приходилось оперировать: векторы, графы, матрицы, множества и др. Как определить для них однозначность или как установить конечность алгоритма, какие шаги считать элементарными? В 1920-х гг. задача точного определения понятия алгоритма стала одной из центральных проблем математики.

Попытки выработать такое определение привели к возникновению теории алгоритмов, в которую вошли труды многих известных математиков – К. Гедель, К. Черч, С. Клини, А. Тьюринг, Э. Пост, А. Марков, А. Колмогоров и др. Несмотря на интересные результаты, полученные в рамках теории алгоритмов, дать четкое определение понятию алгоритма не удалось. И с современной точки зрения «алгоритм, алгорифм, – одно из основных понятий (категорий) математики, не обладающих формальным определением в терминах более простых понятий, а абстрагируемых непосредственно из опыта».

Неформальное определение алгоритма. В повседневной жизни каждый человек сталкивается с необходимостью решения задач самой разной сложности. Некоторые из них трудны и требуют длительных размышлений для поиска решений (а иногда его так и не удается найти), другие же, напротив, столь просты и привычны, что решаются автоматически.

При этом выполнение даже самой простой задачи осуществляется в несколько последовательных этапов (шагов). В виде последовательности шагов можно описать процесс решения многих задач, известных из школьного курса математики: приведение дробей к общему знаменателю, решение системы линейных уравнений путем последовательного исключения неизвестных, построение треугольника по трем сторонам с помоhttp://reflex-language.narod.ru щью циркуля и линейки и т. д. Это всё алгоритмы, рано или поздно приводящие к конечному результату. В то же время можно привести примеры формально бесконечных алгоритмов, широко применяемых на практике.

Например, алгоритм работы системы сбора метеорологических данных состоит в непрерывном повторении последовательности действий («измерить температуру воздуха», «определить атмосферное давление»), выполняемых с определенной частотой (через минуту, час) во все время существования данной системы.

Понятие алгоритма близко к другим понятиям, таким, как метод (метод Гаусса решения систем линейных уравнений), способ (способ построения треугольника по трем сторонам с помощью циркуля и линейки).

Дадим неформальное определение алгоритма. Алгоритм – это точно определенная, возможно циклически повторяемая инструкция по преобразованию входных данных в выходные.

Появление первых проектов вычислительных машин стимулировало исследование возможностей практического применения алгоритмов, использование которых ввиду их трудоемкости было ранее недоступно.

Дальнейший процесс развития вычислительной техники определил развитие теоретических и прикладных аспектов изучения алгоритмов.

Формы представления алгоритмов. Для записи алгоритмов необходим некоторый язык, при этом очень важно, какой именно язык выбран.

Записывать алгоритмы на русском языке (или любом другом естественном языке) неудобно.

Например, описание алгоритма Евклида нахождения НОД (наибольшего общего делителя) двух целых положительных чисел может быть представлено в виде трех шагов. Шаг 1: Разделить m на n. Пусть p – остаток от деления.

Шаг 2: Если p равно нулю, то n и есть исходный НОД.

Шаг 3: Если p не равно нулю, то сделаем m равным n, а n равным p.

Вернуться к шагу 1.

Приведенная здесь запись алгоритма нахождения НОД очень упрощенная. Запись, данная Евклидом, представляет собой страницу текста, причем последовательность действий существенно сложней.

Одним из распространенных способов записи алгоритмов является запись на языке блок-схем. Запись представляет собой набор элементов (блоков), соединенных стрелками. Каждый элемент – это «шаг» алгоритма. Элементы блок-схемы делятся на два вида. Элементы, содержащие инструкцию выполнения какого-либо действия, обозначают прямоугольниками, а элементы, содержащие проверку условия, – ромбами. Из прямоугольников всегда выходит только одна стрелка (входить может несколько), а из ромбов – две (одна из них помечается словом «да», другая – словом «нет», они показывают, соответственно, выполнено или нет проверяемое условие).

Построение блок-схем из элементов всего лишь нескольких типов дает возможность преобразовать их в компьютерные программы и позволяет формализовать этот процесс (рис. 1.1).

Проблема формализации записи алгоритмов. Задача нахождения единообразной формы записи алгоритмов, решающих различные задачи, была одной из основных задач теории алгоритмов. Математические определения фигур, чисел, уравнений, неравенств и многих других объектов достаточно четки. Каждый математически определенный объект можно сравнить с другим объектом, соответствующим тому же определению.

Например, прямоугольник можно сравнить с другим прямоугольником по площади или длине периметра. Возможность сравнения математически определенных объектов – важный момент математического изучения этих объектов. Но как сравнивать два произвольных алгоритма? Можно, например, сравнить два алгоритма решения системы уравнений и выбрать более подходящий в данном случае, но невозможно сравнить алгоритм перехода через улицу с алгоритмом извлечения квадратного корня. С этой целью нужно формализовать понятие алгоритма, т. е. отвлечься от сущестhttp://reflex-language.narod.ru ва решаемой данным алгоритмом задачи и выделить свойства различных алгоритмов, привлекая к рассмотрению только его форму записи.

В связи с этим в теории алгоритмов была поставлена следующая задача: представить алгоритм в таком виде, чтобы каждый элементарный шаг алгоритма мог быть выполнен достаточно простым устройством (машиной). Желательно, чтобы это устройство было универсальным, т. е. чтобы на нем можно было выполнять любой алгоритм. Механизм работы машины должен быть максимально простым по логической структуре, но настолько точным, чтобы эта структура могла служить предметом математического исследования. Впервые это было сделано математиком из США Эмилем Постом в 1936 г. (машина Поста) еще до создания современных вычислительных машин и (практически одновременно) английским математиком Аланом Тьюрингом (машина Тьюринга).

Обе машины были созданы для уточнения понятия «алгоритм».

Машина Поста. Статья Э. Поста, в которой была впервые описана его машина, называлась «Финитные комбинаторные процессы, формулировка 1». В этой статье Пост доказывал, что предлагаемая система обладает алгоритмической полнотой. В 1967 г. профессор В. Успенский пересказал эти статьи с новых позиций. Он же и ввел в употребление термин «машина Поста» и предложил новую интерпретацию. Машина Поста (МП) – абстрактная машина, которая работает по алгоритмам, раз- Э. Пост работанным человеком, и обладает следующим (1897–1954) свойством: если для решения задачи можно построить машину Поста, то она алгоритмически разрешима.

Машина Поста (рис. 1.2) состоит из каретки (или считывающей / записывающей головки), устройства управления кареткой (УУ) и разбитой на ячейки бесконечной в обе стороны ленты. КажК дая ячейка ленты может быть меткой ‘’. В МП используется унарная система счисления, число P записывается как P + 1 единиц: числу 4 соответствует 5 ячеек с метками, расположенных по порядку. За один шаг каретка может сдвинуться на одну позицию влево или вправо, считать, поставить или уничтожить символ в том месте, где она стоит.

Работа машины Поста определяется программой, записанной в УУ и состоящей из конечного числа строк. Всего команд шесть:

n. a Cдвиг каретки вправо и переход к строке a Здесь n – номер строки в программе, a, b – строка, на которую передается управление.

Для работы машины нужно задать программу и ее начальное состояние (т. е. состояние ленты и позицию каретки). После запуска возможны варианты:

• работа может закончиться ошибкой (невыполнимой командой: стирание несуществующей метки или запись в помеченное поле);

• работа может закончиться командой «останов»;

• работа никогда не закончится.

В качестве примера работы и программирования машины Поста рассмотрим задачу вычитания натуральных чисел P – Q.

Как это принято в машине Поста, будем представлять натуральное (целое неотрицательное) число P набором из P + 1 единиц и разделять числа нулём. Исходное положение каретки помечено символом v:

Сложение двух чисел тривиально – достаточно поставить 1 между ними и стереть крайний правый символ у Q.

Программа вычитания состоит из последовательного затирания крайних левых меток у Q и правых у P:

4. Stop – стоп, если затерли Q = 0 (терминальную единицу) Отметим, что номер команды перехода не указывается, если переход происходит на следующую по порядку строку (для наглядности текста).

В шестой строке возможно зацикливание, если Q > P (вы можете добавить проверку сами).

В 1970 г. сотрудники Симферопольского университета разработали машину Поста «в металле».

Важность идей Эмиля Поста в том, что был предложен простейший способ преобразования информации, а именно он построил алгоритмическую систему (алгоритмическая система Поста):

• вся информация, которая должна быть обработана по существу, должна быть обработана по форме, т. е. с помощью двоичного алфавита;

• вся информация должна обрабатываться побуквенно.

Машина Тьюринга (рис. 1.3) представляет собой некоторое автоматически действующее устройство управления (УУ), способное находиться в конечном числе внутренних состояний: S = {s0, s1, …, sp} (от англ.

state), и снабженное бесконечной внешней памятью – лентой (Л). Среди состояний имеются два выделенных – начальное (s1) и заключительное (s0). Лента разделена на ячейки (клетки) и не ограничена влево и вправо.

В каждой ячейке ленты может быть записан любой из А. Тьюринг символов, входящих в некоторый заранее заданный пере- (1912–1954) чень C = {c0, c1, …, cm} (от англ. character). Ради единообразия считают, что в пустой ячейке записана «пустая буква» – c0.

(Г) для считывания / записи) одну из ячеек своей ленты, воспри- Рис. 1.3. Машина Тьюринга нимает записанный в ней символ (cj). Если в текущий момент времени машина находится не в заключительном состоянии (s0), то в следующий за ним момент:

• она переходит в новое состояние (si+1), которое в частном случае может совпадать со старым или оказаться заключительным;

• в рассматриваемой ячейке старый символ (cj) заменяется новым, который в частном случае может быть пустым (c0) или совпадающим со старым;

• лента машины сдвигается на одну ячейку влево или вправо либо остается на месте. Этот шаг машины вполне определяется её текущим состоянием (si ) и текущим воспринимаемым символом (cj).

Программа для машины Тьюринга представляет собой таблицу, в каждой ячейке которой записана команда. Команда представляет собой указание: какой символ записать в текущую ячейку ленты, в какую сторону передвинуть головку чтения / записи и в какое состояние перейти машине.

Текущее полное описание машины Тьюринга задаётся её конфигурацией, которая состоит из указания для данного момента следующей информации:

• конкретного заполнения клеток ленты символами;

• клетки, находящейся в поле зрения машины;

• состояния, в котором машина находится.

Если у конкретной машины Тьюринга взять в качестве исходной какую-либо конфигурацию с не-заключительным состоянием, то работа этой машины будет состоять в последовательном преобразовании исходной конфигурации в соответствии с программой машины. Работа будет продолжаться до тех пор, пока не будет достигнута конфигурация с заключительным состоянием. Эта последняя, если она существует, и считается результатом работы данной машины над исходной конфигурацией.

По своему устройству машина Тьюринга крайне примитивна. Она намного проще самых первых компьютеров. Примитивизм состоит в том, что у нее предельно прост набор элементарных операций, производимых головкой – считывание и запись, а также в том, что доступ к ячейкам памяти (секциям ленты) в ней происходит не по адресу, как в компьютерах, а путем последовательного перемещения вдоль ленты. По этой причине даже такие простые действия, как сложение или сравнение двух символов, машина Тьюринга производит за несколько шагов, а обычные операции сложения и умножения требуют весьма большого числа элементарных действий. Однако машина Тьюринга была придумана не как модель (прототип) реальных вычислительных машин, а для того, чтобы показать принципиальную (теоретическую) возможность построения сколь угодно сложного алгоритма из предельно простых операций, причем сами операции и переход от одной к последующей машина выполняет автоматически.

В 1937 г. сотрудники Малой Крымской академии наук построили машину Тьюринга «в металле».

Обе машины – Поста и Тьюринга – «эквивалентны», т. е. доказано, что класс алгоритмов, представленных в форме машины Поста, и класс алгоритмов, представленных в форме машины Тьюринга, совпадают. В рамках теории алгоритмов Тьюринг выдвинул тезис, получивший название тезис Тьюринга, согласно которому всякий алгоритм представим в форме машины Тьюринга. Это принимаемое без доказательства фундаментальное положение теории алгоритмов может также рассматриваться как неформальное определения понятия «алгоритм».

Важный момент, на который следует обратить внимание, – это характер данных, записываемых и считываемых с ленты. Как и в случае с машиной Поста, используются численные значения фиксированной длины – алфавит.

Машина Поста и машина Тьюринга в дальнейшем получили развитие в качестве модели конечного автомата.

Вопросы для самопроверки Вопрос 1. В приведенной программе для машины Поста в шестой строке возможно зацикливание, если Q > P. Попытайтесь добавить проверку.

Вопрос 2. Как вы считаете, почему известна лишь одна практическая реализация машины Тьюринга? Зачем это было сделано?

Вопрос 3. Назовите число ячеек машины Поста, необходимых для хранения максимально возможной суммы двух байтовых переменных?

Вопрос 4. Что сложнее, машина Поста или машина Тьюринга? Как вы считаете, для какой из этих машин проще создавать программы?

автомата В середине XX столетия была создана и получила широкое использование электронная цифровая машина с программным управлением. На повестку дня встал вопрос о рациональном конструировании, или, как было принято говорить, синтеза схем таких машин. Первые ЭВМ рассматривались как преобразователи дискретных данных. Поэтому в литературе было достаточно распространено альтернативное название для ЭВМ – дискретные, или цифровые автоматы (устройства, машины).

Для формализации решения задач синтеза дискретных устройств была предложена математическая модель в виде абстрактного автомата, во многом сходная с машиной Тьюринга. Абстрактный автомат A задается шестеркой:

A = (S, I, O, Fs, Fo, s1), у которого:

1. S = {s1,..., sk,..., sK} – множество состояний (алфавит состояний);

2. I = {i1,..., im,..., iM} – множество входных символов (входной алфавит);

3. O = {o1,..., on,..., oN} – множество выходных символов (выходной алфавит);

4. Fs : S I S – функция переходов, отображающая DFs S I в S.

Другими словами, функция Fs некоторым парам состояние – входной символ (sk, im) ставит в соответствие состояние автомата sj = Fs (sk, im), sj S ;

5. Fo : S I O – функция выходов, отображающая DFo S I в O.

Функция Fo некоторым парам состояние – входной символ (sk, im) ставит в соответствие выходные символы автомата, on = Fs (sk, im), on O ;

6. s1 S – начальное состояние автомата.

Обозначения выбраны по следующим соображениям: A – от «automaton», S / s – от «state», I / i – от «input», O / o – от «output», F – от «function».

Автомат называется полностью определенным, если DFs = DFo = S I.

1.3. Необходимые пояснения к понятию «конечный автомат»

Поговорим немного об этой модели и попытаемся найти точки соприкосновения этой математической модели с реальной жизнью.

Часто дезориентирует само название «абстрактный автомат». Почему «абстрактный», почему «автомат»? Повторимся: «автомат» – это «аппарат (машина, прибор, устройство), после включения самостоятельно выполняющий ряд заданных операций». Слово «абстрактный» можно переводить как «существующий только с математической точки зрения». Это слово используется потому, что с математической точки зрения множества состояний, входных и выходных символов у автомата могут быть бесконечными множествами. Разумеется, все существующие на практике цифровые устройства, будучи представлены в виде абстрактного автомата, имеют конечные множества S, I, O. В рамках теории автоматов модели таких устройств называются конечными автоматами. Впредь мы всегда будем говорить исключительно о конечных автоматах.

Что значит «алфавит»? В теории автоматов это «непустое множество попарно различных символов». Опять получается не очень понятно. Чтобы разобраться с этим вопросом, следует вспомнить некоторые факты из истории.

Дело в том, что при возникновении теории автоматов кодирование в двоичной системе не было стандартом, поэтому вопросы кодирования рассматривались отдельно. На физическом уровне допускалось кодирование не только в виде битов (0 / 1), но и в троичной системе, четверичной и т. д.

Также не было использовано понятие «переменная». Эти исторические факты, как правило, неизвестны студентам, и без них понимание модели автомата уже в этой части может вызвать затруднения.

С точки зрения современной практики программирования все значительно проще. Под символами в теории автоматов понимаются просто некоторые значения (переменной). Входной (выходной) алфавит – это просто переменная с заранее определенным набором допустимым значений.

Из сказанного можно сделать один весьма интересный вывод.

Поскольку практическая работа в силу чисто физических ограничений проектировщика может вестись с сотней-другой значений, весь алфавит большинства реальных автоматов может быть представлен байтом, максимум двумя.

соответствии с принятым в кибернетике подходом автомат рассматривается как «черный ящик» и изображается так, как показано на Рис. 1.4. Автомат рис. 1.4. Автомат имеет один вход и один выход. На вход ему подается последовательность разрешенных входных значений. В теории автоматов эта последовательность называется входным словом. На выходе автомат генерирует выходную последовательность заранее определенных значений, которая называется выходным словом. На уровне абстрактной теории понятие «работа автомата» понимается как преобразование входной последовательности значений в выходную последовательность значений. Автомат получает на своем входе некоторое значение и на основании этого значения и текущего внутреннего состояния формирует выходное значение.

Поскольку прозвучало слово «работа» и сделана заявка на кибернетический подход, в котором основное внимание уделяется поведению системы с точки зрения внешней среды, возникает целый ряд вопросов.

Например, зависит ли поведение автомата от частоты подачи ему на вход новых значений? Как устроен автомат и что же такое «состояние»? К сожалению, этим важным вопросам редко уделяется должное внимание.

Для начала вспомним, что с помощью автомата моделируется цифровое устройство, т. е. полностью дискретное устройство, в котором все сигналы квантованы по уровню, а все действия квантованы по времени. Квантование работы автомата по времени, необходимость считывать значения со своего входа, обрабатывать их и реагировать на входные значения соответствующим образом, выдавая выходные значения, возможно единственно в соответствии с циклической схемой, изображенной на рис. 1.5.

К сожалению, классическая теория автоматов опускает обсуждение этого важного вопроса. Мы же можем сделать по этому поводу следующую ремарку. Поскольку действия цифровой системы требуют временных затрат на исполнение, становится понятно, что у автомата есть еще и некоторая временная характеристика – временной интервал, характеризующий цикл исполнения. Этот временной интервал может быть постоянным или плавающим, но самое главное, что сейчас требуется осознать, – сам факт его существования. Возьмем этот факт на заметку.

Понятие «состояние». Про состояние обычно говорится следующее.

«Понятие состояния введено в связи с тем, что часто возникает необходимость в описании поведения систем, выходы которых зависят не только от состояния входов в данный момент времени, но и от некоторой предыстории, т. е. от сигналов, которые поступали на вход системы ранее. Состояние как раз и соответствует некоторой памяти о прошлом, позволяя устранить время как явную переменную и выразить выходной сигнал как функцию состояния и входа в данный момент времени». Это требуется прокомментировать. Во-первых, не стоит обращать внимание на заявление о том, что состояние позволяет устранить время как явную переменную.

Это не совсем так. Забегая вперед, можно сказать, что оно действительно может сильно помочь и обеспечить работу с временными интервалами, но в рамках классической теории автоматов это не делается. Во-вторых, в приведенном отрывке поясняется, для чего служит состояние и что достигается с помощью состояния, но ответа на вопрос, что же такое состояние, не звучит.

Самая простая интерпретация состояния – это просто некоторое числовое значение. Аналогично входному и входному алфавиту. Соответственно, можно ввести понятие «алфавит состояний», понимая под этим некоторую переменную (ячейку памяти) со специфицированным набором допустимых значений состояний. Функцию переходов Fs и функцию выходов Fo без потери связи с теорией автоматов можно воспринимать уже как функции в программистском смысле, – функции от двух переменных типа «беззнаковое целое», возвращающие целое значение, – Fo(s, i) и Fs(s, i).

После этого пояснения становится очевидным, что же скрыто за элементом «вычисление выходного значения» на рис. 1.5. В терминах языка Си это будут две строки (рис. 1.6).

Обратим внимание на порядок вызова функций Fo и Fs, в каком порядке вычисляются эти функции. Вообще говоря, порядок может быть произвольным, но приведенный на рис. 1.6 удобнее с точки зрения использования: в качестве аргументов обеих функций используются одни и те же значения, что минимизирует число рассматриваемых вариантов.

Рис. 1.6. Цикл автомата. Раскрытие элемента О внутреннем наполнении функций переходов и выходов можно сказать следующее. Если аналитические зависимости между значением входов и значением выходов еще встречаются на практике, то аналитические зависимости между состояниями и выходами – практически никогда, также пренебрежимо редки случаи, когда в аналитическом виде можно задать функцию Fs.

Это означает, что в подавляющем большинстве случаев функции Fo и Fs задаются исключительно таблично. С другой стороны, при создании устройства нас в первую очередь волнует его поведение, реакция устройства на внешнее воздействие в конкретный момент времени, для данного цикла. Внутреннее наполнение, – его состояние, – может выбираться произвольно, к нему не предъявляется никаких жестких требований, в кибернетическом подходе оно малоинтересно. Эти обстоятельства делают более удобным подход, в котором сначала производится абстрагирование от значения переменной «состояние» s и, тем самым, функции переходов и выходов редуцируются к функциям от одного переменного. Дополнительный плюс такого подхода в том, что функция выходов, возможно, описывается в компактном аналитическом виде. Именно этот порядок формирования функций негласно подразумевается, когда говорится, что «состояние – это память о прошлом».

На рис. 1.7 отражен такой подход.

Сначала по текущему значению s определяется, какие же конкретно функции использовать для вычисления значений выходов и состояния следующего цикла, а затем выбранные функции исполняются. При этом функции выходов и переходов задаются как множества функций Fo_XX, Fs_XX от одного переменного – значения выходов i (XX – служит для идентификации принадлежности функции к определенному состоянию, например, F0_41, Fs_35 и т. п.).

Если взглянуть на состояние и порядок работы с ним под другим углом, то мы придем к понятию функций-состояний – функций, объединяющих редуцированные функции выходов и переходов. Эти функции взаимоисключающие в том смысле, что на одном цикле автомата исполняется только одна функция-состояние – текущая.

Рис. 1.7. Цикл автомата. Редукция числа аргументов При вызове функция-состояние определяет, как отреагировать на входное значение – какое выходное значение сформировать на текущем цикле автомата, и вычисляет, какая функция-состояние будет вызвана на следующем цикле автомата – станет текущей.

Понятие функции-состояния существенно для изучения способов задания автоматов.

Автомат с одним состоянием. Для автоматов с одним состоянием необходимость в табличном выборе функций отпадает, так как вариант всегда один. Автоматы такого класса называются комбинационные схемы.

У таких автоматов для одинакового входного значения выходные значения всегда одинаковы.

Комбинационная схема осуществляет перевод одного множества значений в другие. С помощью комбинаторной схемы можно реализовать взаимно однозначное отображение произвольного конечного множества из N элементов на множество {1, 2, 3,..., N} и наоборот. Если после считывания входного значения поставить комбинаторную схему, отображающую M-элементное множество I в множество {1, 2,..., M}, а перед выдачей выходного значения поставить комбинаторную схему, отображающую N-элементное множество O в множество {1, 2,..., N}, то множества I и O в модели автомата можно заменить на множества {1, 2,..., M} и {1, 2,..., N}.

Замена множества S на множество {1, 2,..., K} также несущественна.

Более того, с переходом к понятию функции-состояния теряет смысл использование самого понятия алфавита состояний.

Модернизированная модель конечного автомата. С учетом сказанного можно определить конечный автомат как циклически активизируемый набор альтернативных функций, полностью определяемый пятеркой:

A = (F, x, y, fcur, f1), у которого:

1. x – входная переменная с допустимыми значениями из множества 2. y – выходная переменная с допустимыми значениями из множества 3. F = {f1,..., fk,..., fK} – множество альтернативных функцийсостояний, отображающих I в O и I в F. Другими словами, каждая из функций fk содержит две подфункции: а) подфункцию выходов fok, которая некоторому значению входа m ставит в соответствие значение выхода n, и подфункции переходов fsk, которая вычисляет функцию-состояние для следующего цикла из множества F : y = fok (x), fok (x) O; fcur = fsk (x), fsk (x) F;

4. fcur F – текущая функция-состояние автомата для рассматриваемого момента времени;

5. f1 F – начальная функция-состояние автомата, текущая функциясостояние по началу работы.

Текущее полное описание конечного автомата задаётся его текущей функцией-состоянием fcur для рассматриваемого момента времени, точнее – для рассматриваемого цикла.

Дополнительное указание на множества I и O в данном определении и спецификация их вида ({1, 2, 3,..., N}) не дает никаких видимых преимуществ при работе с моделью. Для простоты можно рассматривать и все возможные значения переменных x и y, просто автомат будет не полностью определенным. Смысл этих манипуляций – показать, что модель автомата представляет собой и как она может быть трансформирована.

В конце параграфа вернемся к математической модели автомата и попытаемся ответить на серию вопросов для самопроверки.

Вопросы для самопроверки Вопрос 1. В чем отличие начального состояния автомата s1 от других состояний?

Вопрос 2. Как, по вашему мнению, может быть реализована функция выходов Fo на языке программирования Си? То же для функции переходов Fs? То же для множества функций-состояний F в модифицированной модели? При выполнении задания вспомните, какой оператор языка Си предназначен для реализации табличного разбора.

Вопрос 3. Назовите максимальный элемент из возможных вариантов множества I, если x – это переменная типа unsigned char (байт)?

1.4. Автоматы Мили и Мура.

Способы задания автоматов На практике в рамках теории автоматов наибольшее распространение получили два класса автоматов – автоматы Мили и автоматы Мура, названные по имени исследовавших эти модели ученых из США G. H. Mealy и E. F. Moore. Автоматы Мили и Мура – это просто две различные формы конечных автоматов. Функционирование конечного автомата в форме автомата Мили задается уравнениями s(t + 1) = Fs (s(t), i(t)); o(t + 1) = Fo (s(t), i(t)), t = 0, 1, 2, …, а закон функционирования автомата Мура – уравнениями s(t + 1) = Fs (s(t), i(t)); o(t + 1) = Fo (s(t)), t = 0, 1, 2 … Формы описания Мура и Мили отражают наше желание изобразить функционирование конечного автомата во времени. Однако с учетом отмеченного в предыдущем параграфе циклического характера функционирования конечного автомата под t следует понимать, разумеется, не время, а порядковый номер цикла (начиная с момента запуска, t = 0).

Отличия между этими формами задания автомата следующие. В функциях-состояниях автомата Мура значение выдаваемого сигнала y неизменно (fok (x) = const), а у автомата Мили fok (x) const и вычисляется каждый раз в зависимости от значения входного сигнала x.

Табличное задание автоматов Мили и Мура. Как уже отмечалось, в подавляющем большинстве случаев невозможно описать функции fok, fsk аналитически. Поэтому один из наиболее популярных средств задания автоматов – таблица (табл. 1.1, 1.2).

Функция переходов автомата Функция выходов автомата Строки этих таблиц соответствуют возможным значениям входной переменной x, а столбцы – возможным значениям переменной «состояние» s.

На пересечении столбца sk и строки im в левой таблице (таблице переходов) указывается значение состояния для следующего цикла sj = Fs (sk, im), а в правой таблице (таблице выходов) – значение сигнала y = Fo (sk, im), выдаваемого на выход.

Аналогичные таблицы (табл. 1.3, 1.4) для некоторого автомата Мура приведены ниже.

Буквы входного Поскольку в автомате Мура функции fok имеют вид у = const (обратите внимание, что в таблице для Fo обе строки с oi -ми совпадают, зависят только от значения состояния), то описание автомата Мура может быть дано в одной таблице (табл. 1.5).

Таблица 1.5. Совмещенная таблица для автомата A Иногда и при задании автоматов Мили используют совмещенную таблицу (табл. 1.6) переходов и выходов, в которой на пересечении столбца sk и строки im записываются сразу и новые значения s и o.

В отличие от машин Тьюринга и Поста автоматы Мили и Мура достаточно широко использовались на практике. Практика показала, что общим минусом для обеих моделей является экспоненциальный рост размеров их таблиц. В качестве одного из способов снижения сложности таблиц был предложен частичный способ задания автоматов, когда не все ячейки специфицируются, например в случаях, когда требуется сохранить старое значение состояния или выходного сигнала. В таких случаях в ячейке ставится прочерк. Это не снимает проблему экспоненциального роста сложности полностью, но упрощает работу с таблицами и в ряде случаев позволяет сократить число функций-состояний автомата (табл. 1.7, 1.8).

Таблица 1.6. Совмещенная таблица для автомата A Или то же с помощью совмещенной таблицы (табл. 1.9):

Таблица 1.9. Совмещенная таблица для автомата Мили Графическое задание автоматов Мили и Мура. Граф автомат – ориентированный граф, вершины которого соответствуют значениям переменной s, а дуги – переходам между ними. Пример такого графа дан на рис. 1.8 (автомат Мили) и рис. 1.9 (автомат Мура).

Преобразование автоматов Мили и Мура. Автоматы Мили и Мура могут быть преобразованы друг в друга. Эти преобразования с некоторой натяжкой можно назвать взаимнооднозначными. Возникающие при этом проблемы связаны с начальным состоянием: для автомата Мура первое выходное воздействие всегда одинаково, в то время как для автомата Мили его можно сделать разным. При преобразованиях выходные сигналы сдвигаются на цикл вперед или назад в зависимости от направления преобразования.

Переход от автомата Мура к автомату Мили осуществляется по схеме, изображенной на рис. 1.10, обратный переход – на рис. 1.11.

Рис. 1.10. Преобразование автомата Мура к автомату Мили Рис. 1.11. Преобразование автомата Мили к автомату Мура Совмещенный автомат (автомат Мура + автомат Мили). При использовании на практике автомат Мура и автомат Мили имеют свои специфические особенности. Так, автомат Мура, несомненно, более привлекателен для задач управления, при ожидании сигнала обратной связи.

В этом случае установленный сигнал держится до тех пор, пока не придет сигнал о срабатывании устройства. Ожидание внешнего события удобнее всего реализовывать в одной функции-состоянии, в то время как внутренние вычисления, не требующие обратной связи, удобнее производить с использованием автомата Мили. Как правило, в реальных задачах возникает необходимость в обоих типах операций.

Соображения практического характера говорят о целесообразности использования совмещенной модели автомата Мили и Мура – С-автомата.

Проблема заключается в том, что автоматы Мили и Мура при попытке совместного использования начинают конфликтовать: вспомним, что в автомате Мура выходное значение – это неизменная для текущей функции-состояния константа, в то время как в автомате Мили она может меняться в зависимости от состояния входов. В теории автоматов в качестве средства разрешения конфликта предлагается разбивать входной алфавит на два непересекающихся подмножества.

В терминах модифицированной модели конечного автомата это означает появление второй выходной переменной.

Особенности использования конечных автоматов в начале компьютерной эпохи. Теория автоматов активно развивалась на фоне процесса быстрого вытеснения аналоговых управляющих систем дискретными автоматическими устройствами в эпоху зарождения цифровой техники.

В начале этого процесса отсутствовали не только высокоразвитые системы программирования и среды разработки, без которых в настоящее время невозможно представить цифровую технику. Отсутствовали языки высокоуровневого программирования. Не было даже концепции ассемблеров.

Все «программирование» велось в терминах нулей и единиц, в терминах самых примитивных операций. Машинные команды 8-разрядных процессоров были бы восприняты в конце 1950-х гг. как непозволительная роскошь. Эти обстоятельства следует учитывать при анализе возникавших в то время идей и применявшихся подходов. В рамках теории автоматов конструировались не программы, а устройства. На решение этой проблемы и были направлены основные усилия теоретиков.

слева направо. Считывающая головка (СГ) считывает символы из ячеек входной ленты (ВхЛ). Эти символы поступают на вход дискретного устройства (ДУ). В соответствии со считанными значениями и внутренним «конечно-автоматным» алгоритмом ДУ формирует выходную последовательность значений, которая записывается в ячейки выходной ленты (ВыхЛ) посредством записывающей головки (ЗГ).

Несмотря на присущий конечному автомату механицизм, его концептуальная схема достаточно универсальна. Например, она позволяет хорошо описывать формальные языки и грамматики. Один из мощных разделов теории автоматов – математическая лингвистика, в частности, широко используемая при создании трансляторов языков программирования.

Другая широчайшая область их применения – конструирование информационно-управляющих систем, в котором «входная» и «выходная»

ленты служат для общения с внешней средой, например с объектом управления. «Входная лента» подменяется потоком данных о состоянии объекта управления, а «выходная лента» – сигналами управления, формируемыми управляющим алгоритмом.

Большой вклад в развитие теории автоматов и разработку методов их практического применения в информационно-управляющих системах внесли отечественные ученые-кибернетики, такие как В. М. Глушков, М. А. Гаврилов, С. И. Баранов и многие другие.

Синтез конечного автомата. Схемный подход.

В классическом подходе, в создание которого значительный вклад внес Виктор Михайлович Глушков, при построении сложного дискретного устройства выделяется несколько этапов.

блочного синтеза, осуществляется разбиение схемы автомата на отдельные более простые блоки-автоматы и определяется общий план обмена данными между этими блоками.

На в т о р о м этапе, который называется этаГлушков пом абстрактного синтеза, строится алгоритм блоков в (1923–1982) виде конечного автомата, выбирается форма описания, определяются функции-состояния без привязки к реализующим автомат элементам.

Т р е т и й этап – структурный синтез, выбор логических и запоминающих элементов (триггеров, И-НЕ сборок и т. п.) для построения спроектированных блоков, и на основе специальных формальных методик – так называемых «канонических уравнений» – общая задача синтеза автомата-блока сводится к синтезу схем из элементов дискретного действия, не обладающих памятью.

Следующим, ч е т в е р т ы м этапом является синтез этих последних схем, называемый обычно комбинационным синтезом.

алгоритма, возникающей из-за параллельности исполняемых операПрофессор С. И. Баранов читает лекцию ций в логических элементах) – В результате теоретических исследований выяснилось, что очень хорошо поддаются формализации третий и четвертый этапы проектирования, частично второй этап. Удовлетворительную формализацию первого и второго этапа получить не удалось. Отсутствие формальных методик в паре с экспоненциальным ростом объема работы при линейном росте размерности объекта (размерности входной / выходной переменных) существенно ограничивали сложность автоматизированных объектов.

Вопросы для самопроверки Вопрос 1. Что такое s(t), при t = 0 в автомате Мили? В автомате Мура?

Вопрос 2. Чему равно o(t), при t = 0 в автомате Мили? В автомате Мура?

Вопрос 3. Определить число ячеек таблицы при табличном задании автомата Мили при числе состояний 10, при 8-битовых входной и выходной переменных x, y?

Вопрос 4. Какие из этапов синтеза конечного автомата нетипичны для современных методик программирования? Какие проблемы сходны?

2. Специфика задач промышленной автоматизации В настоящее время практически вся промыш- Датчики реализуется на цифровых системах управления.

В качестве базового эле- Двигатели мента систем управления Источники используются программи- питания руемые логические контроллеры (ПЛК). ПЛК имеют в своем составе микропроцессорный модуль, множество входов и выходов, и программное обеспечение – управляюуправления щий алгоритм (УА), который реализует разнообразные функции: контролирует значения входных / выходных сигналов, выполняет логические / арифметические операции, осуществляет регулирование, обеспечивает связь с датчиками и исполнительными органами (клапанами, насосами, двигателями, источниками питания, регуляторами). ПЛК могут работать автономно в полностью автоматических системах, или же такая базовая схема может усложняться.

Например, ПЛК могут подключаться к автоматизированному рабочему месту (АРМ) оператора для осуществления супервизорного управления или к базам данных для накопления информации и интеграции в автоматизированную систему управления (АСУ) предприятия. Через датчики в ПЛК поступает информация о текущем состоянии управляемого объекта, а через исполнительные органы ПЛК может воздействовать на него – управлять технологическим процессом.

Поскольку все ПЛК строятся на базе цифровой техники, естественным образом предполагаются некоторые языковые средства их программирования. Из-за специфики задачи алгоритмические языки программирования, такие как Си, Паскаль, Си++ не годятся для этих целей.

Анализ специфики задач промышленной автоматизации, в результате которого эти задачи удалось выделить в отдельный класс, был проведен Аркадием Дмитриевичем Закревским при разработке специализированного языка ПРАЛУ.

Открытость, цикличность и событийность. Существенное отличие задач автоматизации от задач для персонального компьютера – это открытость, наличие внешней (по отношению к системе управления) среды – управляемого объекта – и активное воздействие на нее через органы это обстоятельство обусловливает цикличность управляющего алгоритма по схеме, уже обсуждаемой ранее: «считывание состояния входных сигналов через датчики» – «их обработка и формирование выходных сигналов» – «выдача выходных сигналов на исполнительные органы».

Открытость и устойчивое функционирование механизмов во внешней среде изучаются в гомеостатике, свойства событийности исследуются в теории реагирующих систем.

Синхронизм и временные интервалы. Управляемый объект принадлежит физическому миру, подчиняется объективным законам физики, химии, биологии. Если, скажем, автоматизируется рост дрожжевых палочек в автоклаве и для выращивания партии дрожжей требуется 250 кВт · час, то эта энергия должна подаваться в систему равномерно и в течение длительного времени, около двух суток. Наивная попытка вкачать эту энергию как можно быстрее приведет к тому, что микроорганизмы погибнут от перегрева. Механические элементы конструкции, например клапаны, не могут отработать управляющий сигнал мгновенно. Для передачи пакета данных требуется время, зависящее от длины пакета и скорости передачи.

Увеличив силу тока на массивном нагревательном элементе, ошибочно ожидать мгновенного установления равновесного режима по температуре.

Иными словами, существуют вполне объективные временные требования к порядку выдачи управляющих воздействий. Таким образом, алгоритм управления предполагает синхронизацию своего исполнения с физическими процессами во внешней среде. Это обусловливает необходимость развитой службы времени и активную работу с временными объектами: задержками, паузами, тайм-аутами. Проблемами синхронизации иногда занимаются в рамках так называемых систем «реального» времени.

Примечание. Вообще в большинстве случаев, когда разговор заходит о «реальном времени», подразумевается решение проблемы нехватки вычислительных ресурсов и выбора алгоритма планирования для организации исполнения нескольких независимых задач на одном процессоре. Иногда это словосочетание и вовсе не имеет четкого технического смысла, используется чисто в маркетинговых целях, для позиционирования продукта на рынке. Например, достаточно часто встречается слоган «ОС QNX – система реального времени».

Логический параллелизм. Другая характерная особенность алгоритмов управления – логический параллелизм, отражающий существование множества параллельно протекающих процессов в объекте управления.

Регулирование температуры, давления, скоростей перемещения и вращения рабочих органов технологической системы по определению допускают и, более того, предполагают параллельность в работе алгоритма управления. Поскольку события, происходящие в различных компонентах системы, возникают независимо и в произвольной последовательности, то попытка задать реакцию системы единым блоком означает комбинаторный перебор большого числа вариантов и неоправданный рост сложности описания. Логический параллелизм предполагает наличие в алгоритме управления независимых или слабозависимых частей.

Следует сразу отметить, что параллелизм алгоритмов управления отличается от параллелизма высокопроизводительных многопроцессорных или многомашинных вычислительных систем. Параллелизм высокопроизводительных систем, или так называемый физический параллелизм, направлен на сокращение времени получения результата некоторого вычислительного алгоритма и исследуется в рамках параллельного программирования.

Для систем автоматического управления получение результата в минимальные сроки в подавляющем большинстве практических случаев неактуальна (см. выше «синхронизм и временные интервалы»), параллелизм используется для того, чтобы упростить логическую структуру алгоритма управления.

Сложность и человеческий фактор. Механизмы структуризации и абстрагирования. Поскольку программы пишутся человеком и исключительно для человека, то на процесс создания алгоритмов сильное влияние оказывает человеческий фактор: человеческая психика устанавливает естественные ограничения на сложность объектов, с которыми человек может работать. Поэтому при создании алгоритмов (в частности, и управhttp://reflex-language.narod.ru ляющих) языки программирования предусматривают различные средства, позволяющие упростить работу с программой. Среди основных средств такого плана следует указать механизмы структуризации алгоритма (в нашем случае – средства описания и организации совместного функционирования логически параллельных частей) и механизмы абстрагирования (в нашем случае – понятийный переход от датчиков и исполнительных органов к целевому технологическому процессу). Иными словами, программа должна быть организована в виде обозримых, информационноизолированных компонентов, возможно, иерархически вложенных друг в друга, и на некотором уровне иерархии программирование должно вестись в естественных терминах технологического процесса.

Степень соответствия модели конечного автомата специфике задач управления. Несмотря на то что модель конечного автомата достаточно привлекательна для решения простых задач автоматизации, лежит в основе целого ряда языков и подходов, изучается в физико-технических вузах и исторически разрабатывалась для решения задач логического управления, ряд серьезных недостатков ограничивает ее практическое использование в программировании. Главным образом недостатки обусловлены тем фактом, что специфика алгоритмов управления учтена в модели конечного автомата не в полной мере.

Обсудим эти недостатки, крайне усложняющие работу по описанию реальных алгоритмов управления.

Модель конечного автомата несет на себе груз идеи схемной реализации алгоритмов, причем реализации на базе микросхем малой степени интеграции. Поэтому попытка использовать в современных программных комплексах понятийный аппарат стандартных этапов синтеза автоматов (структурный синтез, комбинационный синтез, надежностный синтез), напрямую связанных с элементной базой реализации, приводит к низкоуровневому программированию – неэффективному, чреватому ошибками, а, значит, и недопустимому для использования на практике.

В модели конечного автомата отсутствуют операции работы со временем.

В рамках теории конечного автомата так и не удалось выработать эффективных и универсальных методов блочного синтеза автоматов, необходимых при конструировании реальных алгоритмов, предполагающих структурную компоновку алгоритма, активное использование логического параллелизма: дивергенции (расхождения) и конвергенции (схождения) потоков управления.

Концепция входного и выходного алфавита крайне затрудняет описание арифметических операций и делает невозможным использование операций сравнения, присваивания. Это ограничивает область применения МКА системами логического управления, которые крайне редко встречаются на практике в чистом виде. Концепция переменной выглядит в данhttp://reflex-language.narod.ru ном случае более предпочтительной в силу гибкости. Другой негативный момент теории автоматов – это сам формальный математический подход.

Манипулирование нулями и единицами, не привязанное к семантике автоматизируемого процесса, провоцирует примитивные логические ошибки, крайне усложняет как процесс создания алгоритма, так и процесс его дальнейшего сопровождения (изучение, верификацию, модификацию, в частности, коррекцию обнаруживаемых ошибок).

Модель конечного автомата сложна для понимания современным выпускником школы или вуза, так как ее понятийный аппарат не соответствует текущим тенденциям в образовании, ориентированном на информационные технологии и тотальную компьютеризацию.

Перечисленные недостатки приводят к тому, что практическое применение модели конечного автомата в формате «as is» на современном этапе крайне неудобно в силу сложности и ненадежности. Создание программных управляющих систем характеризуется высокой трудоемкостью и отсутствием унифицированного подхода.

Чтобы создать теоретический базис для высоконадежных методов описания управляющих алгоритмов повышенной сложности, требуется адаптация модели конечного автомата к современным реалиям индустрии и образования, чему и посвящены следующие разделы нашего пособия.

Вопросы для самопроверки Вопрос 1. Что такое «время»? (Сверьте свой ответ с определением из энциклопедического словаря) Вопрос 2. Рис. 2.2 изображает ситуацию с точки зрения алгоритма управления. Как, по-вашему, должен выглядеть рисунок с точки зрения объекта управления?

Вопрос 3. Попытайтесь составить таблицу отличий для логического и физического параллелизма. Сравните их по целям использования, типовым аппаратным платформам, достигаемым при их использовании преимуществам, присущим недостаткам и характерным проблемам. Попытайтесь выделить основной отличительный признак для обоих случаев.

3. Гиперавтомат 3.1. Процесс и событийный полиморфизм Вернемся к рассмотрению модернизированной модели конечного автомата, задаваемой пятеркой A = (F, x, y, fcur, f1), и поговорим немного о функциях-состояниях. В этой модели мы определили F = {f1,..., fk,..., fK} как множество альтернативных функций-состояний, отображающих x в y (y = fok (x), fok (x) O) и x в F (fcur = fsk (x), fsk (x) F). Сделаем следующее тривиальное замечание. Нет причин так жестко привязывать функциисостояния к уникальным переменным, как это делается в модели конечного автомата. Переменные для каждой функции-состояния могут быть уникальными. Таким образом, переменные могут привязываться исключительно к функции-состоянию. При этом функция-состояние может трактоваться исключительно в программистском смысле как обычная функция или процедура (функция, работающая с глобальными переменными). Сохраним наименование «функция-состояние» для отражения факта их альтернативности, переключаемости. Также в качестве возможных функций-состояний будем рассматривать и «пустые» функции, которые не производят никаких действий. Такие «пустые» функции, значение которых обсудим чуть позже, мы будем называть «пассивными», а все остальные – «активными».

Сделанные замечания позволяют ввести понятие «процесса». Процесс – это полиморфная функция, совокупность альтернативных функцийсостояний, представляемых в программе как единая неделимая сущность.

При вызове этой полиморфной функции (процесса) исполняется одна и только одна из составляющих его функций-состояний – текущая функциясостояние. Дополнительно к этому каждый процесс снабжен индивидуальными часами – счетчиком времени, который работает постоянно и обнуляется при смене текущей функции-состояния.

Таким образом, процесс pi задается четверкой элементов, которые отражают статическую и динамическую информацию о процессе:

где Fi – множество функций-состояний процесса (как активных, так и пассивных); f i1 – начальная функция-состояние (активная функция), f i1 Fi ;

f i cur – текущая функция-состояние, f i Fi ; Ti p – текущее время нахожcur дения процесса в текущей функции-состоянии, или текущее время отсутствия переходов.

Статика процесса определяется элементами Fi и f i 1, для рассмотрения процесса в динамике дополнительно используются элементы fi cur и Ti p.

3.2. Функция-состояние. События и реакция на событие В свою очередь, j-я функция-состояние произвольного i-го процесса задается парой элементов:

где X i j = { xij1,..., xijL } – множество событий f i j ; Yi j = { yij1,..., yijL } – множество реакций f i j.

В качестве события функции-состояния может рассматриваться произвольная суперпозиция фактов: значение текущей функции-состояния некоторого процесса, некоторое определенное значение переменной и некоторое определенное значение текущего времени отсутствия переходов процесса (оператор timeout).

Реакцией называется произвольная суперпозиция действий по изменению значений переменных и текущих функций-состояний процессов, определяемая на основе событий текущей функции.

Среди функций-состояний процесса Fi различаются взаимно непересекающиеся множества активных и пассивных функций-состояний, Fi a и Fi p соответственно. Функция-состояние процесса пассивна, если его множество реакций пустое:

Среди пассивных функций-состояний выделены функции f NS «нормальный останов» и f ES «останов по ошибке», которые одинаковы для всех процессов.

3.3. Математическая модель гиперпроцесса (гиперавтомата) Совокупность совместно функционирующих процессов образует гиперпроцесс (гиперавтомат) – надстройку над (гипер)процессами. Модель управляющего алгоритма в виде гиперпроцесса терминологически ориентирована на программную реализацию и позволяет отразить перечисленные свойства алгоритмов управления: открытость, событийность, цикличность, синхронизм и логический параллелизм.

Гиперпроцесс H представляет собой упорядоченный набор процессов, циклически активизируемых с периодом активизации TH :

где TH – период активизации гиперпроцесса; P – множество процессов (P = {p1, p2, …, pM}, где M – число процессов гиперпроцесса);

p1 – начальный процесс, p1 P.

По запуску гиперпроцесса текущая функция-состояние выделенного процесса p1 – начальное состояние, для всех остальных процессов текущее состояние – состояние нормального останова:

Пассивные функции служат для организации взаимодействия между процессами и начальной инициализации.

Циклическая схема функционирования гиперпроцесса (рис. 3.1) подобна схеме исполнения конечного автомата, и если не учитывать тот факт, что процессы слабосвязаны (влияют друг на друга), то единственные отличия – это множественность независимых блоков и тактируемость запуска циклов активизации (с периодом TH ).

Строго говоря, вопрос о том, как же активизируются процессы – физически параллельно или же последовательно, открытый, но для простоты Рис. 3.1. Цикл гиперавтомата. Множественность обрабатывающих блоков восприятия можно считать, что они активизируется последовательно, в порядке описания, как и показано на рис. 3.1. Заметим, что в этом случае гиперпроцесс представляет собой некоторый вариант кооперативной многозадачности, рассматриваемый в вузовских курсах при изучении операционных систем. В такой кооперативной многозадачности каждый процесс является по сути отдельным потоком управления, а сам гиперпроцесс – структурой логического параллелизма с гранулярностью (параллелизма) на уровне нескольких инструкций (функций-состояний).

Формальное описание функций-состояний. Функции-состояния описываются в стиле языка Си с помощью стандартных безусловных и условных if-else операторов произвольной вложенности. Например, для гипотеhttp://reflex-language.narod.ru тического процесса р3 описание начального состояния f 31 могло бы выглядеть следующим образом:

Комментарий к коду. Переменной у1 присваивается значение 1. Если текущая функция процесса р2 – это функция нормального останова, то переменной у1 присваивается значение 0. Процесс р2 переводится в начальное состояние, а текущая функция-состояние процесса р3 меняется на f 32.

В случае отсутствия других событий через три секунды ( T3z > 3 с) наступает событие тайм-аута и процесс р3 меняет свою текущую функциюсостояние на пассивную функцию «останов по ошибке».

Для большей наглядности записи используются следующие обозначения. Запуск процесса (установка его текущего состояния в начальное активное) обозначается через одноместный оператор start. Например, запись start f 2 эквивалентна записи f 2cur = f 21. Одноместные операторы stop и error служат для обозначения перевода в пассивные состояния нормального останова и останова по ошибке соответственно:

Ниже мы рассмотрим основные приемы, используемые при организации совместного функционирования процессов как единой совокупности – гиперпроцесса.

Организация совместного функционирования процессов. Поясним основные приемы работы с процессами. Поначалу ситуация всегда стандартна: активен только первый процесс, все другие пассивны. Это позволяет полностью контролировать начальное «разворачивание» алгоритма.

Перевод процесса в активное состояние – start pi – по сути порождает отдельный поток управления. Перевод процесса в пассивное состояние – stop pi или error pi – закрывает поток управления, ассоциируемый с процессом. Хотя при этом формально процесс продолжает активизироваться.

Аналогом вызова процедуры служит следующая конструкция.

Комментарий к коду. Из процесса p3 запускается процесс p2. Производится переход в следующее состояние. Ожидается событие «переход процесса p2 в пассивное состояние».

Соответственно сам процесс p2 предполагает по окончании переход в пассивное состояние. Различение пассивных состояний позволяет организовать передачу некой примитивной информации о возможных причинах завершения: возникновении ошибок при выполнении.

Следует отметить, что при порождении нового потока управления порождающий поток управления не прекращает свою работу. Также при порождении новых потоков управления не возникают какие-либо отношения родственности между потоками управления. Последнее обстоятельство позволяет организовывать очень гибкие иерархические структуры.

Например, в любом процессе можно организовать дивергенцию потока управления произвольной степени. Последующая конвергенция также не вызывает проблем. Ниже приведен пример кода (гипотетический процесс p3), порождающий два потока (процессы p4 и p5) с их последующей конвергенцией.

... etc.

Вопросы для самопроверки Вопрос 1. Какие недостатки с точки зрения восприятия присущи использованным тут формальным нотациям? Каким способом, по-вашему, это можно устранить?

Вопрос 2. Какие способы организации логического параллелизма вам известны?

Вопрос 3. Известно, что любые операции занимают время. Какие, на ваш взгляд, ограничения на ресурсоемкость алгоритма присущи модели гиперпроцесса?

Вопрос 4. Попытайтесь предложить способ для вычисления T i p. В качестве разминки ответьте, какие значения T i p будет принимать во время исполнения при предположении, что время отработки алгоритма много меньше периода активизации гиперпроцесса ТН ?

4. Реализация гиперавтомата 4.1. Логический параллелизм Рассмотрим следующий пример. Сначала распараллелим некоторую задачу, а затем выполним ее в рамках однопроцессорной архитектуры.

С точки зрения цели физического параллелизма это выглядит как полный абсурд, так как время расчета увеличивается. Но есть ли у такого подхода положительные моменты? Несомненно. С точки зрения удобства программирования в таком распараллеливании легко обнаруживается глубокий смысл.

«Разделяй и властвуй»: старая поговорка имеет для программистов форму закона. Сложность современных программных систем может быть преодолена только путем разбиения проблемы на множество обособленных частей, и наоборот. Программные комплексы произвольной сложности могут строиться только на основе независимых или, в крайнем случае, слабо зависимых компонентов. А это также подразумевает максимальную обособленность частей с целью минимизации перекрестных связей, что необходимо для эффективной организации групповой разработки.

Выделение параллельных (а вернее, независимых) сущностей исходя из соображений удобства программирования – в первую очередь, с целью снизить сложность описания системы, – верный признак логического параллелизма.

Популярность операционных систем во многом обусловлена именно этим – возможностью конфигурирования функциональной среды отдельно взятого компьютера из набора параллельно исполняемых компонентовзадач. При вызове менеджер задач в любой многозадачной операционной системе покажет около десятка задач, выполняющих параллельно незаметную, но необходимую работу. В дополнение к этим задачам пользователь может запустить проигрыватель mp3-файлов, антивирусный мониторинг, редактор, почтовую программу и браузер… причем открытых для редактирования файлов и окон браузера может быть несколько. Попытка связать такую функциональность в целое и описать единым блоком однозначно приводит к комбинаторному взрыву сложности.

Логический параллелизм на уровне операционных систем называется многозадачным логическим параллелизмом. Планировщик – выделенная задача операционной системы – занимается переключением процессора с одной задачи на другую. Алгоритмы таких переключений могут быть как примитивными, так и весьма сложными. Самый простой – алгоритм разделения по времени. Планировщик работает с очередью задач и активизируется по прерываниям от таймера с некоторым заданным периодом (обычно это десятки миллисекунд). После активизации он сохраняет контекст теhttp://reflex-language.narod.ru кущей задачи, ставит ее в конец очереди, восстанавливает контекст следующей задачи из очереди и запускает ее на исполнение.

Поскольку задачи различны по исполняемым функциям и ресурсоемкости, возникает проблема, как распределить вычислительную мощность процессора соразмерно задачам. В этом случае базовый алгоритм может усложняться. Например, механизмом приоритетов, когда задачам присваиваются приоритеты и при смене задач управление передается наиболее приоритетной. В системе может быть предусмотрено динамическое изменение приоритетов. Планировщик может вызываться по прерываниям не только от таймера, но и от других источников прерываний. Вызов планировщика может быть предусмотрен и по требованию активной задачи, после выполнения необходимых высокоприоритетных операций. Однако появление гибкости сопровождается повышением накладных расходов на планирование, сильно зависящих от числа обслуживаемых задач.

Преимущества мелкозернистого логического параллелизма. Задача с уникальным набором данных и функций достаточно тяжеловесна для вызова и обслуживания. Многозадачный логический параллелизм предполагает небольшое количество задач (обычно в пределах одного десятка).

Между тем существуют области, в которых необходим мелкозернистый логический параллелизм (разбиение задачи на большое число мелких независимо исполняемых частей). В серверах баз данных, новостных интернет-порталах, мобильных сервисах, обслуживающих распределенные системы из нескольких сотен тысяч абонентов, требуется механизм независимого обслуживания тысяч одновременно поступающих запросов.

В таких системах надо не только не пропустить поступивший запрос, но и обслужить его, возможно, организовав интерактивный диалог, контроль достоверности, перезапрос информации в случае ошибки.

Мелкозернистый логический параллелизм также чрезвычайно эффективен в задачах управления сложным промышленным оборудованием.

Необходимость отражать параллелизм процессов, протекающих на объекте управления, требует создавать по меньшей мере сотни параллельно исполняемых процессов. Например, алгоритмически эквивалентное «монолитное» решение в виде одного процесса (конечного автомата) для практической задачи управления выращиванием монокристаллического кремния приводит к рассмотрению 1030 (sic!) различных ситуаций.

Сжатие информации достигается при логическом параллелизме за счет упрощения описания комбинаций независимых случаев: описание алгоритма как набора независимых частей – это описание суммы ситуаций, в то время как монолитное описание – это описание произведения ситуаций.

Редукция сложности за счет распараллеливания выражается следующей формулой:

(L – число независимых участков кода, Ni – число состояний).

Невообразимое число ситуаций (1030) может быть получено всего лишь из сотни параллельно исполняемых процессов с двумя состояниями, в то время как независимое описание алгоритма – это рассмотрение всего 200 уникальных случаев.

Многопоточный логический параллелизм. Очевидные преимущества мелкозернистого логического параллелизма заставляют искать пути снижения накладных расходов, присущих многозадачности. Известные решения для операционных систем – это легковесные процессы (lightweight process), – например, в Sun OS 5.x, – облегченный вариант задач, и потоки (thread), состояние которых полностью характеризуется значениями регистров-указателей на код и стек. Переключение процессора на поток минимизировано, таким образом, до операций сохранения / восстановления этих указателей. Планировщик по-прежнему присутствует и активизируется по прерываниям от таймера.

Необходимо отметить, что переключение потоков по времени не всегда удобно и приводит к непроизводительным простоям процессора. Если в некотором потоке для продолжения вычислений требуется внешнее событие (отклик оборудования, реакция абонента на запрос, подтверждение успешной передачи сообщения), то поток честно тратит отведенное ему время на ожидание:

Step1();

while (!EventOnStep1());

Step2();

Если для появления реакции на действие требуется значительное время (например, событие – это реакция пользователя на запрос системы), то более приемлемой стратегий была бы передача управления после опроса.

Этот подход используется при организации многопоточности методом циклического опроса (round-robin), иногда обозначаемом термином «кооперативная многозадачность». При циклическом опросе потоки могут быть представлены просто функциями, которые опрашиваются в бесконечном цикле:

Необходимость ожидания внешней реакции естественным образом задает разбиение потоков на части. Каждая из таких частей является простейшей функцией. Если присвоить каждой из таких частей число, то реализация потоков естественным образом выражается в терминах языка Си.

При этом неожиданно выясняется, что такая реализация не больше и не меньше, чем реализация конечного автомата, в части организации работы с состояниями:

thread_i () { switch (State_i) { case STATE_1:

if (EventOnStep1()) State_i = STATE_2; /* смена состояния */ case STATE_2:

Чтобы убедиться, что приведенный участок кода соответствует классическому конечному автомату, заключите его в бесконечный цикл for (;;) { }.

Таким образом, для многопоточности можно минимизировать или даже полностью исключить накладные расходы, присущие многозадачности.

А простота организации делает многопоточность крайне привлекательной для организации мелкозернистого логического параллелизма.

К сожалению, получаемый выигрыш от многопоточности также связан с рисками потенциально возможных ошибок (которые могут возникнуть, например, из-за общей области данных). К счастью, эти риски могут быть радикальным образом снижены за счет специальных механизмов, которые мы обсудим чуть позже.

4.2. Использование процедурных языков Описанный подход является классическим при программной реализации конечного автомата на процедурных языках. В этом подходе организуется бесконечный цикл вызова конструкции, соответствующей конечному автомату. Конкретизируем запись автомата Мура А2, заданного таблицей 1.5, и вместо абстрактных идентификаторов подставим конкретные числовые значения (табл. 4.1). (Как мы помним, в силу соображений, приведенных в п. 1.3, эта подстановка дает эквивалентный автомат, в качестве числовых значений использованы индексы при идентификаторах.) Таблица 4.1. Численная конкретизация автомата Мура A Опишем приведенный в таблице алгоритм на языке Си-файла.

Можно построчно убедиться, что приведенный алгоритм полностью идентичен заданному в табл. 4.1.

Чего не хватает для реализации гиперавтомата «в лоб»? Во-первых, автомат только один, а, во-вторых, нет службы времени. Первая проблема решается просто: дополнительные автоматы (процессы) означают дублирование переменных х, у, s. Но как быть со службой времени? Поступим следующим образом. Введем функцию инициализации таймера InitTimer (int T), которая будет настраивать таймер на генерацию прерываний в заданное параметром T число миллисекунд, а в процедуре обработки прерывания инкрементировать переменную InterruptFlag. Таким образом, тактирование будет обеспечиваться следующей конструкцией.

if (InterruptFlag) { Далее встает вопрос о текущем времени отсутствия переходов Ti для каждого процесса. Выход очевиден: для каждого процесса заводим дополнительную переменную ti, которую будем инкрементировать при каждом вызове и обнулять при каждом переходе.

Для краткости приведем фрагмент:

BYTE x, y, s, t; /*nn-й процесс*/ InitTimer(10);

if (InterruptFlag) { Input(x1); /* считывание входных переменных */ Output(y1); /* запись выходных переменных */ Составление списка недостатков для приведенного способа реализации автомата и гиперавтомата не представляет особого труда. Их много и они лежат на поверхности. Недостатки связаны с многочисленными рутинными операциями, прямой работой с числами и операциями с большим количеством глобальных переменных. Программы, написанные таким способом, чрезвычайно ненадежны, их составление трудоемко, их дальнейшая модификация практически исключена. При программировании происходит полный разрыв со смыслом задачи, остаются неясными вопросы интерфейса с УСО, реализация допускает различные подходы, что, опять же, затрудняет чтение алгоритмов, написанных в этом стиле. Верификация алгоритма даже с помощью специально разработанных методик не гарантирует отсутствия ошибок. Более того, при проверке экспоненциально расhttp://reflex-language.narod.ru тущих вариантов для сколько-нибудь серьезной программы практически невозможно не только проанализировать лог-файлы, но и вообще получить таковые.

Чтобы лучше прочувствовать методику программирования «в лоб», используем приведенный способ и опишем процесс открытия отсечного вакуумного клапана.

Рис. 4.1. Работа клапана. Слева – клапан в закрытом состоянии, справа – состояние после нормального включения (открытия) Постановка задачи. Имеется вакуумный клапан, который имеет один управляющий вход (для системы управления – это выходной сигнал y) и один сигнал положения (для системы управления – это входной сигнал x).

В исходном закрытом состоянии значения обоих сигналов – 0 (рис. 4.1).

При подаче на вход клапана единицы клапан должен открыться в течение 0,5 секунды (сигнал положения должен принять значение 1). В противном случае диагностируется отказ клапана.

InitTimer(10);

if (InterruptFlag) { В заключение обсудим еще один важный момент предложенной реализации гиперавтомата. Кстати, этот момент мы затрагивали в вопросах для самопроверки в предыдущем параграфе. Речь идет о третьем вопросе – вопросе о ресурсоемкости алгоритма. Дело в том, что когда время, требуемое для обсчета цикла гиперавтомата, превышает период активизации, наступает очевидное логическое противоречие, связанное с нехваткой ресурсов: необходимость начать новый цикл возникает до того, как предыдущий цикл был обсчитан. Это обстоятельство предполагает выполнение некоторых условий на ресурсоемкость алгоритма. Проблема эта, разумеется, не нова. Например, для решения аналогичных проблем в рамках проекта по языку Esterel была выдвинута гипотеза идеального синхронизма (perfect synchrony hypothesis). Гипотеза устанавливает, что в рамках модели языка Esterel накладные расходы на вычисления и связь между компонентами равны нулю. Разумеется, в рамках гиперавтомата можно снизить требование этой гипотезы до разумного уровня и переформулировать ее следующим образом. Время, затрачиваемое на организацию и выполнение алгоритма при реализации модели гиперавтомата, не должно превышать периода активизации гиперавтомата TH.

Вопросы для самопроверки Вопрос 1. Какое число состояний возникнет при «монолитном» рассмотрении 10 независимых алгоритмов с четырьмя состояниями в каждом?

Вопрос 2. Предложите альтернативный способ организации тактированного циклического исполнения гиперавтомата.

Вопрос 3. Какие методы могут быть использованы в рамках процедурных языков для исключения недостатков реализации конечного автомата и гиперавтомата «в лоб»?

4.3. Языки стандарта МЭК 61131- и возможные альтернативы В 1993 г. Международная электротехническая комиссия выпустила в свет третью часть стандарта МЭК 61131-3. Этот международный стандарт входит в группу МЭК 61131-стандартов, которые охватывают различные аспекты использования программируемых логических контроллеров, т. е.

предназначены для программирования информационно-управляющих систем. Декларируемые цели МЭК 61131-3 – стандартизация существующих языков ПЛК, а вернее, базовая платформа для такой работы в национальных комитетах стандартизации. Кратко остановимся на особенностях стандарта, затем проанализируем языки стандарта на соответствие специфике задачи и обсудим приемы создания с их помощью управляющих алгоритмов, близких по свойствам к гиперавтомату.

Международная электротехническая комиссия. Цели создания стандарта на языки программирования ПЛК Международная электротехническая комиссия – это международный орган стандартизации, создающий базовые стандарты для последующей адаптации в национальных комитетах. Интересный факт, которым могут гордиться граждане России: в создании и работе этой комиссии принимал активное участие СССР, поэтому русский – один из трех официальных языков МЭК.

Что касается стандартизации языков, используемых для программирования ПЛК, то эта проблема назрела давно. К концу 1980-х гг. несколько базовых концепций на практике были представлены сотней вариаций.

Их унификация сулила ощутимый экономический эффект. Для решения этой проблемы была создана рабочая группа, состоящая из представителей ведущих игроков на рынке автоматизации, которая начала работу.

В силу того что общепринятого подхода к программированию ПЛК не существовало (и сейчас не существует), членам комиссии договориться о едином языке не удалось. Поэтому было принято компромиссное решение – включить в стандарт языки, используемые в фирмах, представителям которых посчастливилось оказаться членами комиссии.

Среди языков-«счастливцев» оказались:

1. SFC (Sequential Function Chart) – графический язык, используемый для описания алгоритма в виде набора связанных пар: шагов (step) и переходов (transition). Шаг – набор операций над переменными, переход – набор логических условных выражений, определяющий передачу управления к следующей паре шаг-переход. По внешнему виду описание на языке SFC напоминает хорошо известные логические блок-схемы алгоритмов, хотя идеологически SFC близок к сетям Петри. SFC имеет возможность распараллеливания алгоритма, однако не имеет средств для описания шаhttp://reflex-language.narod.ru гов и переходов, которые могут быть выражены только средствами других языков стандарта. Происхождение: язык Grafcet фирмы TelemechaniqueGroupe Schneider. Пример кода, созданного с использованием языка SFC, приведен на рис. 4.2.

2. LD (Ladder Diagram) – графический язык, стандартизованный вариант класса языков релейно-контактных схем (РКС). Основной выразительный элемент – «реле». Реле представлено парой: обмотка (аналог выходной переменной) и контакт (аналог входной переменной). Контакты и обмотки между собой и с левой, и с правой силовой шиной соединены горизонтальными линиями («проводниками»). РКС были очень мощным средством автоматизации в докомпьютерную эпоху.

Сильнейшие школы теоретиков автоматизации на базе РКС существовали в СССР, одна из них – школа Михаила Александровича Гаврилова. РКС были настолько идеи, заложенные в РКС, были реализованы в виде специализированного языка программирования. Это оказалось очень удобно при внедрении ПЛК: старые кадры очень быстро осваивали язык программирования, поскольку концептуальный уровень (метафора реле) осМихаил Александрович Ввиду своих ограниченных возможностей язык доГаврилов полнен привнесенными средствами: таймерами, счетчиками и т. п. Происхождение: различные варианты языка релейно-контактных схем, поддерживаемые в компаниях Allen-Bradley, AEG Schneider Automation, GE-Fanuc, Siemens. Пример кода, написанного на языке LD, приведен на рис. 4.3.

3. FBD (Functional Block Diagram) – графический язык по своей сути похожий на LD: вместо реле в этом языке используются функциональные блоки. Алгоритм работы некоторого устройства, выраженный средствами этого языке, напоминает функциональную схему электронного устройства:

элементы типа «логическое И», «логическое ИЛИ» и т. п., соединенные линиями (рис. 4.4). Корни языка выяснить сложно, однако большинство специалистов сходятся во мнении, что это язык, подобный LD, но использующий в качестве метафоры другую элементную базу.

4. ST (Structured Text) – текстовый высокоуровневый язык общего назначения, по синтаксису ориентированный на Паскаль (рис. 4.5).

Самостоятельного значения не имеет; используется совместно с SFC.

Происхождение: язык Паскаль, язык Grafcet фирмы TelemechaniqueGroupe Schneider.

5. IL (Instruction List) – текстовый язык низкого уровня. Выглядит как язык Ассемблера (рис. 4.6), что объясняется его происхождением: для некоторых моделей ПЛК фирмы Siemens является языком Ассемблера.

В рамках стандарта IEC 1131-3 он не привязан к архитектуре конкретного процессора. Самостоятельного значения не имеет: используется совместно с SFC. Происхождение – язык STEP 5 фирмы Siemens.

Основные недостатки МЭК 61131-3. Мифологемы стандарта.

При анализе стандарта выявляются некоторые моменты, которые следует сразу обсудить.

Во-первых, имеется перекос в выборе языков. С одной стороны, в стандарт попадает ассемблер (IL), с другой стороны, чрезвычайно мощная ветка так называемых языков машин конечных состояний FSM оказывается за рамками рассмотрения.

Во-вторых, некорректным и дезориентирующим пользователей решением МЭК стала группировка языков в едином стандарте, что в корне отличается от общепринятых подходов к стандартизации языков программирования (см., например, стандарты ANSI C, Ada и т. д.).

В-третьих, стандарт исключает из рассмотрения вопросы унифицированного представления графических языков стандарта, что автоматически означает проблемы совместимости продуктов разных производителей. Эта особенность стандарта сводит практически на нет выгоды от его использоhttp://reflex-language.narod.ru вания. Кроме того, в стандарте МЭК61131-3 не рассматривается вопрос привязки алгоритма к интерфейсной аппаратуре, которая с необходимостью присутствует в любой системе управления.

Вокруг стандарта МЭК 61131-3 возникло несколько мифологем, основные из которых рассмотрены ниже.

Мифологема 1. Для программирования ПЛК допускается применять только языки стандарта МЭК 61131-3.

Комментарий. Это неверно. Для программирования ПЛК могут применяться произвольные языки, естественно, наиболее адекватные решаемой задаче. Более того, во многих (если не в большинстве) средств программирования, ориентированных на МЭК 61131-3, язык Си – это, по сути, шестой язык программирования. Многие ПЛК по-прежнему программируются и языками класса FSM, и на языках Си / Си++.

Мифологема 2. Среда разработки МЭК 61131-3 должна обеспечивать возможность программирования на всех пяти языках.

Комментарий. Это неверно. Языки стандарта независимы, и разработчиками стандарта предполагалось, что средство программирования МЭК 61131-3 поддерживает только один язык из набора. Более того, мультиязыковые программы расцениваются как потенциально ненадежные и затратные в сопровождении. На практике нарушение принципа языковой однородности программ всегда вынужденно и просто отражает ограничения, присущие языкам МЭК 61131-3.

Мифологема 3. МЭК 61131-3 обеспечивает кросс-брендовую и кроссплатформенную переносимость пользовательских программ.

Комментарий. Это неверно. Стандарт специфицирует лишь внешний вид, синтаксис языков, что недостаточно для обеспечения переносимости графических языков (для текстовых – достаточно). Выбрав фирмупоставщика, пользователь с большой вероятностью навсегда связывает с ней свою судьбу. Также стандарт допускает создание несовместимых вариаций и регламентирует лишь наличие списка несоответствий стандарту.

Несомненно, перечисленные недостатки и дезориентирующие мифологемы на руку мегакорпорациям, так как крайне затрудняет передел сложившегося рынка и появление на нем новых игроков. Существуют и другие, более жесткие, мнения, в которых стандарт МЭК 61131-3 прямо называется контрпродуктивным. Не останавливаясь подробно на этом аспекте, можно посоветовать интересующимся статью об использовании стандартизации в конкурентной борьбе [6].

PLCopen. Попытка адаптировать стандарт для целей сообщества конечных пользователей Обеспечение кросс-брендовой переносимости и реальная стандартизация языков программирования ПЛК весьма актуальны для индустрии.

Функции сертификации и развития стандарта взяла на себя независимая организация PLCopen [www.plcopen.org], которая попыталась адаптировать стандарт МЭК 61131-3 к нуждам конечных пользователей.

PLCopen объединила средних и мелких игроков на рынке ПЛК, системных интеграторов и пользователей. Внутри PLCopen долгое время действовала группа по разработке независимого формата, обеспечивающего кросс-брендовую переносимость пользовательских программ. Была развернута активность по формированию и продвижению корректировок стандарта, отвечающих нуждам сообщества. Была разработана процедура и организована работа экспертных комиссий по сертификации CASEсредств, ориентированных на стандарт.

К сожалению, базовые подходы, использованные при разработке стандарта, оказали серьезное сопротивление деятельности PLCopen. Как следствие, работы по созданию переносимых программ были практически прекращены, предполагаемый формат, разрабатываемый для обеспечения переноса программ – FxF (File-eXchange-Format), – не получил поддержки.

Наиболее значимым результатом по корректировке стандарта явился, пожалуй, ввод локальных переменных. Сертификация CASE-средств ограничивается языками ST и IL (текстовыми языками, не имеющими самостоятельного значения). В силу этого обстоятельства проблема переносимости программ МЭК 61131-3 остается по-прежнему нерешенной. К большому сожалению, скептические прогнозы относительно будущего стандарта МЭК 61131-3, сделанные при его появлении рядом специалистов, стали реальностью.

Прагматика языков МЭК 61131-3. Выбор языка под конкретную задачу. Несмотря на недостатки, существуют вполне определенные ситуации, когда языки МЭК 61131-3 могут быть использованы на практике.

В относительно простых задачах, не предъявляющих строгих требований по надежности, языки МЭК могут оказаться экономически эффективными.

Даже в ситуации, когда языки МЭК слабо подходят для практической задачи, отказ от их использования совсем не очевиден. В первую очередь, это вызвано тем обстоятельством, что конечному пользователю или системному интегратору тяжело конкурировать с мегакорпорациями, разрабатывать и поддерживать альтернативные решения. Ведь, кроме собственно языка, в среду разработки входит набор вспомогательных программ и библиотек, существенно облегчающих работу по тестированию и настройке системы. Поэтому, несмотря на недостатки, языки МЭК 61131-3 вполне допустимо использовать. Но при выборе языка реализации проекта требуется учитывать особенности языков стандарта.

Ниже рассмотрены характеристики языков МЭК 61131-3 с точки зрения прагматики их использования и даны некоторые рекомендации по выбору.

Pages: |

| 2 |

Главная >> Методички

[ СКАЧАТЬ ОРИГИНАЛ ДОКУМЕНТА .pdf ]

Похожие работы:

«Минобрнауки России Филиал государственного образовательного учреждения высшего профессионального образования Вятского государственного гуманитарного университета в г. Кирово-Чепецке Кафедра экономики и управления УТВЕРЖДАЮ Зав. кафедрой экономики и управления Савиных Г.П. Подпись 03.02.2011 УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС учебной дисциплины Социология и психология управления для специальности: 080505.65 Управление персоналом Кирово-Чепецк Учебно-методический комплекс составлен в соответствии с ГОС...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Государственное образовательное учреждение высшего профессионального образования ГОРНО-АЛТАЙСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Кафедра безопасности жизнедеятельности и анатомии, физиологии ФИЗИОЛОГИЯ ФИЗИЧЕСКОГО ВОСПИТАНИЯ И СПОРТА Учебно-методический комплекс Для студентов, обучающихся по специальности 050720 Физическая культура Горно-Алтайск РИО Горно-Алтайского госуниверситета 2008 Печатается по решению...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ГОУ СПО ПЕРЕСЛАВСКИЙ КИНОФОТОХИМИЧЕСКИЙ КОЛЛЕДЖ ТЕХНОЛОГИЧЕСКАЯ КАФЕДРА Методические рекомендации по выполнению и защите курсовых работ По дисциплине Мониторинг загрязнений окружающей среды Для студентов специальности 280201 – Охрана окружающей среды и рациональное использование природных ресурсов 2010 2 Рассмотрена на заседании Составлена в соответствии Технологической кафедры с Государственными требованиями Протокол заседания к минимуму...»

«В.В. Коротаев, А.В. Краснящих ТЕЛЕВИЗИОННЫЕ ИЗМЕРИТЕЛЬНЫЕ СИСТЕМЫ Учебное пособие X Санкт-Петербург 2008 МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, МЕХАНИКИ И ОПТИКИ В.В. Коротаев, А.В. Краснящих ТЕЛЕВИЗИОННЫЕ ИЗМЕРИТЕЛЬНЫЕ СИСТЕМЫ Учебное пособие Санкт-Петербург УДК 621.397 + 681. В.В. Коротаев, А.В. Краснящих. Телевизионные измерительные системы / Учебное пособие. – СПб:...»

«Министерство образования и науки Российской Федерации Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования Тобольский государственный педагогический институт имени Д.И. Менделеева Кафедра алгебры и геометрии Утверждено на заседании кафедры алгебры и геометрии (протокол № 07 от 12.02. 2008 г.) ПРОГРАММА ДИСЦИПЛИНЫ “ДИФФЕРЕНЦИАЛЬНАЯ ГЕОМЕТРИЯ И ТОПОЛОГИЯ” Специальность: 050201.65 – “Математика” Специализация: “Алгебра и геометрия”...»

«Мир издательств РЕАЛИЗАЦИЯ ТРЕБОВАНИЙ ФГОС В УЧЕБНИКАХ БИОЛОГИИ ИЗДАТЕЛЬСТВА ДРОФА З авершённые линии учебно-методических комплексов по биологии, выпускаемые издательством ДРОФА, отличаются по структуре изложения материала и степени его сложности, что даёт педагогам возможность выбора учебников в зависимости от типа школы и уровня подготовки класса. Современный методический аппарат и актуальное содержание позволяют достигать личностных, метапредметных и предметных результатов образования. Об...»

«И.М. Прищепа Возрастная анатомия и физиология Допущено Министерством образования Республики Беларусь в качестве учебного пособия для студентов небиологических специальностей учреждений, обеспечивающих получение высшего образования МИНСК ООО НОВОЕ ЗНАНИЕ 2006 УДК [611+612](075.8) ББК 28.706/707я73 П77 Рецензенты: кафедра анатомии, физиологии и валеологии Белорусского государственного педагогического университета им. Максима Танка (зав. кафедрой — доктор медицинских наук Ю.М. Досин); кандидат...»

«Семь лекций по истории социологии. Гофман А.Б. ББК 60.5 Г 57 Издание осуществлено при поддержке книготорговой фирмы Гофман А. Б. Г 57 Семь лекций по истории социологии: Учебное пособие для вузов. -5-е изд. - М.: Книжный дом, 2001. - 216 с., ил. ISBN 5-8013-0137-2 В книге рассматриваются основные принципы истории социологии; анализируются ключевые идеи, из которых сформировалась социология и благодаря которым предыстория этой дисциплины превратилась в ее историю; представлены интеллектуальные...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, МЕХАНИКИ И ОПТИКИ С.Ф. Соболев Технология электромонтажа Санкт-Петербург 2007 УДК 65.015.13 Соболев С.Ф. Технология электромонтажа. Методические указания по разработке курсового проекта и подготовки к занятиям по технологии электромонтажа. –СПб СПбГУ ИТМО-2008-88с. Методические указания содержат описание видов электромонтажа...»

«Учреждение образования Федерации профсоюзов Беларуси Международный институт трудовых и социальных отношений Кафедра мировой экономики и финансов Курсовая работа и методические рекомендации по её выполнению для студентов заочной формы обучения по дисциплине Макроэкономика Рассмотрена и рекомендована к утверждению на заседании кафедры мировой экономики и финансов (Протокол № 1 от 28 августа 2007 года) Одобрена и рекомендована к утверждению научно-методическим и редакционноиздательским советом УО...»

«Учреждение образования БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ Кафедра технологии стекла и керамики Химическая технология стекла и ситаллов Программа, методические указания и контрольные задания для студентов специальности 1-48 01 01 Химическая технология неорганических веществ, материалов и изделий специализации 1-48 01 06 Технология стекла и ситаллов заочной формы обучения Минск 2007 1 УДК 666.11 (075.4) ББК 35.41 Х 46 Рассмотрены и рекомендованы к изданию...»

«Программа вступительных испытаний по специальной дисциплине по направлению 38.06.01 – Экономика 1.Особенности сельского хозяйства, как отрасли 2.Специализация и концентрация в сельском хозяйстве 3.Горизонтальная и вертикальная интеграция, ее формы в сельском хозяйстве 4. Кооперация в сельском хозяйстве 5. Понятия рынка и рыночного механизма, функции 6. Аграрная политика и государственное регулирование рынка в АПК 7. Понятие конкуренции и ее виды 8. Сущность и формы разделения труда 9. Сущность,...»

«Учреждение образования БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ Кафедра лесозащиты и древесиноведения ЛЕСНАЯ ФИТОПАТОЛОГИЯ Программа, методические указания и контрольные задания для студентов заочной формы обучения специальности 1-75 01 01 Лесное хозяйство Минск 2011 УДК 630*44(075.8) ББК 44.7я73 Л 50 Рассмотрены и рекомендованы к изданию редакционноиздательским советом университета Составители: А. В. Хвасько, В. Н. Кухта Рецензент кандидат сельскохозяйственных наук, доцент...»

«Инновационный менеджмент Кафедра менеджмента НГАСУ (Сибстрин) ИННОВАЦИОННЫЙ МЕНЕДЖМЕНТ СОДЕРЖАНИЕ ДИСЦИПЛИНЫ Тема 1. Методологические основы инновационного менеджмента. Введение. Инновационный менеджмент, предмет и задачи курса. Связь с социальноэкономическими, общепрофессиональными и специальными дисциплинами. Основные понятия инновационного менеджмента. Задачи и функции инновационного менеджмента. Социальнопсихологические аспекты инновационного менеджмента. Технология и методы инновационного...»

«ПРАВИТЕЛЬСТВО МОСКВЫ ДЕПАРТАМЕНТ ЗДРАВООХРАНЕНИЯ СОГЛАСОВАНО УТВЕРЖДАЮ Заместитель председателя Первый заместитель Учного медицинского совета руководителя Департамента Департамента здравоохранения здравоохранения Л.Г. Костомарова Н.Ф. Плавунов ПРИНЦИПЫ АНЕСТЕЗИИ У ДЕТЕЙ С ЦЕРЕБРАЛЬНЫМ ПАРАЛИЧОМ Методические рекомендации № Часть 1 Главный детский невролог Департамента здравоохранения Т.Т. Батышева Москва Учреждение разработчик: Научно-практический центр детской психоневрологии Департамента...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ ФГБОУ ВПО Уральский государственный лесотехнический университет Кафедра менеджмента и ВЭД предприятия Одобрена: Утверждаю: кафедрой менеджмента и ВЭД предприятия протокол № 1 от 2 сентября 2013 г. Декан ФЭУ В.П. Часовских Зав. Кафедрой _В.П. Часовских методической комиссией ФЭУ Протокол № 1 от 9 сентября 2013 г. Председатель НМС ФЭУ_ Е.Н. Щепеткин Программа учебной дисциплины Б3.В5 УПРАВЛЕНИЕ КАЧЕСТВОМ Направление 080200.62– менеджмент Трудоемкость- 4...»

«ISSN 2079-875Х УЧЕБНЫЙ ЭКСПЕРИМЕНТ В ОБРАЗОВАНИИ Научно-методический журнал ГУМАНИТАРНЫЕ НАУКИ ЕСТЕСТВЕННЫЕ НАУКИ ТЕХНИЧЕСКИЕ НАУКИ 2/2011 УЧЕБНЫЙ ЭКСПЕРИМЕНТ В ОБРАЗОВАНИИ Научно-методический рецензируемый журнал № 2 2011 июнь Основан в марте 1997 г. Выходит 4 раза в год ISSN 2079-875Х Издание журнала одобрено МИНИСТЕРСТВОМ ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Материалы первого этапа второй Всероссийской научно-практической конференции с...»

«Учебно-методические пособия (размножено в количестве 50-250 экз.) Экономика и бухгалтерский учет Банковское дело Операционная деятельность в логистике Статистика: Методические указания и контрольные задания для студентов заочного отделения по специальности 0601 Экономика и бухгалтерский учет и контроль/ Сост.: С.А.Ефимова. - Уфа: УГКТиДО, 2001.-25 с. 1 Анализ финансово-хозяйственной деятельности. Программа, методические указания и контрольные задания для студентов заочной формы обучения по...»

«Министерство образования и науки Российской Федерации Федеральное государственное автономное образовательное учреждение высшего профессионального образования Российский государственный профессионально-педагогический университет Институт социологии и права Кафедра права 6015/2010 МЕТОДИЧЕСКИЕ УКАЗАНИЯ И РЕКОМЕНДАЦИИ ПО ВЫПОЛНЕНИЮ И ОФОРМЛЕНИЮ ДИПЛОМНОЙ РАБОТЫ для студентов всех форм обучения специальности 050402.65 Юриспруденция (032700) (ГОС 2005) Екатеринбург 2010 Методические указания и...»

«ЧЕЛОВЕЧЕСКОЕ РАЗВИТИЕ: новое измерение социально экономического прогресса Программа развития ООН Экономический факультет МГУ им. М.В. Ломоносова ЧЕЛОВЕЧЕСКОЕ РАЗВИТИЕ: новое измерение социально экономического прогресса Учебное пособие Второе издание, дополненное и переработанное МОСКВА Издательство ПРАВА ЧЕЛОВЕКА 2008 ББК 67.91 4 39 Ч 39 Содержание данной книги не обязательно отражает точку зрения Программы развития Организации Объединенных Наций или какой либо иной организации, с которой...»

наверх

<< ГЛАВНАЯ | КОНТАКТЫ

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

ПРОГРАММИРОВАНИЕ

ИНФОРМАЦИОННО-УПРАВЛЯЮЩИХ СИСТЕМ

НА ОСНОВЕ КОНЕЧНЫХ АВТОМАТОВ

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ПРОГРАММИРОВАНИЕ

ИНФОРМАЦИОННО-УПРАВЛЯЮЩИХ СИСТЕМ

НА ОСНОВЕ КОНЕЧНЫХ АВТОМАТОВ

ОГЛАВЛЕНИЕ

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА (Авторефераты, диссертации, методички, учебные программы, монографии)

ПРОГРАММИРОВАНИЕ

ИНФОРМАЦИОННО-УПРАВЛЯЮЩИХ СИСТЕМ

НА ОСНОВЕ КОНЕЧНЫХ АВТОМАТОВ

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ПРОГРАММИРОВАНИЕ

ИНФОРМАЦИОННО-УПРАВЛЯЮЩИХ СИСТЕМ

НА ОСНОВЕ КОНЕЧНЫХ АВТОМАТОВ

ОГЛАВЛЕНИЕ

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)