Задача об обедающих мудрецах

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

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

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

Всякий раз, когда философ пытается дотянуться до своей левой вилки, его левый сосед мгновенно перехватывает вилку. Таким образом, может оказаться, что сидящий философ никогда не приступит к еде, что приведёт к его гибели.

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

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

Рис.4.12. Сеть Петри, моделирующая систему обедающих мудрецов

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

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