===Алгоритм обедающих философов===
1) Все соседние вилки должны быть чистые, чтобы философ мог войти Как построить алгоритм (вроде описан в критическую секцию"The Drinking Philosophers Problem" от K.M.Chandy и K.Misra):
2) После еды # Ориентируем граф конфликтов так, чтобы он должен отдать стал ациклическим. Например, по результатам сравнения id философов. Ориентация ребра задаёт, у кого вилка. Так как в ациклическом графе есть исток, то хотя бы у кого-то все вилкиесть. А когда поест, то можно перевернуть все рёбра у истока, тогда граф останется ациклическим. Если предположить, что философы всегда хотят есть (но мы едят конечное количество времени), то философы будут бесконечно есть.# Заметим, что голодания ни у кого нет: возьмём множество вершин, которые будут есть бесконечное количество раз. Тогда заметим, что если есть ребро между этим множеством и его дополнением, то рано или поздно это ребро начнёт вести из этого множества и не будет переключаться обратно (так как для переключения обратно надо, чтобы процесс из дополнения поел). А значит, что его конец в множестве тоже не может бесконечно много есть. Противоречие. Стало быть, это множество — компонента связности графа конфликтов.# Теперь можно сэкономить сообщения, если кто-то есть не хочет. Для этого не будем тратить сообщения на их передачусразу после еды отдавать вилку, а будем помечать её "грязной" и отдавать, только если наш сосед её явно попросит. Просто помечаемА если снова захотели есть, что то надо сначала попросить все вилки у соседей (и не отдавать, пока не поедим), а только потом помыть грязные: пока будем просить у соседей, грязные могут отобрать. Если бы мы их просто так помыли и не отдавали, то будет deadlock уже при N=3.
3) При запросе соседа-философа будем мыть совместную вилку (делать ее чистой) и отдавать ее, даже если сами хотим есть.Другое описание:
4# Все соседние вилки должны быть чистые, чтобы философ мог войти в критическую секцию.# После еды он должен отдать вилки, но мы не будем тратить сообщения на их передачу. Просто помечаем, что вилки грязные.# При запросе соседа-философа будем мыть совместную вилку (делать ее чистой) и отдавать ее, даже если сами хотим есть.# При получении запроса на вилку, чистые вилки отдавать не будем.
Итого:
