|
В. C. Любченко
Можно скачать текст статьи в формате html (zip архив около 11 кб)
Часть 3. Тест на синхронную работу
Часть 1. Электронная схема и формальные модели
Часть 2. Программирование
Введение
В [1] мы создали несколько формальных моделей триггера,
в [2] мы их
реализовали, используя различные языки программирования. Но, во-первых, при
тестировании программ мы столкнулись с вопросами, которые для ответа на них
требуют дополнительной информации о работе триггере. Во-вторых, необходима
защита от "умельцев", которые при условии создать триггер, используя
параллельную модель, создавая ее, попытаются "замаскировать" ее под
параллельную.
С этой целью мы расширим модель, добавив в нее еще одну компоненту. Которая,
будет с одной стороны выдавать дополнительную информацию, а с другой - это еще
одна параллельная компонента, которая создаст дополнительные трудности в
попытке встроить ее в последовательную программу. И, в-третьих, она аргумент
для тех, кто считает тест триггера частным примером. В данном случае мы
расширяем тест триггера до более общей задачи, включая в нее модуль ни как не
связанный с "электронной спецификой" триггера.
Дополнительной компоненте на электронной схеме будет соответствовать
подключению к выходам триггера, например, элемента И-НЕ (см. соединения
пунктиром на рис. 1. в [1]).
Именно такая схема применяется на практике для
индикации завершения переходных процессов в триггере [3].
На уровне модели и
ее программной реализации этому соответствует еще один параллельный объект.
В данном случае мы возложим на него задачу подсчета любых одинаковых комбинаций
на выходах триггера. Конечно, он будет включать в себя и функцию, которую
выполняет дополнительный элемент И-НЕ.
Всего состояний выходов триггера может быть четыре: 00, 01, 10, 11. Из них две
комбинации соответствуют устойчивым состояниям: 01, 10, а другие две -
промежуточным, которые часто при анализе работы триггера даже не
рассматриваются или, более того, считаются запрещенными. Но это не значит, что
они не могут возникнуть. А потому одна из практических задач наших моделей -
подтвердить (или опровергнуть) версию возникновения запрещенных комбинаций
на выходах триггера и выявить условия их возникновения.
Но есть и еще один смысл в расширении модели. Правильная работа триггера служит
тестом корректной реализации параллелизма. Но, скорее всего, одного триггера
для этого мало. И дополнительный элемент должен не просто дать информацию о
работе триггера. Он должен дать информацию, которая бы дополнительно отражала
концепцию параллелизма. Например, два элемента триггера и компонента,
подключенная к его выходам, работают параллельно и в едином времени. В режиме
генерации компоненты триггера синхронно меняют свое состояние с 11 на 00 и
обратно. Эту - и ни какую другую! - информацию также синхронно должен
воспринимать и подключенный элемент. А она может возникнуть в зависимости от
реализации модели. Речь идет о том, что в последовательной среде параллелизм
имитируется, а потому одновременная параллельная синхронная работа реализуется
последовательно. Но модель должна работать одинаково вне зависимости от среды
реализации. Даже если эта среда последовательная (однопроцессорная, например).
И если триггер служит тестом параллельной работы при наличии у компонент
обратных связей, то вместе с дополнительным элементом это уже тест, проверяющий
синхронную работу параллельных компонент. При этом роль триггера - поставлять
тестовую информацию. Например, в режиме генерации триггер синхронно меняет
состояние выходов с 00 на 11 и обратно. При параллельной работе одинаковых по
своим характеристикам компонент других состояний в режиме генерации не должно
быть. Если они появляются, то это служит индикатором неправильной реализации
синхронной работы параллельных компонент, или неправильной синхронной работы
множества параллельных компонент. И то и другое может служить источником ошибок
в параллельных программах.
Счетчик на Visual Basic
В [2] мы объявили программную реализацию на VB эталоном, на который должны
равняться остальные модели. Поэтому счетчик состояний в первую очередь
реализуем на этом языке, чтобы было с чем сравнивать. Программный код счетчика
на VB представлен в листинге 1, а в листинге 2
показано его подключение к
модели триггера. На листингах счетчик представлен в двух вариантах:
Counter1, Counter2. Но и тот и другой, если обратить внимание, считают
только изменение состояний на входах счетчика. В первом случае для этого в
счетчик введены теневые состояния входов Tx1 и Tx2. Во втором случае
использовано внутреннее состояние самого счетчика. Когда оно равно
единице, считаются единичные состояния на входах счетчика, а остальные
состояния считаются в нулевом внутреннем состоянии счетчика. Кроме того,
в окно диалога были добавлены элементы для отображения состояний выходов
триггера - ed00, ed01, ed10, ed11.
Данная программа считает состояния правильно во всех режимах работы триггера.
Результаты ее работы по-прежнему тот эталон, которому должны соответствовать
тесты, написанные на других языках. Они должны быть таковы: в режиме генерации
количество переходов через состояние 11 должно быть равно количеству переходов
через состояние 00; в других режимах - количество нахождений в состоянии 11 на
единицу меньше суммы переходов через все остальные состояния триггера.
1. Тестирование во Flora/C+
Для реализации счетчика во Флоре введем в проект еще один объект типа task.
Его код показан в листинге 3.
В программу введены дополнительные переменные:
iError00, iError01, iError10 и iAccount для подсчета каждого из возможных
состояний на выходах триггера (соответственно 00, 01, 10, 11). Для отображения
значения счетчиков в окно диалога программы введены дополнительные объекты типа
FigEditLine. Кроме того, введены <теневые> переменные Tx1, Tx2 для входов
счетчика. Они необходимы, чтобы счетчик отслеживал только смену состояний
своих входов.
Данный объект, работая параллельно с объектами, реализующими триггер
(последовательной или параллельной моделью), анализирует состояния переменных,
соответствующих состояниям триггера и, посчитывая их комбинации, выводит
значения в окно диалога.
У нас есть две реализации триггера на Flora/C+: последовательная и
параллельная. Работают они, как показало тестирование в [2], особенно в
режиме генерации, различно. Протестируем каждую из них теперь и со счетчиком.
Может это позволит выяснить причины отказов во Флоре.
1.1. Последовательный триггер
Проведем тестирование последовательного триггера. Переключение между устойчивыми
состояниями, если оценивать конечный результат, происходит правильно. Т.е. если
триггер, например, находится в состоянии 01 (на входе при этом комбинация 10) и
на вход подать комбинацию 01, то триггер перейдет в состояние 10. (Но -
внимание! - при этом переход от входной комбинации 01 к 10 должен происходить
через "сохраняющую" комбинацию входов - 11. Такая комбинация, в отличие от
комбинации 00, не изменяет устойчивые состояния триггера.) Мы уже знаем, что
триггер, переключаясь из одного устойчивого состояния в другое, переходит через
промежуточное состояние 11. Исправно подсчитывая конечные состояния, счетчик
почему-то не улавливает этого промежуточного состояния. Попытка устанавливать
это состояние явно, заменой операторов y1=1 и y2=1 на y1=y2=1, ни чего не
меняет. Прием, который заставил последовательный триггер генерировать ("тупая"
вставка строки y1=y2=0 сразу за строкой y1=y2=1) здесь не "проходит".
Итак, почему счетчик не фиксирует промежуточного состояния при переключении
между устойчивыми состояниями, выяснить не удалось. Возможно потому, что
триггер находится в нем очень малое время и счетчик не успевает его
зафиксировать? Это первый вопрос, на который хочется получить ответ от
разработчиков Флоры.
В режиме генерации тоже происходят странные вещи. Видно, что триггер генерирует,
но счетчик при этом фиксирует не только состояния 00 и 11, что и должно быть
(см. тестирование счетчика на VB), но и промежуточные состояния 01 и 10,
которых по замыслу параллельного моделирования быть не должно. Получается,
что счетчик, который только что не успевал фиксировать промежуточное
состояние 11, сейчас успевает схватывать промежуточные состояния 01 и 10.
Безусловно, они реально существуют, т.к. мы моделируем параллелизм
последовательными операциями, но почему в одном случае скорости счетчика
хватает, чтобы их зафиксировать, а в другом - нет? И это второй вопрос,
требующий ответа.
Третий вопрос возникает, если мы посмотрим на результаты подсчета состояний в
режиме генерации. Они трудно объяснимы. Должно соблюдаться определенное
соотношение между количеством нахождения в состояниях 00 и 11 (см. результаты
теста на VB). Но, не говоря уж о количестве промежуточных состояний, которых
модель не должна фиксировать, число их ни как не стыкуется друг с другом. И
можно было бы что-то предположить, если бы это отличие было постоянным
(все-таки мы работаем с детерминированной моделью). Но в данном случае, его
предсказать нет ни какой возможности.
1.2. Параллельный триггер
Параллельный вариант триггера со счетчиком во Флоре работает почти так же, как
и вариант на VB. Но иногда он может все же пропустить и не посчитать
промежуточное состояние 11. Кроме того, в режиме генерации он не фиксирует
промежуточных состояний. Но как только он останавливается, сразу видно, что
причиной этого является возникновение непредусмотренного состояния 01 или 10.
Войдя в любое из них, уже ни какая сила не может сдвинуть его с этой точки, т.к.
входное состояние 11 для этих состояний является сохраняющим. Чтобы ввести
триггер вновь в режим генерации нужно опять создать на входах комбинацию 00, а
потом - 11.
Тестируя параллельный вариант, можно, изменяя период запуска объектов task,
влиять на скорость работы модели. Но чем выше скорость, т.е. чем меньше период
перезапуска, тем меньше вероятность возникновения генерации у триггера. С
какого момента он вообще перестает входить в режим генерации.
2. Счетчик на Visual С++
Полный текст программы на С++, реализующей счетчик, показан в листинге 4,
а один из возможных вариантов его соединения с триггером в листинге 5.
Хлопот с его созданием было гораздо меньше, чем в выше приведенных случаях.
Здесь не надо было <ломать> голову и изобретать <теневые> переменные, т.к.
фактически их роль выполняют внутренние состояния модели. В данном случае
нужны только переменные для хранения количества нахождений в том или ином
состоянии и действия по их установке и наращиванию. Алгоритму работы автоматной
модели счетчика близок алгоритм второго варианта счетчика на VB, где
использовалось внутреннее состояние счетчика - y.
Результаты работы программ на С++ и на Visual Basic совпадают, хотя и созданы
они с использованием различных подходов: программа на С++ - параллельная, а
на VB - последовательная. Это как раз то, к чему и нужно стремиться. Это тот
результат, который следует и из теории, где доказывается возможность построения
для любой параллельной программы ее последовательного аналога и наоборот. И
этим все сказано, т.к. все остальное, т.е. результаты тестирования, рассмотрены
для программы на VB.
3. О проблеме бесконечности алгоритмов
В "новобранцах" [4] специально было обращено
внимание на проблему бесконечности
алгоритмов. И, как оказывается, вовремя. Было сказано, что параллельные системы
позволяют безо всякой опаски использовать бесконечные циклы. Тем более, когда их
использование оправдано, как, например, и в случае с триггером. До этого
постоянную "жизнь" в реальном времени мы обеспечивали, задавая программе период
перезапуска (программы на Flora/C+) или помещая вызовы подпрограмм в обработчик
сообщений таймера (программа на VB). Теперь, в параллельной среде, их можно
просто зациклить. И от этого "параллельные соседи" не пострадают. Убедимся в
этом, поставив эксперимент над "бесконечностью".
3.1. Бесконечные алгоритмы во Flora/C+
Зададим объекту task, реализующему последовательный триггер, однократный запуск
вместо периодического, а код объекта "окантуем" конструкцией while (1). Так мы
создадим "бесконечную" модель триггера. В результате триггер стал работать
несколько иначе. Если раньше он проскакивал почти всегда свои опасные
промежуточные состояния, то теперь он стал работать "честнее". Войдя в режим
генерации, он исправно работает, но при входе в этот режим время от времени
он сразу "влетает" в устойчивое состояние, каким-то образом минуя 11, и
исправно в нем замирает.
Сложно сказать улучшает ли "бесконечность" качество алгоритмов Флоры, т.к. для
этого нужно провести отдельное расследование, но то, что она оказывает влияние
на работу, заметно. По крайней мере, на примере триггера. В отличие от
триггера, работа "бесконечного счетчика" неотличима от его обычного варианта.
3.2. Бесконечные алгоритмы в C++
В случае FSA алгоритм работы счетчика "бесконечен". Он постоянно что-то
считает. Отслеживает любое изменение его входов и считает ..., считает:
"Бесконечны" и элементы триггера. И в этом нет ни чего "криминального". Это
естественное состояние этих объектов. Было бы, наоборот, неестественным
придумывать им заключительные состояния. При этом они исправно, как и положено
"по определению" алгоритма, результативно завершали бы свою работу, а мы бы
потом <ломали голову>, как их вновь запустить в нужный момент. Таким образом,
как это обычно и бывает при обычном подходе, мы бы создали бы, например, не
только счетчик, но и "хлопоты" по управлению им.
В параллельной среде - иное. Создав объект-счетчик и указав ему, откуда
черпать информацию, мы его "оживляем", т.е. загружаем в среду исполнения. А
чтобы не отвлекаться на проблемы загрузки выгрузки модели, мы задаем ей
бесконечный цикл работы. Дальше наша роль проста - отслеживаем результаты
работы. В программе на С++, если обратить внимание, почти любой ее объект имеет
бесконечный алгоритм работы. Это не только элементы И-НЕ и счетчик, но и объект,
отображающий данные в окно диалога.
4. Выводы. Чем ...
4.1. Чем "плохая" Флора лучше "хорошего" Visual Basic
Тем, что параллельна. Не так как хотелось бы и не так как надо, но и не хуже
остальных параллельных систем. Она честно повторяет встроенные в операционную
систему средства распараллеливания. Плохо ли хорошо, но оба варианта триггера
во Флоре работают. В отличие от Флоры на VB мы имеем только последовательный
вариант (который мы и считаем эталоном - но по результатам, а не по реализации -
для других программ). Так чем же может привлекать Флора, несмотря на свою
нестабильность?
Пусть качества параллелизма и далеки от желаемого, но все же он позволяет
проще писать программы, чем "параллелизм" VB. Это сразу проявляется, если мы
последовательный триггер на VB перепишем по образу и подобию триггера во Флоре
(см. листинг 1 в [2]).
Триггер работать будет (см. RSTrigger2 листинг 6), но
счетчик откажется работать совсем. И заставить его выполнять свои функции в
этом случае будет не просто! Более того, эта модель может подвесить программу
(вот они "капканы" бесконечных циклов!), если не вставить в нее специальный
метод DoEvents!
Чтобы счетчик считал, мы должны или вернуться к варианту триггера с теневыми
состояниями, или изобрести другой метод программирования (попробуйте, может и
получится?), или создать параллельный вариант триггера (но, может быть, тогда
легче изобрести метод?). Думаю, что в этом случае, программистам на VB нужно,
как минимум, сказать спасибо В.Пудову и взять, не колеблясь, на вооружение его
метод.
Несколько сложнее программистам на Flora/C+. Нужно ведь как-то решать проблемы,
выявленные тестированием триггера!? Можно пойти по пути VB, т.е. применить
метод "теневых состояний" (см. листинг 4
в [2] и проект RS_VALERY.ots), но
тогда к чему стремились и к чему такой параллелизм, которому нет доверия? Можно
попытаться разработать свои универсальные "теневые приемы", которые, сохраняя
простоту и ясность параллельных программ, не будут усложнять алгоритмы, давая
при этом гарантии надежной и предсказуемой по результатам работы. Если кто-то
придумает - поделитесь находками так же, как В.Пудов поделился своим методом!
4.2. Чем C++ лучше всех ...
Тем, что в нем есть FSA. С ее помощью С++ стал параллельным. Наверное, если бы
подобная библиотека имелась в VB и Флоре, то это же можно было бы сказать и о
них. И, безусловно, автоматные методы программирования можно встроить и в эти
языки. При этом, возможно, для VB это будет сделать сложнее, чем для Флоры,
хотя бы в силу того, что язык Флоры по своим возможностям и даже внешнему
виду (синтаксису и семантике) ближе к C++. Например, в VB нет понятия
указателя, как в С++, не говоря уж о том, что и объектные возможности VB
оставляют желать лучшего.
Программы на C++ сложнее, но несравненно быстрее по скорости работы. Даже
простейшая оценка тестирования скорости моделей триггера показывает, что по
сравнению с Флорой программа на С++ работает в двадцать раз быстрее (и притом
правильно!), а по сравнению с VB в сорок раз. Это можно оценить по скорости
счета состояний в режиме генерации. А это уже, сами понимаете, не "копейки"!
Если скорость важна, то выбора практически и нет.
Параллельные программы на С++ с применением FSA надежнее, чем аналогичные
параллельные программы во Флоре. Их результат детерминирован, т.е. однозначно
предсказуем. Во Флоре на примере триггера со счетчиком мы можем наблюдать, что
для нее результат иногда предсказать невозможно. Программы во Флоре выглядят
проще, но какими они станут, чтобы на их надежность и результат работы можно
было бы полагаться?
4.3. И прочее ...
Еще раз подчеркнем, что подсчет состояний триггера не только дает
дополнительную информацию о работе триггера, но и функционально расширяет тест,
проверяя параллельную синхронную работу компонент. Сама синхронная работа
компонент при этом моделируется работой логических элементов триггера.
Реализован редкий случай успешной "охоты" за "несколькими зайцами".
Анализ текстов программ на разных языках дает много информации и для сравнения
различных технологий проектирования на базе различных программных моделей.
В данном случае в первую очередь сравнивается блок-схемная и автоматная модели
программ. Но в [1] были рассмотрены примеры на базе сетей Петри и
функциональные модели (в том числе рекурсивная модель на Лисп). Легко видеть,
что в сравнении с этими вариантами "автоматный счетчик" гибче, т.к. позволяет
легко расширить его функциональные возможности.
Сравнение параллельных вариантов программ на Flora/C+ и Visual С++ с их
последовательными аналогами убеждает в простоте и эффективности параллельного
программирования. Но при этом нужно быть внимательным. Во Флоре параллельные
процессы живут каждый своей жизнью и, чтобы их синхронизировать, нужны совсем
нетривиальные усилия. В трехмерной программной среде, которую реализует FSA,
параллельные компоненты функционируют в едином дискретном времени. Это не
только снимает многие проблемы обмена информацией (тестирование обратных
информационных связей с помощью триггера), но и автоматически организует
удобную синхронную работу компонент (тест на синхронную работу с помощью
счетчика).
Литература
-
Любченко В.С.
Искусство программирования ... RS-триггера?! Часть 1. Электронная схема
и формальные модели
.
-
Любченко В.С.
Искусство программирования ... RS-триггера?! Часть 2. Программирование
.
-
Апериодические автоматы. Под ред. В.И. Варшавского. - М.: Наука.
Гл. ред. Физ.-мат. лит. 1976 - 424 с.
-
Любченко В.С. Стрелки! Нале-во! Мир ПК>, № 8,9/01.
Листинг 1. Cчетчики состояний на Visual Basic
Dim Tx1 As Integer
Dim Tx2 As Integer
' 1-й счетчик переключений триггера
Public Sub Counter1(x1 As Integer, x2 As Integer, y As CheckBox)
If Tx1 = x1 And Tx2 = x2 Then
Exit Sub
End If
If x1 And x2 Then
If (y = 1) Then
edAccount = edAccount + 1: y = 0
End If
ElseIf (x1 = 1 And x2 = 0) Then
ed10 = ed10 + 1: y = 1
ElseIf (x1 = 0 And x2 = 1) Then
ed01 = ed01 + 1 y = 1
Else
ed00 = ed00 + 1 y = 1
End If
Tx1 = x1: Tx2 = x2
End Sub
' 2-й счетчик переключений триггера
Public Sub Counter2(x1 As Integer, x2 As Integer,
y As CheckBox, Ty As Integer)
KA x1, x2, CInt(y), Ty
' учет предыдущего состояния счетчика!
' если единицы на входах, а пред.состояние (выход) в единице,
' то будет переключение в ноль и его нужно считать
' если единицы на входах, а выход уже был в нуле,
' это "переключение в ноль" не нужно считать
If (x1 = 1 And x2 = 1 And y = 1) Then
edAccount = edAccount + 1: Ty
ElseIf (x1 = 0 And x2 = 1 And y = 0) Then
ed01 = ed01 + 1: Ty = 1
ElseIf (x1 = 1 And x2 = 0 And y = 0) Then
ed10 = ed10 + 1: Ty = 1
ElseIf (x1 = 0 And x2 = 0 And y = 0) Then
ed00 = ed00 + 1: Ty = 1
End If
y = Ty
End Sub
Листинг 2. Подключение счетчика к триггеру на Visual Basic
Dim TstateC As Integer
' установка входов триггера в 11
Private Sub btOpen_Click()
:
edAccount = 0: ed00 = 0: ed01 = 0: ed10 = 0
End Sub
' инициализация модели
Private Sub Form_Load()
edAccount = 0: ed00 = 0: ed01 = 0: ed10 = 0
:
End Sub
' моделирование дискретного времени
Private Sub Timer1_Timer()
:
' Counter2 edQ, edNQ, edINE, TstateC
Counter1 edQ, edNQ, edINE
End Sub
Листинг 3. Счетчик состояний на Flora/C+
if (Tx1==x1 && Tx2==x2) return;
if (x1&&x2)
{
if (y==1) iAcc++; y=0;
}
else if (x1==1 && x2==0)
{
iError10++; y=1;
}
else if (x1==0 && x2==1)
{
iError01++; y=1;
}
else {
iError00++; y=1;
}
Tx1=x1; Tx2=x2;
Листинг 4. Счетчик состояний на С++
class CCounter : public LFsaAppl
{
public:
CCounter(LFsaAppl** tsk1, LFsaAppl** tsk2);
virtual ~CCounter();
int nCounter, nCnt10, nCnt01, nCnt11, nCnt00;
void ClearCnt();
protected:
int x2(), x1();
void y1(), y2(), y3(), y4();
LFsaAppl** tskIne1;
LFsaAppl** tskIne2;
};
// таблица переходов
LArc stCount[] = {
LArc("S1", "S0", "x1x2", "y1"),
LArc("S0", "S1", "^x1x2", "y2"),
LArc("S0", "S1", "x1^x2", "y3"),
LArc("S0", "S1", "^x1^x2","y4"),
LArc()
};
CCounter::CCounter(LFsaAppl** tsk1, LFsaAppl** tsk2):LFsaAppl(stCount)
{
tskIne1 = tsk1; tskIne2 = tsk2;
nCounter = nCnt00 = nCnt01 = nCnt10 = nCnt11 = 0;
}
CCounter::~CCounter() { }
// предикаты
int CCounter::x1() { return string((*tskIne1)->FGetState()) == "S1"; }
int CCounter::x2() { return string((*tskIne2)->FGetState()) == "S1"; }
// действия
void CCounter::y1() { nCounter++; nCnt11++; }
void CCounter::y2() { nCnt01++; }
void CCounter::y3() { nCnt10++; }
void CCounter::y4() { nCnt00++; }
void CCounter::ClearCnt() { nCnt00 = nCnt01 = nCnt10 = nCnt11 = 0; }
Листинг 5. Подключение счетчика к триггеру на С++
class CDat;
class CFlipFlop
{
public:
:
char* GetCnt();
char* GetCounter();
CFlipFlop(CDat* dat);
virtual ~CFlipFlop();
protected:
CDat* pDatInOu;
private:
LFsaAppl* pIne3;
:
char ch[10];
};
CFlipFlop::CFlipFlop(CDat* dat)
{
pIne3= NULL;
:
pIne3= new CCounter(&pIne1, &pIne2);
pIne3->FLoad(theApp.pNetFsa,1);
theApp.pNetFsa->go_task();
}
CFlipFlop::~CFlipFlop()
{
:
if (pIne3) delete pIne3;
}
char* CFlipFlop::GetCnt() { return pIne3->FGetState(); }
char* CFlipFlop::GetCounter()
{
int n = ((CCounter*)pIne3)->nCounter;
itoa(n,ch,10);
return ch;
}
Листинг 6. "Бестеневая" модель триггера на Visual Basic
Public Sub RSTrigger2()
If (edS) Then
If edR = 0 Then
edQ = 0: edNQ = 1:
While (edS)
DoEvents
Wend
edQ = 1
Else
edQ = 0: edNQ = 0
edQ = 1: edNQ = 1
End If
Else
If (edR) Then
edQ = 1: edNQ = 0
While (edR)
DoEvents
Wend
edNQ = 1
Else
edQ = 1: edNQ = 1
End If
End If
End Sub
|