Базовые понятия
Сложность перехода от навыков программирования обычных последовательных процессов к организации параллелльных процессов в значительной мере обусловлена системой обучения, привычкой все упорядочивать, выстраивать в однозначные, безвариантые структуры, не замечая зависимости принятых решений от выбора структур и последовательности действий по их обработке.
По мнению Т.Хоара "Параллельная композиция действий внешне не сложнее последовательного сочетания строк в языке программирования" [[25]]. Функциональное программирование на Лиспе и других языках благодаря необычности (не смягчившейся за 40 с лишним лет) и более гибкой модели организации вычислений позволяет предоставить простые примеры для показа непривычных идей параллелизма, интуитивное понимание которых не требует напряжения [[8]].
Теория взаимодействия процессов богата разнообразием схем, что образует естественный полигон для научного творчества профессионального математика, особенно математика, знакомого с информационными технологиями.
При обсуждении тонкостей сложных проблем параллелизма принято привлекать шуточные и игровые сюжеты, такие как притча про пять философов, читатели-писатели, банкир, торговые автоматы, точное понимание которых не требует математической символики. Кажущаяся простота таких примеров помогает без затруднений воспринять сложность идей параллелизма [[25]].
Ряд моделей параллельных процессов концептуально сродни недетерминизму. Многие из них строятся как коллективное поведение объектов - автоматов с состояниями, изменение которых рассматривается как вычислительный процесс.
Термин "процесс" используется для обозначения поведения "объекта".
Описание процесса начинается с определения класса событий, представляющих интерес для участвуюущих в нем объектов. Множество имен событий, используемых при описании процесса или объекта, называют алфавитом.
Первая абстракция при моделировании процессов - исключение времени, т.е. отказ от ответов на вопрос происходят ли события строго одно за другим.
Это обеспечивается следующими договоренностями:
- элементарные действия исполняются мгновенно,
- протяженное действие: всегда пара событий - начало и конец,
- нет точной привязки действий к моменту времени,
- определены отношения "раньше-позже", "одновременно", "независимо",
- совместность событий понимается как отношение "синхронизация",
- одно событие из независимых возникает в любом порядке, без причинно-следственной связи.
Если известно, что процесс P может произойти вслед за событием x, влекущим этот процесс, то событие x называют префиксом процесса P.
x -> P -- P за x
Обычно для решения конкретной задачи вводится специальный объект - автомат, способный реагировать на определенное множество событий в зависимости от состояния автомата.
Поведение объекта, который способен действовать, можно описать в виде системы правил, внешне похожих на уравнения. Решением такой системы уравнений являются процессы, которые может выполнить автомат.
Пример 6.1. Рассмотрим автомат, установленный в здании НГУ на 4-ом этаже, продающий кофе.
Торговый автомат: {деньги, кофе} (деньги => ( кофе => автомат ) )
- нет кофе без денег - нет двойных порций
сломанный автомат - нет кофе
(деньги => СТОП )
- нет действий = нет событий
Пример 6.2. [25] Рассмотрим простые задачи типа перемещения фишки на клетчатой доске по свободным позициям.
| X | ||
| O | X |
( враво вверх вправо => СТОП )
Пример 6.3. [25] Простейшая модель часов - типовой пример рекурсивного описания процессов.
Часы: { тик-так }
(тик-так - часы) - рекурсия
Пример 6.4. [25] Небольшое изменение разрешенных позиций на клетчатой доске показывает возможность выбора вариантов хода событий при выполнении процессов. Появляется понятие "меню".
| X | ||
| O |
| - представление вариантов в меню процесса
Обычно выделяют начальное меню процесса. Не сложно выразить выбор из произвольного числа альтернатив и взаимную рекурсию. При этом достаточно естественно используется понятие "переменная", что существенно расширяет возможности записи систем уравнений.
Рассматривая примеры работы с одним автоматом, не видно причин для выхода за пределы обычных последовательных процессов. Просто лишь выделен ряд понятий, которые позволят потом гладко перейти к описанию процессов, выполняемых взаимодействующими автоматами.
Высказывание: Если для всякой альтернативы меню дальнейшего поведения совпадают, то процессы тождественны.
Формулировка такого рода закономерностей позволяет разделить описание процесса на уровень спецификации и реализации.
Сравнивая запись меню процесса с представлением текстов языка (см. лекцию 2), можно обратить внимание на их подобие. Отличие заключается в отношении к одновременности существования элементов. Во многих моделях процессов используются множества текстов или языки как характеристика, показывающая разнообразие вариантов хода событий.
