Гипноз RS-триггера

© 2002 г. С. А. Ваганов

Можно скачать текст статьи в формате html (40 кб)

Введение

Во времена MS DOS, заведя разговор о резидентных программах, и сейчас, рассуждая о нитях и особенностях операции "fork" современных ОС, можно ввести в состояние гипноза далеко не новичка от программирования. Вот и В.С. Любченко своей сагой [1-3] о параллелизме RS - триггера, сумел добиться ошеломляющих результатов в этом направлении просто рассуждениями о параллелизме, по ходу дела отвергая нити и общепринятые понятия.

Опираясь на опыт, полученный при создании Флоры и проектировании систем АСУ ТП (сейчас это называется SCADA), а также на элементарные знания по использованию параллелизма в программировании, я смог избежать горькой участи персонажей эпиграфа.

Статья не ставит своей целью переубедить В.С. Любченко. Переписка, содержащая более сотни посланий, отголоски которой видны в эпиграфах [1, 2], говорит о невозможности этого. Одной из причин появления статьи стало желание вывести читателей из состояния гипноза. Может быть, я и преувеличиваю эту опасность, скорее всего большинство читателей, увидев кавалерийские наскоки на нити и семафоры, с FSA наголо и с RS - триггером наперевес, просто улыбнулись и отдали дань литературному таланту автора.

Немаловажным является желание заступиться за Флору, подвергнувшуюся в основном необоснованной критике наряду с Basic, и C++. Трудно предположить, что авторы Basic заступятся за свое детище, скорее всего, мы не дождемся, благодарности и от Страуструпа за кардинальное улучшение C++ . А по сему отбиваться придется Флоре.

Не хотелось бы, подобно многим, поддавшимся гипнозу RS - триггера, воспринимать все высказывания его главного адепта абсолютно серьёзно, пускаться в теоретические изыскания, писать программы и проводить изнурительное тестирование. Все же, придерживаясь, правил оппонирования, и следуя структуре [1-3], поговорим немного о моделях, порассуждаем о преимуществах параллельного программирования и разберем несколько примеров RS - триггера на Флоре.

Начнем с модели

Рассмотрев в [1] последовательную и параллельную модели RS - триггера автор предлагает с их помощью тестировать на параллелизм программные среды, совершенно не учитывая, что говорить в этом контексте о параллельности или последовательности отдельно взятой модели RS - триггера нельзя. Необходимо рассматривать модель совокупности среды и RS - триггера. И уже на этой обобщенной модели говорить об условиях генерирования RS - триггера.

Триггер может моделироваться двумя элементами 2И-НЕ, назовем их по входам триггера R и S, каждый из которых выполняет два атомарных действия: чтение входных сигналов, действие In, и формирование выходных сигналов, действие Out.

Модель триггера без взаимной синхронизации элементов приведена на рис. 1.

Рис. 1.

На рис. 2 приведена модель, обеспечивающая согласованную работу двух элементов триггера.

Рис. 2.

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

Рис. 3.

В зависимости от того, есть синхронизация работы элементов И-НЕ или ее нет, обобщенная модель триггера и среды, куда он погружен, будет либо последовательной, либо параллельной. Это хорошо видно на приведенных ниже моделях в нотации UML.

Модель RS-триггера в нотации UML

Представим модель RS-триггера в нотации UML, как <Диаграмму деятельности>. Рассмотрим два варианта, с <единым автоматным временем> и без оного. На каждый элемент выделяется дорожка. Штрих пунктир в середине рисунка изображает зацикливание или бесконечный цикл работы.

Рис. 4.

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

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

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

В.С. Любченко, запуская параллельный RS-триггер во Флоре, получил результат, полностью подтверждающий вышесказанное.

Как уже говорилось, переход к единому автоматному времени можно осуществить несколькими путями [4], либо, добавляя синхронизирующие состояния, либо последовательно выполняя переходы в автоматах, что, и реализовано в FSA. Не важно как это будет сделано, и сколько состояний будет у автоматов, реализующих элементы И-НЕ, будут ли состояния основаны на действиях по чтению входных данных и формированию выходных, или основаны на значениях выходов. Модель будет иметь следующий вид, рис. 5.

Рис. 5.

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

Анализ моделей показывает, что погружение параллельной модели RS-триггера в последовательную среду, аналогичную FSA, дает, в конечном счете, последовательную обобщенную модель, которая и генерирует (рис. 5). Погружение той же модели в параллельную среду, например Флоры, приводит к параллельной обобщенной модели, которая не склонна к устойчивой генерации, да и не обязана. Ниже будет показано, что во Флоре есть возможность создать последовательную обобщенную модель, которая также будет генерировать.

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

"Параллелизм по Любченко" и библиотека FSA

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

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

