Задача об обедающих философах.
Напомним, что задача об обедающих философах была предложена Дейкстрой и связана с пятью философами, которые попеременно то гуляли по саду и думали, то ели. За едой философы сидят за круглым столом, в центре которого стояла большая миска спагетти. На столе также лежало пять вилок, по одной между соседними посадочными местами. Для употребления спагетти необходимо две вилки. Поэтому каждый философ должен сначала взять вилку слева и вилку справа, а затем приступать к еде. Возможна ситуация, в которой каждый философ возьмет вилку слева, а затем будет ждать, когда освободится вилка с правой стороны. Так они будут ждать, пока не умрут от голода. Тем самым, это состояние системы «обедающие философы» является тупиковым.
Проблема тупика в этой системе может быть решена путем следующей модификации ее правил поведения. Пусть философ при переходе из состояния размышления в состояние приема пищи берет одновременно обе вилки (слева и справа), если они свободны. Сеть Петри (рис. 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 -тым философом».
Анализ сетей Петри
Моделирование систем сетями Петри, прежде всего, обусловлено необходимостью проведения глубокого исследования их поведения. Для проведения такого исследования необходимы методы анализа свойств самих сетей Петри. Этот подход предполагает сведение исследования свойств реальной системы к анализу определенных свойств моделирующей сети Петри.
Дата добавления: 2015-12-20; просмотров: 25; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!