Задача обедающих философов — различия между версиями
Xottab (обсуждение | вклад) |
(→Решение) |
||
| Строка 8: | Строка 8: | ||
==Решение== | ==Решение== | ||
| − | |||
| − | |||
| − | + | ===Алгоритм обедающих философов=== | |
| + | 1) Обе соседние вилки должны быть чистые, чтобы философ мог войти в критическую секцию. | ||
| − | + | 2) После еды он должен отдать вилки (поменять направление ребёр в графе), но мы не будем тратить сообщения на их передачу. Просто помечаем, что вилки грязные. | |
| − | + | 3) При запросе соседа-философа будем мыть вилки (делать их чистыми) и отдавать их, даже если сами хотим есть. | |
| − | + | 3) При получении запроса на вилку, чистые вилки не отдавать не будем. | |
===Token ring=== | ===Token ring=== | ||
Версия 21:08, 9 марта 2018
Содержание
Задача обедающих философов
За круглым столом сидят шесть философов. На столе шесть тарелок с рисом и шесть вилок. В каждый момент философ может либо есть (тогда ему необходимо две вилки), либо думать (для этого ему нужен только он сам). Философы не разговаривают между собой. Необходимо, чтобы все философы поели и не возникло драки за вилки.
Обобщение
Данная задача представляет из себя задачу получения взаимной блокировки.
Решение
Алгоритм обедающих философов
1) Обе соседние вилки должны быть чистые, чтобы философ мог войти в критическую секцию.
2) После еды он должен отдать вилки (поменять направление ребёр в графе), но мы не будем тратить сообщения на их передачу. Просто помечаем, что вилки грязные.
3) При запросе соседа-философа будем мыть вилки (делать их чистыми) и отдавать их, даже если сами хотим есть.
3) При получении запроса на вилку, чистые вилки не отдавать не будем.
Token ring
Все процессы объединяются в логическое кольцо независимо от реальной структуры сети.
По кольцу передается маркер (token). Процесс, получивший маркер, проверяет, нужно ли ему войти в критическую секцию. Если нужно, то входит, а после ее завершения отправляет маркер дальше по кольцу. Если не нужно, то сразу отправляет маркер дальше.
То есть, если ни один из процессов не заинтересован в критической секции, то маркер будет просто циркулировать по кольцу.
