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

Сетями Петри легко моделируется создание и выполнение параллельных ветвей различных вычислительных процессов. К примеру, на рис. 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. Другое представление задачи

 

 

Одним из довольно простых решений этой проблемы, хотя, конечно, далеко не самым лучшим, является следующее. К сети, изображенной на рис. 23, добавим барьерную синхронизацию после того, как каждый философ осуществит прием пищи по одному разу. Для этого добавим к каждому философу по две позиции – позицию todo, количество фишек в которой отражает количество предстоящих подходов философа к еде до следующего барьера, и позицию done, отражающую количество выполненных подходов. Полученная сеть изображена на рис. 24.

Рис. 24. Решение задачи вместе с барьерном синхронизацией

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

С учетом такой модификации сети каждый философ будет получать доступ к еде в обычном порядке, пока не закончатся фишки в соответствующей позиции todo, после чего остановится на размышлениях. Таким образом, пока каждый из пяти философов не получит доступ к еде заданное количество раз, переход к следующему циклу осуществлен не будет. Когда все фишки из позиций todo постепенно переместятся в соответствующие позиции done, переход-барьер снова переместит их в позиции todo, после чего начнется следующий цикл приема пищи. [5]