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

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

За круглым столом сидят шесть философов. На столе шесть тарелок с рисом и шесть вилок. В каждый момент философ может либо есть (тогда ему необходимо две вилки), либо думать (для этого ему нужен только он сам). Философы не разговаривают между собой. Необходимо, чтобы все философы поели и не возникло драки за вилки.

Обобщение

Данная задача представляет из себя задачу получения взаимной блокировки.

Решение

Алгоритм обедающих философов

1) Обе соседние вилки должны быть чистые, чтобы философ мог войти в критическую секцию.

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

3) При запросе соседа-философа будем мыть вилки (делать их чистыми) и отдавать их, даже если сами хотим есть.

3) При получении запроса на вилку, чистые вилки не отдавать не будем.

Token ring

Все процессы объединяются в логическое кольцо независимо от реальной структуры сети.

По кольцу передается маркер (token). Процесс, получивший маркер, проверяет, нужно ли ему войти в критическую секцию. Если нужно, то входит, а после ее завершения отправляет маркер дальше по кольцу. Если не нужно, то сразу отправляет маркер дальше.

То есть, если ни один из процессов не заинтересован в критической секции, то маркер будет просто циркулировать по кольцу.