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

Материал из Викиконспекты
Перейти к: навигация, поиск

Задача обедающих философов[править]

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

Обобщение[править]

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

Решение[править]

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

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

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

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

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

Итого:

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

Token ring[править]

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

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

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