Голодание процессов

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

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

Голодание возникает в результате некорректной работы алгоритмов распределения ресурсов, особенно в системах с вытесняющей многозадачностью и приоритетным планированием. Основные причины включают:

Несправедливое планирование

Если планировщик процессов (scheduler) отдаёт предпочтение процессам с высоким приоритетом, низкоприоритетные процессы могут никогда не получить процессорное время. Это характерно для систем с фиксированными приоритетами, где высокоприоритетная задача постоянно находится в состоянии готовности.

Ошибки в синхронизации

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

Дефицит ресурсов

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

Инверсия приоритетов

Особый случай, когда высокоприоритетный процесс косвенно блокируется низкоприоритетным, удерживающим необходимый ресурс. Это может привести к тому, что средний по приоритету процесс вытесняет низкоприоритетный, и высокоприоритетный процесс голодает.

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

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

Примеры из практики

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

• В ранних версиях ОС Windows (до Windows 95) приоритетное планирование могло приводить к голоданию фоновых задач, если активное приложение постоянно запрашивало процессор.
• В Linux при использовании планировщика O(1) (до версии 2.6.23) существовала проблема голодания интерактивных процессов при высокой нагрузке на CPU.

Многопоточное программирование

• В Java при использовании synchronized без справедливой блокировки (fair lock) один поток может постоянно захватывать монитор, а другой — ждать бесконечно.
• В C++ с использованием std::mutex без дополнительных механизмов (например, std::condition_variable) возможно голодание при интенсивной конкуренции.

Базы данных

• В системах управления базами данных (СУБД) при использовании блокировок на уровне строк (row-level locking) транзакция с низким приоритетом может голодать, если высокоприоритетные транзакции постоянно изменяют те же строки.

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

Справедливое планирование (fair scheduling)

Использование алгоритмов, гарантирующих каждому процессу доступ к ресурсу в разумные сроки. Примеры:

• Round-robin — циклическое переключение между процессами с равными квантами времени.
• Алгоритм с вытеснением по приоритету с повышением — приоритет голодающего процесса постепенно увеличивается, пока он не получит ресурс.

Очереди с приоритетами и старением (aging)

Механизм, при котором приоритет процесса увеличивается со временем ожидания. Например, в планировщике Linux CFS (Completely Fair Scheduler) используется виртуальное время, которое компенсирует неравномерность доступа.

Использование семафоров с очередями

Вместо простых мьютексов применяются семафоры, поддерживающие очередь ожидания (FIFO). Это гарантирует, что процессы получают доступ в порядке запроса.

Ограничение времени удержания ресурса

Установка тайм-аутов на захват блокировки. Если процесс не получает ресурс за заданное время, он освобождает уже захваченные ресурсы и повторяет попытку.

Избегание инверсии приоритетов

В операционных системах реального времени (RTOS) применяется протокол наследования приоритетов (priority inheritance): низкоприоритетный процесс, удерживающий блокировку, временно получает приоритет ожидающего высокоприоритетного процесса.

Диагностика

Обнаружение голодания в работающей системе может быть затруднено, так как процесс не завершается аварийно, а просто не выполняется. Основные методы диагностики:

• Мониторинг загрузки CPU — если процессор загружен на 100 %, а некоторые процессы не получают времени, это может указывать на голодание.
• Анализ логов планировщика — в Linux можно использовать perf sched или ftrace для отслеживания времени ожидания процессов.
• Профилирование приложений — инструменты вроде strace (Linux) или Process Monitor (Windows) показывают, какие системные вызовы выполняются и сколько времени процесс ждёт.
• Статистика по блокировкам — в Java можно использовать jstack для анализа состояния потоков и выявления потоков в состоянии BLOCKED длительное время.

Последствия

Голодание процессов может приводить к:

• Снижению пропускной способности системы — часть ресурсов простаивает, пока голодающие процессы не выполняются.
• Увеличению времени отклика — критически важные задачи (например, обработка пользовательского ввода) могут задерживаться.
• Неравномерному распределению нагрузки — одни процессы выполняются быстро, другие — практически стоят.
• Сложности отладки — голодание часто проявляется нерегулярно, что затрудняет воспроизведение ошибки.

Интересные факты

• Термин «голодание» (starvation) в контексте вычислительных систем впервые появился в литературе по операционным системам в 1960-х годах, в частности в работах Эдсгера Дейкстры по синхронизации процессов.
• В некоторых системах реального времени (например, авионика, медицинское оборудование) голодание считается критической ошибкой, так как может привести к отказу системы.
• Алгоритм «старения» (aging) был предложен в 1970-х годах как решение проблемы голодания в пакетных системах с приоритетами.

Источники

• Таненбаум Э., Бос Х. «Современные операционные системы». 4-е издание. — СПб.: Питер, 2015.
• Сильбершац А., Гэлвин П., Гэгн Г. «Операционные системы: внутреннее устройство и принципы проектирования». 9-е издание. — М.: Вильямс, 2016.
• Дейкстра Э. «Cooperating sequential processes» (1965).
• Документация Linux Kernel: «CFS Scheduler» (kernel.org).
• Oracle: «Java Concurrency in Practice» — Brian Goetz et al. (2006).