Голодание (информатика)

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

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

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

Приоритетное планирование

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

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

Некоторые классические алгоритмы, такие как «первый пришёл — первый обслужен» (FCFS) в условиях длительных задач, могут привести к тому, что короткие задачи, поступившие позже, будут ожидать завершения длительной задачи. Однако в случае с циклическими алгоритмами (Round Robin) голодание обычно не возникает, если квант времени фиксирован. Проблема проявляется в алгоритмах с динамическим приоритетом, где приоритет процесса может быть снижен после каждого использования ресурса (например, в некоторых реализациях алгоритма «самый короткий остаток»).

Синхронизация и блокировки

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

Проблема «инверсии приоритетов»

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

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

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

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

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

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

В ранних версиях операционной системы Windows (до Windows 95) приоритетное планирование могло приводить к голоданию фоновых задач, если пользователь запускал множество приложений с высоким приоритетом. В современных ОС (Linux, Windows, macOS) используются механизмы предотвращения голодания, такие как динамическое изменение приоритетов (aging — «старение») и справедливые планировщики (например, Completely Fair Scheduler в Linux).

Базы данных

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

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

В протоколах управления доступом к среде (например, CSMA/CD в Ethernet) голодание может возникнуть при высокой нагрузке, когда некоторые станции постоянно проигрывают в коллизиях и не могут передать данные. В современных сетях используются алгоритмы, гарантирующие равномерное распределение пропускной способности.

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

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

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

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

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

• Round Robin с фиксированным квантом времени.
• Гарантированное планирование (Guaranteed Scheduling), где каждому процессу выделяется определённая доля процессорного времени.
• Планирование на основе очередей с обратной связью (Multilevel Feedback Queue), где процессы перемещаются между очередями с разными приоритетами.

Механизмы синхронизации с гарантией прогресса

Использование блокировок, которые не допускают голодания, например:

• Спин-блокировки (spinlocks) с очередью (ticket lock), где каждый поток получает номер в очереди и обслуживается строго по порядку.
• Семафоры с очередями (FIFO semaphores), где потоки блокируются в порядке поступления.
• Мониторы с условными переменными (condition variables), где сигналы отправляются всем ожидающим потокам (broadcast), а не одному.

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

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

Отказ от приоритетов

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

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

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

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

Источники

• Таненбаум Э., Бос Х. «Современные операционные системы». 4-е издание. — СПб.: Питер, 2015. — 1120 с.
• Silberschatz A., Galvin P. B., Gagne G. «Operating System Concepts». 10th Edition. — Wiley, 2018. — 1040 p.
• Stallings W. «Operating Systems: Internals and Design Principles». 9th Edition. — Pearson, 2017. — 800 p.
• Herlihy M., Shavit N. «The Art of Multiprocessor Programming». 2nd Edition. — Morgan Kaufmann, 2020. — 560 p.
• Документация ядра Linux: «Completely Fair Scheduler» (CFS) — kernel.org/doc/Documentation/scheduler/sched-design-CFS.txt.