Параллельные вычисления и синхронизация

Сетями Петри легко моделируется создание и выполнение параллельных ветвей различных вычислительных процессов. К примеру, на рис. 13 изображена одна из довольно популярных на сегодняшний день конструкций fork/join. Переход fork моделирует «разветвление» - создание из одной ветви выполнения двух параллельных ветвей. Это, как правило, реализуется путем создания одной дополнительной ветви вдобавок к существующей. Переход join, в свою очередь, осуществляет «слияние» двух ветвей по завершению их работы - уничтожение созданной параллельной ветви за ненадобностью.

Рис. 19.

Пример конструкции fork/join

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

Рис. 20.

Барьерная синхронизация процессов

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

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

Рис. 21.

Пример ожидания

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

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

Рис. 22.

Задача об обедающих философах

На рис. 2 изображена сеть Петри, решающая задачу об обедающих философах. Позиции eating и thinking здесь характеризуют пребывание соответствующего философа в состоянии еды или размышлений. Позициями fork обозначается доступность вилок. Переходы start и stop характеризуют переход философа к еде и к размышлениям соответственно.

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

Рис. 23.

Другое представление задачи