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

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

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

Обобщение

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

Решение

1)Процесс ест когда у него есть вилки от всех процессов

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

3)Чтобы войти в критическую секцию - все вилки должны быть чистыми

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

5)Полученные вилки считаются чистыми

6)Грязные вилки можно мыть когда есть все остальные

Token ring

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

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

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