"Параллелизм по Любченко"> и алгоритм работы библиотеки FSA объясняются следующей цитатой[5]:

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

Где здесь параллелизм, и к какой реальной ситуации это ближе? К реальной ситуации с параллелизмом в FSA? Где одновременность запуска переходов на выполнение, когда в FSA это просто цикл по автоматам с запуском переходов по одному?

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

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

История умалчивает, что появилось раньше - библиотека FSA или идея тестировать параллелизм с помощью RS-триггера, но можно полагать, что они, библиотека и идея, служат только для оправдания друг друга.

М.В. Беляев в [8], указывая на последовательную организацию FSA, все же оставил RS-триггеру лазейку, ссылаясь на некую поочередность организации параллелизма в однопроцессорных системах. В результате последний, уже в который раз, все же вырвался из тисков критики и воспарил над сайтом целой трилогией. Надо было сказать, что поочередность поочередности рознь, и учесть, что нельзя давать ни малейшего шанса усомниться в последовательности генерирующей модели RS-триггера и полной абсурдности идеи тестировать с ее помощью параллелизм программных сред, я думаю, М.В. Беляев почувствовал это и был вынужден опубликовать [9].

Флоре не повезло так как С++, в ней нет FSA, но ей повезло в другом. Модель работы с автоматами реализованная в FSA, является частным случаем работы объекта "<Конечный автомат" во Флоре, это подтверждается и тем, что, FSA может быть реализована во Флоре самим пользователем, одним объектом "Задача" с тремя строчками текста.

 
#define eTick 1
for (int i=1;i<=automats.ChildCount;i++) { // цикл по автоматам
  ptr@StateMashine fsm=Ptr@StateMashine(automats.Child[i]); // приведение
  if (fsm) fsm.A(eTick); // если узел - автомат, то выполнение одного шага
}

где :

• automats - директория с синхронными автоматами,
• eTick - событие инициализирующее работу одного шага автомата .

Тестирование с использованием модели RS-триггера

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

• параллельная программная среда,
• последовательная программная среда,
• параллельная программа,
• последовательная программа.

Имеется правила:

• параллельная программа работает в последовательной среде. На этом основывается технология нейтрино, позволяющая многонитевым приложениям работать на ядрах младших моделей.
• последовательная программа может не работать в параллельной среде. Ярким подтверждением служит использование операции <++> без критической секции в многонитевом приложении, работающем в многопроцессорной среде.

Имеется объекты исследования:

• программная среда №1,
• программная среда №2,
• программа.

О последовательности или параллельности объектов достоверных сведений нет. Имеется эмпирические данные:

• Программа работает в среде №1 и не работает в среде №2.

Человек знакомый с логикой сделает вывод:

• Программа и среда №1 последовательны, а среда №2 параллельна.

По крайней мере, он скажет, что такой вывод имеет больше прав на существование, чем вывод о том, что программа и среда №1 параллельны, а среда №2 последовательна.

В.С.Любченко же делает вывод, что генерирует параллельная модель RS-триггера, а библиотека FSA - идеал параллелизма, и с упорством, достойным иного применения, продолжает утверждать, что не только Флора не обладает свойством параллельности, но и то, что под Windows и Linux, читай Unix, подразумевай POSIX, в принципе нельзя писать параллельные программы.

Вторая причина неправомочности такого тестирования основана на правиле из экспериментальной физики:

<Если эксперимент не могут повторить другие, значит, он ошибочен>. После стольких лет гордого одиночества в создании параллельных программ, таким способом, можно было бы и задуматься: "А подходит ли такой способ для создания параллельных программ?"

Вопросы по правомочности тестирования появляются при чтении трилогии на каждом шагу. Взять хотя бы две цитаты[2].

Первая:

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

Явно утверждать, что в параллельной среде RS-триггер работать не будет, все же упорно использовать его в качестве теста на параллельность. Его можно использовать, но выводы надо делать другие: <Триггер не генерирует, значит, среда параллельная>. Наблюдается также нарушение чистоты эксперимента. В Visual Basic два таймера использовать нельзя, так как могут быть ошибки. Во Флоре две задачи можно, похоже, даже нужно, чтобы ошибки были.

Вторая цитата:

"Во-вторых, необходима защита от "умельцев", которые при условии создать триггер, используя параллельную модель, создавая ее, попытаются "замаскировать" ее под параллельную."

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

Реализации модели RS-триггера на "Флоре"

Можно было бы, и закончить, несколько перефразировав эпиграф, но тогда не было бы выполнено главное требование оппонента "Сделай и покажи", и была бы опасность услышать строгое и безапелляционное "Слабо!"

