SoftCraft
разноликое программирование

Отправная точка
Программирование
Windows API
Автоматы
Нейроинформатика
Парадигмы
Параллелизм
Проектирование
Теория
Техника кодирования
Трансляторы
Учебный процесс
Прочие вопросы

Разное

Беллетристика
Брюзжалки
Цели и задачи
Об авторе


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

© Беляев М.В.

(Новосибирск, НГПУ)

belyaev@e-mail.ru

В архиве лежит упакованная версия статьи (18 кб)

"Судя по всему, на программирование надвигается новый переворот...", - писал известный компьютерный публицист Рубен Герр (PC MAGAZINE/RUSSIAN EDITION, 10/98) в рецензии на книгу А. А. Шалыто "SWITCH-технология. Алгоритмизация и программирование задач логического управления". Пока это пророчество не сбылось, но парадигма автоматного программирования (АП) по-прежнему подает надежды и продолжает привлекать все новых сторонников. В последнее время отечественные адепты АП "тусуются" на сайте www.softcraft.ru. Знакомство с материалами этого сайта навело меня на размышления по поводу автоматного программирования, продуктом которых стала настоящая заметка. Я разделяю оптимизм сторонников автоматной парадигмы, но хотел бы развеять некоторые мифы, вызревшие под сенью этого благородного древа.

О чем пойдет речь

В частности мое внимание привлекли публикации В.С. Любченко [1, 2, 3] , популяризирующие автоматное программирование на принципах КА-технологии [4]. Любченко [1] вводит понятие размерности програмного пространства:

"Будем считать одномерной программой линейную последовательность команд (не включающую команд перехода)...

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

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

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

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

И далее:

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

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

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

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

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

Что такое триггер?

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

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

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

Давольно часто триггер задают таблицей истиности. Вот таблица истиности RS-триггера из статьи Любченко [1]:

Таблица истинности для RS-триггера

-S -R Q -Q
1 1 Без изменения
1 0 0 1
0 1 1 0
0 0 1 1
(Запрещено)

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

Как работает "триггер"?

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

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

Каждый вентиль может реализовывать одну из четырех логических функций: "И-НЕ", "ИЛИ-НЕ", "И", "ИЛИ". Всего возможно десять различных комбинаций вентилей и соответственно десять типов "триггеров". Рассмотрим классическую схему - триггер на двух элементах "И-НЕ":

