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

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

За круглым столом сидят шесть философов (процессы). На столе шесть тарелок с рисом и шесть вилок.

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

Обобщение

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

Решение

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

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

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

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

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

Итого:

• 0 сообщений на повторный заход в CS одним философом (процессом);
• 2N-2 сообщений в худшем случае;
• Количество сообщений пропорционально числу процессов, которые хотят попасть в критическую секцию.

Token ring

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

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

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