В информатике нехватка ресурсов — это проблема, возникающая при параллельных вычислениях , когда процессу постоянно отказывают в необходимых ресурсах для выполнения его работы. [1] Нехватка ресурсов может быть вызвана ошибками в алгоритме планирования или взаимного исключения , но также может быть вызвана утечками ресурсов и может быть преднамеренно вызвана с помощью атаки типа «отказ в обслуживании», такой как « fork bomb» .
Когда в параллельном алгоритме невозможно голодание , такой алгоритм называется свободным от голодания , свободным от блокировок [2] или имеющим конечный обход . [3] Это свойство является примером жизнеспособности и одним из двух требований к любому алгоритму взаимного исключения; другое — корректность . Название «конечный обход» означает, что любой процесс (конкурентная часть) алгоритма обходит не более конечного числа раз, прежде чем ему будет разрешен доступ к общему ресурсу . [3]
Голодание обычно вызвано чрезмерно упрощенным алгоритмом планирования . Например, если (плохо спроектированная) многозадачная система всегда переключается между первыми двумя задачами, а третья никогда не запускается, то третья задача испытывает голод процессорного времени . Алгоритм планирования, который является частью ядра , должен распределять ресурсы справедливо; то есть алгоритм должен распределять ресурсы так, чтобы ни один процесс не испытывал постоянной нехватки необходимых ресурсов.
Многие планировщики операционных систем используют концепцию приоритета процесса. Высокоприоритетный процесс A будет запущен до низкоприоритетного процесса B. Если высокоприоритетный процесс (процесс A) блокируется и никогда не уступает, низкоприоритетный процесс (B) (в некоторых системах) никогда не будет запланирован — он испытает голодание. Если есть еще более высокоприоритетный процесс X, который зависит от результата процесса B, то процесс X может никогда не завершиться, даже если он является самым важным процессом в системе. Это состояние называется инверсией приоритета . Современные алгоритмы планирования обычно содержат код, гарантирующий, что все процессы получат минимальное количество каждого важного ресурса (чаще всего процессорного времени), чтобы предотвратить голодание любого процесса.
В компьютерных сетях, особенно беспроводных, алгоритмы планирования могут страдать от нехватки планирования. Примером может служить планирование максимальной пропускной способности .
Голодание обычно вызвано тупиком, поскольку оно приводит к зависанию процесса. Два или более процессов становятся тупиковыми, когда каждый из них ничего не делает, ожидая ресурса, занятого другой программой в том же наборе. С другой стороны, процесс находится в состоянии голодания, когда он ждет ресурса, который непрерывно выделяется другим процессам. Свобода от голодания является более сильной гарантией, чем отсутствие тупика: алгоритм взаимного исключения, который должен выбрать, допустить ли один из двух процессов в критическую секцию , и выбирает один произвольно, свободен от тупиков, но не свободен от голодания. [3]
Возможным решением проблемы голодания является использование алгоритма планирования с приоритетной очередью, который также использует технику старения . Старение — это техника постепенного увеличения приоритета процессов, которые долгое время ждут в системе. [4]