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

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

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

В этой сети Петри позиция п_i, i {1,2,3,4,5}, представляет условие «i-тая вилка свободна». В начальной маркировке каждая из этих позиций имеет фишку. Каждому философу i {1,2,3,4,5} соответствует две позиции: позиция д_i– представляющая условие «i-тый философ думает»; и позиция е_i – представляющая условие «i-тый философ ест». В начальной маркировке все позиции д_iсодержат фишку, а все позиции е_i пусты.

Каждому философу i {1,2,3,4,5} также соответствует два перехода: переход нач_i – представляющий событие «начало приема пищи i-тым философом»; и переход зав_i – представляющий событие «завершение приема пищи i-тым философом».