На этом шаге мы введем и проиллюстрируем указанные понятия.
Сетями Петри легко моделируется создание и выполнение параллельных ветвей различных вычислительных процессов. К примеру, на рисунке 1 изображена конструкция fork/join, впервые предложенная Деннисом и Ван Хорном. Переход fork моделирует "разветвление" - создание из одной ветви выполнения двух параллельных ветвей. Это, как правило, реализуется путем создания одной дополнительной ветви вдобавок к существующей. Переход join, в свою очередь, осуществляет "слияние" двух ветвей по завершению их работы - уничтожение созданной параллельной ветви.
Рис.1. Моделирование конструкции fork/join сетью Петри
Другое предложение по введению параллелизма основано на операциях parbegin и parend. Структура управления была предложена Дейкстрой и имеет вид parbegin S1; S2; …; Sn parend, где Si - предложение. Смысл структуры parbegin/parend заключается в параллельном выполнении каждого из предложений S1,S2,…,Sn. Эта конструкция может быть представлена сетью Петри, показанной на рисунке 2.
Рис.2. Моделирование структуры parbegin/parend сетью Петри
Используемые сегодня объекты синхронизации также легко моделируются сетями Петри. К примеру, на рисунке 3 изображен фрагмент сети Петри, моделирующий барьерную синхронизацию трех процессов.
Рис.3. Фрагмент сети Петри, моделирующий барьерную синхронизацию трех процессов
В начале работы сети разрешенными являются три длительных перехода, характеризующих выполнение некоторых подзадач. Три независимых процесса выполняют эти подзадачи, и лишь после их полного завершения становится разрешенным переход-барьер wait(all). После его срабатывания все три процесса снова продолжают свою работу.
Похожим образом может быть смоделировано ожидание завершения любой из подзадач, первой завершившей свое выполнение. К примеру, на рисунке 4 показан такой фрагмент сети.
Рис.4. Фрагмент сети Петри, моделирующий ожидание завершения любой из подзадач, первой завершившей свое выполнение
При завершении выполнения любого длительного перехода становится разрешенным переход wait(any). После его срабатывания дальнейшая работа продолжается, в то время как остальные подзадачи завершают свое выполнение. Дополнительная входная позиция перехода wait(any) защищает его от срабатывания при завершении остальных подзадач в случае, если в текущий момент ожидание не выполняется. В процессе дальнейшей работы сети фишка в эту позицию возвращается, и тем самым разрешается ожидание и обработка результатов выполнения остальных подзадач.
Введение параллелизма полезно только в том случае, когда компоненты процессов могут взаимодействовать при получении решения задачи. Такое взаимодействие требует распределение ресурсов между процессами. Для гарантии правильности работы системы в целом распределением нужно управлять. Проблемы синхронизации, возникающие при взаимодействии процессов, иллюстрируются многочисленными примерами. Среди задач синхронизации: задача о взаимном исключении, производителе/потребителе, обедающих мудрецах, чтении/записи.
На следующем шаге мы рассмотрим задачу о взаимном исключении.
