Голодание (программирование)

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

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

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

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

Алгоритмы планирования процессов, которые отдают приоритет одним типам задач перед другими, могут привести к тому, что низкоприоритетные процессы никогда не получат процессорного времени. Например, в системе с вытесняющим планированием, если постоянно поступают высокоприоритетные задачи, низкоприоритетная задача может быть отложена на неопределённый срок. Классический пример — алгоритм с абсолютными приоритетами (fixed-priority preemptive scheduling), где процесс с наименьшим приоритетом может «голодать» бесконечно.

Неправильная реализация семафоров и блокировок

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

Конкуренция за ресурсы с ограниченной пропускной способностью

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

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

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

Отличие от взаимной блокировки и состояния гонки

Голодание часто путают с другими проблемами синхронизации, но между ними есть принципиальные различия:

• Взаимная блокировка (deadlock): Процессы застревают навсегда, ожидая друг друга, и ни один из них не может продолжить выполнение. Голодание же не блокирует процессы полностью — они готовы к работе, но не получают ресурса.
• Состояние гонки (race condition): Возникает, когда результат вычислений зависит от непредсказуемого порядка выполнения потоков. Голодание — это не состояние гонки, а детерминированное следствие политики планирования.
• Livelock: Процессы активно выполняют действия, но не продвигаются к завершению (например, постоянно переключаются между состояниями). Голодание — это пассивное ожидание, а не активное переключение.

Примеры в реальных системах

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

В ранних версиях ОС семейства Unix планировщик с фиксированными приоритетами мог приводить к голоданию фоновых задач (например, демонов печати или обновления системы) при интенсивной работе интерактивных пользовательских процессов. В современных ОС (Linux, Windows) применяются алгоритмы с динамической коррекцией приоритетов (например, «aging» — старение), чтобы предотвратить это.

Базы данных

В системах управления базами данных (СУБД) при использовании блокировок на уровне строк или таблиц транзакция с низким приоритетом может постоянно откладываться в пользу более высокоприоритетных транзакций, что приводит к «голоданию» и увеличению времени ожидания. Механизмы изоляции (например, MVCC) частично решают эту проблему.

Сетевые протоколы

В протоколах передачи данных с контролем перегрузки (например, TCP) потоки с низкой пропускной способностью могут страдать от голодания, если высокоскоростные потоки постоянно захватывают всю полосу пропускания. Алгоритмы справедливого распределения (fair queuing) призваны это предотвратить.

Многопоточные приложения

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

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

Старение приоритетов (Aging)

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

Очереди с дисциплиной FIFO

Использование очередей «первым пришёл — первым обслужен» (First In, First Out) для доступа к ресурсам гарантирует, что каждый процесс в конечном итоге получит ресурс, даже если он низкоприоритетный. Это простое решение, но оно может снизить общую производительность системы, так как не учитывает срочность задач.

Приоритетное наследование (Priority Inheritance)

Механизм, используемый для предотвращения инверсии приоритетов. Когда высокоприоритетный процесс блокируется в ожидании ресурса, удерживаемого низкоприоритетным, низкоприоритетный временно получает приоритет блокирующего процесса. Это позволяет ему быстрее завершить работу и освободить ресурс. Применяется в ОС реального времени (например, VxWorks, QNX) и в некоторых ядрах Linux (через протоколы наследования приоритетов).

Планировщики с гарантией справедливости

Алгоритмы, такие как Fair Queuing (в сетях) или Lottery Scheduling (в ОС), распределяют ресурсы пропорционально «весу» или «билетам» каждого процесса. Это гарантирует, что даже самый низкоприоритетный процесс получит некоторую долю ресурсов, исключая полное голодание.

Использование условных переменных и сигналов

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

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

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

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

Источники

• Таненбаум Э., Бос Х. «Современные операционные системы» (4-е издание). — СПб.: Питер, 2015. — Глава 2: Процессы и потоки, раздел 2.4.5 «Голодание».
• Столлингс У. «Операционные системы: внутреннее устройство и принципы проектирования» (9-е издание). — М.: Вильямс, 2018. — Глава 5: Планирование процессов, раздел 5.7 «Голодание».
• Silberschatz A., Galvin P. B., Gagne G. «Operating System Concepts» (10th Edition). — Wiley, 2018. — Chapter 7: Deadlocks, Section 7.5 «Starvation».
• Лав Р. «Linux. Системное программирование» (2-е издание). — СПб.: Питер, 2014. — Глава 4: Планирование процессов, описание CFS.
• Документация Microsoft Windows. «Priority Inversion» — MSDN Library, 2020.