Я думаю, ни у кого не возникает сомнения, что последовательные модели будут работать во Флоре. Хотя трудности из-за параллелизма могут возникнуть даже в этом случае, так как при тестировании последовательного триггера мы будем иметь как минимум три задачи: задача собственно триггера, задача рисования и одна или несколько задач подачи данных на входы триггера. Само использование оператора r=s=1, не гарантирует одновременную установку входов триггера, потому что переключение между задачами может произойти как раз между присваиваниями. Мне кажется, оппонент это наблюдал, отсюда столько вопросов к авторам Флоры.

В ходе подготовки статьи реализованы пять моделей RS-триггера:

• обобщенный автомат "!single_fsm", моделирующий последовательную модель, автор А.А.Даровских, готовящий отдельную статью по этому вопросу;
• модель "Nostril RS" триггер состоит из двух асинхронных автоматов, моделирующих элементы И-НЕ. Для обеспечения условий генерации в каждый автомат введены состояния синхронизации;
• модель "FSA RS", элементы И-НЕ представлены синхронными автоматами без состояний синхронизации. Синхронизация достигается тем, что автоматы запускаются последовательно один за другим из одной задачи. Это полный аналог FSA и он работает, то есть генерирует последовательность нулей и единиц на выходах, и генерирует устойчиво;
• модель "Period RS", элементы И-НЕ представлены задачами, запускающимися по периоду. Синхронизации никакой нет, все держится на честном слове, генерация неустойчивая;
• модель "Strob RS", элементы И-НЕ представлены задачами, запускающимися по стробу. Характеристики те же. Пример активности объектов Флоры, обратить особое внимание на различия ссылок в последних двух примерах.

В примерах "Nostril RS" и "FSA RS", применены некоторые хитрости, чтобы добиться одновременности присваивания входам триггера. Для варианта "Nostril RS" они могут и не дать 100% гарантии, правильнее было бы синхронизироваться по состояниям элементов И-НЕ, как это сделано в самих автоматах.

NODE.StateOn = !NODE.StateOn; // переключение состояния кнопки
bStart = false; // остановка автоматов
Sleep(Max(`$/!Q`.Period,`$/Q`.Period)+0.3); // ожидание остановки
r = s = NODE.StateOn; // присваивание значений входам И-НЕ
bStart = true; // запуск автоматов

В примерах и двухтактная схема работы элементов И-НЕ достигается задержкой Sleep(0.2).

int v=x1 && x2; // Такт чтения входных данных In
Sleep(0.2);     // Задержка 
y=!v;           // Такт формирования выходных данных Out

Все примеры помещены в файл examples\automat.ots среды программирования "Флора". На рабочем столе среды есть соответствующая иконка <Автоматы> [14].

Нельзя оставить без внимания и примеры моделирования RS-триггера, представленные оппонентом. После доказательства того, что RS-триггер генерирует только в среде с жесткой синхронизацией действий, и после выяснения неправомочности использования RS-триггера в качестве теста на параллельность, отзывы оппонента перестают иметь отрицательную окраску. Мало того слегка восторженно удивленные суждения выступают ярким подтверждением достоинств Флоры.

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

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

Технология <Флора>, приглашение к разговору

Хочется показать, что Флоре не чужд параллелизм, не прибегая к злополучному RS-триггеру. Флора изначально проектировалась как мультизадачная, переносимая система. Параллелизм во Флоре присутствует на двух уровнях, на уровне нитей ОС при реализации обращений к БД, файлам и объектам ОС, и на внутреннем уровне в виде невытесняющей мультизадачности при реализации активных объектов. Мультизадачность во Флоре реализована переключением задач в пределах одной нити ОС. Однако это переключение происходит при обращении к дереву. Так как операция обращения к дереву более мелкая и достаточно частая, параллелизм во Флоре соответствует общепризнанным канонам, непредсказуемости последовательности и независимости переключений.

Следует напомнить, что Флора портирована на Windows 98/ME, Windows NT/2000, Linux, SUN Solaris Intel, SUN Solaris SPARC, QNX RtP. Почти в каждой из указанных ОС свои особенности параллелизма. В качестве примера скажем, что при создании новой нити, управление получает в одних ОС дочерняя нить в других родительская, особенно это видно для однопроцессорных систем.

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

Приверженцы ООП увидят наиболее полную реализацию объектно-ориентированной среды. Достаточно только отметить, что во Флоре класс и инстанция отличаются только значениями пары битов, что позволяет говорить о метаклассе в самом чистом виде. Интересные результаты может дать и тот факт, что таблица виртуальных методов строится для каждой инстанции, так как есть понятие метода инстанции.

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

