Проблема голодания (программирование)

Голодание (программирование) — это состояние в многозадачных вычислительных системах, при котором один или несколько процессов (или потоков) не получают доступа к ресурсам (процессорному времени, памяти, дисковому вводу-выводу, блокировкам) на протяжении неопределённо долгого времени, несмотря на то, что они готовы к выполнению и не заблокированы взаимной блокировкой (deadlock). Голодание является одной из классических проблем синхронизации и планирования задач, приводящей к деградации производительности системы или полной остановке выполнения отдельных процессов.

Причины возникновения

Голодание возникает из-за несправедливого распределения ресурсов между конкурирующими процессами. Основные причины включают:

Несправедливые алгоритмы планирования

Некоторые алгоритмы планирования задач (scheduling algorithms) могут систематически отдавать предпочтение одним процессам перед другими. Например:

• Приоритетное планирование (priority scheduling) — если в системе существует процесс с очень высоким приоритетом, который постоянно поступает на выполнение, процессы с более низким приоритетом могут никогда не получить процессорное время. Это явление называется «инверсией приоритетов» (priority inversion), когда низкоприоритетный процесс удерживает ресурс, необходимый высокоприоритетному, но сам не может быть выполнен.
• Планирование с вытеснением (preemptive scheduling) — если алгоритм отдаёт ресурс только процессам с наивысшим приоритетом, процессы с низким приоритетом могут «голодать» бесконечно.

Неправильное использование блокировок

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

• Спин-блокировки (spinlocks) — если процесс, удерживающий блокировку, выполняется дольше, чем ожидалось, другие процессы, ожидающие эту блокировку, могут тратить процессорное время впустую, не получая доступа.
• Несправедливые блокировки (unfair locks) — некоторые реализации блокировок (например, в стандартной библиотеке pthreads на некоторых платформах) не гарантируют порядок доступа (first-in-first-out), что может привести к тому, что один процесс будет получать блокировку многократно, а другой — никогда.

Ограниченность ресурсов

Если ресурс (например, количество открытых файлов, сетевых соединений или потоков) исчерпан, процессы, запрашивающие его, могут быть поставлены в очередь, которая никогда не обрабатывается из-за того, что другие процессы постоянно занимают ресурс.

Отличие от взаимной блокировки (deadlock)

Голодание часто путают с взаимной блокировкой (deadlock), но это разные явления:

Примеры голодания

В операционных системах

• Планировщик процессов Windows (до Windows 10) — в ранних версиях алгоритм планирования мог приводить к голоданию фоновых процессов при высокой нагрузке на процессор со стороны приложений реального времени.
• Linux CFS (Completely Fair Scheduler) — хотя CFS стремится к справедливому распределению процессорного времени, в некоторых сценариях (например, при большом количестве процессов с одинаковым приоритетом) возможна ситуация, когда один процесс не получает квант времени из-за особенностей виртуального времени выполнения.

В многопоточных приложениях

• Проблема «обедающих философов» (Dining Philosophers Problem) — классический пример, где при неправильной реализации (например, если все философы одновременно берут левую вилку) некоторые философы могут никогда не поесть (голодание), хотя другие едят постоянно.
• Банковский алгоритм (Banker's Algorithm) — если система использует этот алгоритм для предотвращения взаимных блокировок, он может привести к голоданию процессов, которые запрашивают ресурсы в неподходящий момент.

В распределённых системах

• Протоколы разрешения конфликтов (например, Ethernet CSMA/CD) — при высокой загрузке сети некоторые узлы могут не получить доступ к среде передачи из-за того, что другие узлы постоянно выигрывают состязание (backoff-алгоритм может приводить к голоданию).

Методы предотвращения и устранения

Справедливые алгоритмы планирования

• Планирование с квантованием времени (round-robin) — каждому процессу выделяется фиксированный квант времени, что гарантирует прогресс для всех.
• Планирование с приоритетами и старением (priority aging) — приоритет процесса постепенно увеличивается со временем ожидания, что предотвращает бесконечное голодание низкоприоритетных процессов.

Справедливые блокировки

• Очередные блокировки (queued locks, fair locks) — гарантируют, что доступ к ресурсу предоставляется в порядке поступления запросов (FIFO). Примеры: std::mutex с политикой std::defer_lock в C++11, java.util.concurrent.locks.ReentrantLock(true) в Java.
• Семафоры с очередями — использование семафоров, которые ставят процессы в очередь, а не просто проверяют состояние.

Управление ресурсами

• Резервирование ресурсов — выделение минимального количества ресурсов для каждого процесса, чтобы гарантировать его выполнение.
• Мониторинг и динамическое перераспределение — операционная система может отслеживать время ожидания процессов и принудительно предоставлять ресурс «голодающему» процессу.

Алгоритмические решения

• Использование алгоритмов, свободных от голодания (starvation-free) — например, алгоритм Петерсона (Peterson's algorithm) для двух потоков или алгоритм Деккера (Dekker's algorithm) гарантируют, что каждый поток в конечном итоге получит доступ к критической секции.
• Избегание инверсии приоритетов — в системах реального времени применяются протоколы наследования приоритетов (priority inheritance) или потолочного приоритета (priority ceiling).

Критика и ограничения

Хотя голодание считается менее критичной проблемой, чем взаимная блокировка (так как система в целом продолжает работать), оно может привести к серьёзным последствиям в системах реального времени, где время отклика критично. В некоторых случаях голодание может перерасти в deadlock, если «голодающий» процесс удерживает ресурс, необходимый другим процессам.

В современных операционных системах (Linux, Windows, macOS) голодание встречается редко благодаря использованию сложных алгоритмов планирования (например, CFS с виртуальным временем выполнения) и справедливых блокировок. Однако в пользовательских приложениях, особенно с неправильным использованием многопоточности, голодание остаётся распространённой ошибкой программирования.

Источники

• Tanenbaum, A. S. (2014). Modern Operating Systems (4th ed.). Pearson.
• Silberschatz, A., Galvin, P. B., & Gagne, G. (2018). Operating System Concepts (10th ed.). Wiley.
• Herlihy, M., & Shavit, N. (2012). The Art of Multiprocessor Programming (2nd ed.). Morgan Kaufmann.
• Stallings, W. (2017). Operating Systems: Internals and Design Principles (9th ed.). Pearson.