Целевая аудитория: Java-разработчики, изучающие многопоточность и синхронизацию.
Версия Java: 11
Цель статьи: понять классическую проблему параллелизма, её причины, последствия и способы решения с использованием средств Java.
Введение
Задача «обедающие философы» (Dining Philosophers Problem) была предложена Эдсгером Дейкстрой в 1965 году как учебный пример для демонстрации сложностей, возникающих при совместном использовании ресурсов в многопоточных системах.
Она идеально подходит для изучения:
- взаимной блокировки (deadlock),
- голодания (starvation),
- синхронизации потоков,
- и правильного проектирования конкурентных алгоритмов.
Разберём задачу шаг за шагом — от постановки до рабочего решения на Java 11.
Постановка задачи
Представьте:
- За круглым столом сидят 5 философов.
- Перед каждым философом лежит тарелка спагетти.
- Между каждой парой философов лежит одна вилка.
- Всего 5 вилок, по одной между соседями.
Чтобы поесть, философу нужны две вилки — левая и правая.
После еды он кладёт обе вилки обратно и продолжает размышлять.
Каждый философ циклически выполняет три действия:
- Думает (не использует ресурсы).
- Голоден → пытается взять две вилки.
- Ест (удерживает вилки).
❗ Проблема: если все философы одновременно возьмут левую вилку, никто не сможет взять правую → все зависнут в ожидании → взаимная блокировка (deadlock).
Наивная реализация (и почему она ломается)
Начнём с простого, но опасного кода:
Запуск:
Что может пойти не так?
Запустите программу несколько раз. Иногда всё работает. Но часто — все философы берут левые вилки и ждут правые. Программа зависает навсегда.
Это классический deadlock, возникающий при выполнении четырёх условий (по Коттлу):
- Взаимное исключение: вилка может быть у одного философа.
- Удержание и ожидание: философ держит левую вилку и ждёт правую.
- Отсутствие вытеснения: нельзя отобрать вилку.
- Круговое ожидание: каждый ждёт ресурс у следующего.
🔥 Deadlock гарантирован, если все философы одновременно начнут брать левые вилки.
Решение 1: Нарушение кругового ожидания
Самый известный способ — ввести порядок захвата ресурсов.
Правило: всегда брать вилки в порядке возрастания их ID.
Но! У философа №4 левая вилка = 4, правая = 0 → 0 < 4 → он должен брать сначала 0, потом 4.
Изменим конструктор:
Результат: круговое ожидание нарушено → deadlock невозможен.
💡 Это решение масштабируется на любое количество философов.
Заключение
Пример, рассмотренный в статье, можно найти по адресу:
https://github.com/ShkrylAndrei/blog_yandex/tree/main/src/main/java/info/multithreading/the_dining_philosophers