Для отслеживания изменения сигналов используем следующие обозначения:

  • S(x), R(x), Q(x), P(x) - сигналы на входах и выходах, где x - 0 или 1;
  • S'() - сигнал в S' неизвестен и не имеет значения;
  • S(0->1) или S(1->0) - изменение сигнала в точке S;
  • {S(x),S'(y)} => Q(z) - результат выполнения логической операции вентилем S,
  • Q(x)=>R'(x) - передача сигнала с выхода Q на вход R'.

Пусть на входы S и R поданы сигналы 0, 0. Исходная конфигурация такова:

{S(0),S'( )}=>Q(1)=>R'(1)=>{R'(1),R(0)}=>P(1)=>S'(1)=>{S(0),S'(1)}=>Q(1)

далее цепочка повторяется (Q(1)==Q(1)) - следовательно, состояние устойчиво. Т. е. на выходах Q и P может быть только по 1 (состояние Q(1),P(1)). Изменим сигнал на входе S и проследим все последствия этого:

{S(0->1),S'(1)}=>Q(1->0)=>R'(1->0)=>{R'(0),R(0)}=>P(1) =>S'(1)=>{S(1),S'(1)}=>Q(0)

Результат - Q(0)==Q(0). Произошло переключение триггера - переход в другое устойчивое состояние (состояние Q(0),P(1)).

Изменим сигнал на входе R: {R'(0),R(0->1)}=>P(0) - на выходе P сигнал не изменился: это состояние "хранения информации" (состояние Q(0),P(1) сохранилось).

Опять изменяем сигнал на входе S и снова триггер переключается:

{S(1->0),S'(1)}=>Q(0->1)=>R'(0->1)=>{R'(1),R(1)}=>P(1->0) =>S'(1->0)=>{S(1),S'(0)}=>Q(1)
- состояние Q(1),P(0).

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

Состояние, с которого мы начали - (S(0),R(0),Q(1),P(1)) - принято называть запрещенной комбинацией входных сигналов, так как, во-первых, оно лишнее (третье) и, во-вторых, если одновременно поменять 0 на обоих входах на 1, то триггер перейдет в одно из двух основных состояний (Q(1),P(0) или Q(0),P(1)) непредсказуемым образом.

Общий вывод проведенного анализа: в данной схеме (2"И-НЕ") генерация НЕВОЗМОЖНА.

Теперь рассмотрим систему из вентиля "И-НЕ" (S) и вентиля "И" (R).

Чтобы не утомлять читателя сразу перейду к искомой (для генерации) комбинации входных сигналов: S(1), R(1). Предположим, что P(1).

P(1)=>S'(1)=>{S(1),S'(1)}=>Q(0)=>R'(0)=>{R'(0),R(1)}=>P(0) =>S'(0)=>{S(1),S'(0)}=>Q(1)=>R'(1)=>{R'(1),R(1)}=>P(1) и т. д.

Сколько бы мы не продолжали цепочку - она будет постоянно содержать переключения. То есть, какое бы предположение о P мы не сделали - оно НЕ ОПРАВДЫВАЕТСЯ! Используя физическую терминологию, можно сказать, что мы получили развитие неустойчивости, то есть генерацию. В качестве самостоятельного упражнения читатель может исследовать на неустойчивость оставшиеся восемь типов "триггеров".

Резюме к этому разделу:

  1. Вентили в физическом (кремнеевом) "триггере" работают поочередно.
  2. Генерация в физическом "триггере" не связана с параллельностью, а возникает при наличии положительной обратной связьи.

Автоматный подход

С историей вопроса и разнообразными аспектами SWITCH-технологии лучше всего познакомится по монографии А.А. Шалыто [5] и его материалам на сайте www.softcraft.ru. Для первого знакомства со SWITCH-технологией программирования рекомендую статью Б.П. Кузнецова [6]. Я надеюсь, что читатель последует моему совету, но для связности изложения мне все-таки придется в виде нескольких тезисов сформулировать суть автоматного подхода к решению задач программирования (в соответствии с концепцией SWITCH-технологии).

  1. Рассматриваемой задаче сопоставляется некоторый конечный автомат (формальный объект, имеющий конечное число состояний).
  2. Автомат представляется в виде ориентированного графа, в котором вершины представляют состояния автомата, а дуги - переходы между состояниями.
  3. Принято выделять начальное состояние (с которого начинается работа автомата) и конечное состояние (last_state) после попадания в которое, вся работа фатально прекращается.
  4. Считается, что:
    • в каждый момент времени автомат находится в одном из своих состояний;
    • переходы между состояниями происходят мгновенно;
    • переход из состояния A в состояние B происходит при выполнении определенного условия (условия перехода) и сопровождается выполнением определеных действий (действия на переходе), которые включают выполнение различных операторов и вызовы функций;
  5. Переход осуществляется изменением переменной state.
  6. Автомат реализует некоторый циклический алгоритм.
  7. Очередной шаг цикла инициируется программным циклом опроса while(state != last_state).

Каждый оборот цикла while застает автомат в некотором состоянии, которое регистрируется оператором switch. Далее происходит последовательная проверка условий переходов и, в случае выполнения одного из таких условий, выполняются действия на переходе и сам переход.
        Широкому распространению АП препятствует недоразумение, о котором хорошо написал Б.П. Кузнецов в статье "Психология автоматного программирования":

"Абсолютно нигде в современной литературе не указывается явно тот факт, что программа, реализующая граф (таблицу) переходов, должна быть циклической. Пока я этого не понял, никому ничего объяснить было нельзя. Рисуя граф переходов, мы с Вами заведомо полагаем, что подразумевается цикл, который на этом рисунке нигде не фигурирует. Поэтому большинству программистов и непонятно ничего" [6].

Автоматная модель "триггера"

Конечной нашей целью является построение программной модели "триггера". Для создания этой программы я хочу воспользоваться автоматной парадигмой в форме, предлагаемой SWITCH-технологией.

Автоматная парадигма требует начать проектирование програмного продукта с разработки схемы соответствующего конечного автомата. Как следует из наших прежних рассуждений, нужный нам автомат должен иметь два рабочих состояния: "S" - активен вентиль S (ожидается изменение входа S), и "R" - активен вентиль R (ожидается изменение входа R). Начальным состоянием можно считать любое из них. В конечное состояние система переходит после нажатия клавиши ESC.

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

Состояния автомата обозначены кружками. VS и VR - это действия на переходах.

Программная реализация автоматной модели

В соответствии с канонами SWITCH-технологии (см. [6]) основу программы должен составить следующий цикл:

 state='S';
 while(state != last_state)
      {
       switch(state)
             {
              case 'S': VS(); state='R'; break; 
              case 'R': VR(); state='S'; break;
             }
      }

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

 while(state != last_state)
      {
       VS(); 
       VR();
      }

Именно в этой форме он используется в программе. Полный листинг программы с подробными комментариями вы можете найти в Приложении 1. Здесь я хочу обратить внимание только на один аспект реализации - функцию CheckKey(). Эта функция проверяет, не была ли нажата клавиша и если была, то реагирует на нажатие. Важно отметить, что эта функция ввода НЕ ПРИОСТАНАВЛИВАЕТ выполнение программы (асинхронный ввод). Реализуется это комбинацией функций kbhit() и getch() из библиотеки conio:

void CheckKey()       /* управление входами "триггера" */
{
 if(kbhit())          /* была ли нажата клавиша?       */
   {
    switch(getch())
          {
           case '1'    : S=0; break; /* установка */
           case '2'    : S=1; break; /* входов    */
           case '3'    : R=0; break; /* "триггера"*/
           case '4'    : R=1; break;
           case '\033' : state=last_state;  /* ESC - конец работы */
          }
   }
}
К обсуждению этого аспекта мы еще вернемся.

Результаты работы программной модели "триггера"

Программа написана на чистом C (даже без коротких комментариев). (Кажется, именно короткие комментарии являются наиболее ценным нововведением C++ - от них труднее всего отказаться.) Программа создавалась в среде Borland C++Builder 5.0 и тестировалась также с компилятором Borland C++ 3.1. Использовались только функции стандартных библиотек языка C не считая функций getch() и kbhit() из библиотеки conio - стандартной для DOS и Windows. Поэтому можно утверждать, что под DOS или Windows программу можно компилировать любым компилятором C или C++. На других платформах этим двум функциям придется найти замену.

Программа успешно моделирует все 10 различных типов рассматриваемого нами устройства. С помощью этой программы я "экспериментально" установил что:

  1. Только три из десяти "триггеров" являются триггерами - 2"И-НЕ", 2"ИЛИ-НЕ", "И"+"ИЛИ".
  2. Четыре системы при некоторой комбинации входных сигналов являются генераторами - "И-НЕ"+"И", "И-НЕ"+"ИЛИ", "ИЛИ-НЕ"+"И", "ИЛИ-НЕ"+"ИЛИ".
  3. Три системы не являются ни триггерами, ни генераторами - "И-НЕ"+"ИЛИ-НЕ", 2"И", 2"ИЛИ".

Пытливый читатель (выполнивший самостоятельные упражнения) должен получить те же результаты "на кончике пера".

В заключение раздела еще одна цитата из В.С. Любченко [1]: "Возможно, кто-то обвинит меня в голословном объявлении почти всех существующих параллельных систем двумерными (по моей классификации Си++ - это строго двумерный язык программирования, Windows и Unix - двумерные системы с имитацией третьего измерения). Повторюсь, я признаю упреки справедливыми только в том случае, если мне будут предъявлены "вещественные доказательства" - листинги работающей модели RS-триггера. Только так может состояться содержательный разговор, а не просто словесная перепалка".

То, что Вы хотели Вячеслав Селиверстович - в приложении.

Мистическая сила параллелизма

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

Прежде всего, в однопроцессорной системе без некоторой "поочередности" нельзя обойтись в принципе. В компьютере с одним скалярным процессором параллелизм давно и успешно реализуется путем поочередного выполнения параллельных процессов. Такая реализация паралельных процессов известна как режим разделения времени. Такой же метод (параллелизм с помощью чередования - interleaving) используется во многих подхода, ставших классическими. Например, в CSP исчислении Хоара [7]. Между прочим, и Любченко в КА-технологии использует именно такую модель параллелизма [3]:

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

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

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

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

  1. События не взаимодействуют. Тогда их последовательное наступление в любом порядке (сначала A - потом B, или наоборот - сначала B - потом A) по существу ни чего не изменит.
  2. События взаимодействуют. Для нормального функционирования системы такая ситуация должна быть исключена. Одновеменное наступление взаимодействующих событий не приводит ни к чему кроме неприятностей. Классический пример - одновременное изменение одних и тех же данных разными процессами.

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

Как же быть с третьим программным измерением?

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

Представим себе такую ситуацию - ваша (а лучше не ваша) программа вошла в бесконечный цикл и не подает признаков жизни. Что вы делаете? - Жмете Ctrl-C, Ctrl-Break, Ctrl-Z или Ctrl-Alt-Del. - Операционная система оставляет за собой право убить проштрафившийся процесс. (Иногда ни одна комбинация клавиш не помогает - но это говорит только о несовершенстве реализации.)

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

Но в нашей программе моделирования "триггера" третье измерение присутствует в явном виде. Попробуйте обойтись без функции kbhit() - если вы просто уберете вызов CheckKey(), то "триггер" станет неуправляемым, а если замените связку kbhit()-getch() какой-нибудь стандартной функцией ввода (останавливающей выполнение), то при наступлении генерации она будет давольно странной - переключений "триггера" будет ровно столько, сколько нажатий клавиш. (Совсем как в двумерном Doom-е.)

Поэтому сформулированное выше диалектическое противоречие разрешается просто - надо подкорректировать критерий трехмерности. Минимальное требование к трехмерности - возможность использования аппаратных и программных прерываний (именно через механизм прерываний реализована функция kbhit() и ей подобные). Есть ли смысл в таком слабом критерии? Наверное да, - ведь ему не соответствуют такие стандартизованные языки программирования как C и C++ (в этом я согласен с В.С. Любченко). Ведь даже минимальные возможности функции kbhit() не доступны в стандартных библиотеках!

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

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

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

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

События, события...

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

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

Несколько слов об эффективности программной модели триггера в частности, и SWITCH-технологии вообще. В нашей программе (и в любой другой, SWITCH-программе) колесо while вращается без остановки и загружает процессор на 100%. В многозадачной операционной системе такое поведение прикладной программы не приветствуется. Это и есть плата за простоту и "несобытийность". Простейший выход из этой ситуации - инициировать цикл опроса таймером. В Приложении 2 приведена программная модель "триггера" с таймерным управлением. Эта программа является консольным приложением Windows. В DOS ее скомпилировать не удасться в виду отсутствия соответствующих функций API.

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

Как быть с обвинениями, брошенными В.С. Любченко в адрес Windows и Unix? Истолкуем их как полемический прием обострения. Вы, наверное, заметили, что я тоже пользуюсь этим приемом.

Литература

  1. Любченко В.С. Фантазия или программирование? “Мир ПК”, № 10/97, с.116-119.
  2. Любченко В.С. Новые песни о главном (римейк для программистов). “Мир ПК”, № 6/98, с.114-119.
  3. Любченко В.С. Новые песни о главном II. “Мир ПК”, № 07/98, с.112-119.
  4. Любченко В.С. Конечно-автоматная технология программирования. 2001. Материалы сайта www.softcraft.ru.
  5. Шалыто А.А. SWITCH-технология . Алгоритмизация и программирование задач логического управления. СПб.: Наука , 1998. 628 с. См. также
  6. Кузнецов Б.П. Психология автоматного программирования // BYTE / Россия . 2000. №11 . С .22-29.
  7. Хоар Ч. А. Р. Взаимодействующие последовательные процессы. М.: Мир, 1989. 264 с.

Copyright © М.В. Беляев, 2001

Приложение 1.
/*-------------------------------------------------
 Программная модель "триггера"
 - двух перекрестно соединенных логических вентилей
 на основе SWITCH-технологии 
 Copyright © М.В. Беляев, 2001
 ------------------------------------------------- */

#include <stdio.h>
#include <conio.h>

#define last_state '\0'

/* возможные типы вентилей*/
typedef  enum
  {and_not, or_not, and_, or_} v_types; 

v_types vs_type, vr_type; /* типы вентилей S и R  */

int S, R;         /* входы и               */
int Q, P;        /* выходы "триггера"     */

char state='S';   /* начальное состояние   */

/*------------------------------------------------- */

v_types SetVType(char *prompt) /* задание типа вентиля */
{
 printf("Choose %s ventil type:\n", prompt);
 for(;;)
    {
     puts("0 - and_not, 1 - or_not, 2 - and_, 3 - or_");
     switch(getch())
           {
            case '0': return and_not;
            case '1': return or_not;
            case '2': return and_;
            case '3': return or_;
           }
    }
}

/*------------------------------------------------- */

void CheckKey()       /* управление входами "триггера" */
{
 if(kbhit())          /* была ли нажата клавиша?       */
   {
    switch(getch())
          {
           case '1':S=0; puts("S=0"); break; /* установка */
           case '2':S=1; puts("S=1"); break; /* входов    */
           case '3':R=0; puts("R=0"); break; /* "триггера"*/
           case '4':R=1; puts("R=1"); break;
           case '\033' : state=last_state;   /* ESC - конец работы */
          }
   }
}

/*------------------------------------------------- */

void print() /* вывод на косоль состояния входов и выходов */
{
 printf(" S= %1d R= %1d Q= %1d P= %1d\n", S, R, Q, P);
}

/*------------------------------------------------- */

int op(v_types v_type, int x, int y) /* логическая операция вентиля */
{
 switch (v_type)
        {
         case  and_not: return !(x && y);
         case  or_not : return !(x || y);
         case  and_   : return  (x && y);
         case  or_    : return  (x || y);
        }
}


 /*------------------------------------------------- */
/* действие на переходе S -> R                      */
void VS()       
{
 int x; 
 CheckKey();  /* если нажали нужную клавишу - изменить S или R */
 x = op(vs_type, S, P);
 if(x != Q)
   {
    Q=x;     /* вентиль S на выходе дает Q */
    print();/* вывод на консоль - только если выход изменился */
   }
}

 /*------------------------------------------------- */
/* действие на переходе R -> S                      */
void VR()       
{
 int x;
 CheckKey();  /* если нажали нужную клавишу - изменить S или R */
 x = op(vr_type, Q, R);
 if(x != P)
   {
    P=x;     /* вентиль R на выходе дает P */
    print();/* вывод на консоль - только если выход изменился */
   }
}

/*------------------------------------------------- */

int main()
{
 vs_type=SetVType("S");      /* задать тип вентиля S */
 printf("S= %1d \n", vs_type);

 vr_type=SetVType("R");   /* задать тип вентиля R  */
 printf("R= %1d \n", vr_type);

 /* подсказка - как управлять "триггером"       */   
 puts("\nPress key to change any trigger enter:");
 puts("1 - S=0; 2 - S=1");
 puts("3 - R=0; 4 - R=1\n");

 puts("Now press any key to start");
 puts("Press ESC to stop\n");
 getch();

 while(state != last_state) /* пока не нажали ESC          */
      {
       VS();               /*   S и R работают по очереди */
       VR();        
      }

 return 0;
}

/*------------------------------------------------- */
Приложение 2.
/*-------------------------------------------------
 Программная модель "триггера"
 - двух перекрестно соединенных логических вентилей
 с таймерным управлением
 Copyright © М.В. Беляев, 2001
 ------------------------------------------------- */
#include <windows.h>
#include <stdio.h>
#include <conio.h>

#define last_state '\0'

/* возможные типы вентилей*/
typedef unsigned int UINT;

typedef  enum
  {and_not, or_not, and_, or_} v_types; 

v_types vs_type, vr_type; /* типы вентилей S и R  */

int S, R;      /* входы и           */
int Q, P;      /* выходы "триггера" */

UINT uTimerID;
HANDLE hEvent;

char state='S';   /* начальное состояние   */

/*------------------------------------------------- */

v_types SetVType(char *prompt) /* задание типа вентиля */
{
 printf("Choose %s ventil type:\n", prompt);
 for(;;)
    {
     puts("0 - and_not, 1 - or_not, 2 - and_, 3 - or_");
     switch(getch())
           {
            case '0': return and_not;
            case '1': return or_not;
            case '2': return and_;
            case '3': return or_;
           }
    }
}

/*------------------------------------------------- */

void CheckKey()       /* управление входами "триггера" */
{
 if(kbhit())          /* была ли нажата клавиша?       */
   {
    switch(getch())
          {
           case '1':S=0; puts("S=0"); break; /* установка */
           case '2':S=1; puts("S=1"); break; /* входов    */
           case '3':R=0; puts("R=0"); break; /* "триггера"*/
           case '4':R=1; puts("R=1"); break;
           case '\033' : state=last_state;   /* ESC - конец работы */
          }
   }
}

/*------------------------------------------------- */

void print() /* вывод на косоль состояния входов и выходов */
{
 printf(" S= %1d R= %1d Q= %1d P= %1d\n", S, R, Q, P);
}

/*------------------------------------------------- */

int op(v_types v_type, int x, int y) /* логическая операция вентиля */
{
 switch (v_type)
        {
         case  and_not: return !(x && y);
         case  or_not : return !(x || y);
         case  and_   : return  (x && y);
         case  or_    : return  (x || y);
        }
}

 /*------------------------------------------------- */
/* функция вызывается таймером                      */
void CALLBACK TimerCallBack(
    UINT uTimerID, 
    UINT uMessage, 
    DWORD dwUser, 
    DWORD dw1,DWORD dw2)
 {
  if(uTimerID) SetEvent(hEvent); /* инициация события */
 }

 /*------------------------------------------------- */
/* действие на переходе S -> R                      */
void VS()       
{
 int x;
 CheckKey();  /* если нажали нужную клавишу - изменить S или R */
 x=op(vs_type, S, P);
 if(x != Q)
   {
    Q=x;     /* вентиль S на выходе дает Q */
    print();/* вывод на консоль только если выход изменился */
   }
}

 /*------------------------------------------------- */
/* действие на переходе R -> S                      */
void VR()       
{
 int x;
 CheckKey();  /* если нажали нужную клавишу - изменить S или R */
 x=op(vr_type, Q, R);
 if(x != P)
   {
    P=x;     /* вентиль R на выходе дает P */
    print();/* вывод на консоль только если выход изменился */
   }
}

/*------------------------------------------------- */
void TimerTick() /* таймер запускает автомат */
 {
  switch(state) /* опрос текущего состояния */
        {
         /* действия на переходах */
         case 'S': VS(); if(state != last_state) state='R'; break; 
         case 'R': VR(); if(state != last_state) state='S'; break;
        }
 }

/*------------------------------------------------- */

int main()
{
 vs_type=SetVType("S");      /* задать тип вентиля S */
 printf("S= %1d \n", vs_type);

 vr_type=SetVType("R");     /* задать тип вентиля R  */
 printf("R= %1d \n", vr_type);

 /* подсказка - как управлять "триггером" */
 puts("\nPress key to change trigger enters:");
 puts("1 - S=0; 2 - S=1");
 puts("3 - R=0; 4 - R=1\n");

 puts("Now press any key to start");
 puts("Press ESC to stop\n");
 getch();

 hEvent = CreateEvent(NULL, 0, 0, NULL); /* создаем событие */

   /* создаем таймер */
 uTimerID = timeSetEvent( 10, 1, &TimerCallBack, NULL, TIME_PERIODIC );
 /* период таймера 10±1 мс */

 while(state != last_state) /* пока не нажали ESC          */
      {
       WaitForSingleObject(hEvent,INFINITE); /* ждем тика */
       TimerTick();   /* запускаем автомат */
      }

 timeKillEvent(uTimerID); /* освобождаем ресурсы */
 CloseHandle(hEvent);
 return 0;
}

/*------------------------------------------------- */