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

і

Задача об обедающих мудрецах была предложена Дейкстрой в [79] и связана с пятью мудрецами, которые попеременно то думали, то ели. Мудрецы сидят за большим круглым столом, на котором много блюд китайской кухни. Между соседями лежит одна палочка » для еды. Однако для приема китайской пищи необходимо две палоч- ѵ ки, следовательно, каждый мудрец должен взять палочку слева _ и палочку справа: проблема, конечно, заключается в том, что если / все мудрецы возьмут палочки слева и затем будут ждать, когда

1    освободятся палочки с правой стороны, то они будут ждать вечно И умрут от голода (состояние тупика).

На рис. 3.32 показано решение этой задачи с помощью сети Петри. Позиции С и ..., С6 представляют палочки для еды, и так как каждая из них первоначально свободна, то в начальной маркировке в каждой из этих позиций имеется фишка. Каждый мудрец представлен двумя позициями Мг и Et для состояний размышления и принятия пищи соответственно. Для того чтобы мудрец перешел Из состояния размышления в состояние принятия пищи, обе палочки (слева и справа) должны быть свободны. Это легко моделируется сетью Петри.