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

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

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

Обобщение

Взаимное исключение -- это полный граф конфликтов, т.е есть вилка для каждой пары философов. Вначале раздадим вилки, например, по результатам сравнения id философов.

Решение

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

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

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

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

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

Token ring

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

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

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