Адепты автоматного программирования могут увидеть во Флоре идеальную среду для реализации своих пожеланий, так как соответствующие объекты еще не устоялись. Но даже сейчас видна органичность реализации автоматов во Флоре. Это объясняется тем, что автоматному программированию чуждо текстовое представление, а во Флоре автомат представлен объектом диаграммой, и тем что Флора событийная среда, в которой работу автоматов можно организовать не вызывая явно их методы. Кстати, реализация объектов автоматного программирования в параллельной событийной среде Флоры показывает ошибочность вывода о цикличности программы автомата, высказанного Кузнецовым Б.П. в [10] и процитированного Беляевым М.В. в [8].

Последователи новомодного UML увидят среду, где реализованы большинство его понятий и где графическое изображение объекта в нотации UML строится по самому объекту, а не наоборот. Флора делает не совсем корректным высказывание [11]. "Процесс прямого проектирования приводит к потере информации, поскольку, написанные на языке UML модели семантически богаче любого из существующих языков"

Рискну сделать некоторые заявления, не опасаясь вызвать огонь критики, даже скорее желая его:

• Флора - идеальная реализация парадигмы ООП;
• Флора - идеальная среда реализации автоматного программирования;
• Флора - идеальная среда создания приложений с высоким уровнем параллелизма;
• Флора - в скором будущем станет идеальной средой применения нотации UML в проектировании больших систем.

Выводы

В заключении можно сделать следующие выводы:

• необходимо рассматривать обобщенную модель RS-триггера и среды, в которую он погружен;
• феномену генерации подвержена только последовательная модель с синхронизацией состояний автоматов, реализующих И-НЕ. Эта синхронизация может достигаться либо средствами внутри триггера, введением дополнительных состояний, либо снаружи организацией последовательной работы автоматов;
• факт генерации RS-триггера ни коим образом не может быть положен в основу тестирования наличия параллелизма, скорее наоборот;
• FSA на поверку оказывается простенькой библиотекой, реализующей работу автоматов через таблицу переходов. Причем работа эта достигается последовательными запусками автоматов один за другим;
• автор библиотеки FSA применил крайне неудобную модель ее пропаганды. Тем самым в какой-то степени дискредитировав саму идею применения параллельного программирования в последовательной среде;
• имитация библиотеки FSA средствами Флоры, не составляет никакого труда. Таким образом, во Флоре можно создавать приложения, руководствуясь как общепринятым понятием параллелизма, так и <"параллелизмом по Любченко";
• нападки автора эпопеи о RS-триггере на нити, семафоры и другие атрибуты параллельных программ не выдерживают критики, и не заслуживают внимания.

P.S.Некоторая резкость в оценках высказываний В.С. Любченко может быть оправдана безаппеляционностью рассматриваемых публикации, призывами модератора к дуэли, тщетностью более мягких увещеваний, предпринятых, в уже упомянутой переписке, простотой реализации "параллелизма по Любченко" во Флоре.

Ссылки и литература

1. Любченко В.С. Искусство программирования ... RS-триггера?! Часть 1. Электронная схема и формальные модели, www.softcraft.ru/auto/ka/rsm/rsm01/.
2. Любченко В.С. Искусство программирования ... RS-триггера?! Часть 2. Программирование, www.softcraft.ru/auto/ka/rsm/rsm02/.
3. Любченко В.С. Искусство программирования ... RS-триггера?! Часть 3. Тест на синхронную работу, www.softcraft.ru/auto/ka/rsm/rsm03/.
4. Любченко В.С. Фантазия или программирование? "Мир ПК", №10/97, с.116-119.
5. Любченко В.С. Новые песни о главном II. "Мир ПК", № 07/98, с.112-119.
6. А.А. Шалыто. SWITCH-технология. Алгоритмизация и программирование задач логического управления. - СПб.: Наука, 1998. - 628 с.
7. Шалыто А.А., Туккель Н.И. SWITCH-технология: автоматный подход к созданию программного обеспечения "РЕАКТИВНЫХ" систем, www.softcraft.ru/design/switch/sw01/.
8. М.В. Беляев Размерность программного пространства и модель триггера, www.softcraft.ru/design/trmod/trmod/.
9. М.В. Беляев P. S. Размерность программного пространства... , www.softcraft.ru/design/pstrmod/.
10. Кузнецов Б.П. Психология автоматного программирования // BYTE / Россия . 2000. №11 . С .22-29.
11. Грейди Буч, Джеймс Рамбо, Айвар Джекобсон, UML. Руководство пользователя, Издательство <ДМК>, Москва,2000.
12. Сайт компании, http://www.compassplus.ru
13. Документация по Флоре, http://www.compassplus.ru/flora/docs/index.htm
14. Адрес для скачивания последней версии, ftp://ftp.compassplus.ru/FloraWare_II/